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 ĐỀ,
BÀI TOÁN BẰNG MÁY TÍNH
GV: Trần Phước Tuấn
EMAIL: tranphuoctuan.khoatoan.dhsp@gmail.com

Nội dung bài học
1. Vấn đề - bài toán
2. Thuật toán - thuật giải
3. Các phương pháp biểu diễn thuật toán
4. Các bước để giải một bài toán trên máy tính
5. Tổng quan về ngôn ngữ lập trình

Page 2

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

1

1. Vấn đề - bài toán
Khái niệm
• Vấn đề thường được dùng với nghĩa rộng hơn

bài toán, bài toán là vấn đề mà để giải quyết nó
phải liên quan ít nhiều đến tính toán

• Pitago chia mọi vấn đề mà con người cần giải

quyết thành hai loại:

– Theorema: vấn đề cần khẳng định tính đúng – sai
– Problema: vấn đề cần tìm giải pháp để để đạt
được mục tiêu từ những điều kiện ban đầu nào đó

Page 3

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

1. Vấn đề - bài toán
Khái niệm
• Theo nhiều kết quả nghiên cứu: việc giải quyết

vấn đề - bài toán mà Pitago nêu ra đều có thể
diễn ra theo một sơ đồ chung:
AB
• Ở đây:
– A có thể là giả thiết, điều kiện ban đầu
– B có thể 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
Page 4

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

2

1. Vấn đề - bài toán
Khái niệm
• Ví dụ 1: Bài toán kiểm tra tính nguyên tố
– Cho: Số nguyên dương N
– Cần biết: N có là số nguyên tố hay không?
• Ví dụ 2: Bài toán quản lý hồ sơ sinh viên
– Cho: Hồ sơ gốc của các sinh viên trong trường
– Cần biết: Bảng thống kê, phân loại sinh viên
theo kết quả học tập

Page 5

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

1. Vấn đề - bài toán
Khái niệm
• Cấu trúc một bài toán:
– Thông tin đầu vào (input): cái cho trước
– Thông tin đầu ra (output): cái cần tìm
• Giải bài toán: là việc xác định tường minh

output theo input bằng một quá trình có thể
thực hiện một cách hiệu quả

Page 6

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

3

1. Vấn đề - bài toán
Một số phương pháp giải quyết vấn đề - bài toán bằng máy tính

1.
2.
3.
4.
5.

Page 7

KĨ THUẬT CHIA ÐỂ TRỊ
KĨ THUẬT “THAM LAM”
QUY HOẠCH ÐỘNG
KĨ THUẬT QUAY LUI
KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

2. Thuật toán – thuật giải
Thuật toán – khái niệm
• Thuật toán là khái niệm cơ sở của toán học

và tin học
• Thuật toán là một dãy các chỉ thị rõ ràng
và có thể thi hành được để hướng dẫn
thực hiện hành động nhằm đạt được mục
tiêu đặt ra
• Thuật toán là sự thể hiện của một phương
pháp để giải quyết vấn đề
Page 8

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

4

2. Thuật toán – thuật giải
Thuật toán – đặc trưng
• Nhập (input). Các thuật toán thường có giá trị đầu vào
• Xuất (output). Từ giá trị vào thuật toán cho ra kết quả.
• Tính xác định (definiteness). Các bước trong thuật toán phải chính

xác rõ ràng.

• Tính hữu hạn (finiteness). Thuật toán phải cho ra lời giải (hay kết

quả) sau một số bước hữu hạn.

• Tính hiệu quả. Tính hiệu quả được đánh giá dựa trên một số tiêu

chuẩn như khối lượng tính toán, không gian và thời gian sử dụng
(khi thực hiện thuật toán trên máy tính).

• Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài

toán cùng dạng, chứ không chỉ áp dụng được cho một số trường
hợp riêng lẻ nào đó.
Page 9

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

2. Thuật toán – thuật giải
Thuật toán
• Cùng một bài toán có thể có nhiều thuật

toán khác nhau để giải

• Thuật toán đơn giản, dễ hiểu, có độ chính

xác cao, được bảo đảm về mặt toán học, dễ
triển khai trên máy, thời gian thao tác ngắn,
được gọi là thuật toán tối ưu

Page 10

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

5