Thiết Kế Và Phân Tích Thuật Toán

Giới thiệu

Tiểu luận "Thiết Kế Và Phân Tích Thuật Toán" tập trung vào việc xác định độ phức tạp của các thuật toán, một khía cạnh quan trọng trong khoa học máy tính. Thay vì chỉ dừng lại ở việc đưa ra thuật toán giải quyết bài toán, tiểu luận nhấn mạnh tầm quan trọng của việc lựa chọn thuật toán tối ưu dựa trên hiệu quả hoạt động.

Nội dung chính của tiểu luận bao gồm:

• Đánh giá độ phức tạp của thuật toán: Phân tích các khái niệm về độ phức tạp, bao gồm bậc O-lớn, độ phức tạp hằng số, tuyến tính, đa thức và hàm mũ.
• Ứng dụng phương pháp đệ quy: Giải quyết các bài toán trên nhiều kiểu dữ liệu khác nhau như mảng, danh sách liên kết đơn và cây nhị phân.
• Áp dụng phương pháp Quy hoạch động: Giải quyết các bài toán tối ưu, minh họa bằng các ví dụ cụ thể như bài toán cái túi nguyên, bài toán sinh viên ôn thi, bài toán người đi du lịch và bài toán xâu con cực đại.

Tiểu luận được thực hiện bởi sinh viên Cao Chí Hiển, dưới sự hướng dẫn của TS. Hoàng Quang. Đây là tài liệu tham khảo hữu ích cho những ai muốn tìm hiểu sâu hơn về thiết kế và phân tích thuật toán.

Mục lục chi tiết:

• PHẦN I: NỘI DUNG
  • I: ĐỘ PHỨC TẬP THUẬT TOÁN
    • 1. Độ phức tạp thuật toán
    • 2. Bài tập: So sánh độ phức tạp O(√N) và O(log n), Viết hàm tính aⁿ có độ phức tạp O(1)
  • II. PHƯƠNG PHÁP ĐỆ QUY
    • 1. Tìm hiểu đệ quy
    • 2. Bài tập Đệ quy trên kiểu dữ liệu mảng: Xóa phần tử, Tìm Max
    • 3. Bài tập Đệ quy trên kiểu dữ liệu danh sách liên kết đơn: Xóa nút, Tìm Max
    • 4. Bài tập Đệ quy trên kiểu dữ liệu cây nhị phân: Đếm nút, Bổ sung nút lá vào cây tìm kiếm nhị phân
  • III. PHƯƠNG PHÁP QUY HOẠCH ĐỘNG
    • 1. Cơ sở lý thuyết
    • 2. Phương pháp thực hiện
    • 3. Giải bài toán bằng phương pháp Quy hoạch động (4 bước)
    • 4. Một số bài toán Giải bằng phương pháp Quy hoạch động: Bài toán cái túi nguyên, Bài toán Sinh viên ôn thi, Bài toán Người đi du lịch, Bài toán xâu trong cực đại
• TÀI LIỆU THAM KHẢO