Bài giảng Tin học đại cương - Chương 6: Thuật toán và ngôn ngữ lập trình (Mới)

 Bài giảng Tin học đại cương 
 2.1 Khái niệm thuật toán 
•  Thuật toán (thuật giải, algorithms): là tập hợp hữu hạn 
 các thao tác, phép toán được thực hiện theo một trình tự 
 xác định trên một số đối tượng dữ liệu nào đó để đạt được 
 kết quả mong muốn. 
•  Để tìm thuật toán cho một bài toán ta cần xác định dữ liệu 
 vào (input) và dữ liệu ra (output) cho bài toán. 
•  VD: Bài toán giải phương trình bậc 2 ax2 + bx + c = 0 
 –  Dữ liệu vào: Giá trị của 3 hệ số a, b, c 
 –  Dữ liệu ra: Là nghiệm của phương trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 5 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 NỘI DUNG CHƯƠNG 6 
1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH 
2. THUẬT TOÁN 
 2.1. Khái niệm thuật toán 
 2.2. Các tính chất của thuật toán 
 2.3. Độ phức tạp của thuật toán 
 2.4. Các cách diễn đạt thuật toán 
3. NGÔN NGỮ LẬP TRÌNH 
 3.1. Khái niệm về ngôn ngữ lập trình 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
 3.3. Trình biên dịch và trình thông dịch 
 3.4. Các công việc của lập trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 6 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 2.2. Các nh chất của thuật toán 
•  Tính kết thúc 
•  Tính thực hiện được 
•  Tính kết quả 
•  Tính hiệu quả 
•  Tính duy nhất 
•  Tính hình thức 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 7 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 NỘI DUNG CHƯƠNG 6 
1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH 
2. THUẬT TOÁN 
 2.1. Khái niệm thuật toán 
 2.2. Các tính chất của thuật toán 
 2.3. Độ phức tạp của thuật toán 
 2.4. Các cách diễn đạt thuật toán 
3. NGÔN NGỮ LẬP TRÌNH 
 3.1. Khái niệm về ngôn ngữ lập trình 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
 3.3. Trình biên dịch và trình thông dịch 
 3.4. Các công việc của lập trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 8 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 2.3. Độ phức tạp của thuật toán 
•  Đánh giá một thuật ta dựa vào hai tiêu chí sau: 
 –  Thời gian thực hiện: Đây là tiêu chí chủ yếu để đánh giá 
 –  Dung lượng bộ nhớ sử dụng 
•  Đánh giá thời gian thực hiện thuật toán người ta dùng “Độ 
 phức tạp tính toán của thuật toán”. 
=> Độ phức tạp tính toán của thuật toán là thời gian thực 
 hiện của thuật toán được đánh giá mà không phụ thuộc vào 
 máy tính và các yếu tố liên quan, chỉ phụ thuộc vào kích 
 thước của dữ liệu đầu vào. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 9 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 2.3. Độ phức tạp của thuật toán 
•  Gọi n là kích thước của dữ liệu vào, thì thời gian thực hiện T của 
 một giải thuật được biểu diễn như một hàm của n, gọi là T(n). 
•  Nếu T(n) = Cn2 trong đó C là hằng số, thì ta nói độ phức tạp tính 
 toán của thuật toán này có cấp n2, kí hiệu là: T(n) = O(n2) 
•  Tổng quát: 
 –  Hàm f(n) có độ phức tạp tính toán cấp g(n) nếu hàm f(n) bị chặn bởi 
 Cg(n), với C là hằng số. Kí hiệu là f(n) = O(g(n)) 
•  Các hàm thể hiện độ phức tập tính toán của giải thuật có các 
 n n 3 2
 dạng sau: n , n!, 2 , n , n , nlog2n, n, log2n. Các hàm đó đã 
 được sắp theo thứ tự ưu tiên giá trị giảm dần 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 10 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 NỘI DUNG CHƯƠNG 6 
1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH 
2. THUẬT TOÁN 
 2.1. Khái niệm thuật toán 
 2.2. Các tính chất của thuật toán 
 2.3. Độ phức tạp của thuật toán 
 2.4. Các cách diễn đạt thuật toán 
