Chương 1: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN
1. Giải bài toán trên máy tính
Xác định bài toán
Việc xác định bài toán tức là phải xác định xem ta phải giải quyết vấn đề gì?,
với giả thiết nào đã cho và lời giải cần phải đạt những yêu cầu nào.
Input → Process → Output
(Dữ liệu vào → Xử lý → Kết quả ra)
Đối với những bài toán tin học ứng dụng trong thực tế, lời giải cần tìm chỉ cần
tốt tới mức nào đó, thậm chí là tồi ở mức chấp nhận được. Bởi lời giải tốt nhất đòi
hỏi quá nhiều thời gian và chi phí.
Ví dụ:
Khi cài đặt các hàm số phức tạp trên máy tính. Nếu tính bằng cách khai triển
chuỗi vô hạn thì độ chính xác cao hơn nhưng thời gian chậm hơn hàng tỉ lần so với
phương pháp xấp xỉ.
Trên thực tế việc tính toán luôn luôn cho phép chấp nhận một sai số nào đó
nên các hàm số trong máy tính đều được tính bằng phương pháp xấp xỉ của giải
tích số
Xác định đúng yêu cầu bài toán là rất quan trọng bởi nó ảnh hưởng tới cách
thức giải quyết và chất lượng của lời giải. Một bài toán thực tế thường cho bởi
những thông tin khá mơ hồ và hình thức, ta phải phát biểu lại một cách chính xác
và chặt chẽ để hiểu đúng bài toán.
Ví dụ:
• Bài toán: Một dự án có n người tham gia thảo luận, họ muốn chia thành các
nhóm và mỗi nhóm thảo luận riêng về một phần của dự án. Nhóm có bao nhiêu
người thì được trình lên bấy nhiêu ý kiến. Nếu lấy ở mỗi nhóm một ý kiến đem ghép
lại thì được một bộ ý kiến triển khai dự án. Hãy tìm cách chia để số bộ ý kiến cuối
cùng thu được là lớn nhất.
• Phát biểu lại: Cho một số nguyên dương n, tìm các phân tích n thành tổng
các số nguyên dương sao cho tích của các số đó là lớn nhất.
Trên thực tế, ta nên xét một vài trường hợp cụ thể để thông qua đó hiểu được
bài toán rõ hơn và thấy được các thao tác cần phải tiến hành. Đối với những bài

một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bài toán. Các bộ Input này
được gọi là các test.
Bước 5: Viết tài liệu
Tài liệu phải mô tả chi tiết bài toán, thiết kế thuật toán, chương trình, kết quả
thử nghiệm và hướng dẫn sử dụng.
Các bước trên có thể lặp đi lặp lại nhiều lần cho đến khi mà ta cho là chương
trình đó làm việc đúng đắn.
2. Mô hình dữ liệu (Data Model)
Mô hình dữ liệu là các trừu tượng dùng để mô tả bài toán: Mô hình toán học,
ví dụ đồ thị, tập hợp, danh sách, cây... Một mô hình dữ liệu thường có hai khía
cạnh:
- Giá trị mà đối tượng có thể nhận được, ví dụ đối tượng nhận giá trị nguyên,
thực,… Đó là khía cạnh tĩnh (static) của mô hình dữ liệu, nó cho biết những
giá trị mà một đối tượng có thể nhận được. Thành phần tĩnh này gọi là kiểu
dữ liệu (type data).
- Các phép toán ( operation) trên mô hình đó, ví dụ: các phép cộng trừ số
nguyên, số thực chẳng hạn. Đây là khía cạnh động ( dynamic) của mô hình,
cho biết cách thức thay đổi giá trị để thu được giá trị mới.
Mô hình dữ liệu của các ngôn ngữ lập trình
Mỗi chương trình có quyền truy/xuất đến các “ hộp” có thể xem như những
vùng lưu trữ. Một hộp có một kiểu (type), chẳng hạn như Int hoặc Char. Thường
ta gọi những giá trị được lưu trong hộp là các đối tượng dữ liệu (data object). Ta
hoàn toàn có thể đặt tên cho các hộp này.
3. Kiểu dữ liệu có cấu trúc
Trong thực tế chỉ với các kiểu dữ liệu cơ sở không đủ biểu diễn các bài, dẫn đến
nhu cầu phải xây dựng các kiểu dữ liệu mới dựa trên việc tổ chức, liên kết các thành
phần dữ liệu có kiểu dữ liệu đã được định nghĩa. Những kiểu dữ liệu được xây dựng
như thế gọi là kiểu dữ liệu có cấu trúc (hay còn gọi là cấu trúc dữ liệu). Đa số các ngôn
ngữ lập trình đều cài đặt sẵn một số kiểu có cấu trúc cơ bản như mảng, chuỗi, tập tin,
bản ghi...và cung cấp cơ chế cho lập trình viên tự định nghĩa kiểu dữ liệu mới.

b) Sơ đồ khối
- Để có thể mô tả thuật toán một cách trực quan, người ta dùng một số hình
vẽ kết hợp chú thích bằng lời. Thường hay dùng các hình vẽ chủ yếu sau: