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

Mời các bạn tham khảo Đề thi Phân tích và thiết kế thuật toán sau đây để nắm được cấu trúc đề thi cũng như cách thức làm đề thi, từ đó giúp bạn nắm vững kiến thức môn Phân tích và thiết kế thuật toán một cách tốt hơn. | Đề thi môn Phân tích và thiết kế thuật toán Thời gian 90 phút - Không sử dụng tài liệu - Nộp lại đề Bài 1. Với mỗi khẳng định sau đây cho biết khẳng định nào là đúng khẳng định nào là sai và giải thích câu trả lời la H3 Ể Gkn2 log rì . lb log n G ơ n với mọi hằng số a dưong. lc na e O 2n với mọi hằng số a dưong. Bài 2. Cho tập I gồm n đoạn thẳng trên trục số thực íZi ỏi 2 Ố2 bn . cần tìm tập p có lực lượng nhỏ nhẩt gồm các điểm trên trục số thực sao cho mỗi đoạn ai ỗ đều chứa ít nhất một điểm nào đó thuộc p i 1 2 . n. Xét thuật toán tham lam sau đây để giải bài toán đặt ra GREEDY 7 1 m min ứ 72 . an - 1 2 p 0 3 Sắp xếp các đoạn thẳng trong I theo thứ tự không giảm của mút phải bị Không giảm tổng quát giả thiết là bi bi . bn 4 for i 1 to n lần lượt xét các đoạn theo thứ tự được sắp xếp 5 if Oi m 6 P Pv biỴ 7 m bi 8 9 return P p là tập điểm cần tìm 2a Hãy chỉ ra rằng thuật toán trên có thể cài đặt với thời gian tính O n log rì . 2b Thuật toán trên có cho lời đúng không Giải thích câu trả lời. Bài 3. Trình diễn thuật toán quy hoạch động tính khoảng cách sửa đổi xâu x ALGORITHM thành xâu y ALTRUISTIC . Ket quả cuối cùng cần đưa ra khoảng cách tìm được và cách biến đổi xâu X thành xâu Y. Bài 4. Trình diễn thuật toán Kuhn-Munkres giải bài toán phân công với ma trận hiệu quả sau đây 4 5 5 2 6 5 3 7 7 6 3 8 5 Bài 5. Cho đồ thị có hướng G V E tập con E E được gọi là tập cung ngược Feedback Arc Set nếu như sau khi loại bỏ các cung trong E khỏi đồ thị G ta thu được đồ thị không có chu trình. Bài toán tập cung ngược FAS được phát biểu như sau Cho đồ thị có hướng G V E và số nguyên không âm k hỏi có thể tìm được tập cung ngược với lực lượng không vượt quá k hay không 5a Hãy chỉ ra bài toán FAS là thuộc lớp NP 5b Chứng minh rằng bài toán FAS thuộc lớp NP-khó. Gợi ý Qui dẫn bài toán phủ đỉnh Vertex Cover về FAS Đề thi môn Thiết kế và Phân tích thuật toán Thòi gian 90 phút - Không sử dụng tài liệu - Nộp lại đề Bài 1. Giả sử T ri được xác định bởi công thức đệ qui sau đây T ri 1 T

• Kỹ thuật lập trình
• Phân tích thiết kế thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Thuật toán tham lam
• Trình diễn thuật toán
• Phân tích thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Bài giảng Phân tích và thiết kế thuật toán
• Phân tích Top down
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Phân tích đệ quy
• Thuật toán đệ quy
• Phân tích toán học
• Bài toán sắp xếp
• Sắp xếp chèn
• Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thiết kế giải thuật
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Đánh giá độ phức tạp thuật toán
• Đánh giá thuật toán dựa trên thực nghiệm
• Phân tích câu lệnh
• Qui tắc phân tích câu lệnh trong thuật toán
• Tìm kiếm tuần tự
• Xem xét phân bố khóa
• Tìm kiếm nhị phân
• Ngôn ngữ lập trình
• Tự học lập trình
• Lập trình máy tính
• Phân tích và thiết kế thuật toán
• Kỹ thuật Greedy
• Bài toán tối ưu tổ hợp
• Bài toán trả tiền của ATM
• Đánh giá bằng công cụ toán học
• Công cụ toán học sơ cấp
• Đánh giá bằng thực nghiệm
• Quy hoạch động
• Bài toán quy hoạch động
• Bài toán con
• Chia để trị
• Bài tập Chia để trị
• Phương pháp giải bài toán trên máy tính
• Phương pháp trực tiếp
• Phương pháp gián tiếp