Bài giảng Tin học đại cương - Nguyễn Duy Hiệp

ác bảng phù hợp cho cơ sở dữ liệu được chỉ ra 
 bởi đồ thị. 
Hệ quản trị cơ sở dữ liệu
  Mô hình cơ sở dữ liệu cho thuê phim
Review
1. Hệ thống thông tin là gì?
2. Phần mềm bảng tính dùng để làm gì?
3. Phần mềm quản trị cơ sở dữ liệu dùng để làm gì?
1.XX Trí tuệ nhân tạo
Project 1: Cách mạng 4.0
 1. Trình bày về khái niệm cách mạng công nghệ 4.0
 + Cách mạng 4.0 là gì, khác gì so với 3.0, 2.0
 + Nền tảng của 4.0 dựa trên gì
 + Cách mạng 4.0 làm thay đổi việc sản xuất như thế nào?
 + Một số ví dụ của công nghệ 4.0
 + Những vấn đề mà cách mạng 4.0 cần xử lý
 + Người dân bình thường được hưởng lợi thế nào?
 + Xu hướng nghề nghiệp sẽ thay đổi ra sạo?
Project 2: SmartHome
 2. Công nghệ điều khiển, giao tiếp các thiết bị trong 
 smarthome - nhà thông mình
 + Nhà thông minh là gì?
 + Có các mô hình giao tiếp giữa các thiết bị trong 
 smarthome nào? Đặc điểm của các mô hình đó ra sao?
 + Việc bảo mật như thế nào?
 + Hiện tại có các hãng nào đang dẫn đầu trong lĩnh vực 
 này
Project 3: Năng lượng tái tạo
 3. Năng lượng tái tạo
 + Năng lượng tái tạo là gì, có những nguồn nào?
 + Hiện tại năng lượng tái tạo đang được sử dụng tại dâu?
 + Có những vấn đề khó khăn gì với năng lượng tái tạo
 + với người dùng cá nhân thì có thể tham gia vào đâu 
 trong sử dụng năng lượng tái tạo
 + kể tên những công ty lớn áp dụng năng lượng tái tạo 
 trong sản xuất
Project 4: Trí tuệ nhân tạo
 4. Trí tuệ nhân tạo - học máy
 + trí tuệ nhân tạo là gì ?
 + Trí tuệ nhân tạo đang được ứng dụng trong sản xuất 
 thế nào?
 + Trong cuộc sông hàng này, trí tuệ nhân tạo đang được 
 ứng dụng tại đâu
 + Những công ty nào đang dùng trí tuệ nhân tạo phục vụ 
 sản xuất?
 + những vấn đề khó khăn mà trí tuệ nhân tạo đang gặp 
 phải
 5. Tìm hiểu về công nghệ Block chain
  Block chain là gì ?
  Cơ chế hoạt động của block chain ra sao
  Ứng dụng của Block chain trong tiền ảo (bitcoin)?
  Ứng dụng của block chain trong các lĩnh vực khác
 . Hợp đồng thông minh
 . Giám sát nguồn gốc thực phẩm
 . ..
 6. Tìm hiểu về học sâu – Deep Learning
  Học sâu là gì, khác gì so với học máy – Machine Learning
  Có các mô hình học sâu phổ biến nào
  Ứng dụng của mô hình học sâu
 . Nhận dạng, phân loại,
 . Ứng dụng trong thực tế? – trợ lý ảo,..
 7. Tìm hiểu về nhận dạng (dọng nói hoặc chữ viết)
  Có các mô hình nào để nhận dạng chữ viết
  Ưu nhược điểm của các mô hình ra sao
  Demo một mô hình nhận dạng chữ viết cơ bản dùng mạng
 neural (dùng ngôn ngữ bất kỳ)
1.10 Giải quyết vấn đề
 và thiết kế thuật toán
•Những vấn đề nào được giải quyết bằng máy tính ?
•Cách giải quyết vấn đề bằng máy tính
Nội dung
 1.10.1 Các khái niệm cơ bản
 1.10.2 Các phương pháp xây dựng thuật toán
 1.10.3 Biểu diễn thuật toán
 1.10.4 Một số thuật toán cơ bản
