TAILIEUCHUNG - Bài giảng Phân tích thiết kế giải thuật: Introduction - GV. Hà Đại Dương

Bài giảng do GV. Hà Đại Dương biên soạn. Nội dung của bài giảng trình bày khái niệm thuật toán, cách biểu diễn thuật toán, tính đúng đắn và hiệu quả của thuật toán; đánh giá độ phức tạp thuật toán: độ tăng của hàm, độ phức tạp của thuật toán, đánh giá bằng thực nghiệm. . | 2/2/2017 Design and Analysis of Algorithms Lecture 1 Introduction Lecturer: Ha Dai Duong duonghd@ 2/2/2017 1 Nội dung 1. Giới thiệu 2. Thuật toán Khái niệm thuật toán Biểu diễn thuật toán Tính đúng đắn và hiệu quả của TT 3. Đánh giá độ phức tạp TT Độ tăng của hàm Độ phức tạp của TT Đánh giá bằng thực nghiệm 2/2/2017 2 Nội dung 1. Giới thiệu 2. Thuật toán 3. Độ phức tạp thuật toán 2/2/2017 3 1 2/2/2017 Mục đích • Cung cấp kiến thức về việc đánh giá thuật toán – Lý thuyết – Thực nghiệm • Thiết kế thuật giải – Chia để trị – Tham lam – Quy hoạch động – 2/2/2017 4 Nội dung môn học • Tổng quan về thuật toán và độ phức tạp của thuật toán • Đánh giá thuật toán • Thiết kế thuật toán • Phương pháp thiết kế thuật toán – Trực tiếp – Chia để trị – Tham lam 2/2/2017 5 Hình thức kiểm tra • 10% Chuyên cần • 20% Thường xuyên (bài tập, bài kiểm tra) • 70% Thi cuối kỳ (vấn đáp) – Mô tả bài toán – Thiết kế thuật toán – Đánh giá – Cài đặt – Báo cáo 2/2/2017 6 2 2/2/2017 Tài liệu tham khảo • Slide bài giảng. • Bài giảng Thiết kế và Đánh giá Thuật toán, Trần Xuân Sinh, NXB, ĐHQG, 2010. • Cẩm nang thuật toán, Robert Sedgewich - Trần Đan Thư dịch (tái bản lần 2), NXB KHKT, 2006. • Cấu trúc dữ liệu và giải thuật, Đỗ Xuân Lôi, NXB ĐH Quốc Gia, 2006. • Giải một bài toán trên máy tính như thế nào (3 tập), Hoàng Kiếm, NXB Giáo dục, 2005 2/2/2017 7 Tài liệu tham khảo • Giải thuật và lập trình (bài giảng chuyên đề), Lê Minh Hoàng, ĐHSP, 2002. • Computer Algorithms Introduction to Design and Analysis, Addison-Wesley, 1988. • Algorithms and Complexity, Herbert S. Wilf, University of Pennsylvania, Philadelphia 1999. • Algorithm Design, Jon Kleinberg, Eva Tardos Pearson, 2006 2/2/2017 8 Nội dung 1. Giới thiệu 2. Thuật toán 3. Độ phức tạp thuật toán 2/2/2017 9 3 2/2/2017 Khái niệm • Một thuật toán là một bản liệt kê các chỉ dẫn, các quy tắc cần thực hiện theo từng bước xác định nhằm giải quyết một bài toán đã cho trong một khoảng thời gian

• Kỹ thuật lập trình
• Phân tích thiết kế giải thuật
• Biểu diễn thuật toán
• Tính đúng đắn của thuật toán
• Tính hiệu quả của thuật toán
• Đánh giá độ phức tạp thuật toán
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ 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ân tích thuật toán
• 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
• Phân tích thiết kế 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
• 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
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• 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
• 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
• 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
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích giải thuật
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Quy hoạch động
• Biểu diễn thuật giải
• Phân tích thiết kế thuật toán
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Chia để trị
• Giải thuật quay lui
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• 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
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân