Bài giảng Tin học đại cương: Chương 4 - Trần Phước Tuần

CHƯƠNG 4: GIẢI QUYẾT VẤN ĐỀ,<br /> BÀI TOÁN BẰNG MÁY TÍNH<br /> GV: Trần Phước Tuấn<br /> EMAIL: tranphuoctuan.khoatoan.dhsp@gmail.com<br /> <br /> Nội dung bài học<br /> 1. Vấn đề - bài toán<br /> 2. Thuật toán - thuật giải<br /> 3. Các phương pháp biểu diễn thuật toán<br /> 4. Các bước để giải một bài toán trên máy tính<br /> 5. Tổng quan về ngôn ngữ lập trình<br /> <br /> Page 2<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 1<br /> <br /> 1. Vấn đề - bài toán<br /> Khái niệm<br /> • Vấn đề thường được dùng với nghĩa rộng hơn<br /> <br /> bài toán, bài toán là vấn đề mà để giải quyết nó<br /> phải liên quan ít nhiều đến tính toán<br /> <br /> • Pitago chia mọi vấn đề mà con người cần giải<br /> <br /> quyết thành hai loại:<br /> <br /> – Theorema: vấn đề cần khẳng định tính đúng – sai<br /> – Problema: vấn đề cần tìm giải pháp để để đạt<br /> được mục tiêu từ những điều kiện ban đầu nào đó<br /> <br /> Page 3<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 1. Vấn đề - bài toán<br /> Khái niệm<br /> • Theo nhiều kết quả nghiên cứu: việc giải quyết<br /> <br /> vấn đề - bài toán mà Pitago nêu ra đều có thể<br /> diễn ra theo một sơ đồ chung:<br /> AB<br /> • Ở đây:<br /> – A có thể là giả thiết, điều kiện ban đầu<br /> – B có thể là kết luận, mục tiêu cần đạt<br /> –  là suy luận, giải pháp cần xác định<br /> Page 4<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 2<br /> <br /> 1. Vấn đề - bài toán<br /> Khái niệm<br /> • Ví dụ 1: Bài toán kiểm tra tính nguyên tố<br /> – Cho: Số nguyên dương N<br /> – Cần biết: N có là số nguyên tố hay không?<br /> • Ví dụ 2: Bài toán quản lý hồ sơ sinh viên<br /> – Cho: Hồ sơ gốc của các sinh viên trong trường<br /> – Cần biết: Bảng thống kê, phân loại sinh viên<br /> theo kết quả học tập<br /> <br /> Page 5<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 1. Vấn đề - bài toán<br /> Khái niệm<br /> • Cấu trúc một bài toán:<br /> – Thông tin đầu vào (input): cái cho trước<br /> – Thông tin đầu ra (output): cái cần tìm<br /> • Giải bài toán: là việc xác định tường minh<br /> <br /> output theo input bằng một quá trình có thể<br /> thực hiện một cách hiệu quả<br /> <br /> Page 6<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 3<br /> <br /> 1. Vấn đề - bài toán<br /> Một số phương pháp giải quyết vấn đề - bài toán bằng máy tính<br /> <br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> <br /> Page 7<br /> <br /> KĨ THUẬT CHIA ÐỂ TRỊ<br /> KĨ THUẬT “THAM LAM”<br /> QUY HOẠCH ÐỘNG<br /> KĨ THUẬT QUAY LUI<br /> KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 2. Thuật toán – thuật giải<br /> Thuật toán – khái niệm<br /> • Thuật toán là khái niệm cơ sở của toán học<br /> <br /> và tin học<br /> • Thuật toán là một dãy các chỉ thị rõ ràng<br /> và có thể thi hành được để hướng dẫn<br /> thực hiện hành động nhằm đạt được mục<br /> tiêu đặt ra<br /> • Thuật toán là sự thể hiện của một phương<br /> pháp để giải quyết vấn đề<br /> Page 8<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 4<br /> <br /> 2. Thuật toán – thuật giải<br /> Thuật toán – đặc trưng<br /> • Nhập (input). Các thuật toán thường có giá trị đầu vào<br /> • Xuất (output). Từ giá trị vào thuật toán cho ra kết quả.<br /> • Tính xác định (definiteness). Các bước trong thuật toán phải chính<br /> <br /> xác rõ ràng.<br /> <br /> • Tính hữu hạn (finiteness). Thuật toán phải cho ra lời giải (hay kết<br /> <br /> quả) sau một số bước hữu hạn.<br /> <br /> • Tính hiệu quả. Tính hiệu quả được đánh giá dựa trên một số tiêu<br /> <br /> chuẩn như khối lượng tính toán, không gian và thời gian sử dụng<br /> (khi thực hiện thuật toán trên máy tính).<br /> <br /> • Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài<br /> <br /> toán cùng dạng, chứ không chỉ áp dụng được cho một số trường<br /> hợp riêng lẻ nào đó.<br /> Page 9<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 2. Thuật toán – thuật giải<br /> Thuật toán<br /> • Cùng một bài toán có thể có nhiều thuật<br /> <br /> toán khác nhau để giải<br /> <br /> • Thuật toán đơn giản, dễ hiểu, có độ chính<br /> <br /> xác cao, được bảo đảm về mặt toán học, dễ<br /> triển khai trên máy, thời gian thao tác ngắn,<br /> được gọi là thuật toán tối ưu<br /> <br /> Page 10<br /> <br /> T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG<br /> <br /> 9/16/2008<br /> <br /> 5<br /> <br />