Đề thi Phân tích và thiết kế thuật toán

Tài liệu này là một đề thi môn Phân tích và Thiết kế Thuật toán, bao gồm các câu hỏi lý thuyết và bài tập ứng dụng về các chủ đề cốt lõi trong lĩnh vực thuật toán.

Tài liệu này phù hợp cho sinh viên ngành Khoa học Máy tính, Kỹ thuật Máy tính, hoặc các ngành liên quan đang theo học môn Phân tích và Thiết kế Thuật toán, cũng như các giảng viên và nhà nghiên cứu quan tâm đến các bài tập và vấn đề điển hình trong lĩnh vực này.

Đề thi môn Phân tích và Thiết kế Thuật toán này bao gồm nhiều bài tập chuyên sâu, được thiết kế để đánh giá kiến thức và kỹ năng của sinh viên trong các lĩnh vực cốt lõi của thuật toán. Bài 1 tập trung vào phân tích độ phức tạp thời gian của thuật toán, yêu cầu sinh viên chứng minh các khẳng định về ký hiệu Big O, giải các công thức đệ quy bằng định lý Thợ (Master Theorem) hoặc phương pháp lặp, và phân tích hoạt động của các thuật toán đệ quy cụ thể. Bài 2 khám phá các thuật toán tham lam, bao gồm việc thiết kế thuật toán tham lam cho bài toán phủ đoạn thẳng, bài toán phủ điểm, bài toán lập lịch tối ưu hóa tiền thưởng, và bài toán sắp xếp file trên băng từ để tối thiểu hóa thời gian truy cập. Sinh viên cần chứng minh tính đúng đắn hoặc đưa ra phản ví dụ cho các thuật toán tham lam đã cho, đồng thời phát triển các thuật toán tối ưu. Bài 3 đi sâu vào kỹ thuật quy hoạch động, đặc biệt là bài toán nhân chuỗi ma trận, yêu cầu trình diễn chi tiết quá trình tính toán và đưa ra kết quả cuối cùng về số phép nhân tối thiểu và trình tự nhân tối ưu. Ngoài ra, một phần của Bài 3 còn liên quan đến việc sửa đổi giả mã tìm kiếm theo chiều sâu (DFS) để liệt kê các cạnh của đồ thị. Bài 4 tập trung vào lý thuyết đồ thị, bao gồm việc áp dụng thuật toán Kuhn-Munkres để giải bài toán phân công, phân tích cận dưới và độ phức tạp thời gian của bài toán kiểm tra chu trình trong đồ thị (AcycGraph), và đánh giá các khẳng định về phát hiện chu trình bằng DFS. Cuối cùng, Bài 5 đề cập đến các chủ đề nâng cao về độ phức tạp tính toán, bao gồm việc chứng minh các bài toán như Feedback Arc Set (FAS), Colored Path (CPath), và Subgraph Isomorphism (SGISO) thuộc lớp NP, và đặc biệt là chứng minh tính NP-khó của chúng thông qua quy dẫn từ các bài toán NP-đầy đủ đã biết. Toàn bộ đề thi đòi hỏi sự hiểu biết sâu sắc về cả lý thuyết và ứng dụng của các thuật toán cơ bản và nâng cao.