3. NGÔN NGỮ LẬP TRÌNH 
 3.1. Khái niệm về ngôn ngữ lập trình 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
 3.3. Trình biên dịch và trình thông dịch 
 3.4. Các công việc của lập trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 11 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 2.4. Các cách diễn đạt thuật toán 
Cách 1: 
•  Liệt kê các bước bằng lời: Sử dụng ngôn ngữ tự nhiên để liệt kê 
 các công việc của thuật toán qua các bước: Bước 1, Bước 2, Bước 3 
VD: Cho hai số m, n tìm d = USCLN(m,n) 
Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 
 2 
Bước 2: Nếu m> n thì về bước 4 nếu không thực hiện tiếp bước 3 
Bước 3: m <n, bớt m đi một lượng bằng n và quay về bước 1 
Bước 4: bớt m đi một lượng bằng n và quay về bước 1 
Bước 5: Lấy d chính là giá trị chung của m và n. Kết thúc 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 12 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
VÍ DỤ CÁC BƯỚC CỦA THUẬT TOÁN EUCLID 
m n So sánh Bước 1: Kiểm tra nếu m= n thì về bước 5, 
 nếu không thực hiện tiếp bước 2 
15 21 m>n Bước 2: Nếu m> n thì về bước 4 nếu không 
15 6 m>n thực hiện tiếp bước 3 
 Bước 3: m <n, bớt m đi một lượng bằng n 
9 6 m>n và quay về bước 1 
 Bước 4: bớt m đi một lượng bằng n và quay 
3 6 m<n về bước 1 
3 3 m=n Bước 5: Lấy d chính là giá trị chung của m 
 và n. Kết thúc 
 USCLN(15,21) = 3 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 13 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 2.4. Các cách diễn đạt thuật toán 
Cách 2: 
•  Dùng lưu đồ thuật toán: Sử dụng các hình vẽ 
 cơ bản để vẽ hình có hướng đi thể hiện các công 
 việc và trình tự thực hiện thuật toán. 
•  Các hình cơ bản gồm có: Bắt đầu, Kết thúc, 
 Vào/Ra dữ liệu, Thực hiện một công việc A, Kiểm 
 tra điều kiện đúng/sai. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 14 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 Các hình cơ bản gồm có: 
Khối thao tác 
 Khối output 
đối tượng:= biểu Khối input Khối input 
thức 
 Khởi đầu Kết thúc 
 Khối điều kiện 
 + - 
 Thứ tự xử lý 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 15 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 VD: BIỂU DIỄN BẰNG LƯU ĐỒ THUẬT TOÁN EUCLID 
 Bước 1: Kiểm tra nếu m= n 
 Vào m,n thì về bước 5, nếu 
 không thực hiện tiếp 
 bước 2 
 Sai Đúng Bước 2: Nếu m> n thì về 
 So sánh bước 4 nếu không thực 
 m=n? hiện tiếp bước 3 
 Bước 3: m <n, bớt m đi một 
Đúng Sai d:=+ m lượng bằng n và quay 
 m>n ? về bước 1 
 Bước 4: bớt m đi một lượng 
 d bằng n và quay về 
 m:=m-n n:= n - m bước 1 
 Bước 5: Lấy d chính là giá trị 
 chung của m và n. Kết 
 thúc 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 16 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 2.4. Các cách diễn đạt thuật toán 
Cách 3: 
•  Sử dụng giả ngôn ngữ lập trình (giả mã): Sử dụng 
 ngôn ngữ tự nhiên kết hợp với một số từ khóa và cấu 
 trúc điều khiển trong ngôn ngữ lập trình bậc cao để 
 diễn tả các công việc của thuật toán. 
•  VD: Viết thuật toán m USCL của 2 số nguyên dương 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 17 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 VD: Viết thuật toán tìm USCL của 2 số nguyên 
 dương 
Trong khi m ≠ n thì lặp lại khối sau: read(m,n); 
 while m n do 
 Nếu m > n thì 
 if m>n then 
 Bớt m đi một lượng là n 
 m:=m-n 
 Nếu ngược lại thì 
 else 
 Bớt n đi một lượng là m 
 n:= n-m; 
 write(m); 
