Tinhọcđạicương - bài 6: phương pháp giải các bài toán tin học

Thuật toán: Một dãy hữu hạn các chỉ thị có thể thi hành để đạt mục tiêu đề ra nào đó.Các đặc trưng của thuật toán:Tính có đại lượng vào và ra.Tính xác định.Tính hữu hạn dừng.Tính đúng đắn.Tính phổ dụng (tổng quát).Tính hiệu quả: Bộ nhớ, số phép tính, thời gian chạy, dễ hiểu, dễ cài đặt.
Nội dung trích xuất từ tài liệu:
Tinhọcđạicương - bài 6: phương pháp giải các bài toán tin họcwww.uit.edu.vn TINHỌCĐẠICƯƠNG BÀI 6 PHƯƠNG PHÁP GIẢI CÁC BÀI TOÁN TRONG TIN HỌC 1 NỘI DUNG Khái niệm về vấn đề và bài toán. Các bước giải quyết vấn đề - bài toán trên máy tính. Thuật toán và thuật giải. Biểu diễn thuật toán và thuật giải.Tinhọcđạicương 2 KHÁI NIỆM VỀ VẤN ĐỀ - BÀI TOÁN Bài toán và giải quyết bài toán được biểu diễn dưới dạng: A → B giả thiết giải pháp mục tiêu  Cần xác định A, B, và các thao tác để đi từ A đến B.  A, B không rõ ràng?Tinhọcđạicương  Các điều kiện của cách !!! giải ko minh bạch? 3 MỘT SỐ NHẬN XÉT Việc xác định bài toán là rất quan trọng. Thông báo về A và B mang tính biểu tượng gợi nhớ về giả thiết và mục tiêu. Bước đầu để xác định bài toán và phát biểu lại theo ngôn ngữ của riêng mình để hiểu. Tiếp theo là tìm hiểu thông tin Input A và Output B và các mối liên hệ.Tinhọcđạicương Thường nên xét một vài trường hợp cụ thể để hiểu rõ hơn bài toán. 4 CÁC BƯỚC GIẢI QUYẾT BT Bước 1: Xác định vấn đề - bài toán. Nhằm phát biểu chính xác vấn đề - bài toán, làm rõ những yêu cầu, xác định tính khả thi. Bước 2: Lựa chọn phương pháp giải. Thường có nhiều cách khác nhau → Tùy theo nhu cầu thực của bài toán mà chọn lựa p/pháp phù hợp. Bước 3: Xây dựng thuật toán hoặc thuật giải. Chi tiết hóa phương pháp đã lựa chọn. Thường theo cấu trúc phân tích → Vấn đề TOP-DOWN. Bước 4: Cài đặt chương trình. Từ thuật giải, dùng NNLT để hiện thực hóa.Tinhọcđạicương Bước 5: Hiệu chỉnh & Thực hiện chương trình. Sửa lỗi, gồm: lỗi cú pháp và lỗi ngữ nghĩa. Bước 6: Lưu trữ, Bảo trì. 5 XÁC ĐỊNH CẤU TRÚC DỮ LIỆU Niklaus Wirth: Cấu trúc dữ liệu + Thuật giải = Ch. trình Dữ liệu và cấu trúc dữ liệu đóng vai trò quan trọng trong việc kết hợp và đưa ra cách giải quyết bài toán. Một số lưu ý về CTDL:  Phải biểu diễn đầy đủ thông tin.  Phù hợp các thao tác của thuật toán.Tinhọcđạicương  Phù hợp điều kiện cho phép của NNLT. 6 THUẬT TOÁN VÀ THUẬT GIẢI Thuật toán: Một dãy hữu hạn các chỉ thị có thể thi hành để đạt mục tiêu đề ra nào đó. Các đặc trưng của thuật toán:  Tính có đại lượng vào và ra.  Tính xác định.  Tính hữu hạn dừng.  Tính đúng đắn.  Tính phổ dụng (tổng quát).Tinhọcđạicương  Tính hiệu quả: Bộ nhớ, số phép tính, thời gian chạy, dễ hiểu, dễ cài đặt. 7 THUẬT TOÁN VÀ THUẬT GIẢI Thuật giải: Khái niệm mở rộng của thuật toán. Với một số đặc điểm chẳng hạn:  Có những bài toán không xác định (có) thuật toán cụ thể.  Hoặc có thuật toán nhưng không thực hiện được (chẳng hạn vì thời gian dài).  Hoặc có cách giải vi phạm thuật toán nhưng vẫn được chấp nhận.Tinhọcđạicương  Heuristic: Giải quyết bài toán với kết quả đúng (gần đúng) trong p. vi cho phép. 8 BIỂU DIỄN THUẬT TOÁN Ngôn ngữ tự nh ...