PHÂN TÍCH VÀ THIẾT KẾ
THUẬT TOÁN
PhạmThếBảo
ptbao@math.hcmuns.edu.vn
http://www.math.hcmuns.edu.vn/~ ptbao/AlgorithmAnalysis/
Nội dung
•Tổng quan vềthuậttoánvàđộ phứctạpcủathuậttoán
•Đánh giá thuậttoánbằng:
–Công cụtoán họcsơcấp
–Thựcnghiệm
–Hàm sinh
–Hoán vị
•Đệ quy và phương pháp đánh giá
•Đánh giá mộtsốthuật toán thông dụng
•Các phương pháp giảiquyết bài toán trên máy tính:
–Tr ựctiếp
–Gián tiếp
•Kỹthuậtthiếtkếthuật toán:
–Chia để trị
–Greedy
–Quy hoạch động
–Tìm kiếmcụcbộ(địaphương)
Phạm Thế Bảo
Hình thứckiểmtra
•Thựchành(4 điểm):
–Làm việc theo nhóm
–Mỗi nhóm sẽđánh giá mộtthuật toán:
•Chạy 20 loạibộdữliệu: 50*i phầntử, với i=1..20
•Mỗiloạibộdữliệuchạy 300*k lần, với k=1..10
•Mộilầnchạydữliệuđược phát sinh ngẫu nhiên
–Vẽđồthị, tính phương sai độ lệch chuNn
–Ướclượng độ phứctạp
–Viết báo cáo
•Lý thuyết(6 điểm)
Phạm Thế Bảo
Tài liệuthamkhảo
1. Cẩmnangthuật toán – cuốn 1 – Robert Sedgewich –
Tr ầnĐan Thư.
2. Lập trình = Thuật toán + CTDL, N. Wirth
3. Algorithm Complexity & Communication Problems,
J.P.Barthélemy,G.Cohen&a.Lobstein,UCLPress,
London 1996.
4. Elementary Introduction to new Generalized
Functions, Jean Francois Colombeau, 1991.
5. Algorithm and Complexity, Herbert S.Wilf, 1994.
6. Giảimột bài toán trên máy tính nhưthếnào, Hoàng
Kiếm, 2003.
7. TheArtofComputerVol.1,2,3,DonaldKnuth,
Addison-Wesley
Phạm Thế Bảo
Tổng quan vềthuật toán
1. Thuậttoánlàgì?
Tậphợphữuhạncáchướng dẫnrõràngđể giải
quyếtmột bài toán (vấnđề).
•Mởrộng (máy tính): mộtdãyhữuhạncác
bướckhông mậpmờvà có thểthựcthiđược,
quá trình hành động theo các bướcnàyphải
dừng và cho đượckếtquảnhưmong muốn.
2. Tính chấtcơbảncủathuật toán:
–Xác định = không mậpmờ+thựcthiđược
–Hữuhạn
–Đúng
Phạm Thế Bảo