Tin học đại cương
Bài 4: Giải quyết bài toán - Phần 2: Giải quyết bài toán
NGUYỄN Thị Oanh
oanhnt@soict.hut.edu.vn
Bộ môn Hệ thống thông tin - Viện CNTT và Truyền Thông
Đại học Bách Khoa Hà nội
2010 - 2011
Bài toán
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
Nội dung
1Bài toán
2Giải quyết bài toán bằng máy tính
3Các phương pháp giải quyết bài toán bằng máy tính
4Phân loại bài toán
2 / 28
Bài toán
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
Khái niệm
✦"Bài toán" vs. "Vấn đề"
–vấn đề có nghĩa rộng hơn bài toán
–bài toán là một loại 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ế, ...
✦Pitago chia mọi vấn đề thành 2 loại:
–Theorema: vấn đề cần được khẳng định tính đúng / sai, ví dụ:
chứng minh định lý trong toán học
–Problema: vấn đề cần tìm được giải pháp để đạt được một mục
tiêu xác định từ những điều kiện ban đầu nào đó, ví dụ: bài toán
dựng hình, tìm đường đi ngắn nhất, ...
3 / 28
Bài toán
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
Khái niệm
✦Biểu diễn vấn đề - bài toán:
A→B
A: giả thiết, điều kiện ban đầu
B: kết luận, mục tiêu cần đạt được
→: suy luận và giải pháp cần xác định
✦Giải quyết vấn đề - bài toán:
–từ Adù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 được B
–trong tin hoc:
A:đầu vào (input)B:đầu ra (output)
→: chương trình tạo thành từ các lệnh cơ bản của máy tính cho
phép biến đổi A thành B (cách mã hóa lại thuật toán hay thuật
giải)
4 / 28
Bài toán
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
Giải quyết bài toán bằng máy tính
✦Máy tính không thể dùng, ít nhất là trực tiếp, để 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
✦Máy tính chỉ làm được những gì mà nó được bảo phải làm. Máy
tính không tự thông minh, nó không thể tự phân tích vấn đề và
đưa ra giải pháp
✦Con người (lập trình viên) là người phân tích vấn đề, tạo ra các
chỉ dẫn để giải quyết vấn đề (chương trình), và máy tính sẽ thực
hiện các chỉ dẫn đó
5 / 28