Giải quyết vấn đề và thiết kế thuật toán
 Vấn đề ? Một khó khăn cần được giải quyết.
 Giải quyết vấn đề: là việc tìm ra một giải pháp cho câu hỏi rắc
 rối, phức tạp, khó hiểu
 Máy tính không thể dùng để giải quyết các vấn đề liên quan
 đến hành động vật lý hoặc biểu thị cảm xúc
 Máy tính chỉ làm được những gì mà nó được bảo phải làm. 
 Máy tính không thông minh, nó không thể tự phân tích vấn đề
 và đưa ra giải pháp.
 Lập trình viên là người phân tích vấn đề, tạo ra các chỉ dẫn để
 giải quyết vấn đề (chương trình), và máy tính sẽ thực hiện các
 chỉ dẫn đó. 
Giải quyết vấn đề và thiết kế thuật toán
 Phương pháp giải quyết vấn đề thông thường: 4 bước
  Bước 1: Hiểu vấn đề: cái gì chưa biết, cái gì là dữ liệu, cái
 gì là điều kiện
  Bước 2: Đưa ra một phương án: tìm mối quan hệ giữa dữ
 liệu và những thứ chưa biết, có thể tham khảo từ cách giải
 quyết các vấn đề tương tự
  Bước 3: Thực hiện phương án
  Bước 4: Kiểm tra lại lời giải thu được
Giải quyết vấn đề và thiết kế thuật toán
 Phương án được gọi là thuật toán trong tính toán
 Một thuật toán là:
  Một dãy hữu hạn các thao tác và trình tự thực hiện các
 thao tác đó sao cho sau khi thực hiện dãy thao tác này
 theo trình tự đã chỉ ra, với đầu vào (input) ta thu được
 kết quả đầu ra (output) mong muốn.
 Giải quyết vấn đề và thiết kế thuật toán
Giải quyết vấn đề bằng máy tính
 Giai đoạn phát triển thuật toán
  Phân tích: hiểu vấn đề
  Đề xuất thuật toán: đưa ra các bước tuần tự giải bài toán
  Kiểm tra thuật toán: theo các bước để kiểm tra lại thuật toán
 Giai đoạn triển khai
  Code: chuyển thuật toán thành chương trình
  Kiểm tra: thực hiện trên máy tính, kiểm tra kết quả và sửa đổi nếu cần
 Giai đoạn bảo trì
  Sử dụng:Dùng chương trình
  Bảo trì: sửa đổi chương trình cho phù hợp yêu cầu mới hoặc để sửa lỗi.
Giải quyết vấn đề và thiết kế thuật toán
 Pha giải quyết vấn đề Pha triển khai, cài đặt
 Giải quyết vấn đề và thiết kế thuật toán
 Xây dựng thuật toán:
  Phương pháp thiết kế top-down (phân rã hàm - functional 
 decomposition): chia vấn đề thành các vấn đề nhỏ
 hơn(module), các vấn đề nhỏ lại được chia tiếp cho đến khi
 nó đủ nhỏ để có thể xử lý trực tiếp
  Phương pháp thiết kế hướng đối tượng: dữ liệu và các
 thuật toán xử lý dữ liệu được kết hợp với nhau trong một
 lớp (class) hoặc đối tượng (object)
Phương pháp thiết kế top-down
 Phương pháp thiết kế top-down
Phương pháp thiết kế top-down
VD. Bài toán tổ chức 1 buổi tiệc lớn.
 Bài toán có thể chia nhỏ thành : 
  Mời mọi người
  Chuẩn bị đồ ăn
 Mời mọi người: Chưa thể gọi điện để mời vì ta chưa biết cần 
 mời những ai. Do đó thao tác này được chia tiếp
  Lên danh sách khách
  Gọi điện cho khách
 Lên danh sách: 
  Ghi tên bạn bè
  Chờ 1 ngày để xem còn quên ai
  Kiểm tra và bổ sung vào danh sách
Phương pháp thiết kế top-down
  Chia nhỏ bài toán
Phương pháp thiết kế top-down
 VD, Với bài toán con là viết tên khách mời (write down name):
  Bạn có giấy chưa ?
 . Chưa có thì lấy giấy
  Bạn có bút chưa?
 . Chưa có thì lấy bút (mua bút)
  Cầm bút và viết tên khách mời lên giấy
Phương pháp thiết kế top-down
 Trong máy tính cũng tương tự, ta có thể dùng ngôn ngữ tự 
 nhiên hoặc giả mã để biểu diễn thuật toán.
 Nếu dùng mã giả (pseudocode) 
  Dùng while, repeat để biểu diễn các thao tác lặp đi lặp lại
  Dùng if để biểu diễn khi phải lựa chọn 1 trong 2 các thao 
 tác để thực hiện.
  Dùng write để biểu diễn việc hiển thị ra (màn hình)
  Dùng read để biểu diễn việc đọc vào (từ bàn phím)
