TRƯӠNG ĐҤI HӐC MӒ ĐӎA CHҨT
KHOA CÔNG NGHӊ THÔNG TIN
Đӄ TÀI:
CҨU TRÚC DӲ LIӊU VÀ GIҦI THUҰT
GIÁO VIÊN HƯӞNG DҮN:
SINH VIÊN THӴC HIӊN:
THҤC SӺ: NGUYӈN ANH TUҨN
NGUYӈN VĂN LҰP
NӜI DUNG BÁO CÁO
y ĐҺT VҨN Đӄ
y CÁC CHIӂN LƯӦC THIӂT Kӂ THUҰT TOÁN
y SҲP XӂP
y CÁC THUҰT TOÁN ĐӖ THӎ
PHƯƠNG PHÁP GIҦI QUYӂT BÀI TOÁN
ĐҺT VҨN Đӄ
y Thuұt toán: đưӧc hiӇu là sӵ đһc tҧ chính xác mӝt dãy các
bưӟc có thӇ thӵc hiӋn đưӧc mӝt cách máy móc.
y BiӇu diӉn thuұt toán: thuұt toán cҫn đưӧc mô tҧ dưӟi dҥng
mã(code). Nhưng đӇ cho thuұt toán ngҳn gӑn nhưng vүn
đҧm bҧo tính chính xác -> biӉu diӉn giҧi mã.
CÁC CHIӂN LƯӦC THIӂT Kӂ
THUҰT TOÁN
y CHIA Đӆ TRӎ
y Đӊ QUY
y QUY HOҤCH ĐӜNG
y QUAY LUI
CHIA Đӆ TRӎ
y Ý tưӣng: chia ra làm nhiӅu phҫn nhӓ hơn
y Giҧi quyӃt tӯng phҫn đӝc lұp
y Xây dӵng kӃt quҧ cӫa bài toán ban đҫu
Đӊ QUY

đҫu đӇ nhұn đưӧc đoҥn
A[0, ,i] đã sҳp xӃp.
SҲP XӂP NӘI BӐT
Thuұt toán:
Ví dө minh hӑa:
y Cho k chҥy tӯ 0 ,1«,n-1.
NӃu 2 thành phҫn kӅ nhau
không đúng trұt tӵ thì ta
trao đәi 2 thành phҫn. Lһp
lҥi vӟi n-1 sӕ lҫn như vұy
ta có đưӧc kӃt quҧ sҳp xӃp.
SҲP XӂP NHANH
y Mô hình minh hӑa:
SҲP XӂP SӰ DӨNG CÂY THӬ TӴ
BӜ PHҰN
Thuұt toán:
Mô hình minh hӑa:
y Cây thӭ tӵ bӝ phұn n đӍnh
trong đó gӕc cây đưӧc lưu
A[0] và 1 đӍnh lưu A[i],
đӍnh con trái A[2*i +1],
đӍnh con phҧi A[2*i+ 2].
Mҧng A thӓa mãn:
A[i]<=A[2*i+1]
A[i]<=A[2*i+2]
CÁC THUҰT TOÁN ĐӖ THӎ
y BIӈU DIӈN ĐӖ THӎ
y ĐI QUA ĐӖ THӎ THEO CHIӄU SÂU
y CÂY BAO TRÙM NGҲN NHҨT
BIӈU DIӈN ĐӖ THӎ