Một số vấn đề về thuật toán

Dưới đây là tóm tắt các nội dung chính:

• Giới thiệu chung về thuật toán: Sách nhấn mạnh tầm quan trọng của thuật toán trong tin học, việc cần nắm vững khái niệm thuật toán và cách phân tích, thiết kế chúng một cách thấu đáo.
• Các cách mô tả thuật toán: Tài liệu trình bày ba cách cơ bản để mô tả thuật toán: bằng lời, bằng sơ đồ khối, và bằng giả mã (cách tối ưu nhất cho việc nghiên cứu và thiết kế thuật toán, được sử dụng trong tài liệu, gần với ngôn ngữ lập trình Pascal).
• Các ví dụ thuật toán:
  • Thuật toán Euclid: Để tìm ước chung lớn nhất (gcd) của hai số nguyên dương, bao gồm cả phiên bản tinh chế sử dụng phép toán mod.
  • Thuật toán lấy căn bậc hai của người Babylon: Phương pháp tính căn bậc hai của một số dương với độ chính xác cho trước dựa trên trung bình cộng.
  • Tính giá trị các đa thức: Giới thiệu thuật toán PolyEval và thuật toán tối ưu hơn HornerEval dựa trên phương pháp của W. G. Horner.
• Thuật toán hồi quy: Giải thích phép hồi quy là một công cụ mạnh mẽ trong phân tích và thiết kế thuật toán, với ví dụ về tính giai thừa (Factorial) và ước chung lớn nhất (Recgcd) theo cách hồi quy.
• Bài toán tháp Hà Nội: Trình bày bài toán kinh điển này và cách giải bằng thuật toán hồi quy, đồng thời tính toán số lần chuyển đĩa.
• Cấu trúc dữ liệu cơ sở:
  • Loại dữ liệu trừu tượng tuyến tính: So sánh mảng và danh sách liên kết, nêu bật ưu nhược điểm của mỗi loại.
  • Loại dữ liệu ngăn xếp trừu tượng (Stack): Định nghĩa ngăn xếp (LIFO), các thao tác đẩy vào (push) và lấy ra (pop).
  • Loại dữ liệu hàng đợi trừu tượng (Queue): Định nghĩa hàng đợi (FIFO).
  • Loại dữ liệu cây nhị phân trừu tượng: Định nghĩa cây nhị phân, các thuật ngữ liên quan (nút gốc, nút lá, cây con, độ sâu/độ cao) và cách thể hiện bằng con trỏ.
• Phương pháp quy nạp toán học: Trình bày nguyên lí quy nạp toán học dạng 1 và dạng 2, cùng với các ví dụ chứng minh tính đúng đắn của các mệnh đề và đánh giá hàm tính toán.
• Hàm đo độ tính toán:
  • Định nghĩa và tính chất: Giới thiệu các ký hiệu Θ (Theta lớn), O (O lớn), Ω (Omega lớn) để đo độ phức tạp của thuật toán, cùng với các tính chất và mối quan hệ giữa chúng.
  • Thứ bậc trong tập hàm số: Sắp xếp các hàm thường dùng trong phân tích thuật toán theo thứ bậc tăng dần độ phức tạp (ví dụ: O(1) ⊂ O(log n) ⊂ … ⊂ O(n!)).
  • Đánh giá một số tổng các số hạng: Đánh giá bậc của tổng log(n!) và tổng điều hòa H(n).
• Phương trình hồi quy: Trình bày cách giải phương trình truy hồi bậc nhất có dạng xn = axn-1 + P(n), bao gồm tìm nghiệm phương trình thuần nhất và thử nghiệm dạng đa thức.

Cuốn sách cung cấp một nền tảng vững chắc về thuật toán, các công cụ toán học để phân tích và thiết kế chúng, cùng với những cấu trúc dữ liệu cơ bản.