Phương pháp thiết kế top-down
 VD. Bài toán lên và in ra danh sách khách mời theo thứ tự chữ 
 cái.
 Bài toán chia thành 3 module:
 Mức 0
  Nhập vào thông tin khách 
  Sắp xếp danh sách theo thứ tự chữ cái
  In ra danh sách
Phương pháp thiết kế top-down
 Nhập vào thông tin khách Mức 1
  Nhập vào từ bàn phím
  Kiểm tra đủ thông tin
  Thêm vào danh sách
Phương pháp thiết kế top-down
 Nhập vào từ bàn phím Mức 2
  write “Nhập vào thông tin khách”
  write “Nhập tên”
  read họtên
  write “Nhập địa chỉ”
  read địachỉ
  write “Nhập số điện thoại”
  read sốđiệnthoại
Phương pháp thiết kế top-down
 Kiểm tra đủ thông tin Mức 2
  if (thiếu họtên) 
 . write “Nhập họ tên”
 . read họtên
  if (thiếu địachỉ)
 . write “Nhập địa chỉ”
 . read địachỉ
  if (thiếu Sốđiệnthoại)
 . write “Nhập số điện thoại”
 . read Sốđiệnthoại
Phương pháp thiết kế hướng đối tượng
 Phương pháp thiết kế hướng đối tượng: Xây dựng lời giải của 
 bài toán theo các thực thể nội tại được gọi là các đối tượng. 
 Mỗi đối tượng bao gồm cả dữ liệu và các thao tác để xử lý dữ 
 liệu đó
 Các đối tượng tương tự nhau được mô tả bằng 1 lớp – class.
 VD. Mặc dù 2 sinh viên khác nhau nhưng có các đặc điểm và 
 hành vi chung: đều là người và cùng tham gia khóa học tại 
 trường. 
Phương pháp thiết kế hướng đối tượng
 Quan hệ giữa các lớp có thể là 
  Chứa đựng – containment: lớp này nằm trong lớp khác. 
 VD đối tượng lốp xe nằm trong đối tượng ô tô
  Kế thừa – Inheritance: lớp này có thể kế thừa dữ liệu và 
 cách ứng xử của lớp khác. VD lớp sinh viên kế thừa từ lớp 
 người.
Phương pháp thiết kế hướng đối tượng
 Quan hệ giữa các lớp có thể là 
  Quan hệ cộng tác – collaboration: Một lớp có thể gọi 1 
 lớp khác để cung cấp thông tin. VD Lớp sinh viên có thể gọi 
 dịch vụ của lớp thư viện – library để mượn sách.
 Giải quyết vấn đề và thiết kế thuật toán
 Biểu diễn thuật toán:
  Dùng ngôn ngữ tự nhiên
  Dùng giả ngôn ngữ
  Dùng sơ đồ khối
  Dùng ngôn ngữ lập trình
 VD. Bài toán tìm giá trị lớn nhất của một dãy N số nguyên
  Đầu vào: N và giá trị của N số nguyên a1, a2,, aN
  Đầu ra: số nguyên lớn nhất của dãy
Giải quyết vấn đề và thiết kế thuật toán
max 3 5 7 9 2 8
max = 3 3
max<5 5
max<7 7
max<9 9
max>2 9
max>8 9
 Kết quả 9
Giải quyết vấn đề và thiết kế thuật toán
Thuật toán: Tìm giá trị lớn nhất trong dãy số nguyên
 B1: Max  a1, i  2.
 B2: Nếu i > N, Chuyển qua bước 6
 B3: Nếu ai > Max, gán Max bằng ai .
 B4: Tăng i lên 1 đơn vị.
 B5: Quay lên B2.
 B6: In ra Max (là giá trị lớn nhất cần tìm)
Giải quyết vấn đề và thiết kế thuật toán
 Bắt đầu
 · Nhập N
 · Nhập a1,..,aN
 · Maxßa1
 · iß2
 Đúng
 Hiển thị giá 
 i>N Kết thúc
 trị Max
 Sai
 Đúng
 ai>Max Maxßai
 Sai
 i=i+1
Giải quyết vấn đề và thiết kế thuật toán
Một số khối trong sơ đồ khối dùng biểu diễn thuật toán
 Bắt đầu hoặc kết thúc
 Thao tác xử lý
 Lệnh vào, ra dữ liệu(read hoặc write)
 Kiểm tra điều kiện
 Nối tiếp đoạn lệnh
 Luồng thực hiện
