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

Nội dung text: 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

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