
1
1
Thiết kế và đánh giá
Thiết kế và đánh giá
thuật toán
thuật toán
Cao học, khoa công nghệ thông tin
Cao học, khoa công nghệ thông tin
Đại học quốc gia Hà nội.
Đại học quốc gia Hà nội.
Phan Thị Hà Dương
Phan Thị Hà Dương
Viện Toán học.
Viện Toán học.
phan.haduong@gmail.com
phan.haduong@gmail.com

2
Chương trình
Chương trình
Chương 1
Chương 1: Giới thiệu về thuật toán
: Giới thiệu về thuật toán
Chương 2
Chương 2: Phân tích tính hiệu quả của thuật
: Phân tích tính hiệu quả của thuật
toán
toán
Chương 3
Chương 3: Phương pháp “tham lam”
: Phương pháp “tham lam”
Chương 4
Chương 4: Phương pháp “chia để trị”
: Phương pháp “chia để trị”
Chương 5
Chương 5: Phương pháp qui hoạch động
: Phương pháp qui hoạch động
Chương 6
Chương 6: Thuật toán trên đồ thị
: Thuật toán trên đồ thị
Chương 7
Chương 7: Phương pháp xác suất
: Phương pháp xác suất
Chương 8
Chương 8: Về độ phức tạp tính toán
: Về độ phức tạp tính toán

3
Ví dụ: Chương 3: Phương pháp
Ví dụ: Chương 3: Phương pháp
“tham lam”
“tham lam”
I.
I. Giới thiệu chung
Giới thiệu chung
II.
II. Thuật toán trên đồ thị
Thuật toán trên đồ thị
1)
1) Cây bao trùm nhỏ nhất
Cây bao trùm nhỏ nhất
2)
2) Đường đi ngắn nhất
Đường đi ngắn nhất
III.
III. Thuật toán sắp xếp lịch làm việc
Thuật toán sắp xếp lịch làm việc
IV.
IV. Thuật toán “heurisitic”
Thuật toán “heurisitic”
1)
1) Tô màu đồ thị
Tô màu đồ thị
2)
2) Người đưa hàng
Người đưa hàng

4
Sách tham khảo
Sách tham khảo

5
Sách tham khảo
Sách tham khảo
2.
2. Algorithmique - conception et analyse
Algorithmique - conception et analyse
G. Brassard and P.Bratley, Masson, Paris ,
G. Brassard and P.Bratley, Masson, Paris ,
1987
1987
3.
3. Data structure and algorithms
Data structure and algorithms
A. Aho, J. Hopcroft and J. Ullman, Addison
A. Aho, J. Hopcroft and J. Ullman, Addison
Wesley Publishing Company
Wesley Publishing Company
4.
4. Lý thuyết độ phức tạp tính toán.
Lý thuyết độ phức tạp tính toán.
Phan Đình Diệu.
Phan Đình Diệu.