Giới thiệu về thuật toán
Tôi sẽ trình bày lại nội dung chi tiết hơn, đảm bảo không sót ý nào từ tài liệu bạn cung cấp. Nội dung sẽ được tổ chức chặt chẽ, bám sát tài liệu gốc. Dưới đây là toàn văn trình bày:
Mục lục
Giới thiệu về Thuật Toán
1. Thuật toán là gì?
Thuật toán là một chuỗi các bước rõ ràng, chính xác, không mơ hồ, có thể thực hiện một cách cơ học để đạt được một mục tiêu cụ thể. Ví dụ, thuật toán để hát bài “99 Bottles of Beer on the Wall” được mô tả như sau:
Thuật toán BOTTLES_OF_BEER(n):
- Lặp từ i=ni = n xuống 1:
- Hát: “ii chai bia trên tường, ii chai bia.”
- Hát: “Lấy một chai xuống, chuyền nó quanh, còn lại i−1i – 1 chai bia trên tường.”
- Khi không còn chai nào:
- Hát: “Không còn chai bia trên tường, không còn chai bia.”
- Hát: “Đi đến cửa hàng, mua thêm, nn chai bia trên tường.”
Thuật ngữ “algorithm” xuất phát từ tên của nhà toán học Hồi giáo thế kỷ thứ 9, Muhammad ibn Musa al-Khwarizmi. Ông đã giới thiệu các phương pháp tính toán sử dụng hệ thống số thập phân và vòng tròn “0” để biểu thị số không. Các phương pháp này, thông qua Fibonacci và các nhà toán học châu Âu khác, trở thành nền tảng của hệ thống số học hiện đại.
2. Lịch sử và các phương pháp tính toán
Phép nhân dạng lưới (Lattice Multiplication)
Đây là một thuật toán quen thuộc với học sinh Mỹ, được Fibonacci phổ biến trong tác phẩm Liber Abaci. Thuật toán này sắp xếp các số cần nhân vào một lưới, tính các tích con rồi cộng dồn các giá trị theo đường chéo. Công thức tổng quát: x⋅y=∑i=0m−1∑j=0n−1X[i]⋅Y[j]⋅10i+jx \cdot y = \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} X[i] \cdot Y[j] \cdot 10^{i+j}
- Độ phức tạp thời gian: O(mn)O(mn).
Phép nhân của nông dân Nga (Russian Peasant Multiplication)
Phương pháp này dựa trên phép chia đôi và nhân đôi:
- Nếu xx là số lẻ, cộng yy vào kết quả.
- Chia xx cho 2 (lấy phần nguyên), nhân đôi yy.
- Lặp cho đến khi x=0x = 0.
- Độ phức tạp thời gian: O(logx⋅logy)O(\log x \cdot \log y).
Compass and Straightedge Multiplication
Trong hình học Hy Lạp, các con số được biểu diễn dưới dạng độ dài đoạn thẳng. Euclid đã phát triển thuật toán sử dụng thước kẻ và compa để nhân hoặc chia hai độ dài. Thuật toán này vận hành dựa trên tính chất của các tam giác đồng dạng.
3. Mô tả thuật toán
Một thuật toán cần được trình bày qua 4 yếu tố:
- Cái gì (What): Mô tả bài toán cần giải quyết.
- Cách làm (How): Mô tả chi tiết các bước của thuật toán.
- Tại sao (Why): Chứng minh thuật toán đúng.
- Tốc độ (How Fast): Phân tích thời gian thực thi.
Ví dụ, thuật toán phân bổ ghế của Huntington-Hill cho Quốc hội Mỹ:
- Mỗi bang được 1 ghế.
- Phân bổ các ghế còn lại dựa trên ưu tiên P/r(r+1)P / \sqrt{r(r + 1)}, trong đó PP là dân số và rr là số ghế hiện tại.
Phân tích tính đúng đắn và thời gian thực thi
- Tính đúng đắn: Sử dụng quy nạp để chứng minh thuật toán luôn đưa ra kết quả chính xác.
- Thời gian thực thi: Phân tích qua số lần thực hiện thao tác cơ bản. Ví dụ:
- BOTTLES_OF_BEER(n) thực hiện 3n+33n + 3 lần nhắc từ “bia”.
- Thuật toán nhân dạng lưới: O(mn)O(mn).
4. Các ví dụ khác về thuật toán
Phân bổ ghế Quốc hội (Congressional Apportionment)
Thuật toán Huntington-Hill:
- Mỗi bang được phân 1 ghế.
- Các ghế còn lại được phân dựa trên ưu tiên P/r(r+1)P / \sqrt{r(r+1)}.
Ví dụ về “thuật toán xấu”
Một ví dụ hài hước về thuật toán không thể thực thi:
- Lấy 1 triệu đô la.
- Nếu bị thu thuế, nói: “Tôi quên.”
Mặc dù không khả thi, ví dụ này minh họa khái niệm “giảm thiểu bài toán” – chuyển bài toán phức tạp thành bài toán đơn giản hơn.
5. Phân tích độ phức tạp
Độ phức tạp được phân tích qua số lần thực hiện thao tác cơ bản. Ví dụ:
- Bài hát “99 Bottles of Beer on the Wall”:
- Độ phức tạp: O(n)O(n).
- Bài hát “The Twelve Days of Christmas”:
- Độ phức tạp: O(n2)O(n^2) (tổng số lần nhắc quà là n(n+1)/2n(n+1)/2).
Một số bài toán yêu cầu độ phức tạp cao hơn, như thuật toán nhân đôi trong nhạc hoặc phép nhân trong các hệ thống biểu diễn khác nhau.
6. Bài tập minh họa
- Mô tả thuật toán xác định người thắng cờ vua từ trạng thái ban đầu.
- Tìm hoặc viết một bài hát có độ phức tạp O(n3)O(n^3).
- Phân tích thời gian hát dựa trên số âm tiết thay vì số từ.
Nguồn bài viết:
https://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf
1 Comments