Bài giảng Hệ thống thông tin - Phần 2: Giải quyết bài toán - 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
Ngo Van Linh
Bộ môn Hệ thống thông tin
Viện Công nghệ thông tin và Truyền thông
Đại học Bách Khoa Hà Nội
2Nộ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
3Chương 1: 
Giải quyết bài toán bằng máy tính
Nguyễn Hồng Phương
Email: phuongnh-fit@mail.hut.edu.vn
Website: 
Bộ môn Hệ thống thông tin
Viện Công nghệ thông tin và Truyền thông
Đại học Bách Khoa Hà Nội
4Nộ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
61.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
71.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ị
81.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