Bài giảng Tin học đại cương: Chương 4 - Lê Thị Ngọc Thảo

Bài giảng Tin học đại cương: Chương 4 Chương trình và giải thuật, cung cấp cho người học những kiến thức như Các khái niệm; Các phương pháp biểu diễn; Ngôn ngữ tự nhiên; Lưu đồ - sơ đồ khối; Mã giả. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học đại cương: Chương 4 - Lê Thị Ngọc Thảo CHƯƠNG 4: CHƯƠNG TRÌNH & GIẢI THUẬTĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 129Các khái niệm (1) Thuật toán • Cách hiểu đơn giản • Tập các hướng dẫn thực hiện một công việc. • Tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. • Một phương pháp thể hiện lời giải của vấn đề. • Algorithm: nhà toán học Trung Á • Muhammad Bin Musa Al-Khwarizmi • http://www2.sjsu.edu/depts/Museum/alkhwa.htmlĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 130 Các khái niệm (2) Thuật toán (tt) • Trong khoa học máy tính • Một dãy hữu hạn các bước rõ ràng và thực thi được. • Quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn. • Tính xác định • Hướng dẫn giải rõ ràng và đúng • Tính hữu hạn • Số bước hữu hạn và tính chất dừngĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 131 Các khái niệm (3) Tính mập mờ: • Xem xét thực hiện công việc tìm một môn học nhiều đvht nhất: • Lập danh sách các môn học. • Sắp thứ tự các môn học. • Chọn ra một môn học nhiều đvht. • Kết quả:??? • Câu hỏi:???ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 132 Các khái niệm (4) Tính mập mờ (tt): • Vi phạm tính rõ ràng – không mập mờ • Hiểu đúng – Hiểu 1 nghĩa duy nhất • Sửa lại : • 1.Lập danh sách các môn học theo tên, số đvht • 2.Sắp thứ tự các môn học giảm dần theo số đvht • 3.Chọn ra một môn học có nhiều đvht nhất • Câu hỏi???ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 133 Các khái niệm (5)Tính mập mờ (tt): • Phân biệt mập mờ và chọn lựa có quyết định. • Mập mờ là thiếu thông tin hoặc có nhiều chọn lựa nhưng không đủ điều kiện để quyết định. • Chọn lựa có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề • Sửa lại: • 3.Chọn ra một môn học có nhiều đvht nhất. • 3.1 Nếu chỉ có một môn học nhiều đvht nhất: chọn một • 3.2 Nếu có nhiều môn học cùng số đvht: sắp xếp tăng dần theo tên môn học trong thứ tự từ điển rối chọn môn đầu tiên.ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 134 Các khái niệm (6) Tính thực thi được: • Hiển nhiên • Chỉ xét trong điều kiện hiện tại của bài toán • Cho ví dụ về điều kiện hiện tại:??? Tính dừng: • Không dừng: Lặp vô tận, bị quẫn • Dễ vi phạm nhấtĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 135Các khái niệm (7) Tính dừng -Ví dụ: • Tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau : • B1. Hỏi giá trị của n. • B2. S = 0 • B3. i = 1 • B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5 • B5. Cộng thêm i vào S • B6. Cộng thêm 2 vào i • B7. Quay lại bước B4. • B8. Tổng cần tìm chính là S. • Thuật toán luôn dừng???ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 136 Các khái niệm (8) Tính dừng -Ví dụ: • Chỉ dừng khi n chẵn • Khi n lẻ phải thay B4 bằng: • B4. Nếu i >= n+1 thì sang bước B8, ngược lại sang bước B5 Tính đúng: • Chứng minh thuật toán đúng!!! • Khó đạt được nhấtĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 137 Các khái niệm (9) Thuật toán thì cứng nhắc ! • Tính chất chặt chẽ và cứng nhắc. • Khả năng giải quyết vấn đề bị giới hạn. làm mềm“: tính xác định và tính đúng • Thuật toán đệ quy. • Thuật giải.ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 138 Các khái niệm (10) Các đặc trưng khác của thuật toán • Ðầu vào và đầu ra (input/output) . • Tính hiệu quả (effectiveness): theo tiêu chuẩn • Khối lượng tính toán, không gian và thời gian thi hành. • Là yếu tố quyết định để đánh giá, chọn lựa • Nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. • Tính tổng quát (generalliness) : • Áp dụng được cho mọi trường hợp của bài toán • Không phải lúc nào cũng đảm bảo được tính tổng quát. • Có lúc chỉ cần xây dựng cho một dạng đặc trưng.ĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 139 Các khái niệm - Ví dụ (1) Thuật toán giải phương trình bậc hai ax2+bx+c=0 (a0) • 1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c • 2. Nếu a=0 thì • 2.1. Yêu cầu đầu vào không đảm bảo. • 2.2. Kết thúc thuật toán. • 3. Trường hợp a khác 0 thìĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 140 Các khái niệm - Ví dụ (2) • 3. Trường hợp a khác 0 thì • 3.1. Tính giá trị D = b2-4ac • 3.2. Nếu D > 0 thì • 3.2.1. Phương trình có hai nghiệm phân biệt x1,x2 • 3.2.2. Giá trị của hai nghiệm được tính theo công thức sau: −b + D −b − D x1 = , x2 = 2a 2a • 3.2.3. Kết thúc thuật toán. • 3.3 Nếu D=0 thìĐH Tôn Đức Thắng, Khoa CNTT - TƯD GV: Lê Thị Ngọc Thảo 141 Các khái niệm - Ví dụ (3) • 3.3. Nếu D = 0 thì • 3.3.1. Phương trình có nghiệm kép x0 • 3.3.2. Giá trị của nghiệm kép là −b x= 2a • 3.3.3. Kết thúc thuật toán • 3.4. Nếu D < 0 thì • 3.4.1. Phương trình vô nghiệm. • 3.4.2. Kết thúc thuật toán.ĐH Tôn Đức Thắng, Khoa CNTT - TƯD ...