Bài giảng Tin học đại cương - Phần 2, Chương 1: Giải quyết bài toán

Nội dung text: Bài giảng Tin học đại cương - Phần 2, Chương 1: Giải quyết bài toán

1. TIN HỌC ĐẠI CƯƠNG Phần 2: GIẢI QUYẾT BÀI TOÁN
2. Phần 2: Giải quyết bài toán Nội dung chính 1. Chương 1: Giải quyết bài toán • Khái niệm về bài toán • Quá trình giải quyết bài toán bằng máy tính • Phương pháp giải quyết bài toán bằng MT 2. Chương 2: Thuật toán • Khái niệm • Biểu diễn thuật toán • Thuật toán đệ quy • Thuật giải heuristic • Một số thuật toán thông dụng 01-Jan-16 2
3. Chương 1: Giải quyết bài toán Nội dung chính 1. Khái niệm về bài toán 2. Quá trình giải quyết bài toán bằng máy tính 3. Phương pháp giải quyết bài toán bằng máy tính 01-Jan-16 3
4. Chương 1: Giải quyết bài toán 1. Khái niệm bài toán Problem – Bài toán hay vấn đề? • Theo Socrate (470-399 TCN): Vấn đề thường được dùng với ý nghĩa rộng hơn bài toán • Bài toán là vấn đề mà để giải quyết phải liên quan ít nhiều đến tính toán – Bài toán trong vật lý, hóa học, xây dựng, kinh tế, 01-Jan-16 4
5. Chương 1: Giải quyết bài toán 1. Khái niệm bài toán Phân loại vấn đề (Pytago) • Theorema: – Vấn đề cần khẳng định đúng sai • Ví dụ: Chứng minh các định lý trong toán học • Problema: – Vấn đề cần tìm giải pháp để đạt mục tiêu xác định từ những điều kiện ban đầu • Ví dụ: Bài toán dựng hình, tìm đường đi ngắn nhất, tổng hợp chất hóa học 01-Jan-16 5
6. Chương 1: Giải quyết bài toán 1. Khái niệm bài toán Biểu diễn vấn đề (1/3) A → B • A: Giả thiết, điều kiện ban đầu • B: Kết luận, mục tiêu cần thực hiện • →: Suy luận, giải pháp cần xác định 01-Jan-16 6
7. Chương 1: Giải quyết bài toán 1. Khái niệm bài toán Biểu diễn vấn đề (2/3) • Cho vấn đề/bài toán: Cho A và B • Giải quyết vấn đề/bài toán: Từ A dùng một số hữu hạn các bước suy luận có lý hoặc hành động thích hợp để đạt B. Cần xác định tập các thao tác cơ bản được dùng trong suy luận và hành động 01-Jan-16 7
8. Chương 1: Giải quyết bài toán 1. Khái niệm bài toán Biểu diễn vấn đề (3/3) Trong tin học A → B • A: Input • B: Output • →: Chương trình cho phép biến đổi A thành B . 01-Jan-16 8
9. Chương 1: Giải quyết bài toán 1. Khái niệm bài toán Chương trình • Chương trình – Cách mã hóa lại thuật toán/thuật giải để giải quyết vấn đề/bài toán đã cho – Tạo thành từ các lệnh cơ bản của máy tính • Khó khăn: – Tồn tại các yếu tố không xác định • A và B không đầy đủ, rõ ràng • Giải quyết bài toán trên máy tính? – Vấn đề tổ chức dữ liệu và thiết kế giải thuật Cấu trúc dữ liệu + Giải thuật = Chương trình 01-Jan-16 9
10. Chương 1: Giải quyết bài toán 1. Khái niệm bài toán Thiết kế thuật giải • Thực hiện bởi con người – Là cách thức chủ yếu, dựa trên • Những thông tin được phản ánh rõ ràng trong A, B hoặc → • Các tri thức của con người • Tự động hóa xây dựng thuật giải – Lĩnh vực mới, đang được nghiên cứu – Cần phải biểu diễn nội dung và các tri thức liên quan dưới dạng tương minh và đầy đủ 01-Jan-16 10
11. Chương 1: Giải quyết bài toán Nội dung chính 1. Khái niệm về bài toán 2. Quá trình giải quyết bài toán bằng máy tính 3. Phương pháp giải quyết bài toán bằng máy tính 01-Jan-16 11
12. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Máy tính & Lập trình viên • Máy tính – Chỉ làm được những gì được bảo. – Không thông minh: không thể tự phân tích vấn đề và đưa ra giải pháp. – 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 • Lập trình viên – Phân tích vấn đề – Tạo ra các chỉ dẫn để giải quyết vấn đề (xây dưng chương trình). • Máy tính sẽ thực hiện các chỉ dẫn này. 01-Jan-16 12
13. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Các bước giải quyết bài toán 1. Xác định bài toán 2. Lựa chọn phương pháp giải 3. Xây dựng thuật toán hoặc thuật giải 4. Cài đặt chương trình 5. Hiệu chỉnh chương trình 6. Thực hiện chương trình 01-Jan-16 13
14. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Bước 1: Xác định bài toán • Mô tả bài toán cần giải quyết – Dữ liệu vào: Danh sách các dữ kiện vào – Điều kiện vào: Ràng buộc, quan hệ giữa chúng – Dữ liệu ra: Danh sách các dữ liệu ra – Điều kiện ra: Ràng buộc, quan hệ giữa chúng • Đánh giá, nhận định tính khả thi của bài toán – Thời gian, kinh phí, nguồn lực, Ví dụ: Bài toán tìm ƯSCLN của 2 số nguyên dương – Nhập: 2 số X, Y – Điều kiện nhập: X, Y nguyên dương – Dữ liệu ra: Z – Điều kiện ra: Z là ƯSCLN(X,Y) 01-Jan-16 14
15. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Bước 2: Lựa chọn phương pháp giải • Tồn tại nhiều phương pháp khác nhau – Khác nhau về thời gian thực hiện, chi phí lưu trữ dữ liệu, độ chính xác • Tùy theo nhu cầu cụ thể và khả năng xử lý tự động được sử dụng để lựa chọn phương pháp thích hợp Ví dụ: Bài toán sắp xếp dãy số – Nổi bọt, Vun đống, Sắp xếp nhanh, 01-Jan-16 15
16. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Bước 3: Xây dựng thuật giải • Xây dựng mô hình chặt chẽ, chính xác và chi tiết cho phương pháp đã lựa chọn • Lặp liên tiếp các bước sau để thuật toán ngày càng hoàn chỉnh hơn (quá trình tinh chỉnh từng bước) 1. Xác định và chính xác hóa các thao tác – Để đạt được kết quả cần làm gì? 2. Xác định các dữ liệu cần dùng và tính chất của chúng – Để thực hiện, thao tác cần gì và sẽ tạo ra gì? 3. Xác định trình tự các thao tác – Thao tác nào cần làm trước – Thao tác thực hiện 1 hay nhiều lần, thực hiện trong điều kiện nào ? 01-Jan-16 16
17. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Bước 3: Xây dựng thuật giải (tiếp) • Quá trình tinh chỉnh từng bước dừng lại khi – Yêu cầu cho biết 1 hay nhiều đại lượng – Tính một đại lượng theo công thức đã biết rõ – Thông báo một hay nhiều kết quả đã xử lý • Sau khi tinh chỉnh cần phải diễn tả giải thuật dưới dạng chuẩn – Ngôn ngữ liệt kê các hành động – Sơ đồ khối 01-Jan-16 17
18. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Bước 4: Cài đặt chương trình Mã hóa giải thuật bằng một ngôn ngữ lập trình • Thay thế các thao tác bằng các lệnh tương ứng của ngôn ngữ sử dụng – Thao tác: In ra một thông báo – Câu lệnh: printf(“ .”)/ write(“ ”); • Lựa chọn ngôn ngữ lập trình, tùy theo bài toán giải quyết – NNLT bậc thấp: Hợp ngữ – NNLT bậc cao: C, Pascal, Java, 01-Jan-16 18
19. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Bước 5: Hiệu chỉnh chương trình Chạy thử để phát hiện và điều chỉnh các sai sót có thể có ở bước 4. – Lỗi cú pháp: • Viết sai cú pháp của ngôn ngữ lập trình lựa chọn – Lỗi ngữ nghĩa • Mã hóa sai giải thuật • Giải thuật sai 01-Jan-16 19
20. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Bước 6: Thực hiện chương trình • Cho máy tính thực hiện chương trình. • Tiến hành phân tích kết quả thu được – Kết quả đó có phù hợp hay không. – Không phù hợp kiểm tra lại toàn bộ các bước. 01-Jan-16 20
21. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Các giai đoạn giải quyết bài toán 1. Giai đoạn quan niệm : – Gồm các bước xác định bài toán, lựa chọn mô hình, xây dựng thuật giải, cài đặt chương trình 2. Giai đoạn khai thác và bảo trì – Gồm các bước hiệu chỉnh và thực hiện chương trình – Nhằm đáp ứng nhu cầu về cải tiến, mở rộng chương trình • Do các yếu tố ban đầu của bài toán có thể thay đổi. 01-Jan-16 21
22. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Ví dụ Tính diện tích hình thang khi biết 4 cạnh b a c d Mô tả bài toán • Nhập: 4 cạnh a, b, c, d • Điều kiện nhập: a, b, c, d > 0 và d > b • Xuất: Một giá trị số • Điều kiện xuất: Diện tích hình thang 01-Jan-16 22
23. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Ví dụ→Xây dựng thuật toán b a c f h 1 d e 1. Để tính diện tích hình thang, cần tính đường cao (công thức S = h(b+d)/2) 2. Tính đường cao h, cần phải biết 3 cạnh của tam 2 p( p − a)(p − b)(p − c) giac (1) h = c c 3. Cần tính cạnh tam giác (1) trước khi tính đường cao h 01-Jan-16 23
24. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Ví dụ→Xây dựng thuật toán b a c f h 1 d e Lặp lại các bước • Để tính cạnh của tam giác (1) cần biết các cạnh của hình thang • Các cạnh của hình thang là dữ kiện cho biết của đề bài (điều kiện dừng) 01-Jan-16 24
25. Chương 1: Giải quyết bài toán 2. Quá trình giải quyết bài toán bằng máy tính Ví dụ→ Chuẩn hóa thuật toán 1. Nhập các số a, b, c, d 2. Tính các cạnh của tam giác (1) • fa • ed-b • p (f+e+c)/2 3. Tính chiều cao của tam giác (1) 2 p( p − e)(p − f )(p − c) h = e 4. Tính diện tích hình thang S= h(d+b)/2 5. In kết quả S 6. Kết thúc 01-Jan-16 25
26. Chương 1: Giải quyết bài toán Nội dung chính 1. Khái niệm về bài toán 2. Quá trình giải quyết bài toán bằng máy tính 3. Phương pháp giải quyết bài toán bằng máy tính 01-Jan-16 26
27. Chương 1: Giải quyết bài toán 3. Phương pháp giải quyết bài toán bằng máy tính Các phương pháp 1. Xác định trực tiếp lời giải 2. Tìm kiếm lời giải 01-Jan-16 27
28. Chương 1: Giải quyết bài toán 3. Phương pháp giải quyết bài toán bằng máy tính Hướng xác định trực tiếp lời giải • Thường sử dụng trong quá trình học tập. – Ví dụ: Tìm nghiệm phương trình bậc 2 theo định lý Viet. • Xác định trực tiếp được lời giải qua – Các thủ tục tính toán theo công thức, hệ thức, định luật – Các thủ tục bao gồm một số hữu hạn các thao tác sơ cấp, có thể chuyền thành các thuật toán và chương trình chạy trên máy tính. 01-Jan-16 28
29. Chương 1: Giải quyết bài toán 3. Phương pháp giải quyết bài toán bằng máy tính Hướng xác định trực tiếp lời giải • Trường hợp dùng các công thức lặp để tính gần đúng nghiệm của bài toán. – Lời giải xác định bởi các công thức lặp có thể xấp xỉ lời giải thật sự của bài toán với độ chính xác tăng theo quá trình lặp. • Ví dụ: giải phương trình f(x)=0 bằng PP chia đôi – Đây là hạn chế khi tính toán thủ công nhưng là thế mạnh của máy tính. – Được xem là cách xác định trực tiếp lời giải 01-Jan-16 29
30. Chương 1: Giải quyết bài toán 3. Phương pháp giải quyết bài toán bằng máy tính Hướng tìm kiếm lời giải • Cách tiếp cận dựa theo nguyên lý “thử - sai”. • Ứng dụng hiệu quả cho một số bài toán - vấn đề phức tạp • Nhiều phương pháp đề xuất 01-Jan-16 30
31. Chương 1: Giải quyết bài toán 3. Phương pháp giải quyết bài toán bằng máy tính Hướng tìm kiếm lời giải→Một số phương pháp • Phương pháp liệt kê hay vét cạn: – Xác định tập các khả năng chứa các lời giải và cách thức liệt kê của từng khả năng để thử, không bỏ sót một khả năng nào. • Phương pháp thử ngẫu nhiên: – Thử một số khả năng được chọn ngẫu nhiên trong tập (rất lớn) các khả năng. – Khả năng thành công tùy theo chiến lược chọn ngẫu nhiên và một số điều kiện cụ thể của bài toán. • Chia bài toán thành bài toán con: – Chia cho tới khi bài toán ban đầu được quy thành bài toán con có lời giải • Phương pháp quay lui: – Đánh dấu các thử nghiệm thất bại và thử khả năng mới (quay lui tìm đường khác). 01-Jan-16 31
32. Chương 1: Giải quyết bài toán 3. Phương pháp giải quyết bài toán bằng máy tính Hướng tìm kiếm lời giải→Ví dụ bài toán 8 hậu 01-Jan-16 32