Giáo trình Tin học đại cương - Chương 1: Giải quyết bài toán bằng máy tính

1Phần II: Giải quyết bài toán 2 Nội dung phần này  Chương 1: Giải quyết bài toán bằng máy tính  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  Các phương pháp giải quyết bài toán bằng máy tính  Phân loại bài toán  Chương 2: Thuật toán  Định nghĩa thuật toán  Biểu diễn thuật toán  Một số thuật toán thông dụng  Thuật toán đệ quy  Thuật giải heuristic 3 Chương 1: Giải quyết bài toán bằng máy tính 4 Nội dung chương này  1.1. Khái niệm về bài toán  1.2. Các bước giải quyết bài toán bằng máy tính  1.3. Các phương pháp giải quyết vấn đề bằng máy tính  1.4. Phân loại bài toán 51.1. Khái niệm về vấn đề và bài toán  Vấn đề rộng hơn bài toán?  Pitago chia vấn đề ra:  Theorema là vấn đề cần được khẳng định đúng-sai  Problema là vấn đề cần tìm giải pháp để đạt được một mục tiêu xác định từ những điều kiện ban đầu.  Diễn đạt bằng sơ đồ: A  B  A là giả thiết, điều kiện ban đầu  B là kết luận, mục tiêu cần đạt   là suy luận, giải pháp cần xác định 6 1.2. Các bước giải quyết bài toán bằng máy tính  Bước 1: Xác định vấn đề-bài toán  Bước 2: Lựa chọn phương pháp giải  Bước 3: Xây dựng thuật toán hoặc thuật giải  Bước 4: Cài đặt chương trình  Bước 5: Hiệu chỉnh chương trình  Bước 6: Thực hiện chương trình 7 1.3. Các phương pháp giải quyết vấn đề bằng máy tính  Giải quyết vấn đề theo hướng xác định trực tiếp lời giải  xác định trực tiếp lời giải qua thủ tục tính toán hoặc thủ tục bao gồm một số hữu hạn các thao tác sơ cấp.  Giải quyết vấn đề theo hướng tìm kiếm lời giải  nguyên lý "thử và sai"  các phương pháp  liệt kê hay vét cạn  thử ngẫu nhiên  quay lui  chia để trị 8 1.4. Phân loại bài toán  Bài toán đa thức  Bài toán không đa thức  NP Problems 9