Cho tới khi m = n thì kết luận USCLN 
chính là giá trị chung của m và n Chương trình 
 trong PASCAL 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 18 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 NỘI DUNG CHƯƠNG 6 
1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH 
2. THUẬT TOÁN 
 2.1. Khái niệm thuật toán 
 2.2. Các tính chất của thuật toán 
 2.3. Độ phức tạp của thuật toán 
 2.4. Các cách diễn đạt thuật toán 
3. NGÔN NGỮ LẬP TRÌNH 
 3.1. Khái niệm về ngôn ngữ lập trình 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
 3.3. Trình biên dịch và trình thông dịch 
 3.4. Các công việc của lập trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 19 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 3.1. Khái niệm về ngôn ngữ lập trình 
•  Ngôn ngữ lập trình (programming language : Tập 
 hợp các ký hiệu và các quy tắc viết các lệnh để thể hiện 
 thuật toán 
•  Ngôn ngữ lập trình gồm 2 loại chính: 
 –  Ngôn ngữ lập trình bậc thấp (hợp ngữ, assembly): 
 •  Có cấu trúc lệnh rất giống với ngôn ngữ máy, chỉ 
 khác là dùng mã chữ thay cho mã nhị phân. 
 •  Ví dụ: Lệnh ADD AX, BX cộng (Addition) nội dung 
 thanh ghi AX và BX, kết quả để trong AX. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 20 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
3.1. Khái niệm về ngôn ngữ lập trình 
–  Ngôn ngữ lập trình bậc cao (ngôn ngữ thuật 
 toán): 
 •  Là ngôn ngữ có các lệnh rất gần với ngôn ngữ con 
 người và ngôn ngữ toán học. 
 •  Các ngôn ngữ này chỉ nhằm vào thể hiện thuật 
 toán nên người ta còn gọi là các ngôn ngữ thuật 
 toán. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 21 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 NỘI DUNG CHƯƠNG 6 
1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH 
2. THUẬT TOÁN 
 2.1. Khái niệm thuật toán 
 2.2. Các tính chất của thuật toán 
 2.3. Độ phức tạp của thuật toán 
 2.4. Các cách diễn đạt thuật toán 
3. NGÔN NGỮ LẬP TRÌNH 
 3.1. Khái niệm về ngôn ngữ lập trình 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
 3.3. Trình biên dịch và trình thông dịch 
 3.4. Các công việc của lập trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 22 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
•  Thế hệ 1 (đầu năm 1950): Lập trình ở mức mã máy 
 điển hình là hợp ngữ (assembly). 
•  Thế hệ 2 (Từ cuối năm 1950 đến hết năm 1960): 
 –  Các lệnh của hợp ngữ được gộp lại thành các câu lệnh 
 có cấu trúc. 
 –  Các ngôn ngữ lập trình: FORTRAN, COBOL, ALGOL và 
 cao hơn một chút là BASIC. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 23 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
•  Thế hệ 3: Đây là thế hệ của các ngôn ngữ lập trình hiện đại, có 
 tính cấu trúc mạnh mẽ. Các ngôn ngữ lập trình trong thế hệ này 
 chia thành 3 lớp: 
 - Ngôn ngữ lập trình cấp cao vạn năng: Gồm có PL/1, Pascal, 
 Modula-2, C và Ada. 
 - Ngôn ngữ lập trình hướng đối tượng: Là các ngôn ngữ lập 
 trình cài đặt được các nội dung của phương pháp lập trình 
 hướng đối tượng. Điển hình là C++, Smalltalk và Eiffel. 
 -  Ngôn ngữ lập trình chuyên dụng: Là ngôn ngữ có dạng cú 
 pháp bất thường được thiết kế riêng cho các ứng dụng. Ví dụ 
 như LISP, PROLOG, APL, FORTH LISP 
•  Thế hệ 4: Gồm có Ngôn ngữ hỏi, bộ sinh chương trình. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 24 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 NỘI DUNG CHƯƠNG 6 
1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH 
2. THUẬT TOÁN 
 2.1. Khái niệm thuật toán 
 2.2. Các tính chất của thuật toán 
 2.3. Độ phức tạp của thuật toán 
 2.4. Các cách diễn đạt thuật toán 
3. NGÔN NGỮ LẬP TRÌNH 
 3.1. Khái niệm về ngôn ngữ lập trình 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
 3.3. Trình biên dịch và trình thông dịch 
 3.4. Các công việc của lập trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 25 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 3.3. Trình biên dịch và trình thông dịch 
•  Máy tính chỉ hiểu được một ngôn ngữ duy nhất là ngôn 
 ngữ máy. Bởi vậy, các chương trình viết bằng các ngôn 
 ngữ lập trình (chương trình nguồn) phải được dịch sang 
 ngôn ngữ máy. 
•  Có hai kiểu dịch: thông dịch và biên dịch. 
 –  Thông dịch (Interpreter) là kiểu dịch từng lệnh để 
 hiểu được công việc phải làm và thực hiện luôn không 
 cần tạo ra những đoạn mã tương ứng trong ngôn ngữ 
 máy. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 26 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 3.3. Trình biên dịch và trình thông dịch 
•  Biên dịch là dịch toàn bộ chương trình nguồn thành một 
 chương trình tương ứng trong ngôn ngữ máy (chương 
 trình đích), sau đó nạp chương trình đích vào máy tính 
 để thực hiện. 
 –  Một chương trình thực hiện việc biên dịch chương 
 trình nguồn sang ngôn ngữ máy được gọi là trình 
 biên dịch. 
 –  Mỗi ngôn ngữ lập trình có một trình biên dịch tương 
 ứng. Ví dụ các ngôn ngữ lập trình có trình biên dịch là 
 Pascal, C, C++, Java, C#... 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 27 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 NỘI DUNG CHƯƠNG 6 
1. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BẰNG MÁY TÍNH 
2. THUẬT TOÁN 
 2.1. Khái niệm thuật toán 
 2.2. Các tính chất của thuật toán 
 2.3. Độ phức tạp của thuật toán 
 2.4. Các cách diễn đạt thuật toán 
3. NGÔN NGỮ LẬP TRÌNH 
 3.1. Khái niệm về ngôn ngữ lập trình 
 3.2. Lịch sử phát triển của ngôn ngữ lập trình 
 3.3. Trình biên dịch và trình thông dịch 
 3.4. Các công việc của lập trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 28 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 3.4. Các công việc của lập trình 
•  Soạn thảo: 
 –  Lưu tệp chương trình với phần mở rộng phù 
 hợp với ngôn ngữ lập trình sử dụng, 
 –  ví dụ .pas cho Pascal, .c cho ngôn ngữ C 
 hay .cpp cho ngôn ngữ C++ 
 –  Vd: Notepad++, 
•  Biên dịch chương trình: 
 –  dịch toàn bộ tệp chương trình nguồn sang tệp 
 mã máy 
•  Chạy thử chương trình 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 29 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 Câu hỏi và bài tập 
1.  Thuật toán là gì? Cho ví dụ. 
2.  Xác định input và output cho các thuật toán sau đây: 
 a. Rút gọn một phân số. 
 b. Kiểm tra xem ba số cho trước a, b và c có thể là độ dài ba 
 cạnh của một tam giác hay không? 
3.  Trình bày tính chất xác định của thuật toán và nêu rõ 
 nghĩa của tính chất này 
4.  Cho tam giác ABC có góc vuông A và cho biết cạnh a và 
 góc B. Hãy viết thuật toán để tính góc C, cạnh b và cạnh 
 c. 
5.  Hãy phát biểu thuật toán để giải bài toán sau: "Có một số 
 quả táo. Dùng cân hai đĩa (không có quả cân) để xác định 
 quả táo nặng nhất" 
6.  Chỉ dùng phép cộng, tính bình phương của một số 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 30 
 Khoa Công nghệ thông n – Học viện Nông nghiệp Việt nam 
 Bài giảng Tin học đại cương 
 Ví dụ chạy trên chương trình Pascal 
•  Bài 1: Tìm USCLN của hai số nguyên dương 
•  Bài 2: Sắp xếp dãy số tăng dần 
•  Bài 3: Tìm vị trí số lớn nhất trong dãy số. 
 Chương 6: Thuật toán và Ngôn ngữ lập trình 31