Biểu diễn thuật toán
 Cấu trúc tuần tự
  Xác định bởi thứ tự các bước trong mã giả hoặc
  Hướng mũi tên trong sơ đồ khối
 x ß5
 Bước 1: gán x = 5
 Bước 2: gán y là dư của phép chia 
 y = x % 2
 module x cho 2
 Bước 3: In ra y
 In ra y
Biểu diễn thuật toán
 Cấu trúc rẽ nhánh
 Đúng
 a<b Max=b
 Sai
Bước 1: So sánh giá trị a và b, Max=a
 nếu a<b thì Max=b
 Ngược lại Max=a
Bước 2: in ra giá trị của Max
 In ra Max
Biểu diễn thuật toán
 i=1
 Cấu trúc lặp
 Sai
 In thông báo hoàn 
 i<10
 thành công việc
 Đúng
 In ra i
 i=i+1
Bước 1: Gán i=1
Bước 2: kiểm tra i<10 
 Nếu đúng thì sang Bước 3
 Nếu sai thì sang Bước 5
Bước 3: In ra i
Bước 4: tăng i thêm 1, quay lại Bước 2
Bước 5: in thông báo hoàn thành
 Biểu diễn thuật toán
  Cấu trúc lặp (tiếp)
Bước 1: Gán i=1
Bước 2: In ra i
Bước 3: tăng i thêm 1
Bước 4: kiểm tra i<10 
 Nếu đúng thì quay lại bước 2 i=1
 Nếu sai thì sang bước 5
Bước 5: in thông báo hoàn thành
 In ra i
 i=i+1
 In thông báo hoàn 
 Đúng i<10
 Sai thành công việc
Một số thuật toán thông dụng
 Thuật toán sắp xếp dãy số theo thứ tự tăng dần
  Đầu vào: Dãy A gồm N số a1, a2,, aN
  Đầu ra: Dãy A dược sắp lại theo thứ tự không giảm
 VD. 
  Dãy ban đầu: 1, 6, 3, 9, 5, 6, 7
  Dãy kết quả: 1, 3, 5, 6, 6, 7, 9
Một số thuật toán thông dụng
 Ý tưởng: Dựa trên ý tưởng trong tuyển quặng: "Quặng nặng thì 
 chìm xuống dưới còn tạp chất nhẹ thì nổi lên trên" 
 Thực hiện so sánh lần lượt các phần tử nằm kề nhau, nếu 
 chúng không đúng thứ tự thì ta đổi chỗ chúng cho nhau.
 Các phần tử có giá trị khóa lớn sẽ bị đẩy về cuối và khóa nhỏ sẽ 
 bị đẩy lên trên (trong trường hợp sắp xếp tăng dần)
 Sắp xếp nổi bọt
 Dãy ban đầu 3 5 2 7 1
lần lặp 1 3 5 2 7 1
 3 5 2 7 1 3 2 5 7 1
 3 2 5 7 1
 3 2 5 7 1 3 2 5 1 7
 kết thúc lần lặp 1 3 2 5 1 7
 Sắp xếp nổi bọt
Lần lặp 2 3 2 5 1 7
 3 2 5 1 7 2 3 5 1 7
 2 3 5 1 7
 2 3 5 1 7 2 3 1 5 7
 kết thúc lần lặp 2 2 3 1 5 7
 Sắp xếp nổi bọt
Lần lặp 3 2 3 1 5 7
 2 3 1 5 7
 2 3 1 5 7 2 1 3 5 7
 kết thúc lần lặp 3 2 1 3 5 7
 Sắp xếp nổi bọt
Lần lặp 4 2 1 3 5 7
 2 1 3 5 7 1 2 3 5 7
 kết thúc lần lặp 4 1 2 3 5 7
 Dãy đã được sắp xếp !
Sắp xếp nổi bọt
 B1: Nhập số N và dãy số a1,a2,,aN
 B2: i ß N
 B3: Nếu i < 2 thì chuyển tới bước 9.
 B4: j ß 2
 B5: Kiểm tra j ≤ i
 Nếu đúng chuyển sang bước 6
 Nếu sai chuyển sang bước 8
 B6: so sánh aj-1 và aj
 Nếu aj-1>aj thì hoán đổi vị trí 2 phần tử
 B7: Tăng j và quay lại bước 5
 B8: giảm i và quay lại bước 3
 B9: Kết thúc
