Giáo trình Phân tích thiết kế và đánh giá thuật toán - Trường Đại học Hàng Hải
BỘ GIAO THÔNG VẬN TẢI
TRƢỜNG ĐẠI HỌC HÀNG HẢI
́ ́
BỘ MÔN: KHOA HOC MAY TINH
̣
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
PHÂN TÍCH THIẾT KẾ VÀ ĐÁNH GIÁ
THUẬT TOÁ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 QUY
DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN
HẢI PHÕNG - 2010
Tên học phần: Phân tich thꢃê
Bộ môn phụ trách giảng dạy: Khoa học Máy tính
Mã học phần: 17208
́
t kê
́
va đanh gꢃa thuât
̣
toan
Loại học phần: 2
Khoa phụ trách: CNTT
Tổng số TC: 3
̀
́
́
́
́
TS tꢃết Lý thuyết Thực hành/Xemꢃna Tự học Bàꢃ tập lớn Đồ án môn học
60 45 15
0
0
0
Điều kiện tiên quyết:
Sꢃnh vꢃên phảꢃ học xong các học phần sau mớꢃ đƣợc đăng ký học phần này:
Kꢀ thuật lập trꢁnh, Câu truc dƣ lꢃêu, Toán rờꢃ rꢂc
́
̣
́
̃
Mục tiêu của học phần:
-
-
-
Cung cấp các kꢃến thức cơ bản vê
Cung câp cac kꢃên thƣc vê chꢃên lƣơc
Rèn luyện tƣ duy khoa học.
̀
thuật toán, cấu trúc dữ lꢃệu.
̣
xây dƣng va đanh gꢃa thuât toan
́
́
́
̀
́
̣
̣
́
́
̀
́
́
Nội dung chủ yếu
Gồm 4 phần:
-
-
-
Các kꢃến thức cơ bản về thuật toán.
Các kꢃến thức cơ bản về sắp xếp và tꢁm kꢃếm dữ lꢃệu.
Các chꢃến lƣợc thꢃế t kê thuât toan : chꢃến lƣợc chꢃa để trị, chꢃến lƣợc quay luꢃ,
́
̣
́
chꢃến lƣợc quꢃ hoꢂch động, chꢃến lƣợc tham lam
̣
Kꢃên thƣc cơ ban vê đanh gꢃa đô phƣc tap thuât toan.
́
-
́
̀
̣
̣
̉
́
́
́
́
Nội dung chi tiết của học phần:
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
TS LT TH/Xemina BT KT
5
4
1
0
1
0
Chƣơng I. Các khái niệm cơ bản
1.1. Gꢃớꢃ thꢃệu về thuật toán
1.1.1 Kháꢃ nꢃệm về thuật toán.
1.1.2. Các phƣơng pháp bꢃểu dꢃꢄn thuật toán
1.1.3. Các ví dụ bꢃểu dꢃꢄn thuật toán sơ đồ khốꢃ
1.2. Độ phức tꢂp thuật toán
2
1
1.2.1. Các ký hꢃệu , hàm đánh gꢃá độ phức tꢂp
thuât
1.2.2. Các lớp thuật toán
1.3. Môꢃ quan hê gꢃƣa câ
thuât
1.4. Môt
Chƣơng II. Săp xêp va tim kiêm
̣
toan
́
0,5
0,5
́
̣
̣
́u truc dƣ lꢃêu va gꢃaꢃ
́ ̀
̃
̉
̃
̣
̣
số vi du
̣
́
́
́
́
15
7
0,5
5
2
1
1
̀
̀
2.1. Bàꢃ toán sắp xếp
2.1.1. Săp xêp trong
2.1.2. Săp xêp ngoaꢃ
2.1.3. Đanh gꢃa thuât
́
́
́
́
̀
̣
toan să
́
p xê
2.2. Các thuật toán sắp xếp cơ bản
2.2.1. Săp xêp chon (Selection Sort)
2.2.2. Săp xêp đôꢃ chô trƣc
2.2.3. Săp xêp chen (Insertion Sort)
2.2.4. Săp xêp nôꢃ bot
2.2.5. So sanh cac thuât
́p
́
́
́
3
2,5
́
́
̣
̉
̃
́
́
̣
tꢃếp (Exchange Sort)
́
́
́
́
̀
̉
̣
(Bubble Sort)
toan săp xêp cơ ban
̣
́
́
̉
́
́
́
i
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
2.3. Săp xêp vun đông
2.3.1. Câu truc Heap
2.3.2. Thuât
2.3.3. Thuât
TS LT TH/Xemina BT KT
́
́
́
2,5 1,5
1
́
́
̣
̣
toan xây dƣn
toan să
̣
g câ
p vun đống
́u truc Heap
́
́
́
́
p xê
́
2.4. Tꢁm kꢃếm tuyến tính
2.4.1. Bàꢃ toán tꢁm kꢃếm
1
1
3
2.4.2. Thuât
Chƣơng III. Đê
3.1. Kháꢃ nꢃệm về đệ quy
̣
toan tim kꢃếm tuyến tinh
́
̀ ́
́
̣ ̣
qui va chiên lƣơc vet can
̀ ́
11
6
1
2
1
0
̣
3.1.1. Gꢃảꢃ thuật đệ quy và thủ tục đệ quy
3.1.2. Thꢃết kế gꢃảꢃ thuật đệ quy
3.1.3. Hꢃệu lực của đệ quy.
3.1.4. Đệ quy và quy nꢂp toán học.
3.2. Chꢃê
́
n lƣơc
̣
vet can
̣
(Bruteforce)
0,5
1
2
́
3.3. Chꢃên lƣơc
́
̣
đê
̣
quꢃ quay luꢃ (backtracking)
3.3.1. Vector nghꢃêm
̣
1
3.3.2. Thủ tục đệ quꢃ
3.3.3. Các gꢃá trị đề cꢅ
1
1
3.3.4. Đꢃê
3.3.5. Môt
Chƣơng IV. Chiên lƣơc
4.1. Cơ sơ cua chꢃên lƣơc
p xêp bă
toan trôn haꢃ Run
ng trôn
p nhanh (Quick sort)
n lƣơc phân hoac
4.3.2. Quick sort
4.4. Tꢁm kꢃếm nhị phân
4.5. Thuât toán nhân số nguyên
4.5.1. Thuât toan nhân tay
4.5.2. Thuât
4.6. Môt sô baꢃ toan khac
Chƣơng V. Qui hoac
5.1. Chꢃên lƣơc quꢃ hoac
5.1.1. Các đꢃều kꢃện để áp dụng
̀
u kꢃên
̣
châ
́
p nhân
̣
0,5
1
6
0,5
1,5
̉
̣
số baꢃ toan backtrackꢃng đꢃên hinh
1
1
̀
́
̀
́
̉
chia đê tri
̣
11
3
1
1
̣
̉
́
̣
chꢃa đê trꢃ
̣
̉
̉
4.2. Thuât
4.2.1. Thuât
4.2.2. Săp xê
4.3. Săp xê
4.3.1. Chꢃê
̣
toan să
́
́
̀
ng trôn
̣
́
̣
̣
́
́
́
p bă
̀
̣
́
́
1,5
1
1
́
̣
̣
h
1
1
̣
̣
̣
́
́
̉
toan chꢃa đê trꢃ
̣
̣
́
0,5
6
1,5
1
2
̀
́
́
12
3
1
̣
h đôn
̣
g
̣
́
̣
̣
h đôn
g
5.1.2. Các bƣớc trong quꢃ hoꢂch động
5.1.3. Các kꢃểu quꢃ hoꢂch động
5.2. Bàꢃ toán dꢆy số Fꢃbonacꢃ
1
0,5
5.2.1. Thuât
5.2.2. Thuât
̣
̣
toan đê
̣
quꢃ
́
toan quꢃ hoach đông
̣
̣
́
5.3. Bàꢃ toán dꢆy con chung dàꢃ nhất
5.4. Bàꢃ toán nhân ma trận
1
1,5
1
4
0,5
1
1
1
0,5
1
1
5.5. Môt
Chƣơng VI. Chiên lƣơc
6.1. Nguyên tăc tham lam
6.2. Bàꢃ toán đꢇꢃ tꢃền
6.3. Bàꢃ toán sắp lịch các sự kꢃện
6.3.1. Thuât toan đê quꢃ
̣
số
vi du
́
̣
khac
́
1
1
́
6
0
̣
tham lam
́
2
1
̣
̣
́
ii
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
6.3.2. Thuât toan theo chꢃê
6.4. So sanh chꢃê
TS LT TH/Xemina BT KT
̣
́
n lƣơc
̣
tham lam
n lƣơc
́
́
n lƣơc
̣
tham lam vơꢃ chꢃê
́
̣
0,5
1
́
́
̣ ̣
quꢃ hoach đông
Nhiệm vụ của sinh viên :
Tham dự các buꢇꢃ thuyết trꢁnh của gꢃáo vꢃên, tự học, tự làm bàꢃ tập do gꢃáo vꢃên gꢃao,
tham dự các bàꢃ kꢃểm tra định kỳ và cuốꢃ kỳ.
Tài liệu học tập :
Nguyꢄn Hữu Đꢃển, Giáo trình một số vấn đề về thuật toán, NXB Gꢃáo dục,
-
2003
-
Đꢃnh Mꢂnh Tƣờng. Cấu trúc dữ liệu và thuật toán. NXB Đꢂꢃ học Quốc gꢃa Hà
nộꢃ. 2002.
-
Nguyꢄn Quốc Lƣợng, Hoàng Đức Hảꢃ. Cấu trúc dữ liệu + giải thuật = chương
trình. NXB Gꢃáo dục. 1996
-
Richard Neapolitan và 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ꢁnh thức thꢃ cuốꢃ kỳ : Thꢃ vấn đáp.
Sꢃnh vꢃên phảꢃ đảm bảo các đꢃều kꢃện theo Quy chế của Nhà trƣờng và của Bộ
Thang điểm: Thang điểm chữ A, B, C, D, F
Điểm đánh giá học phần: Z = 0,3X + 0,7Y.
Bàꢃ gꢃảng này là tàꢃ lꢃệu chính thức và thống nhất của Bộ môn Khoa học Máy tính,
Khoa Công nghệ Thông tꢃn và đƣợc dùng để gꢃảng dꢂy cho sinh viên.
Ngày phê duyệt:
/
/20
Trƣởng Bộ môn: ThS. Nguyễn Hữu Tuân (ký và ghi rõ họ tên)
iii
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
MỤC LỤC
LỜI NÓI ĐẦU............................................................................................................................1
CHƢƠNG I: CꢈC KHꢈI NIꢉM CƠ BẢN................................................................................2
1.2. Đꢊc trƣng của thuật toán........................................................................................2
toan (gꢃảꢃ thuật) - Algorithm...............................................................................2
h nghia thuât toan.............................................................................................2
2.1. Mô tả các bƣớc thực hꢃện.......................................................................................2
2.2. Sꢅ dụng sơ đô (lƣu đồ) gꢃảꢃ thuật (flowchart) .......................................................3
toan ......................................................................................................2
3. Độ phức tꢂp thuật toán – Algorithm Complexity..........................................................4
3.1. Các tꢃêu chí đánh gꢃá thuật toán.............................................................................4
3.2. Đanh gꢃa thơꢃ gꢃan thƣc hꢃên thuât toán.................................................................4
3.3. Các định nghꢋa hꢁnh thức về độ phức tꢂp thuật toán .............................................5
3.4. Các lớp thuật toán..................................................................................................7
4. Cấu truc dƣ lꢃêu – Data structure ..................................................................................9
5. Các chꢃến lƣợc thꢃết kế thuật toán.................................................................................9
5.1. Duyệt toàn bộ (Exhausted search) .........................................................................9
5.2. Đệ quꢃ quay luꢃ – Backtracking .............................................................................9
6. Bàꢃ tập .........................................................................................................................11
1. Bàꢃ toán sắp xếp ..........................................................................................................13
p trong (Internal Sorting) ..........................................................................13
p ngoàꢃ (External Sorting).........................................................................13
́p gꢃán tꢃếp..................................................................................................13
1.3. Các tꢃêu chuẩn đánh gꢃá một thuật toán sắp xếp..................................................14
2. Các phƣơng pháp sắp xếp cơ bản................................................................................15
2.3. Săp xêp chen (Insertion sort) ...............................................................................19
p xếp chon (Selection sort) ..............................................................................15
iv
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
2.5. So sánh các thuật toán sắp xếp cơ bản.................................................................23
3. Câu truc dƣ lꢃêu Heap, săp xêp vun đông (Heap sort). ...............................................24
4. Tꢁm kꢃếm tuyến tính....................................................................................................31
5. Các vấn đê khac ..........................................................................................................33
6. Bàꢃ tập .........................................................................................................................33
CHƢƠNG III: Đꢉ QUI VÀ CHIꢌN LƢꢍC VꢎT CẠN ..........................................................34
1. Kháꢃ nꢃệm đệ quꢃ .....................................................................................................34
2. Chꢃến lƣơc vet can (Brute force).............................................................................34
2. Săp xêp trôn (Merge sort)........................................................................................38
3. Săp xêp nhanh (Quick sort).....................................................................................43
4. Tꢁm kꢃếm nhị phân ..................................................................................................46
5. Bàꢃ tập .....................................................................................................................48
2. Bàꢃ toán 1: Dꢆy Fꢃbonacꢃ.........................................................................................49
3. Bàꢃ toán 2: Bàꢃ toán nhân dꢆy các ma trận ..............................................................51
4. Phƣơng phap quꢃ hoach đông..................................................................................53
5. Bàꢃ toán dꢆy con chung dàꢃ nhất .............................................................................53
6. Bàꢃ tập .....................................................................................................................57
1. Nguyên tắc tham lam...............................................................................................60
2. Bàꢃ toán đꢇꢃ tꢃền ......................................................................................................60
3. Bài toán lập lịch.......................................................................................................61
4. So sánh chꢃến lƣợc tham lam và quꢃ hoꢂch động....................................................64
TÀI LIꢉU THAM KHẢO........................................................................................................65
ĐỀ THI THAM KHẢO............................................................................................................66
v
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
LỜI NÓI ĐẦU
Câu truc dƣ lꢃêu
vơꢃ nhau va la môt
́
̣
va các chꢃến lƣợc thꢃết kế thuật toán là các lꢋnh vực nghꢃên cứu gắn lꢃền
̀
trong nhƣng linh vƣc nghꢃên cƣu lâu đơꢃ cua khoa hoc may tinh . Hầu hết
̣ ̣
̃
̉
́ ̀ ́
̃
́
́
̃
̣
́
̀
̀
các chƣơng trꢁnh đƣợc vꢃết ra , chꢂy trên máy tính , dù lớn hay nhꢐ, dù đơn gꢃản hay phức tꢂp ,
đều phảꢃ sꢅ dụng các cấu trúc dữ lꢃệu tuân theo các trꢁnh tự , cách thức làm vꢃệc nào đꢑ, chính
̉
̣ ̣
hꢃêu bꢃết về cac thuât toan và các chꢃên lƣợc xây dựng thuật toán cho
́ ́
là các gꢃảꢃ thuật . Vꢃêc
phꢒp các lập trꢁnh vꢃên, các nha khoa hoc
̣
may tinh co nê
̀
n tang ly thuyê
́
t vƣng chă
́
c , cꢑ nhꢃều
. Vꢁ vậy vꢃệc học tập
̣
g.
̉
̃
̀
́
́
́
́
lƣa
̣
chon
̣
hơn trong vꢃêc
̣ ̣
đƣa ra cac gꢃaꢃ phap cho cac baꢃ toan thƣc ́
̉
́ ́ ́ ̀ ́
tê
môn hoc
̣
Phân tich thꢃêt kê
́
́
va danh gꢃa gꢃaꢃ thuât
̣
là một đꢃê
̀
u quan tron
̉
̀
́
́
́
Tàꢃ lꢃệu này dựa trên những kꢃnh nghꢃệm và nghꢃên cứu mà tác gꢃả đꢆ đúc rút , thu thập
trong quá trꢁnh gꢃảng dꢂy môn học Câu truc dƣ lꢃêu va gꢃaꢃ thuât tꢂꢃ khoa Công nghệ Thông
tin, Đꢂꢃ học Hàng hảꢃ Vꢃệt nam , cùng vớꢃ sự tham khả o cua cac taꢃ lꢃêu cua cac đông nghꢃêp
n Wꢃkꢃpedꢃa . Vớꢃ bây chƣơng đƣợc chꢃa
cơ ban cho tớꢃ thuât toan săp xêp , tꢁm kꢃếm, các
g, tham lam … hy vọng sẽ
́
̣
̣
́
̃
̀
̉
̣
̀
̣
,
̉
̉
́
̀
́
̉
̉
̣
các tác gꢃả trong và ngoàꢃ nƣớc , tƣ đꢃên trƣc tuyế
̀
thành các chủ đề khác nhau từ cac khaꢃ nꢃêm
̣
̣
́
́
̉
́
́
́
̣ ̣ ̣ ̣ ̣
chꢃến lƣơc thꢃết kế thuât toan nhƣ đê quꢃ , quay lui, quꢃ hoach đôn
́
cung cấp cho các em sꢃnh vꢃên , các bꢂn độc gꢃả một tàꢃ lꢃệu bꢇ ích . Mꢊc dù đꢆ rất cố gắng
song vẫn không tránh khꢐꢃ một số thꢃếu sꢑt, hy vọng sẽ đƣợc các bꢂn bè đồng nghꢃệp, các em
sinh viên, các bꢂn độc gꢃả gꢑp ý chân thành để tôꢃ cꢑ thể hoàn thꢃện hơn nữa tàꢃ lꢃệu này.
Xꢃn gꢅꢃ lờꢃ cảm ơn chân thành tớꢃ các bꢂn bè đồng nghꢃệp và Ban chủ nhꢃệm khoa
Công nghệ Thông tꢃn đꢆ tꢂo đꢃều kꢃện gꢃúp đỡ để tàꢃ lꢃệu này cꢑ thể hoàn thành.
Hải phòng, tháng 04 năm 2010
Tác giả
̃
Nguyên Hƣu Tuân
̃
1
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
CHƢƠNG I: CÁC KHÁI NIỆM CƠ BẢN
1. Thuât
1.1. Đinh nghia thuât
Cꢑ rất nhꢃều các định nghꢋa cꢓng nhƣ cách phát bꢃểu khác nhau về định nghꢋa của thuật
̣
toan (giải thuật) - Algorithm
́
̣
̣
toan
́
̃
̉
toán. Theo nhƣ cuô
́
n sach gꢃao khoa nôꢃ tꢃê
́
ng vꢃê
́
t vê
̀
thuât
̣
toan
là “Introduction to
́
́
́
Algorithms” (Second Edꢃtꢃon cua Thomas H . Cormen, Charles E . Leiserson, Ronald L .
̉
Rꢃvest va Clꢃfford Steꢃn ) thꢁ thuật toán đƣợc định nghꢋa nhƣ sau : “môt
̣
thuât
̣ ̣
p cac gꢃa trꢃ goꢃ la ꢃnput va
̀ ̀
̣ ̣
toan la môt thu
̉
́ ̀
̀
tục tính toán xác định (well-defined) nhân
̣
cac gꢃa trꢃ
̣
̣
môt
̣
tâ
̣
́
́
́
́
sꢃnh ra ra môt vaꢃ gꢃa trꢃ hoăc môt tâp gꢃa trꢃ
̣
̣
̣
̣
̣
̣
̣ ̣
goꢃ
̀
̀
́
́
̉
̀
̀
̀
̉
môt
̣
công vꢃêc
̣
cu
̣
thê xac đꢃn
̣
h (well-defined) nào đꢑ. Vꢁ thế một đoꢂn mꢆ chƣơng trꢁnh tính
́
các phần tꢅ của dꢆy số Fꢃbonacꢃ là một càꢃ đꢊt của một thuật toán cụ thể . Thâm
̣
chi môt ham
̣
̀
́
̉
̣ ̣ ̣ ̣
đơn gꢃan đê công haꢃ số cung la môt thuât toan hoan chinh , măc dù đꢑ là một thuật toán đơn
̃
̀ ́ ̀
̉
̉
gꢃản.
1.2. Đꢀc trƣng của thuật toán
Tính đúng đắn : Thuât toan cân phaꢃ đam bao cho môt
ꢃ vơꢃ cac bô dƣ lꢃêu đâu vao . Đây co thê noꢃ la đăc
̣
̀
̣
kê
́
t qua đung sau khꢃ thƣc
̣
hꢃên
̣
̉
̉
̉
̉
́
́
̉
đô
́
̣
̣
̀
̣
trƣng quan tron
̣
g nhâ
́
t đô
́
ꢃ vơꢃ môt thuât
̣
̣
́
́
̃
̀
́
́
̀
́
toán.
Tính dừng: thuât
̣ ̣ ̣
toan cần phaꢃ đam bao se dƣng sau môt số hƣu han bƣơc.
̉ ̉ ̉
̃ ̃
́ ̀ ́
Tính xác định: Các bƣớc của thuật toán phảꢃ đƣợc phát bꢃểu rꢔ ràng , cụ thể, tránh gây
̃
đô
̉
̣
́ꢃ vơꢃ ngƣơꢃ đoc va hꢃêu, càꢃ đꢊt thuật toán.
́ ̀ ̀
nhâp
̣
nhă
Tính hꢃệu quả: thuât
quả bàꢃ toán đꢊt ra trong thờꢃ gꢃan hoꢊc các đꢃều kꢃện cho phꢒp trên thực tế đáp ứn g đƣơc
câu cua ngƣơꢃ dung.
̀
ng hoăc
̣
nhâ
̀
m lân
̣
toan đƣơc
̣
xem la hꢃêu
̣
qua nê
́
u nhƣ no co kha năng gꢃaꢃ quyê
́
t hꢃêu
̣
̉
̉
̉
́
̀
́
́
̣
yêu
̀
̉
̀
̀
̉ ̉
̣ ̣ ̣
toan đƣơc goꢃ la co tinh phố quat (phô bꢃến) nếu no co thê gꢃaꢃ
̉
́ ̀ ́ ́ ́ ́
́
Tính phꢇ quát : thuât
quyê
́
t đƣơc môt lơp cac baꢃ toan tƣơng tƣ.
̣
̣
̣
́
́
̀
́
Ngoàꢃ ra mꢕꢃ thuật toán theo định nghꢋa đều nhận các gꢃá trị đầu vào đƣợc gọꢃ chung là
̉
̣ ̣ ̣
́t qua cua thuât toan (thƣơng la môt kết qua cu thê nao đo tuy theo
̉ ̉ ̉
́ ̀ ̀ ̀ ́ ̀
các gꢃá trị dữ lꢃệu Input. Kê
các bàꢃ toán và thuật toán cụ thể) đƣơc
̣
̣
goꢃ la Output.
̀
̉
̃
2. Biêu diên thuât toan
̣
́
Thƣờng có hai cách biểu diꢄn một thuật toán, cách thứ nhất là mô tả các bƣớc thực hiện
của thuật toán, cách thứ hai là sꢅ dụng sơ đồ giải thuật.
2.1. Mô tả các bƣớc thực hiện
Để biểu diꢄn thuật toán ngƣời ta mô tả chính xác các bƣớc thực hiện của thuật toán,
ngôn ngữ dùng để mô tả thuật toán có thể là ngôn ngữ tự nhiên hoꢊc một ngôn ngữ lai ghép
giữa ngôn ngữ tự nhiên với một ngôn ngữ lập trꢁnh nào đꢑ gọꢃ là các đoꢂn giả mã lệnh.
2
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
Ví dụ: mô tả thuật toán tꢁm ƣớc số chung lớn nhất của hai số nguyên.
Input: Hai số nguyên a, b.
Output: Ƣớc số chung lớn nhất của a, b.
Thuật toán:
Bƣơc 1: Nê
́
u a=b thì USCLN(a, b)=a.
́
Bƣơc 2: Nêu a > b thì tìm USCLN của a-b và b, quay lꢂi bƣơc 1;
́
́
́
Bƣơc 3: Nếu a < b thì tìm USCLN của a và b-a, quay lꢂi bƣơc 1;
́
́
̀
2.2. Sử dụng sơ đô (lƣu đồ) giải thuật (flowchart)
̉ ̉ ̉
̃
̣ ̣ ̣ ̣
trong nhƣng cach phô bꢃến đê bꢃêu dꢃên thuât toan la sƣ dung sơ đồ thuât toan
̃
́ ́ ̀ ́
̉
Môt
(Algorithm Flowchart).
̉
̣ ̣ ̣ ̣
g cac ky hꢃêu hinh khốꢃ cơ ban đê tao thanh môt mô ta mang
̉ ̉
́ ́ ̀
̀
Sơ đô thuât toan sƣ dun
tính hꢁnh thức (cách này rꢔ ràng hơn so vớꢃ vꢃệc mô tả các bƣớc thực hꢃện thuật toán
thuât toan. Chúng ta cꢑ thể hꢁnh dung vꢃệc sꢅ dụng sơ đồ gꢃảꢃ thuật để mô tả thuật toán gꢃống
nhƣ dung cac ban ve đê mô ta câ
̀
̣
̉
́
) của
̣
́
̉
́
u truc cua cac toa nha.
̉
̃
̉
̉
̀
́
́
́
̀
̀
Các khốꢃ cơ bản của một sơ đồ thuật toán
Bắt đầu
1
Câu lệnh
3
4
Đꢃều kiện
Đ
Kết thúc
2
S
5
Nhập xuất dữ liệu
́
Khôi 1: Khô
́
ꢃ bă
ꢃ kêt thuc thuât
Khối 3: Thƣc hꢃên
̣
đƣơng ra;
́t đầu thuât toan, chꢖ cꢑ duy nhất một đƣờng ra;
̣
́
́
Khôi 2: Khô
́
́
̣
toan, cꢑ thể cꢑ nhꢃều đƣờng vào;
́
́
̣
̣ ̣
câu lệnh (cꢑ thể là một hoꢊc nhꢃều câu lệnh); gồm môt đƣơng vao va
̀ ̀ ̀
môt
̀
̉
̉
̉
Khối 4: Rẽ nhánh, kꢃêm tra bꢃêu thƣc đꢃều kiện (bꢃêu thƣc Boolean), nếu bꢃểu thức đung
́
́
́
̣ ̣
thuât toan se đꢃ theo nhanh Đúng (True), nếu bꢃểu thức saꢃ thuât toan se đꢃ theo nhanh Saꢃ
́ ́ ́ ́
̃ ̃
(False).
3
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
́
Khôi 5: Các câu lệnh nhập và xuất dữ lꢃệu.
3. Độ phức tạp thuật toán – Algorithm Complexity
3.1. Các tiêu chí đánh giá thuật toán
Thông thƣờng để đánh gꢃá mức độ tốt, xấu và so sánh các thuật toán cùng loꢂi, có thể
̉
dựa trên haꢃ tꢃêu chuân:
+ Thuât toan đơn gꢃan, dê
+ Dựa vào thời gian thực hiện và tài nguyên mà thuật toán sꢅ dụng để thực hiện trên các
bộ dữ liệu.
̣
̣
hꢃêu, dê caꢃ đăt.
̃ ̃
̉
̀
̉
́
Trên thực tế các thuật toán hiệu quả thì không dꢄ hiểu, các càꢃ đꢊt hiệu quả cꢓng không
dꢄ dàng thực hiện và hiểu đƣợc một cách nhanh chóng. Và một đꢃều có vẻ nghịch lý là các
thuật toán càng hiệu quả thì càng khó hiểu, càꢃ đꢊt càng phức tꢂp lꢂi càng hiệu quả (không
phảꢃ lúc nào cꢓng đúng). Vꢁ thế để đánh giá và so sánh các thuật toán ngƣờꢃ ta thƣờng dựa
trên độ phức tꢂp về thời gian thực hiện của thuật toán, gọꢃ là độ phức tꢂp thuật toán
(algorithm complexity). Về bản chất độ phức tꢂp thuật toán là một hàm ƣớc lƣợng (có thể
không chính xác) số phép tính mà thuật toán cần thực hiện (từ đꢑ dꢄ dàng suy ra thời gian
thực hiện của thuật toán) đối với một bộ dữ liệu ꢃnput cꢑ kích thƣớc N. N có thể là số phần tꢅ
của mảng trong trƣờng hợp bài toán sắp xếp hoꢊc tìm kiếm, hoꢊc có thể là độ lớn của số trong
bài toán kiểm tra số nguyên tố chẳng hꢂn.
̣ ̣ ̣
3.2. Đanh gia thơi gian thƣc hiên thuât toán
́
́
̀
Để minh họa việc đánh gꢃá độ phức tꢂp thuật toán ta xem xét ví dụ về thuật toán sắp xếp
chọn (selection sort) và sắp xếp đꢇi chꢕ trực tiếp (exchange sort) nhƣ sau:
Cài đꢊt của thuật toán sắp xếp chọn:
for(i=0;i<n;i++)
{
min_idx = i;
for(j=i+1;j<n;j++)
if(a[j]<a[min_idx])
min_idx = j;
if(min_idx!=i)
{
temp = a[i];
a[i] = a[min_idx];
a[min_idx] = temp;
}
4
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
}
Số phép tính thuật toán cần thực hiện đƣợc tính nhƣ sau:
(N-1) + (N-2) + … + 2 + 1 = N*(N-1)/2.
Phân tích chi tiết hơn thꢁ N*(N-1)/2 là số phép toán so sánh cần thực hiện, còn số lần
thực hiện đꢇi chꢕ hai phần tꢅ (số nguyên) tốꢃ đa của thuật toán là N.
Càꢃ đꢊt của thuật toán sắp xếp đꢇi chꢕ trực tiếp:
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(a[j] < a[i])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
̣ ̣
Tƣơng tự đối với thuật toán sắp xếp chọn ta có số phep toan thƣc hꢃên la: (N-1) + (N-2)
́ ́ ̀
+ …+2 +1 = N*(N-1)/2. Chi tiết hơn, N*(N-1)/2 là số lần so sánh thuật toán thực hiện, và
cꢓng là số lần đꢇi chꢕ hai phần tꢅ (hai số nguyên) tốꢃ đa của thuật toán.
Trong trƣờng hợp trung bình, thuật toán sắp xếp chọn cꢑ xu hƣớng tốt hơn so với sắp
xếp đꢇi chꢕ trực tiếp vì số thao tác đꢇi chꢕ ít hơn, còn trong trƣờng hợp tốt nhất thꢁ nhƣ nhau,
trƣờng hợp tồi nhất thì chắc chắn thuật toan sắp xếp chọn tốt hơn, do đꢑ cꢑ thể kết luận thuật
́
toán sắp xếp chọn nhanh hơn so với thuật toán sắp xếp đꢇi chꢕ trực tiếp.
3.3. Các đꢁnh nghꢂa hình thức về độ phức tạp thuật toán
Gọꢃ f, g la cac ham không gꢃam đꢃn
̣
h nghia trên tâp
̣
cac sô
́
nguyên dƣơng . (chú ý là tất
cả các hàm thờꢃ gꢃan đều thꢐa mꢆn các đꢃều kꢃện này ). Chúng ta nꢑꢃ rꢗng hàm f(N) là O(g(N))
(đoc la: f la O lơn cua g) nêu nhƣ tôn taꢃ môt hăng sô c va N0:
̉
̀
́
̀
́
̃
̣
́
̀
̣
̣
̀
́
̉
̀
̀
́
̀
N N0; f (N) c.g(N)
Phát bꢃểu thành lờꢃ nhƣ sau : f(N) là O(g(N)) nê
́
̣ ̣
u tồn taꢃ c sao cho hầu hết phần đồ thꢃ
của hàm f nꢗm dƣớꢃ phần đồ thị của hàm c *g. Chú ý là hàm f tăng nhꢃều nhất là nhanh b ꢗng
hàm c*g.
Thay vi noꢃ f (N) là O(g(N)) chúng ta thƣờng vꢃết là f (N) = O(g(N)). Chú ý rꢗng đẳng
́
̀
thƣc nay không co tinh đô
́
ꢃ xƣng co nghia la chung ta co thê
́
vꢃê
́
t ngƣơc
̣
laꢃ
̣
O(g(N)) = f(N)
́
̀
́
́
́
̀
́
́
́
̃
̉
nhƣng không thê suy ra g(N) = O(f(N)).
Định nghꢋa trên đƣợc gọꢃ là ký hꢃệu O lớn (big-O notation) và thƣờng đƣợc sꢅ dụng để
chꢖ định các chꢊn trên của hàm tăng.
5
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
̣ ̣ ̣
Chăng han đốꢃ vơꢃ vi du về sắp xếp bằng chon
ta cꢑ f(N) = N*(N-1)/2 = 0.5N2 – 0.5N
́
́
̉
chúng ta cꢑ thể vꢃết là f(N) = O(N2). Cꢑ nghꢋa là hàm f không tăng nhanh hơn ham N2.
̀
Chú ý rꢗng thậm chí hàm f chính xác cꢑ công thức nhƣ thế nào không cho chúng ta câu
̣ ̣
trả lờꢃ chính xác của câu hꢐꢃ “Chƣơng trꢁnh cꢑ thơꢃ gꢃan thƣc hꢃên la bao lâu trên may tinh cua
̉
̀ ́
́
̀
tôi?”. Nhƣng đꢃê
toán là hàm bậc haꢃ . Nê
chƣơng trinh se tăng lên xâ
̀
u quan tron
̣
g la qua đo chung ta bꢃê
́
t đƣơc
̣
ham thơꢃ gꢃan thƣc
̣
hꢃên
̣
cua thuât
̣
̉
̀
́
́
̀
̀
́
u chung ta tăng kich thƣơc ꢃnput lên 2 lâ
̀
n, thơꢃ gꢃan thƣc
̣
̣
hꢃê n cua
̉
́
́
̀
́
́
p xi 4 lâ
̀
n không phu
̣
thuôc
̣
vao tô
́
c đô
̣
cua may.
̉
́
̃
̀
̉
̀
Chăn
̣
trên f(N) = O(N2) cho chung ta kê
́
t qua gâ
̀
n nhƣ thê
́
– nꢑ đảm bảo rꢗng độ tăng của
̉
́
hàm thờꢃ gꢃan nhꢃều nhất là bậc haꢃ.
̉
Do đo chung ta se sƣ dun
̣
g ky phap O lơn đê mô ta thơꢃ gꢃan thƣc
̣
hꢃên
(và đôꢃ khꢃ cả bộ nhớ mà thuật toán sꢅ dụng). Đốꢃ vớꢃ thuật toán trong ví dụ 2 chúng ta cꢑ thể
nꢑꢃ “độ phức tꢂp thờꢃ gꢃan của thuật toán là O(N2) hoăc n gọn là “thuật toán là O(N2)”.
ngă
̣ ̣
cua thuât toan
̉
́
́
́
̃
̉
́
́
́
̉
̀
̣
́
Tƣơng tƣ chung ta co cac đꢃnh nghia (omega)và (theta):
Chúng ta nꢑꢃ rꢗng hàm f(N) là (g(N)) nêu nhƣ g(N) = O(f(N)), hay nꢑꢃ cách khác hàm
f tăng it nhât la nhanh băng ham g.
̣
̣
́
́
́
̃
́
́
̀
̀
̀
́
Và nꢑꢃ rꢗng hàm f (N) là
(g(N)) nếu nhƣ f (N) = O(g(N)) và g(N) = O(f(N)), hay noꢃ
́
cách khác cả haꢃ hàm xấp xꢖ nhƣ nhau về độ tăng.
̉
Hꢃên nhꢃên la cach vꢃê
́
t
là để chꢖ ra chꢊn dƣớꢃ và
của một hàm. Còn cꢑ nhꢃều gꢃớꢃ hꢂn khác nữa nhƣng đây là các gꢃớꢃ hꢂn mà chúng ta hay gꢊp
nhât.
là để chꢖ ra một gꢃớꢃ hꢂn chꢊt chẽ
̀
́
́
̣ ̣
Môt vai vi du:
̀
́
0.5N2 – 0.5N = O(N2)
47 N*log(N) = O(N*log(N))
N*log(N) + 1000047N =
Tât ca cac ham đa thƣc bâc
Độ phức tꢂp thờꢃ gꢃan c ủa thuật toán sắp xếp chọn và sắp xếp đꢇꢃ chꢕ
(N2)
Nêu môt thuât
̣
Môꢃ thuât toan sắp xếp dƣa trên so sanh cꢑ độ phức tꢂp tốꢃ ƣu là
́
(N*log(N))
́
̣
k đê
̀
u la O(Nk)
̉
́
̀
́
̀
̣
trƣc tꢃếp là
́
̣
̣
toan la O(N2) thꢁ nꢑ cꢓng là O(N5)
́ ̀
̃
̣
́
(N*log(N))
Thuât
̣
toan să
́
p xê
́
p MergeSort co sô
́
thao tac so sanh la N *log(N). Do
́
́
́
́
̀
đo đô
̣
phƣc tap
̣
thơꢃ gꢃan cua MergeSort la
(N*log(N)) cꢑ nghꢋa là MergeSort là
̉
́
́
̀
̀
̣ ̣ ̣
tꢃêm cân vơꢃ thuât toan sắp xếp tốꢃ ƣu.
́ ́
Khꢃ xem xet so sánh các thuật toán cùng loꢂꢃ ngƣờꢃ ta thƣờng xꢒt độ phức tꢂp của thuật
́
toán trong các trƣờng hợp: trung binh (average case), trƣơng hơp
̣
xâ
́
u nhâ
́
t (the worst case) và
̀
̀
̣
trƣơng hơp tốt nhất (the best case).
̀
6
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
3.4. Các lớp thuật toán
Khꢃ chung ta noꢃ vê đô phƣc tap
dụng các ký hꢃệu hꢁnh thức
f(N) = (N) chúng ta sẽ nꢑꢃ thuật toán là tuyến tính (linear). Cꢑ thể tham khảo thêm:
f(N) = 1: hăng sô (constant)
(log(N)): logarit
(N): tuyên tinh (linear)
(N*log(N)): N log N
̀
̣
̣
thơꢃ gꢃan/ không gꢃan nhơ cua môt
̣
thuât
̣
toan thay vi sƣ
̉
̉
́
́
́
̀
́
́
̀
(f(n)) chúng ta cꢑ thể đơn gꢃản đề cập tớꢃ lớp của hàm f . Ví dụ
̀
́
f(N) =
f(N) =
f(N) =
f(N) =
f(N) =
́
́
(N2): bâc
(N3): bâc
̣
haꢃ (quadratic)
̣
3 (cubic)
f(N) = O(Nk) vơꢃ k la môt
̣
sô
(bN): hàm mꢓ (exponential)
Đốꢃ vớꢃ các bàꢃ toán đồ thị độ phức tꢂp
thƣơc cua đô thꢃ”
Xác định thờꢃ gꢃan thực hꢃện từ một gꢃớꢃ hꢂn tꢃệm cận
Đốꢃ vớꢃ hầu hết các thuật toán chúng ta cꢑ thể gꢊp các hꢗng số bị che đꢃ bởꢃ cách vꢃết O
b thƣơng la kha nho . Chăng han nêu đô phƣc tap thuât toan la
(N2) thꢁ chúng ta sẽ
thơꢃ gꢃan la 10N2 chƣ không phaꢃ la 107N2.
́ nguyên dƣơng: đa thƣc (polynomial)
́
̀
́
f(N) =
(V+E) cꢑ nghꢋa là “tuyến tính đốꢃ vớꢃ kích
̀
̣
.
̉
́
hoăc
̣
̣
́
̣
̣
̣
̀
̉
̀
̀
́
́
́
mong muô
́
̣ ̣
n chinh xac đô phƣc tap
́ ́
́
̉
̀
̀
́
̀
Cꢑ nghꢋa là nếu hꢗng số là lớn thꢁ thƣờng là theo một cách nào đꢑ lꢃên quan tớꢃ một vàꢃ
ng sô cua baꢃ toan. Trong trƣơng hơp nay tôt nhât l à gán cho hꢗng đꢑ một cáꢃ tên và đƣa nꢑ
vào ký hꢃệu tꢃệm cận của hꢗng số đꢑ.
hă
̀
́
̣
́
́
̉
̀
́
̀
̀
Ví dụ: bàꢃ toán đếm số lần xuất hꢃện của mꢕꢃ ký tự trong một xâu cꢑ N ký tự . Môt
̣
thuât
̣
̉
toán cơ bản là duyệt qua toàn bộ xâu đốꢃ vớꢃ mꢕ ꢃ ky tƣ
̣
đê thƣc
̣
hꢃên
u nhâ
ꢃ vơꢃ N . Nhƣng se la tô
̣
đê
́
m xem ky tƣ
̣
đo xuâ
́t
́
́
́
hꢃên
̣
bao nhꢃêu lâ
̀
n . Kích thƣớc của bảng chữ cáꢃ là cố định (nhꢃê
̀
́t la 255 đốꢃ vơꢃ ngôn
̀ ́
ngƣ lâp
̣
trinh C ) do đo thuât
̣
toan la tuyê
́
n tinh đô
́
́
t hơn nê
́
u vꢃê
́t la đô
̣
̀
̃
́
́
̀
́
̃
̀
̀
́
phƣc tap
̣
cua thuât
̣
toan la
(S*N) trong đo S la sô
́
phâ
̀
n tƣ cua bang chƣ caꢃ sƣ dun
̣
g . (Chú ý
̉
̉
̉
̉
̃
̉
́
́
̀
́
̀
́
là cꢑ một thuật toán tốt hơn để gꢃảꢃ bàꢃ toán này vớꢃ độ phức tꢂp là
Trong các cuôc thꢃ lâp trinh môt thuât toan thƣc hꢃên 1000000000 phꢒp nhân cꢑ thể
không thoa man rang buôc thơꢃ gꢃan. Chúng ta cꢑ thể tham khảo bảng sau để bꢃết thêm:
(S + N).
̣
̣
̣
̣
̣
̣
́
̀
̣
̉
̃
̀
̀
Độ phức tạp
Giá trꢁ N lớn nhất
100 000 000
40 000 000
10 000
(N)
(N log N)
(N2)
500
(N3)
7
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
90
20
11
(N4)
(2N)
(N!)
Thơi gian thƣc
̣
hiên
̣
cua cac thuât
̣
toan co đô
̣
phƣc tap
̣
khac nhau
̀
̉
́
́
́
́
́
O(Log(N))
10-7 giây
O(N)
10-6 giây
10-5 giây
10-4 giây
3 phút
O(N*Log(N))
O(N2)
O(N6)
O(2N)
1014 năm
10142 năm
O(N!)
̣
Chꢃ ý về phân tich thuât toan.
́
́
̉
̣ ̣
́t đê noꢃ về đô phƣc tap
́ ́
Thông thƣơng khꢃ chung ta trinh bay môt
̣
thuât
. Tuy nhꢃên trên thƣc
big-O – các kꢃểu khác không cꢑ nhꢃều gꢃá trị lắm , vꢁ cách này rất dꢄ gꢔ và cꢓng đƣợc nhꢃều
̣
toan cach tô
́
t nhâ
̀
́
̀
́
́
̀
thơꢃ gꢃan cua no la sƣ dun
̣
g cac chăn
̣
̣
tế chung ta hay dung ky phap
̉
̉
̀
́
̀
́
́
̀
́
́
̉
̣
́n va hꢃêu ro hơn . Nhƣng đƣng quên la bꢃg-O la chăn trên va thƣơng thi chung ta
̀ ̀ ̀ ̀ ̀ ̀ ́
̃
̀
ngƣơꢃ bꢃê
́
t đê
̀
sẽ tꢁm môt chꢊn trên càng nhꢐ càng tô
́
t.
Ví dụ: Cho môt mang đa đƣơc sắp A . Hꢆy xác định xem trong mảng A cꢑ haꢃ phần tꢅ
̣
̣
̉
̃
nào mà hꢃệu của chúng bꢗng D hay không. Hꢆy xem đoꢂn mꢆ chƣơng trꢁnh sau:
int j=0;
for (int i=0; i<N; i++)
{
while ( (j<N-1) && (A[i]-A[j] > D) )
j++;
if (A[i]-A[j] == D)
return 1;
}
̉
Râ
n, môꢃ lâ
thuật toán là O(N) vꢁ trong cả thờꢃ gꢃan thực hꢃện của thuật toán lệnh tăng j không chꢂy nhꢃều
hơn N lân.
́
t dê
̃
đê noꢃ ră
̀
ng thuât
̣
toan trên la O(N2): vòng lꢊp whꢃle bên trong đƣợc gọꢃ đến N
́ ̀
́
lầ
̃
̀
n tăng j lên tô
́
ꢃ đa N lâ
̣
̀n . Nhƣng môt phân tich tốt hơn se cho chung ta thấy rằng
̃
́
́
̀
8
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
Nê
́
u chung ta noꢃ ră
̀
ng thuât
̣
toan la O(N2) chúng ta vẫn đúng nhƣng nếu nꢑꢃ là thuật
́
́
́
̀
̣ ̣
toán là O(N) thꢁ chúng ta đꢆ đƣa ra đƣơc thông tꢃn chinh xac hơn về thuât toan.
́ ́
́
́
4. Câu truc dƣ liêu
̣
– Data structure
́
̃
Niklaus Wirth, một lập trình viên và nhà khoa học máy tính, ngƣời phát minh ra ngôn
ngữ lập trꢁnh Pascal đꢆ từng nói một câu nói nꢇi tiếng trong lꢋnh vực lập trꢁnh: Chƣơng trꢁnh
(Programs) = Cấu trúc dữ liệu (Data Structures) + Giải thuật (Algorithms). Câu nói này nói
lên bản chất của việc lập trꢁnh là đꢃ tꢁm một cấu trúc dữ liệu phù hợp để biểu diꢄn dữ liệu của
bài toán và từ đꢑ xây dựng giải thuật phù hợp với cấu trúc dữ liệu đꢆ chọn. Ngày nay với sự
phát triển của các kꢀ thuật lập trình, câu nói của Wirth không hẳn còn đúng tuyệt đối nữa
nhƣng nꢑ vẫn phản ánh sự gắn kết và tầm quan trọng của các cấu trúc dữ liệu và giải thuật.
Cấu trúc dữ liệu đƣợc sꢅ dụng để biểu diꢄn dữ liệu còn các giải thuật đƣợc sꢅ dụng để thực
hiện các thao tác trên các dữ liệu của bài toán nhꢗm hoàn thành các chức năng của chƣơng
trình
5. Các chiến lƣꢄc thiết kế thuật toán.
̉
Không co môt
̣
phƣơng phap nao co thê gꢃup chung ta xây dƣn
̣
g
(thꢃết kế) nên cac thuâ
̣
́
́
́
̀
́
́
́
toán cho tất cả các loꢂꢃ bàꢃ toán . Các nhà khoa h ọc máy tính đꢆ nghꢃên cƣu va đƣa ra cac
́
̀
́
chꢃê
́
n lƣơc
5.1. Duyệt toàn bộ (Exhausted search)
Chꢃến lƣợc duyệt toàn bộ là chꢃến lƣợc mà mꢕꢃ lập trꢁnh vꢃên phảꢃ nghꢋ đến đầu tꢃên khꢃ
̣ ̣ ̣ ̣
thꢃết kế cac gꢃaꢃ thuât chung nhất ap dung cho cac loaꢃ baꢃ toan khac nhau.
̉
́ ́ ́ ̀ ́ ́
gꢃảꢃ quyết bất cứ bàꢃ toán nào. Trong phƣơng pháp duyệt toàn bộ, chúng ta sẽ xem xꢒt tất cả
các ứng cꢅ vꢃên thuộc một không gꢃan cꢑ thể cꢑ của bàꢃ toán để xem đꢑ cꢑ phảꢃ là nghꢃệm của
bàꢃ toán hay không. Phƣơng pháp này yêu cầu cꢑ một hàm kꢃểm tra xem một ứng cꢅ vꢃên nào
đꢑ cꢑ phảꢃ là nghꢃệm của bàꢃ toán hay không. Mꢊc dù dꢄ hꢃểu song phƣơng pháp này không
phảꢃ là dꢄ thực hꢃện, và đꢊc bꢃệt là không hꢃệu quả đốꢃ vớꢃ các bàꢃ toán mà kích thƣớc ꢃnput
lớn. Cꢑ nhꢃều phƣơng pháp cảꢃ tꢃến hꢃệu năng của phƣơng pháp duyệt toàn bộ và chúng ta sẽ
xem xꢒt kꢀ hơn trong chƣơng 3.
5.2. Đệ qui quay lui – Backtracking
Chꢃến lƣợc đệ quꢃ quay luꢃ là một chꢃến lƣợc xây dựng thuật toán dựa trên quan hệ đệ
qui. Nghꢃệm của bàꢃ toán đƣợc mô hꢁnh hꢑa dƣớꢃ dꢂng một vecto, mꢕꢃ thành phần của vecto
nghꢃệm sẽ cꢑ một tập gꢃá trị cꢑ thể nhận và thuật toán sẽ tꢃến hành các bƣớc gán các gꢃá trị cꢑ
thể cho các thành phần của nghꢃệm để xác định đúng nghꢃệm của bàꢃ toán. Mꢊc dù không phảꢃ
bàꢃ toán nào cꢓng cꢑ thể áp dụng song các thuật gꢃảꢃ dựa trên phƣơng pháp đệ quꢃ quay luꢃ
luôn cꢑ vẻ đẹp từ sự ngắn gọn, súc tích mà nꢑ mang lꢂꢃ.
̉
̣
5.3. Chia đê tri (Divide and Conquer)
̉
Chꢃê
́
n lƣơc
̣
chꢃa đê trꢃ
la môt
̣
chꢃê
́
n lƣơc
̣
quan tron
̣
g trong vꢃêc
̣
thꢃê
́
t kê
́
cac gꢃaꢃ thuât
̣
. ꢘ
̉
̀
́
tƣơng cua chꢃê
́
n lƣơc
̣
nay nghe râ
́
t đơn gꢃan va dê
̃
nhân thâ
̣
́
y , đo la: khꢃ câ
̀
n gꢃaꢃ quyê
́
t môt
̣
baꢃ
̀
̉
̉
̉
̉
̀
̀
́
̀
9
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
toán, ta se tꢃến hanh chꢃa baꢃ toán đꢑ thành các bàꢃ toán nhꢐ hơn, gꢃảꢃ các bàꢃ toán nhꢐ hơn đꢑ,
̀ ̀
̃
sau đo kê
́
t hơp
Tuy nhꢃên vâ
cach hơp ly thanh cac baꢃ toan con , vꢁ nếu các bàꢃ toán con lꢂꢃ đƣợc gꢃảꢃ quyết bꢗng các
̣
nghꢃêm
̣
cua cac baꢃ toan nho hơn đo laꢃ
̣
thanh nghꢃêm
̣
cua baꢃ toan ban đâ
̀
u.
̉
̉
̉
́
́
̀
́
́
̀
̀
́
́
n đê
̀ kho khăn ơ đây nằm ơ haꢃ yếu tố
̉ ̉
́
: làm thế nào để chꢃa tách bàꢃ toán
môt
thuât
con se đƣơc
̣
̣
́
́
̀
́
̀
́
̣
̣ ̣
toan khac nhau thi sẽ rất phức tꢂp, yếu tố thƣ haꢃ la vꢃêc kết hơp lơꢃ gꢃaꢃ cua cac baꢃ toa n
̉ ̉
́ ́ ́ ̀ ̀ ́ ̀ ́
̀
̣
thƣc
Các thuật toán sắp xếp trộn (merge sort), să
toán chꢃa để trị (các thuật toán này đƣợc trꢁnh bày ở chƣơng 3).
Ví dụ[6, trang 57]: Trong vi du
này chúng ta sẽ xem xꢒt thuật toán tính aN
̣
hꢃên nhƣ thế nao?.
̣
̃
̀
́
p xếp nhanh (quick sort) đều thuộc loꢂꢃ thuật
̣
.
́
Đê tinh aN ta đê y công thƣc sau:
̉
̉
́
́
́
N = 0
aN
Õu N ch½n
nÕu N lÎ
̣ ̣
Tƣ công thƣc trên ta suy ra caꢃ đăt cua thuât toan nhƣ sau:
̉
́
̀
́
̀
int power(int a, int n)
{
if(n==0)
return 1;
else{
int t = power(a, n/2);
if(n%2==0)
return t*t;
else
return a*t*t;
}
}
́
̣
5.4. Chiên lƣơc tham lam (Greedy)
Chꢃến lƣợc tham lam là một chꢃến lƣợc xây dựng thuật toán tꢁm nghꢃệm tốꢃ ƣu cục bộ
cho các bàꢃ toán tốꢃ ƣu nhꢗm đꢂt đƣợc nghꢃệm tốꢃ ƣu toàn cục cho cả bàꢃ toán (trong trƣờng
hợp tꢇng quát). Trong trƣờng hợp cho nghꢃệm đúng, lờꢃ gꢃảꢃ của chꢃến lƣợc tham lam thƣờng
rất dꢄ càꢃ đꢊt và cꢑ hꢃệu năng cao (độ phức tꢂp thuật toán thấp).
̣
Chꢃ ý: Trong môt số baꢃ toán nếu xây dựng đƣợc hàm chọn thích hợp cꢑ thể cho nghꢃệm
̀
tố
ꢃ ƣu. Trong nhꢃêu baꢃ toan, thuât
̀
̣
toan tham ăn chi cho nghꢃêm
̣
gâ
̀
n đung vơꢃ nghꢃêm
̣
tố
ꢃ ƣu.
̀
́
́
̉
́
́
10
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
5.5. Qui hoạch động (Dynamic Programming)
Quꢃ hoꢂch động là chꢃến lƣợc xây dựng thuật toán để gꢃảꢃ quyết các bàꢃ toán tốꢃ ƣu, cꢑ
thể đòꢃ hꢐꢃ của bàꢃ toán không phảꢃ là các gꢃá trị quá chꢃ tꢃết mà chꢖ ở dꢂng gꢃá trị lớn nhất/nhꢐ
nhất là bao nhꢃêu chứ không đòꢃ hꢐꢃ cụ thể khꢃ nào, ở đâu để cꢑ thể đꢂt đƣợc gꢃá trị đꢑ. Trong
chꢃến lƣợc quꢃ hoꢂch động chúng ta sẽ xây dựng các quan hệ đệ quꢃ của bàꢃ toán, bàꢃ toán gốc
sẽ cꢑ lờꢃ gꢃảꢃ dựa trên các bàꢃ toán con (sub problems) dựa trên quan hệ đệ quꢃ. Các thuật toán
quꢃ hoꢂch động thƣờng sꢅ dụng các mảng để lƣu lꢂꢃ gꢃá trị nghꢃệm của các bàꢃ toán con và có
haꢃ cách tꢃếp cận: bottom up và top down.
6. Bài tập
Bài tập 1: Xây dƣn
̣ ̣
g sơ đồ gꢃaꢃ thuât cho baꢃ toan tinh số Fꢃbonacꢃ thƣ N , bꢃết rằng day
̉
̃
̀ ́ ́
́
số
Fꢃbonacꢃ đƣơc đꢃnh nghia nhƣ sau:
̣
̣
̃
F[0] = F[1] = 1, F[N] = F[N-1] + F[N-2] vơꢃ N ≥ 2.
́
̉
̣ ̣
g sơ đồ gꢃaꢃ thuât cho baꢃ toan tinh bꢃêu thƣc:
̉
̀ ́ ́
́
Bài tập 2: Xây dƣn
x x ... x , vơꢃ N sô
́
̣ ̣ ̣
x thƣc nằm trong cac dấu căn bâc haꢃ , N va x nhâp tƣ ban
́ ̀ ̀ ̀
́
phím.
̉
̣ ̣ ̣
phần tƣ a[i][j] đƣơc goꢃ la đꢃêm
̉
̀
Bài tập 3: Trong môt
yên ngƣa cua ma trân (saddle point) nê
nhât trên côt
̣
ma trân
̣
haꢃ chꢃê
̀
u câ
́
p MxN , môt
n tƣ nho nhất trên hang ꢃ va phần tƣ lơn
̉
̀ ̀ ́
̣
̣
́
u nhƣ no la phâ
̀
̉
̉
̉
́
̀
̉
́
̣
j cua ma trân
̣
. Chăng han
̣
a[2][0] = 7 là môt
̣
phâ
̀
n tƣ yên ngƣa
̣
trong ma trân
̣
sau:
̉
̉
1 2 3
4 5 6
7 8 9
Hꢆy vꢃết chƣơng trꢁnh tꢁm tất cả các đꢃểm yên ngựa của một ma trận nhập vào từ bàn
phím và đƣa ra độ phức tꢂp của thuật toán.
Bài tập 4: Cho môt ma trân ki ch thƣơc MxN gô
̣
̣
̀m cac số nguyên (cꢑ cả số âm và
́
́
́
dƣơng). Hꢆy vꢃết chƣơng trꢁnh tꢁm ma trận con của ma trận đꢆ cho sao cho tꢇng các phần tꢅ
̉
̣ ̣
con đo lơn nhất co thê đƣơc (bàꢃ toán maxꢃmum sum plateau). Hꢆy đƣa ra đánh
́ ́ ́
trong ma trân
gꢃá về độ phức tꢂp của thuật toán sꢅ dụng.
Bài tập 5: Vꢃêt chƣơng trinh nhâp vao cac hê
́
̣
̣ ̣
́ cua môt đa thƣc (gꢃả sꢅ các hệ số là
̉
́
sô
̣
n x la môt số nguyên ) và một gꢃá trị x 0. Hꢆy tính gꢃá trị của đa thức
̀
̀
́
̀
nguyên va đa thƣc co bꢃê
́
̀
́
́
theo công thƣc Horner sau:
́
Nê
f(x) = a0 + x*(a1+x*(a2+x*(….+x(an-1+an*x)…) (Công thƣc Horner).
́
u f(x) = an*xn + an-1*xn-1+ .. +a1*x + a0 thꢁ
́
Bài tập 6: Cho 4 hꢁnh hộp kích thƣớc bꢗng nhau , mô
̃
ꢃ măt
̣
cua hinh hôp
̣
đƣơc
̣
tô bằng 1
̉
̀
trong 4 màu xanh, đo, tím, vàng. Hꢆy đƣa ra tất cả các cách xê
́
p cac hinh hôp
̣
thanh 1 dꢆy sao
̉
́
̀
̀
cho khꢃ nhin theo cac phia trên xuống , đằng trƣơc va đằng sau cua day đều co đu ca 4 màu
́ ̀ ́
̃
̉ ̉ ̉
́
̀
́
xanh, đo, tím vàng.
̉
11
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
Bài tập 7: Hꢆy vꢃết chƣơng trꢁnh nhanh nhất cꢑ thể đƣợc để ꢃn ra tất cả các số nguyên
co haꢃ chƣ sô
số
́.
́
̃
Bài tập 8: ꢈp dụng thuật toán sàng để ꢃn ra tất cả các số nguyên tố nhꢐ hơn N.
12
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
́
́
CHƢƠNG II: SĂP XÊP (SORTING) VÀ TꢅM KIẾM (SEARCHING)
1. Bài toán sꢆp xếp
́
́
1.1. Săp xêp trong (Internal Sorting)
Sắp xếp đƣợc xem là một trong những lꢋnh vực nghiên cứu cꢇ đꢃển của khoa học máy
tính. Trƣớc khꢃ đꢃ vào các thuật toán chi tiết chúng ta cần nắm vững một số khái niệm cơ bản
sau:
+ Một trƣờng (field) là một đơn vị dữ liệu nào đꢑ chẳng hꢂn nhƣ tên, tuꢇi, số đꢃện thoꢂi
của một ngƣời ...
+ Một bản ghi (record) là một tập hợp các trƣờng
+ Một file là một tập hợp các bản ghi
Sắp xếp (sorting) là một quá trình xếp đꢊt các bản ghi của một file theo một thứ tự nào
đꢑ. Vꢃệc xếp đꢊt này đƣợc thực hiện dựa trên một hay nhiều trƣờng nào đꢑ, và các thông tꢃn
này đƣợc gọi là khóa xắp xếp (key). Thứ tự của các bản ghꢃ đƣợc xác định dựa trên các khóa
khác nhau và việc sắp xếp đốꢃ đƣợc thực hiện đối với mꢕi khóa theo các thứ tự khác nhau.
Chúng ta sẽ tập trung vào các thuật toán xắp xếp và giả sꢅ khóa chꢖ gồm 1 trƣờng duy nhất.
Hầu hết các thuật toán xắp xếp đƣợc gọi là các thuật toán xắp xếp so sánh: chúng sꢅ dụng hai
thao tác cơ bản là so sánh và đꢇi chꢕ (swap) các phần tꢅ cần sắp xếp.
Các bàꢃ toán sắp xếp đơn gꢃản đƣợc chꢃa làm haꢃ dꢂng.
̣ ̣ ̣
Sắp xếp trong (internal sorting): Dƣ lꢃêu cần sắp xếp đƣơc lƣu đầy đu trong bô nhơ
̃
̉
́
trong để thực hꢃện thuật toán sắp xếp.
́
́
1.2. Săp xêp ngoài (External Sorting)
Săp xêp ngoaꢃ (external sorting): Dƣ lꢃêu
́
́
̣
câ
̉
̣
thê lƣu vao bô nhơ trong đê sắp xếp , các thao tác truy cập dữ lꢃệu cꢓng mất nhꢃều thờꢃ gꢃan
̀ ́
̀n sắp xếp co kich thƣơc qua lơn va không
́ ́ ́ ́ ̀
́
̀
̃
̉
hơn.
Trong pham
thê dƣ lꢃêu săp xêp se la môt
trƣơng khoa), và để tập trung vào các thuật toán chúng ta chꢖ xem xꢒt các trƣờng khꢑa của các
̣
vꢃ cua môn hoc
̣
nay chung ta chi xem xet cac thuât
̣
toan să
́
p xê
́
p trong . Cụ
̉
̀
́
̉
́
́
́
̉
̣
́
́
̣
mang cac ban ghꢃ (gô
̀
m haꢃ trƣơng chinh la trƣơng dƣ lꢃêu
̣
va
̃
̃
̀
̉
́
̉
̀
̀
̀
̃
̀
́
̀
́
bản ghꢃ này, các ví dụ mꢃnh họa và càꢃ đꢊt đều đƣợc thực hꢃện trên các mảng số nguyên , coi
nhƣ la trƣơng khoa cua cac ban ghꢃ.
̉
̉
̀
̀
́
́
́
́
1.3. Săp xêp gián tiếp
Khi các bản ghi có kích thƣớc lớn việc hoán đꢇi các bản ghi là rất tốn kꢒm, khꢃ đꢑ để
giảm chꢃ phí ngƣời ta có thể sꢅ dụng các phƣơng pháp sắp xếp gián tiếp. Việc này có thể đƣợc
thực hiện theo nhiều cách khác nhau và môt trong những phƣơng pháp đꢑ là tꢂo ra một file
mới chứa các trƣờng khóa của fꢃle ban đầu, hoꢊc con trꢐ tới hoꢊc là chꢖ số của các bản ghi ban
đầu. Chúng ta sẽ sắp xếp trên file mới này với các bản ghꢃ cꢑ kích thƣớc nhꢐ và sau đꢑ truy
cập vào các bản ghꢃ trong fꢃle ban đầu thông qua các con trꢐ hoꢊc chꢖ số (đây là cách làm
thƣờng thấy đối với các hệ quản trị cơ sở dữ liệu).
13
́
́
Bài giảng môn học: Phân tich thiêt kê va đánh giá giải thuật
̀
́
Ví dụ: chúng ta muốn sắp xếp các bản ghi của fꢃle sau đây:
Index
Dept
123
23
Last
First Age ID number
1
2
3
4
Smith
Wilson
Charles
Shilst
Jon
3
4
234-45-4586
345-65-0697
508-45-6859
234-45-5784
Pete
2
Philip 9
Greg
45
8
Sau khi sắp xếp xong để truy cập vào các bản ghi theo thứ tự đꢆ sắp xếp chúng ta sꢅ
dụng thứ tự đƣợc cung cấp bởi cột index (chꢖ số). Trong trƣờng hợp này là 3, 2, 4, 1. (chúng
ta không nhất thiết phảꢃ hoán đꢇi các bản ghi ban đầu).
1.3. Các tiêu chuẩn đánh giá một thuật toán sꢆp xếp
Các thuật toán sắp xếp có thể đƣợc so sánh với nhau dựa trên các yếu tố sau đây:
+ Thời gian thực hiện (run-time): số các thao tác thực hiện (thƣờng là số các phép so
sánh và hoán đꢇi các bản ghi).
+ Bộ nhớ sꢅ dụng (Memory): là dung lƣợng bộ nhớ cần thiết để thực hiện thuật toán
ngoàꢃ dung lƣợng bộ nhớ sꢅ dụng để chứa dữ liệu cần sắp xếp.
+ Một vài thuật toán thuộc loꢂꢃ “ꢃn place” và không cần (hoꢊc cần một số cố định) thêm
bộ nhớ cho việc thực hiện thuật toán.
+ Các thuật toán khác thƣờng sꢅ dụng thêm bộ nhớ tꢖ lệ thuận theo hàm tuyến tính hoꢊc
hàm mꢓ vớꢃ kích thƣớc file sắp xếp.
+ Tất nhiên là bộ nhớ sꢅ dụng càng nhꢐ càng tốt mꢊc dù việc cân đối giữa thời gian và
bộ nhớ cần thiết có thể là có lợi.
+ Sự ꢇn định (Stability):Một thuật toán đƣợc gọi là ꢇn định nếu nhƣ nꢑ cꢑ thể giữ đƣợc
quan hệ thứ tự của các khóa bꢗng nhau (không làm thay đꢇi thứ tự của các khóa bꢗng nhau).
Chúng ta thƣờng lo lắng nhiều nhất là về thời gian thực hiện của thuật toán vì các thuật
toán mà chúng ta bàn về thƣờng sꢅ dụng kích thƣớc bộ nhớ tƣơng đƣơng nhau.
Ví dụ về sắp xếp ꢇn định: Chúng ta muốn sắp xếp fꢃle sau đây dự trên ký tự đầu của các
bản ghꢃ và dƣớꢃ đây là kết quả sắp xếp của các thuật toán ꢇn định và không ꢇn định:
14
Tải về để xem bản đầy đủ
74 trang
19640
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Phân tích thiết kế và đánh giá thuật toán - Trường Đại học Hàng Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_phan_tich_thiet_ke_va_danh_gia_thuat_toan_truong.pdf
