BỘ GIAO THÔNG VẬN TẢI<br />
TRƯỜNG ĐẠI HỌC HÀNG HẢI<br />
N H<br />
HỌC<br />
T NH<br />
H<br />
C NG NGHỆ TH NG TIN<br />
<br />
ÀI GIẢNG<br />
PHÂN T CH THIẾT Ế VÀ Đ NH GI<br />
THUẬT T N<br />
TÊN HỌC PHẦN : Phân tích thiết kế và đánh giá thuật toán<br />
MÃ HỌC PHẦN : 17208<br />
TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CH NH QU<br />
DÙNG CHO SV NGÀNH : C NG NGHỆ TH NG TIN<br />
<br />
HẢI PHÒNG - 2010<br />
<br />
Tên học phần P<br />
ộ môn phụ trách giảng dạy K a ọ M y<br />
ã học phần 17208<br />
TS<br />
60<br />
<br />
Lý<br />
45<br />
<br />
y<br />
<br />
Tự<br />
15<br />
<br />
/Xem a<br />
<br />
Điều kiện tiên quyết<br />
S<br />
ê p ả ọ x<br />
K<br />
lp<br />
C<br />
ục tiêu của<br />
-<br />
<br />
Tự ọ<br />
0<br />
<br />
B<br />
0<br />
<br />
ọ p ầ sa mớ<br />
l<br />
T<br />
<br />
học phần<br />
C<br />
p<br />
C<br />
p<br />
Rè l y<br />
ư<br />
<br />
Nội dung chủ yếu<br />
Gồm 4 p ầ :<br />
C<br />
C<br />
C<br />
lượ<br />
K<br />
<br />
Loại học phần 2<br />
hoa phụ trách CNTT<br />
Tổng số TC: 3<br />
p lớ<br />
<br />
ượ<br />
<br />
ă<br />
<br />
Đồ<br />
0<br />
ý ọ p ầ<br />
<br />
ả<br />
<br />
mô<br />
<br />
ọ<br />
<br />
y:<br />
<br />
l .<br />
lượ x y ự<br />
<br />
y<br />
<br />
a ọ .<br />
<br />
ả<br />
ả<br />
<br />
.<br />
sắp x p<br />
<br />
lượ<br />
<br />
m<br />
<br />
:<br />
lượ am lam<br />
ộp<br />
p<br />
<br />
ộ<br />
ả<br />
<br />
m<br />
lượ<br />
<br />
l .<br />
a<br />
<br />
lượ<br />
<br />
ay l<br />
<br />
BT<br />
1<br />
<br />
KT<br />
0<br />
<br />
.<br />
<br />
Nội dung chi tiết của học phần<br />
TÊN CHƯƠNG ỤC<br />
Ch ng I Các khái niệm c ản<br />
1.1. G ớ<br />
1.1.1 K<br />
m<br />
.<br />
1.1. . C p ư<br />
p p<br />
1.1.3. C<br />
ụ<br />
s ồ<br />
1. . Độ p<br />
p<br />
1. .1. C<br />
ý<br />
m<br />
ộ p<br />
1. . . C lớp<br />
1.3. Mố<br />
a<br />
<br />
a<br />
<br />
l<br />
<br />
1.4. Mộ số<br />
ụ<br />
Ch ng II S p ếp và t m kiếm<br />
.1. B<br />
sắp x p<br />
.1.1. Sắp x p<br />
.1. . Sắp x p<br />
.1.3. Đ<br />
sắp x p<br />
. .C<br />
sắp x p<br />
ả<br />
. .1. Sắp x p ọ Sele<br />
S<br />
. . . Sắp x p<br />
ự<br />
p x a e S<br />
. .3. Sắp x p è I se<br />
S<br />
. .4. Sắp x p<br />
ọ B le S<br />
. . .S s<br />
sắp x p<br />
ả<br />
<br />
PHÂN PHỐI SỐ TIẾT<br />
TS LT TH/Xemina<br />
5<br />
4<br />
0<br />
1<br />
ố<br />
2<br />
<br />
1<br />
<br />
p<br />
0,5<br />
0,5<br />
<br />
ả<br />
15<br />
<br />
7<br />
0,5<br />
<br />
5<br />
<br />
2<br />
<br />
3<br />
<br />
2,5<br />
<br />
1<br />
<br />
1<br />
<br />
i<br />
<br />
TÊN CHƯƠNG ỤC<br />
.3. Sắp x p<br />
ố<br />
.3.1. C<br />
Heap<br />
.3. . T<br />
xy ự<br />
Heap<br />
.3.3. T<br />
sắp x p<br />
ố<br />
.4. T m<br />
m y<br />
.4.1. B<br />
m m<br />
.4. . T<br />
m m y<br />
Ch ng III Đệ qui và chiến<br />
c v t cạn<br />
3.1. K<br />
m<br />
quy<br />
3.1.1. G ả<br />
y<br />
ủ ụ<br />
y<br />
3.1. . T<br />
ả<br />
y<br />
3.1.3. H lự ủa<br />
y.<br />
3.1.4. Đ<br />
y<br />
y p<br />
ọ .<br />
3. . C<br />
lượ<br />
B e e<br />
3.3. C<br />
lượ<br />
ay l<br />
a a<br />
3.3.1. Ve<br />
m<br />
3.3. . T ủ ụ<br />
3.3.3. C<br />
3.3.4. Đ<br />
p<br />
3.3. . Mộ số<br />
a a<br />
Ch ng IV Chiến<br />
c chia đ tr<br />
4.1. C s ủa<br />
lượ<br />
a<br />
4. . T<br />
sắp x p<br />
ộ<br />
4. .1. T<br />
ộ a R<br />
4. . . Sắp x p<br />
ộ<br />
4.3. Sắp x p a<br />
s<br />
4.3.1. C<br />
lượ p<br />
4.3.2. Quick sort<br />
4.4. T m<br />
m<br />
p<br />
4. . T<br />
số<br />
yê<br />
4. .1. T<br />
ay<br />
4. . . T<br />
a<br />
4. . Mộ số<br />
Ch ng V Qui hoạch động<br />
.1. C<br />
lượ<br />
ộ<br />
5.1.1. C<br />
p ụ<br />
.1. . C<br />
ướ<br />
ộ<br />
.1.3. C<br />
ộ<br />
. .B<br />
y số<br />
a<br />
. .1. T<br />
. . .T<br />
ộ<br />
.3. B<br />
y<br />
.4. B<br />
ma<br />
. . Mộ số<br />
ụ<br />
Ch ng VI Chiến<br />
c tham am<br />
.1. N yê ắ am lam<br />
. .B<br />
.3. B<br />
sắp l<br />
sự<br />
.3.1. T<br />
<br />
PHÂN PHỐI SỐ TIẾT<br />
TS LT TH/Xemina<br />
2,5<br />
1,5<br />
<br />
11<br />
<br />
11<br />
<br />
12<br />
<br />
6<br />
<br />
1<br />
<br />
1<br />
<br />
6<br />
1<br />
<br />
3<br />
<br />
0,5<br />
<br />
1<br />
2<br />
<br />
1<br />
1<br />
1<br />
0,5<br />
1<br />
6<br />
0,5<br />
1,5<br />
<br />
3<br />
<br />
BT<br />
1<br />
<br />
KT<br />
<br />
2<br />
1<br />
<br />
0<br />
<br />
1<br />
1<br />
<br />
1<br />
<br />
1<br />
2<br />
<br />
1<br />
<br />
1<br />
<br />
1,5<br />
<br />
1<br />
<br />
1<br />
1<br />
<br />
1<br />
<br />
0,5<br />
6<br />
1,5<br />
<br />
3<br />
<br />
1<br />
<br />
0,5<br />
<br />
1<br />
1,5<br />
1<br />
4<br />
0,5<br />
1<br />
2<br />
<br />
1<br />
1<br />
0,5<br />
1<br />
<br />
1<br />
1<br />
1<br />
<br />
0<br />
<br />
1<br />
<br />
ii<br />
<br />
TÊN CHƯƠNG ỤC<br />
.3. . T<br />
e<br />
.4. S s<br />
lượ<br />
ộ<br />
<br />
PHÂN PHỐI SỐ TIẾT<br />
TS LT TH/Xemina<br />
lượ am lam<br />
am lam ớ<br />
lượ<br />
<br />
Nhiệm vụ của sinh viên<br />
T am ự<br />
y<br />
am ự<br />
m a<br />
<br />
ủa<br />
ỳ<br />
<br />
ố<br />
<br />
BT<br />
<br />
0,5<br />
<br />
ê<br />
ỳ.<br />
<br />
ự ọ<br />
<br />
KT<br />
<br />
1<br />
<br />
ự lm<br />
<br />
p do giáo viên giao,<br />
<br />
Tài iệu học tập<br />
N y H Đ<br />
Giáo trình một số vấn đề về thuật toán NXB G<br />
ụ<br />
2003<br />
Đ M<br />
Tư . Cấu trúc dữ liệu và thuật toán. NXB Đ ọ<br />
ố aH<br />
ộ . 00 .<br />
N y<br />
ố Lượ H<br />
Đ Hả . Cấu trúc dữ liệu + giải thuật = chương<br />
trình. NXB G<br />
ụ . 199<br />
R a Neap l a<br />
Kumarss Naimipour, Foundations of Algorithms Using<br />
C++ Pseudocode, Third Edition, Jones and Bartlett Publishers, 2004.<br />
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,<br />
Introduction to Algorithms, Second Edition, MIT Press, 2001.<br />
H nh thức và tiêu chuẩn đánh giá sinh viên<br />
H<br />
ố ỳ:T<br />
S<br />
ê p ả ảm ả<br />
Thang đi m Thang đi m chữ<br />
<br />
p.<br />
e<br />
<br />
y<br />
<br />
ủa N<br />
<br />
ư<br />
<br />
ủa Bộ<br />
<br />
, , C, D, F<br />
<br />
Đi m đánh giá học phần Z = 0,3X + 0,7<br />
B<br />
K a Cô<br />
<br />
ả<br />
<br />
y l<br />
Tô<br />
<br />
Ngày phê duyệt<br />
Tr ởng<br />
<br />
l<br />
<br />
chính thức và thống nhất ủa Bộ mô K a ọ M y<br />
ượ ù<br />
ả<br />
y cho sinh viên.<br />
/<br />
<br />
/20<br />
<br />
ộ môn ThS Nguyễn Hữu Tuân (ký và ghi rõ họ tên)<br />
<br />
iii<br />
<br />
ài giảng môn học Phân tích thiết kế và đánh giá giải thuật<br />
ỤC LỤC<br />
LỜI NÓI ĐẦU ............................................................................................................................ 1<br />
CH<br />
<br />
NG I: C C KH I NI M C<br />
1. T<br />
<br />
ả<br />
<br />
- Algorithm ............................................................................... 2<br />
<br />
a<br />
<br />
............................................................................................. 2<br />
<br />
1.1. Đ<br />
1. . Đ<br />
<br />
ư<br />
<br />
ủa<br />
<br />
........................................................................................ 2<br />
<br />
.B<br />
<br />
....................................................................................................... 2<br />
<br />
.1. Mô ả<br />
. .S<br />
<br />
ướ<br />
<br />
ụ<br />
<br />
3. Độ p<br />
<br />
s<br />
<br />
ự<br />
<br />
ồ lư<br />
<br />
....................................................................................... 2<br />
ồ<br />
<br />
p<br />
<br />
3.1. C<br />
<br />
ả<br />
<br />
l<br />
<br />
ê<br />
<br />
........................................................ 3<br />
<br />
............................................................................. 4<br />
a<br />
<br />
3.3. C<br />
<br />
ự<br />
<br />
................................................................. 4<br />
<br />
a<br />
<br />
3.4. C<br />
<br />
a<br />
<br />
– Algorithm Complexity.......................................................... 4<br />
<br />
3. . Đ<br />
<br />
ộp<br />
<br />
lớp<br />
<br />
p<br />
<br />
.............................................. 5<br />
<br />
.................................................................................................. 7<br />
<br />
4. C<br />
<br />
l<br />
<br />
– Data structure .................................................................................. 9<br />
<br />
.C<br />
<br />
lượ<br />
<br />
. ................................................................................ 9<br />
<br />
.1. D y<br />
<br />
ộ<br />
<br />
. .Đ<br />
.4. C<br />
<br />
D<br />
lượ<br />
<br />
......................................................................... 9<br />
<br />
ea<br />
<br />
C<br />
<br />
e ........................................................................... 9<br />
<br />
am lam G ee y ............................................................................ 10<br />
<br />
. .<br />
.B<br />
<br />
x a s e sea<br />
<br />
ay l – Backtracking ............................................................................. 9<br />
<br />
.3. C a<br />
<br />
CH<br />
<br />
BẢN ................................................................................ 2<br />
<br />
ộ<br />
<br />
Dy am P<br />
<br />
amm<br />
<br />
........................................................... 11<br />
<br />
p ......................................................................................................................... 11<br />
<br />
NG II: S P X P SORTING VÀ TÌM KI M S ARCHING ................................. 13<br />
1. B<br />
<br />
sắp x p .......................................................................................................... 13<br />
<br />
1.1. Sắp x p<br />
<br />
I e al S<br />
<br />
1. . Sắp x p<br />
<br />
x e al S<br />
<br />
1.3. Sắp x p<br />
1.3. C<br />
.C<br />
<br />
.1. Sắp x p<br />
<br />
ẩ<br />
<br />
.4. Sắp x p<br />
<br />
mộ<br />
<br />
p p sắp x p<br />
ọ<br />
<br />
. . Sắp x p<br />
.3. Sắp x p<br />
<br />
......................................................................... 13<br />
<br />
p .................................................................................................. 13<br />
<br />
ê<br />
<br />
p ư<br />
<br />
.......................................................................... 13<br />
<br />
è<br />
<br />
Sele<br />
<br />
sắp x p .................................................. 14<br />
<br />
ả ................................................................................ 15<br />
s<br />
<br />
.............................................................................. 15<br />
<br />
ự<br />
<br />
p<br />
<br />
x a es<br />
<br />
........................................................... 17<br />
<br />
I se<br />
<br />
s<br />
<br />
............................................................................... 19<br />
<br />
ọ B<br />
<br />
le s<br />
<br />
.............................................................................. 21<br />
<br />
iv<br />
<br />
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
