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 sau giá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ám hậ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ủa bài toán. Các bà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 thao tá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 ...
LINK DOWNLOAD
Giáo trình “ Thiết kế và đánh giá thuật toán “ có nội dung tiếp sau giá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ám hậ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ủa bài toán. Các bà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 thao tá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 ...
LINK DOWNLOAD
Không có nhận xét nào: