Giải bài toán bằng máy tính
Module bởi: Khoa CNTT ĐHSP KT Hưng Yên. E-mail the author
Người dùng đánh giá ( How does the rating system work ?)
THUẬT TOÁN
Thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định
nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp
dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán.
Nói cách khác, thuật toán là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong
một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào.
Ví dụ: thuật toán để giải phương trình bậc nhất P(x): ax + b = c, (a, b, c là các số thực), trong tập hợp các
số thực có thể là một bộ các bước sau đây:
Nếu a = 0
b = c thì P(x) có nghiệm bất kì
b ≠ c thì P(c) vô nghiệm
Nếu a ≠ 0
P(x) có duy nhất một nghiệm x = (c - b)/a
Lưu ý:
Khi một thuật toán đã hình thành thì ta không xét đến việc chứng minh thuật toán đó mà chỉ chú trọng
đến việc áp dụng các bước theo sự hướng dẫn sẽ có kết quả đúng. Việc chứng minh tính đầy đủ và tính đúng
của các thuật toán phải được tiến hành xong trước khi có thuật toán. Nói rõ hơn, thuật toán có thể chỉ là việc áp
dụng các công thức hay qui tắc, qui trình đã được công nhận là đúng hay đã được chứng minh về mặt toán học.
"Thuật toán" hiện nay thường được dùng để chỉ thuật toán giải quyết các vấn đề tin học. Hầu hết các
thuật toán tin học đều có thể viết thành các chương trình máy tính mặc dù chúng thường có một vài hạn chế (vì
khả năng của máy tính và khả năng của người lập trình). Trong nhiều trường hợp, một chương trình khi thiết
kế bị thất bại là do lỗi ở các thuật toán mà người lập trình đưa vào là không chính xác, không đầy đủ, hay
không ước định được trọn vẹn lời giải của vấn đề. Tuy nhiên cũng có một số bài toán mà hiện nay người ta
chưa tìm được lời giải triệt để, những bài toán ấy gọi là những bài toán NP-không đầy đủ.
Thuật toán: Thuật toán của một bài toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định
một dãy các thao tác trên những dữ liệu vào (Input), sao cho sau một số hữu hạn bước thực hiện các thao tác ta
thu được kết quả (Output) của bài toán đó.
Chương trình:

). Nhưng heapsort đã giảm độ phức tạp
này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng
số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun
thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách.
Sắp xếp vun đống chạy trong thời gian O(n log n).
Sắp xếp nhanh
Sắp xếp nhanh (quicksort) là một thuật toán theo tư tưởng chia để trị, nó dựa trên thủ tục phân chia như
sau: để chia một dãy ta chọn một phần tử được gọi là "chốt" (pivot), chuyển tất cả các phần tử nhỏ hơn chốt về
trước chốt, chuyển tất cả các phần tử lớn hơn chốt về sau nó. Thủ tục này có thể thực hiện trong thời gian tuyến
tính. Tiếp tục phân chia các dãy con đó như trên cho đến khi các dãy con chỉ còn một phần tử.
Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn việc xác định thứ tự được xác
định khi "trộn", tức là trong khâu tổng hợp lời giải sau khi các bài toán con đã được giải, còn sắp xếp nhanh đã
quan tâm đến thứ tự các phần tử khi phân chia một danh sách thành hai danh sách con.
Ngoài ra còn nhiều giải thuật sắp xếp khác, trong đó nhiều giải thuật sắp xếp được cải tiến từ các giải
thuật trên. Trong sau giải thuật liệt kê trên, ta thường coi các giải thuật chèn, chọn, nổi bọt là các giải thuật cơ
bản, độ phức tạp trong trường hợp trung bình của chúng là O(n
2
). Ba giải thuật còn lại thường được coi là giải
thuật cao cấp, độ phức tạp tính toán trung bình của chúng là n.lnn.
Sắp xếp theo cơ số
Sắp xếp theo cơ số (radix sort) dựa trên tính chất "số" của các khóa. Trong giải thuật sắp xếp theo cơ số,
ta không chỉ so sánh giá trị của các khóa, mà so sánh các thành phần của khóa. Giả sử các khóa là các số biểu
diễn theo hệ ghi số cơ số M. Khi đó sắp xếp theo cơ số sẽ so sánh từng ký số của nó.
Chúng ta mô tả cách sắp này khi cơ số M=10. Giả sử phải sắp các hồ sơ đánh số bởi 3 chữ số thập phân.
Đầu tiên ta chia các hồ sơ vào các đống có cùng chữ số hàng trăm (đồng thới xếp các đống theo thứ tự của chữ
số hàng trăm), trong mỗi đống con lại phân chia theo chữ số hàng chục, cuối cùng trong mỗi đống có cùng chữ
số hàng trăm và hàng chục, sắp xếp theo thứ tự của chữ số hàng đơn vị.
Trong máy tính, đương nhiên việc sắp xếp theo cơ số nhị phân (cơ số 2) hoặc cơ số là lũy thừa của 2 là
thuận lợi nhất. Trong trường hợp cơ số 2, việc phân hoạch tương tự như phân hoạch trong Quick Sort, chỉ khác
ở chỗ cách chọn phần tử chốt.