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