1
1
Thiết kế và đánh giá
Thiết kế và đánh giá
thut toán
thut toán
Cao hc, khoa công ngh thông tin
Cao hc, khoa công ngh thông tin
Đại hc quc gia Hà ni.
Đại hc quc gia Hà ni.
Phan Th Hà Dương
Phan Th Hà Dương
Vin Toán hc.
Vin Toán hc.
phan.haduong@gmail.com
phan.haduong@gmail.com
2
Chương trình
Chương trình
Chương 1
Chương 1: Gii thiu v thut toán
: Gii thiu v thut toán
Chương 2
Chương 2: Phân tích tính hiu qu ca thut
: Phân tích tính hiu qu ca thut
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 hoch đng
: Phương pháp qui hoch đng
Chương 6
Chương 6: Thut toán trên đồ th
: Thut toán trên đồ th
Chương 7
Chương 7: Phương pháp xác sut
: Phương pháp xác sut
Chương 8
Chương 8: V độ phc tp tính toán
: V độ phc tp 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. Gii thiu chung
Gii thiu chung
II.
II. Thut toán trên đồ th
Thut toán trên đồ th
1)
1) Cây bao trùm nh nht
Cây bao trùm nh nht
2)
2) Đường đi ngn nht
Đường đi ngn nht
III.
III. Thut toán sp xếp lch làm vic
Thut toán sp xếp lch làm vic
IV.
IV. Thut toán “heurisitic”
Thut 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 kho
Sách tham kho
5
Sách tham kho
Sách tham kho
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 độ phc tp tính toán.
Lý thuyết độ phc tp tính toán.
Phan Đình Diu.
Phan Đình Diu.