Giáo Trình Thuật Toán

Các điểm chính của tài liệu:

• Đối tượng: Sinh viên (năm cuối và sau đại học), giáo viên (tài liệu tham khảo giảng dạy), chuyên gia (cẩm nang thuật toán).
• Nội dung:
  • Trình bày nhiều thuật toán và kỹ thuật thiết kế, phân tích chúng một cách chi tiết nhưng dễ tiếp thu.
  • Sử dụng “mã giả” (pseudocode) tương tự C, Pascal, Algol để mô tả thuật toán.
  • Hơn 260 hình minh họa, hơn 900 bài tập và 120 bài toán điển cứu.
  • Đi sâu vào phân tích thời gian thực hiện (running time) của thuật toán, bao gồm phân tích trường hợp tốt nhất, xấu nhất và trung bình.
  • Giới thiệu các ký hiệu tiệm cận (asymptotic notation) như \\Theta để mô tả tốc độ tăng trưởng của thời gian thực hiện.
  • Đề cập đến các phương pháp thiết kế thuật toán như phương pháp gia số (incremental) và “chia để trị” (divide-and-conquer).
  • Minh họa chi tiết các thuật toán sắp xếp như sắp xếp chèn (insertion sort) và sắp xếp trộn (merge sort) để so sánh hiệu năng.
• Cấu trúc: Sách được chia thành nhiều chương và phần, mỗi chương tương đối độc lập, cho phép người đọc lựa chọn các chủ đề quan tâm.
  • Lời nói đầu và Lời tựa: Giải thích mục đích, đối tượng và cách tiếp cận của giáo trình.
  • Chương 1: Giới thiệu: Làm quen với các khái niệm cơ bản về thuật toán, phân tích thuật toán (thời gian thực hiện, kích cỡ đầu vào, phép toán nguyên tố), thiết kế thuật toán (chia để trị).
  • Phần I: Căn bản về toán học: Cung cấp các công cụ toán học cần thiết để phân tích thuật toán, bao gồm:
    • Chương 2: Sự Tăng trưởng của Các hàm: Định nghĩa chính xác các hệ ký hiệu tiệm cận (\\Theta, O, \\Omega), quy ước ký hiệu.
    • Chương 3: Phép lấy tổng: Các phương pháp đánh giá và định cận các phép tổng.
    • Chương 4: Các phép truy toán: Các phương pháp giải quyết phép truy toán (bao gồm phương pháp chủ).
    • Chương 5: Các tập hợp: Các định nghĩa cơ bản về tập hợp, quan hệ, hàm, đồ thị và cây.
    • Chương 6: Đếm và xác xuất: Các nguyên lý đếm và xác suất căn bản.
  • Các phần tiếp theo (Mục lục): Bao gồm Sắp xếp và thống kê thứ tự, Các cấu trúc dữ liệu, Các kỹ thuật phân tích và thiết kế cao cấp, Các cấu trúc dữ liệu cao cấp, Thuật toán đồ thị, Các chủ đề chọn lọc.
• Điều kiện tiên quyết: Người đọc nên có kinh nghiệm lập trình (đặc biệt là thủ tục đệ quy, mảng, danh sách nối kết) và khả năng chứng minh bằng phép quy nạp toán học.
• Điểm nổi bật: Sách nhấn mạnh rằng việc lựa chọn thuật toán hiệu quả quan trọng không kém việc chọn phần cứng nhanh, qua ví dụ so sánh siêu máy tính chạy sắp xếp chèn và máy tính cá nhân chạy sắp xếp trộn.