Sắp xếp nổi bọt
 Bắt đầu
 · Nhập N 
 · Nhập a1,..,aN
 i ß N
 Sai
 i > 1 Kết thúc
 Đúng
 j=2
 j=j+1
 Sai
 j≤ i aj-1 > aj Đổi chỗ aj và aj-1
 Đúng Đúng
 Sai
 i=i-1
Một số thuật toán thông dụng
 Thuật toán kiểm tra số nguyên tố
  Đầu vào: số nguyên dương n
  Đầu ra: trả lời n có phải số nguyên tố hay không
 VD. 19, 57 là số nguyên tố
 Ý tưởng: 
  Số nguyên tố là số chỉ chia hết cho 1 và chính nó. 
  Để kiểm tra số nguyên tố ta sẽ thử chia số đó với các số từ 2 
 đến 푛. Nếu chia hết cho bất kỳ 1 số nào thì không phải số 
 nguyên tố.
Một số thuật toán thông dụng
 Bước 1: Nhập n
 Bước 2: i=2
 Bước 3: so sánh 푖 ≤ 푛. 
 Nếu sai thì chuyển sang Bước 6
 Nếu đúng thì chuyển sang Bước 4
 Bước 4: Kiểm tra n có chia hết cho i
 Nếu đúng thì chuyển sang Bước 5
 Nếu sai thì tăng i lên 1 và quay lại Bước 3
 Bước 5: In thông báo n không phải số nguyên tố và kết thúc
 Bước 6: In thông báo n là số nguyên tố và kết thúc
Một số thuật toán thông dụng
 Bắt đầu
 Nhập N
 i=2
 Sai
 N là số 
 i ≤ căn bậc hai của n
 nguyên tố
 Đúng
 N không phải là 
 N chia hết cho i
 Đúng số nguyên tố
 Sai
 i=i+1
 Kết thúc
Review
1. Nêu các bước giải quyết vấn đề
2. Giải quyết vấn đề bằng máy tính có đặc điểm gì
3. Các bước để giải quyết vấn đề bằng máy tính
4. Thuật toán là gì 
5. Trình bày phương pháp thiết kế top-down
1.11. Ngôn ngữ lập trình
1.11. Ngôn ngữ lập trình
 Máy tính là thiết bị điện tử có khả năng lập trình được mà có 
 thể lưu trữ, tìm kiếm và xử lý dữ liệu.
 Dữ liệu và các câu lệnh xử lý dữ liệu về mặt logic là như nhau 
 và có thể được lưu trữ tại cùng một vị trí. 
 Thay đổi cách máy tính xử lý dữ liệu bằng cách thay đổi các câu 
 lệnh.
 Dữ liệu và câu lệnh trong máy được biểu diễn bằng mã máy 
 (mã nhị phân). 
1.11. Ngôn ngữ lập trình
 Ngôn ngữ lập trình : 3 nhóm
  Ngôn ngữ máy: 
 . lệnh(chỉ thị) được viết bằng mã nhị phân, 
 . phụ thuộc vào từng loại máy cụ thể. 
  Hợp ngữ (assembly)
 . Dùng từ tiếng anh viết tắt để biểu diễn một số lệnh
 . Phải qua bộ dịch assembler
1.11. Ngôn ngữ lập trình
1.11. Ngôn ngữ lập trình
 Ngôn ngữ lập trình
  Ngôn ngữ lập trình bậc cao:
 . ít phụ thuộc vào kiến trúc phần cứng máy tính, 
 . gần với tiếng Anh tự nhiên, 
 . có tính độc lập cao
 . Phải có bộ dịch sang ngôn ngữ máy
1.11. Ngôn ngữ lập trình
#include 
int main()
{
 for(int i=0; i<10; i++)
 printf("Hello world !\n");
 return 0;
}
1.11. Ngôn ngữ lập trình
 Hai hình thức dịch :
  Biên dịch (compiler): dịch toàn bộ chương trình từ ngôn
 ngữ bậc cao, hoặc hợp ngữ sang ngôn ngữ máy
1.11. Ngôn ngữ lập trình
1.11. Ngôn ngữ lập trình
 Thông dịch (interpreter): là chương trình dịch mà dịch và thực
 hiện câu lệnh một cách tuần tự
 Chương trình Java được dịch sang Bytecode (là một dạng của
 ngôn ngữ máy chuẩn). Máy ảo java (JVM) thực thi chương trình
 viết bằng Bytecode
 Bất kỳ máy tính nào có JVM đều có thể chạy chương trình java 
 đã biên dịch
1.11. Ngôn ngữ lập trình