Giáo trình thiết kế và đánh giá thuật toán
Giáo trình “ Thiết kế và đánh giá thuật toán “ có nội dung tiếp saugiáo trình “Cấu trúc dữ liệu và thuật toán 1” và “ Toán cao cấp A4”, trình bày trong 3 tín chỉ lý thuyết và 1 tín chỉ thực hành cho các sinh viên ngành Toán – Tin học và Công nghệ thông tin. Trọng tâm chính của giáo trình : - Trình bày một số phương pháp thiết kế thuật toán thông dụng. - Tìm hiểu cơ sở phân tích độ phức tạp của thuật toán. Nội dung giáo trình gồm 6 chương : CHƯƠNG 1: GIỚI THIỆU THIẾT KẾ VÀ ĐÁNH GIÁ THUẬT TOÁN. Chương này giới thiệu khái niệm trực quan của thuật toán, ngôn ngữ mô tả thuật toán, phân tích thuật toán, cải tiến thuật toán. CHƯƠNG 2: PHƯƠNG PHÁP CHIA ĐỂ TRỊ Chương này trình bày kỹ thuật thiết kế chia để trị, môhình thủ tục thường sử dụng và các bài toán minh họa như : bài toán MinMax, thuật toán Strassen về nhân ma trận, thuật toán trộn trực tiếp, . . . CHƯƠNG 3: PHƯƠNG PHÁP QUAY LUI Giới thiệu mô hình đệ quy quay lui và các bài toán minh họa như : bài toán “ ngựa đi tuần”, bài toán “ támhậu “, các bài toán tổ hợp, các thuật toán tìm kiếm trên đồ thị DFS, BFS. . CHƯƠNG 4: PHƯƠNG PHÁP NHÁNH CẬN Chương này mô tả kỹ thuật đánh giá nhánh cận trong quá trình quay lui để tìm lời giải tối ưu củabài toán. Cácbài toán dùng để minh họa như bài toán “ Người du lịch “, bài toán “ chiếc túi xách “. CHƯƠNG 5: PHƯƠNG PHÁP THAM LAM Giới thiệu phương pháp tìm kiếm nhanh lời giải chấp nhận được (và có thể là tối ưu) của bài toán tối ưu. Các bài toán minh họa như : bài toán “ Người du lịch”, thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị, bài toán “ chiếc túi xách “, . . CHƯƠNG 6: PHƯƠNG PHÁP QUY HOẠCH ĐỘNG Chương này mô tả ý tưởng, các thaotác chính sử dụng trong thuật toán quy hoạch động. Các bài toán minh họa như thuật toán Floyd tìm đường đi ngắn nhất giữa các cặp đỉnh của một đơn đồ thị, bài toán nhân tổ hợp các ma trận, cây nhị phân tìm kiếm tối ưu . Trần Tuấn Minh Khoa Toán-Tin Thiết kế và đánh giá thuật toán - 7 - Vì trình độ người biên soạn có hạn nên tập giáo trình không tránh khỏi nhiều khiếm khuyết, chúng tôi rất mong sự góp ý của các bạn đồng nghiệp và sinh viên. Cuối cùng, chúng tôi cảm ơn sự động viên, giúp đỡ nhiệt thành của các bạn đồng nghiệp trong khoa Toán-Tin họcđể tập giáo trình này được hoàn thành.
