Cấu trúc dữ liệu và thuật toán

Tập 2 này gồm 4 chương chính:

• Chương 1: Sắp xếp ngoài
  • Giới thiệu khái niệm sắp xếp ngoài, khó hơn sắp xếp trong do dữ liệu nằm trên bộ nhớ ngoài (băng từ, đĩa cứng, đĩa quang) với dung lượng lớn và tốc độ truy xuất chậm.
  • Trình bày Phương pháp xếp trộn các run (Merge Sort Run) với thuật toán chi tiết, ví dụ minh họa, đánh giá độ phức tạp (O(N log₂N) cho copy và O(N/2 log₂N) cho so sánh), và cài đặt bằng C.
  • Trình bày Thuật toán trộn tự nhiên nhằm khắc phục nhược điểm của thuật toán trộn run (tốn thời gian phân phối ban đầu). Thuật toán này trộn các run có độ dài lớn nhất với nhau. Bao gồm các bước và yêu cầu cài đặt chi tiết với các cách nhập liệu (bằng tay, tự động) và hiển thị kết quả trung gian.
  • Giới thiệu Thuật toán sắp xếp trộn đa đường cân bằng (Balanced MultiWay Merging – BMM). Thuật toán này chỉ thực hiện 1 giai đoạn trộn, tiết kiệm 1/2 thời gian sao chép nhưng tốn gấp đôi không gian nhớ ngoài (cần 2k tệp). Bao gồm mô tả ngắn gọn, ví dụ minh họa và mã giả chi tiết các bước.
  • Giới thiệu Thuật toán trộn đa pha (Polyphase Merge Sort – PMS). Khắc phục nhược điểm của BMM bằng cách chỉ cần k+1 tệp và thay đổi vai trò của các file trong cùng một lượt xử lý. Mô tả thuật toán bằng ngôn ngữ tự nhiên và ví dụ cách cải tiến PMS nhờ dùng hệ thức Fibonacci.
• Chương 2: Phép băm và bảng băm
  • Giới thiệu khái niệm phép băm (hàm băm) và bảng băm, mục đích là giảm thời gian thực thi các thao tác xử lý dữ liệu.
  • Trình bày các chỉ tiêu về một hàm băm tốt (tính toán nhanh, phân bố đều, hạn chế đụng độ).
  • Giải thích khái niệm đụng độ trong bảng băm.
  • Giới thiệu một số loại hàm băm điển hình:
    • Hàm băm hoàn chỉnh (Perfect Hashing Function) và hàm băm hoàn chỉnh tối thiểu (Minimal Perfect Hashing Function).
    • Hàm băm phân bố đều dữ liệu (Hashing Uniformly Distributed Data).
    • Hàm băm phổ quát (Universal Hashing Function) và cách thiết kế.
  • Cung cấp code C mô tả một số thao tác cơ bản trên bảng băm nói chung (định nghĩa, khởi tạo, thiết lập hàm băm, kiểm tra rỗng, thêm, tìm, hủy, duyệt, xóa toàn bộ).
  • Trình bày các phương pháp giải quyết đụng độ trong bảng băm:
    • Kết nối phân nhóm (Separate Chaining): Gồm kết nối trực tiếp (Direct Chaining) và kết nối hợp nhất (Coalesced Chaining).
      • Tạo bảng băm bằng phương pháp kết nối trực tiếp: Tổ chức dữ liệu bằng danh sách liên kết đơn, cài đặt chi tiết bằng C và phân tích tốc độ xử lý (độ phức tạp O(n/M) hoặc O(1) tùy M).
      • Tạo bảng băm bằng phương pháp kết nối hợp nhất: Tổ chức dữ liệu bằng mảng các danh sách liên kết đơn, mô tả các thao tác cơ bản (khởi trị, kiểm tra rỗng, tìm, cập nhật vị trí trống, chèn, xem, xóa) và cài đặt chi tiết bằng C. Đánh giá hiệu quả (tối ưu khi băm đều O(1), tồi tệ nhất O(n)).
    • Địa chỉ mở (Open Addressing): Gồm dò tuyến tính (Linear Probing), dò bậc hai (Quadratic Probing) và băm kép (Double Hashing).
      • Tạo bảng băm dùng phương pháp dò tuyến tính (Linear Probing Method – LPM): Tổ chức dữ liệu bằng danh sách kề, mô tả các thao tác cơ bản (chèn, tìm), ví dụ minh họa quá trình kiến tạo. Code C mô tả khởi trị, khai báo cấu trúc node, chèn khóa mới, xóa, tìm, xem toàn bộ bảng băm, và thiết kế bảng chọn (menu). Đánh giá hiệu quả của LPM dựa trên hệ số nạp λ.
      • Tạo bảng băm dùng phương pháp dò bậc hai (Quadratic Probing Method – QPM): Tổ chức dữ liệu, các thao tác cơ bản (khởi tạo, chèn, tìm) và ví dụ minh họa phép chèn thành công.