Thuật toán và độ phức tạp

Đây là module cung cấp cho người học Modul này giới thiệu những kỹ thuật và công cụ cơ bản cho việc phân tích và thiết kế các thuật thuât. Modul trình bày cách thiết kế và phân tích những bài toán sang mô hình toán học để rồi đi tới các lời giải theo thuật ngữ lập trình.

Modul cũng trình bày những chiến lược thiết kế thuật toán quan trọng như: tham lam, chia-để-trị, quy hoạch động, nhánh cận, quay lui, và những thuật toán dựa trên kinh nghiệm. Trong mỗi chiến lược thiết kế, bên cạnh việc đào sâu phân tích, chúng còn được thảo luận về độ phức tạp thông qua các bài toán cụ thể.

Ngoài việc học phân tích và thiết kế thuật toán, người học còn được cung cấp những kiến thức, kỹ năng cần thiết giải các bài toán hay gặp trong tin học để trở thành người lập trình viên chuyên nghiệp.

Module này sử dụng ngôn ngữ C# để minh họa, cài đặt. Tuy nhiên người học dễ dàng cài đặt được bằng các ngôn ngữ lập trình khác như: VB.NET, C/C++, Pascal...

Sau khi hoàn thành module này, người học có khả năng:

• Trình bày được các khái niệm và kỹ thuật để thiết kế một thuật toán hiệu quả.
• Thiết lập được các phương trình đệ qui để mô tả độ phức tạp về thời gian và không gian của một thuật toán đệ qui.
• Xác định được độ phức tạp về thời gian và không gian của thuật toán xác định, trong các trường hợp: tốt nhất, trung bình cũng như xấu nhất.
• Nhận ra các bài toán mà ở đó dùng phương pháp quy hoạch động là một giải pháp hiệu quả.
• Áp dụng kỹ thuật chia-để-trị vào việc thiết kế bài toán cũng như phân tích độ phức tạp tính toán.
• Cài đặt các thuật toán tham lam (gready), chia để trị (divide-and-conquer), quay lui (backtracking), nhánh-cận (branch-and-bound), A* (heuristic) và quy hoạch động (dynamic programming) cho một số bài toán.
• Chuyển đổi hiệu quả được từ sơ đồ thuật toán sang chương trình.
• Áp dụng những kỹ thuật, chiến lược thiết kế thuật toán cho bài toán: Lập kế hoạch cho một quy trình sản xuất, tìm đường đi trên bản đồ phức tạp, viết chương trình Game,...
• Áp dụng những kỹ thuật thiết kế thuật toán nhằm tăng hiệu năng cho những dự án cụ thể trong khi phát triển phần mềm.
• Làm việc nhóm trong quá trình xây dựng bài tập lớn để đạt được các mục tiêu trên.

Để học tốt môn học này mỗi người học phải tự xây dựng cho mình một phương pháp học thích hợp. Nhưng phương pháp chung để học môn học này là người học phải hiểu thật kỹ các phần lý thuyết cơ sở, rèn luyện sự tư duy logic một vấn đề và vận dụng một cách linh hoạt vào các trường hợp cụ thể, cài đặt các thuật toán….