Bài giảng Thuật toán nâng cao - Nguyễn Thanh Bình
Thu t toán nâng cao
Nguyꢀn Thanh Bình
Khoa Công nghꢁ Thông tin
Trꢂꢃng Čꢄi hꢅc Bách khoa
ꢆꢄi hꢅc ꢆà Nꢇng
M c čích
• Các khái niꢁm liên quan Č%n bài toán và
gi(i quy%t bài toán
• Phân tích và Čánh giá thu,t toán
• Các k- thu,t thi%t k% thu,t toán
• V,n d0ng gi(i quy%t các bài toán c0 th1
2
1
N i dung
• Gi4i thiꢁu
7
• Ch6ng minh s8 Čúng Č:n
• ꢆ= ph6c tꢄp (complexity)
• ꢆꢁ quy (recursion)
• Chia Č1 trD (divide and conquer)
• Quy hoꢄch Č=ng (dynamic programming)
• Thu,t toán tham lam (greedy algorithms)
• Quay lui (backtracking)
41
70
122
152
191
290
355
• Thu,t toán xác xuHt (probabiliste algorithms) 399
• L4p các bài toán NP ČJy ČK (NP-complete) 442
• Thu,t toán xHp xM (approximation algorithms) 461
3
ꢀánh giá
• Bài t,p l4n 1
¢ Tóm t:t bài báo khoa hꢅc
• Bài t,p l4n 2
¢ Tìm hi1u và trình bày m=t chK ČP vP thu,t
toán
• Thi k%t thúc môn hꢅc
4
2
Tài li u tham kh o
1.
Introduction to algorithms, T.H. Cormen, C.E. Leiserson,
R.R. Rivest, Mit Press 1990.
2.
Type de Données et Algorithmes, M-C Gaudel, M. Soria, C.
Froidevaux, Ediscienne international, 1993.
3.
Cours Complexité, M. Daniel, ESIL, 2006.
4.
Data structures and algorithms, Alfred V. Aho, John E.
Hopcroft, Addison-Wesley, 1983.
5.
6.
7.
Algorithm Analysis and Computational Comlexity, Ian
Parberry, Lecture Notes, University of North Texas, 2001.
The Art of Computer Programming, Volume 2, D. Knuth,
Addison-Wesley, 1981.
Các tài liꢁu khác trên Internet.
5
Bài t p l n
• Mbi hꢅc viên chꢅn trình bày mꢀt trong các chꢁ
Čꢂ sau
¢ K- thu,t nhánh và c,n (branch and bound)
¢ K- thu,t bi%n Čci Fourier (Fourier transform)
¢ Thu,t toán di truyPn (genetic algorithm)
• Yêu cJu
¢ Tìm hi1u và trình bày vP chK ČP
¢ Minh hoꢄ và gi(i thích phꢂeng pháp bfi ít nhHt 2 ví d0
c0 th1
¢ ꢆánh giá và phân tích gi(i pháp các ví d0
¢ Hꢅc viên t8 tìm ki%m các tài liꢁu liên quan Č%n chK ČP
• K%t qu(
¢ Báo cáo tg 10 Č%n 20 trang
¢ Báo cáo ph(i trích dꢃn rꢄ ràng các tài liꢁu tham kh(o
6
3
Gi i thi u (1)
Nguyꢀn Thanh Bình
Khoa Công nghꢁ Thông tin
Trꢂꢃng Čꢄi hꢅc Bách khoa
ꢆꢄi hꢅc ꢆà Nꢇng
Gi i thi u
• Khái niꢁm gi(i thu,t/thu,t toán (algorithm)
¢ Thu,t toán là m=t dãy xác ČDnh các thao tác ce b(n áp
d0ng trên dj liꢁu vào nhkm Čꢄt Čꢂlc gi(i pháp cho m=t
vHn ČP
¢ Hai vHn ČP
• Tìm m=t phꢂeng pháp gi(i quy%t vHn ČP
° Gi(i pháp cho ax2 + bx + c = 0 : rp ràng và xác ČDnh
° Gi(i pháp cho ax5 + bx4 + cx3 + dx2 + ex + f = 0 : không có
gi(i pháp tcng quát
• Tìm m=t gi(i pháp hiꢅu quꢆ
¢ Phân biꢁt gi(i thu,t và chꢂeng trình
• Chꢂeng trình là cài Čqt thu,t toán bkng m=t ngôn ngj l,p
trình
8
4
Gi i thi u
• Thu,t toán
¢ ThK t0c tính toán nh,n t,p các dꢇ liꢅu vào
(input) và tꢄo các dꢇ liꢅu ra (output)
¢ Thu,t toán Čꢂlc gꢅi là Čúng Čꢈn (correct),
n%u thuꢉt toán d ng cho k"t quꢆ Čúng v4i
mꢅi dj liꢁu vào
9
Gi i thi u
• Thu,t toán hkng ngày trong cu=c srng
¢ NHu cem
• …
¢ Gꢅi Čiꢁn thoꢄi
• Thu,t toán trong toán hꢅc/tin hꢅc
¢ Nhân hai ma tr,n
¢ Tính tích phân
¢ Gi(i hꢁ phꢂeng trình b,c nhHt
¢ …
10
5
Gi i thi u
• Các tính chHt cKa thu,t toán
¢ Tính tcng quát
¢ Tính hju hꢄn
¢ Tính không nh,p nhkng
¢ Tính hiꢁu qu(
11
Gi i thi u
• Tính tcng quát (1)
¢ Thu,t toán ph(i áp d0ng cho tHt c( các mtu dj
liꢁu vào ch6 không chu là m=t mtu dj liꢁu vào
c0 th1
¢ Ví d0
• S:p x%p tvng dJn m=t dãy các giá trD
• Dj liꢁu vào :
• K%t qu(
2
1
1
2
4
3
3
4
5
5
:
12
6
Gi i thi u
• Tính tcng quát (2)
¢ Phꢂeng pháp
• So sánh hai phJn tw liên ti%p nhau tg trái qua ph(i,
n%u không Čúng th6 t8 thì hoán Čci vD trí chúng
Bꢂ4c 1: 2 ↔ 1
4
4
3
3
5
5
5
5
Bꢂ4c 2:
Bꢂ4c 3:
Bꢂ4c 4:
2
1
1
1
2
2
4 ↔ 3
3
4
• Dãy Čã Čꢂlc s:p x%p
• Thu,t toán có tcng quát không ?
• Không
° Ví d0 dj liꢁu vào: 2 1 5 4 3
13
Gi i thi u
• Tính hju hꢄn
¢ Thu,t toán ph(i dgng sau m=t sr bꢂ4c xác
ČDnh
¢ Ví d0
nh,p n
while (n ≠ 0)
n = n œ 2
endwhile
¢ Thu,t toán có dgng không ?
14
7
Gi i thi u
• Tính không nh,p nhkng
¢ Các thao tác trong thu,t toán ph(i Čꢂlc Čqc t( chqt ch{
• | mbi bꢂ4c th8c thi, bꢂ4c ti%p theo s{ Čꢂlc th8c thi ph(i
Čꢂlc xác ČDnh rõ ràng
¢ Ví d0
Bꢂ4c 1: x = 0
Bꢂ4c 2: tvng x lên 1 hoqc gi(m x xurng 1
Bꢂ4c 3: if (x [-2,2]) then
goto Bꢂ4c 2
¢ Thu,t toán có nh,p nhkng ?
15
Gi i thi u
• Tính hiꢁu qu(
¢ Thu,t toán ph(i sw d0ng hiꢁu qu( ngu€n tài nguyên máy
tính
• Thꢃi gian
• B= nh4
¢ Ví d0
gt1 (n)
begin
gt2 (n)
begin
p = 1
if (n = 0) return (1)
else
return (n*gt(n-1))
endif
end
for i from 1 to n do
p = p * i;
endfor
end
¢ Thu,t toán nào hiꢁu qu( hen ?
16
8
Gi i thi u
• ꢆqc t( thu,t toán (1)
¢ Có nhiPu cách Čqc t( thu,t toán
• Không hình th6c
° Ngôn ngj t8 nhiên
• Nja hình th6c
° Kêt hlp ngôn ngj t8 nhiên và các kí hiꢁu toán hꢅc
° Se Č€ khri, ngôn ngj gi(, …
• Hình th6c
° Các kí hiꢁu toán hꢅc
° Ngôn ngj Z, ngôn ngj B, …
17
Gi i thi u
• ꢆqc t( thu,t toán (2)
¢ Chꢅn phꢂeng pháp Čqc t( nja hình th6c
• Ngôn ngj gi( t8a C/Pascal k%t hlp ngôn ngj t8 nhiên
if (ČiPu kiꢁn) then
…
else
…
endif
while () do
…
endwhile
for … from … to … do
…
endfor
18
9
Gi i thi u
• Ví d0 1
¢ Có 15 h=p Činh có chiPu dài khác nhau. CJn
Čqt chúng vào trong 15 ngvn kéo. Chúng ta
cJn ph(i th8c hiꢁn th% nào Č1 có th1 lHy Čꢂlc
loꢄi Činh chúng ta cJn m=t cách nhanh nhHt?
19
Gi i thi u
• Ví d0 1
¢ Gi(i pháp thô
• Chúng ta x%p các h=p Činh vào các ngvn kéo theo th6 t8
bHt k„. Sau Čó, mbi khi cJn lHy Činh chúng ta mf các
ngvn kéo theo th6 t8 tg trái qua ph(i.
• Trꢂꢃng hlp xHu nhHt: ph(i mf 15 ngvn kéo
• Trꢂꢃng hlp trung bình: gi( sw xác xuHt lHy các loꢄi Činh
ngang nhau, ph(i mf 8 ngvn kéo
i =
=
ƒ
• N%u nhjng loꢄi Činh trong các ngvn kéo curi cùng luôn
Čꢂlc sw d0ng, cJn nhiPu lJn mf các ngvn kéo
20
10
Gi i thi u
• Ví d0 1
¢ Gi(i pháp Las Vegas
• Chúng ta chꢅn ngvn kéo Č1 mf m=t cách ngtu nhiên
° N%u may m:n, chúng ta có loꢄi Činh cJn lHy
° N%u không, chúng ta loꢄi bp ngvn kéo vga mf, th8c
hiꢁn mf ngvn kéo khác m=t cách ngtu nhiên
+
+
+
=
i =
ƒ
21
Gi i thi u
• Ví d0 1
¢ Gi(i pháp tiPn xw lð
• Chúng ta s:p x%p các h=p Činh theo th6 t8 chiPu dài cKa
chúng
• X%p vào các ngvn kéo theo th6 t8 trên
• N%u lꢄi mf các ngvn kéo tg trái sang ph(i thì s{ không
thu Čꢂlc lli ích gì
• Mf các ngvn kéo theo phꢂeng pháp tìm ki%m nhD phân
• Trꢂꢃng hlp xHu nhHt: 4 lJn mf ngvn kéo
• Trꢂꢃng hlp trung bình: 3.26
+
+
+
=
• Gi(i pháp chu có ð nghMa khi chúng ta thꢂꢃng xuyên mf
các ngvn kéo lHy Činh
22
11
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân hai sr nguyên
¢ Thu,t toán nhân B:c M-
5 6 7
1 2 3 4
2 2 6 8
1 7 0 1
1 1 3 4
5 6 7
6 9 9 6 7 8
23
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân Anh
5 6 7
1 2 3 4
5 6 7
1 1 3 4
1 7 0 1
2 2 6 8
6 9 9 6 7 8
24
12
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân ˆ-r,p
5
6
7
0
0
1
1
2
0
1
2
2
1
2
3
4
0
5
6
7
1
6
0
2
8
4
4
1
8
1
9
5
2
9
0
6
7
8
¢ So sánh Č= hiꢁu qu( các thu,t toán ?
25
Gi i thi u
• Ví d0 2
¢ ꢆ%m sr phép toán nhân và c=ng Čꢂlc th8c hiꢁn
• Thu,t toán nhân B:c M- và thu,n toán nhân Anh ČPu sw
d0ng 12 phép nhân và 15 phép c=ng
• Thu,t toán ˆ-r,p sw d0ng 12 phép nhân và 20 phép c=ng
• Sr phép toán ph0 thu=c vào sr chj sr cKa mbi sr nguyên
° Sr phép nhân bkng m*n v4i m và n lJn lꢂlt là sr chj sr cKa
mbi sr nguyên
26
13
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân Nga
567
283
141
70
35
17
8
1234
2468
4936
#u Či$m: không cJn
ghi nh4 các k%t qu(
nhân trung gian, chu
cJn th8c hiꢁn phép
c=ng và chia cho 2
9872
19744
39488
78976
157952
315904
631808
699678
4
2
1
27
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân « chia Č1 trD »
• Sr chj sr cKa hai sr nguyên ph(i bkng nhau và ph(i bkng
lu- thga 2
° N%u sr chj sr cKa hai sr nguyên khác nhau thì thêm vào các
sr 0 f bên trái
• Ð tꢂfng: chúng ta thay phép nhân cKa hai sr nguyên có n
chj sr bfi 4 phép nhân cKa hai sr nguyên có n/2 chj sr.
Ti%p t0c, thay phép nhân cKa hai sr nguyên có n/2 chj sr
bfi 4 phép nhân cKa hai sr nguyên có n/4 chj sr, …
• CJn nhân hai sr nguyên: a và b. Gꢅi aL và aR là hai nja
trái và ph(i cKa sr a, tꢂeng t8 bL và bR là hai nja trái và
ph(i cKa b
28
14
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân « chia Č1 trD »
aL
bL
aR
bR
*
aLbR
aRbL
aRbR
+ aLbL
aLbL + (aLbR +aRbL) + aRbR
a*b
= (aL*10n/2+ aR)*(bL*10n/2+ bR)
= aL*bL*10n + aL*bR*10n/2 + aR*bL*10n/2 + aR*bR
= aL*bL*10n + (aL*bR + aR*bL)10n/2 + aR*bR
ꢆ1 nhân a và b bfi các nja cKa a và b, cJn sw d0ng 4 phép nhân
29
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân « chia Č1 trD »
• Gi(m sr phép nhân a và b bfi các nja cKa a và b tg 4
xurng còn 3
ꢆqt:
p = aL*bL
q = aR*bR
r = (aL + aR)*(bL + aR)
Khi Čó:
a*b
= aL*bL*10n + (aL*bR + aR*bL)*10n/2 + aR*bR
= p*10n + (r œ p - q)*10n/2 + q
• Sr phép nhân sw d0ng bfi thu,t toán này Čꢂlc Čánh giá
là n*m0.59 v4i n ≥ m
• Khi nhân hai sr nguyên khá l4n, thu,t toán này Čꢂlc
Čánh giá nhanh hen các thu,t toán trꢂ4c
30
15
Gi i thi u
• Ví d0 2
¢ Thu,t toán nhân « chia Č1 trD »
0567 * 1234
nhân
sr bꢂ4c dDch
k%t qu(
60
170
804
2278
05 12
05 34
67 12
67 34
4
2
2
0
05 * 34
nhân
0 3
0 4
5 3
sr bꢂ4c dDch
k%t qu(
2
1
1
0
0
0
699678
15
20
5 4
170
31
Gi i thi u
• Ví d0 3: tính xn
¢ Vào: m=t sr nguyên x và m=t sr nguyên
không âm n
¢ Ra: y = xn
¢ Thu,t toán Čen gi(n
if n = 0 then
y = 1
else
y = x
endif
for i from 1 to n do
y = y * x
endfor
32
16
Gi i thi u
• Ví d0 3: tính xn
¢ Thu,t toán nhD phân
• Gi(m sr phép toán
• Ð tꢂfng: sw d0ng các k%t qu( trung gian
• Nguyên t:c: n%u n/2 = 0 thì xn = xn/2 * xn/2 n%u không thì
xn = xn-1 * x
• Ch•ng hꢄn
° x35 = x34 * x
° x34 = x17 * x17
° x17 = x16 * x
° x16 = x8 * x8
° x8 = x4 * x4
° x4 = x2 * x2
° x2 = x * x
33
Gi i thi u
• Ví d0 3: tính xn
¢ Thu,t toán nhD phân
1. Bi1u diꢀn n bfi dãy nhD phân
2. Thay mbi bít nhD phân
« 1 » bfi các kí hiꢁu SX
« 0 » bfi các kí hiꢁu X
3. Xoá cqp kí hiꢁu SX bên trái nhHt
4. K%t qu(: cách tính xn trong Čó
S nghMa là bình phꢂeng
X nghMa là nhân v4i x
B:t ČJu tg x
34
17
Gi i thi u
• Ví d0 3: tính xn
¢ Thu,t toán nhD phân
Bi1u diꢀn n bfi dãy nhD phân: ek-1ek-2…e0
if ek-1 = 0 then
y = 1 // khi n = 0
else
y = x
endif
for i from k-2 to 0 do
y = y * y
if ei = 1 then
y = y * x
endif
endfor
35
Gi i thi u
• Ví d0 3: tính xn
¢ Thu,t toán nhD phân
• Ví d0: n = 35 = 100011(2)
ei
y
x
sr phép nhân
1
0
0
0
0
1
1
x2
x4
1
2
3
5
7
x8
x17
x35
36
18
Gi i thi u
• Ví d0 3: tính xn
¢ Thu,t toán nhD phân: gi(i thích
p
i
n =
Ai
• Bi1u diꢀn nhD phân cKa n:
ƒi=
• Gi( sw chúng ta Čang trong quá trình tính xn. Gꢅi j là vD trí
bít bên curi cùng (trái nhHt) bi1u diꢀn n, yj là k%t qu( curi
cùng có Čꢂlc. Ban ČJu: j = p, yp = x = xAp
• Có hai kh( nvng cKa Aj-1
° Aj-1 = 1. Thay th% Aj-1 bfi SX. V,y yj-1 = yj2 * x
° Aj-1 = 0. Thay th% Aj-1 bfi S. V,y yj-1 = yj2
C( hai trꢂꢃng hlp: yj-1 = yj2 * xAj-1
• V,y: yp-1 = yp2 * xAp-1 = (xAp)2 * xAp-1 = x2Ap + Ap-1
• Bkng truy h€i:
i
p
i=
Ai
y = xƒ
= xn
37
Gi i thi u
• Ví d0 3: tính xn
¢
Thu,t toán nhD phân: có gi(i pháp trt hen ?
•
Ch•ng hꢄn tính x15
1. n = 15 = 1111
2. SX
3.
SX
SX
SX
SX
SX
SX
4. B:t ČJu bfi x, chúng ta có: x2, x3, x6, x7, x14, x15
V,y, chúng ta sw d0ng 6 phép nhân
Tuy nhiên, chúng ta có th1 tính x15 bfi:
x2, x3, x6, x12, x15 = x12 * x3
NghMa là chu cJn sw d0ng 5 phép nhân
38
19
Gi i thi u
• Ví d0 3: tính xn
¢ Phꢂeng pháp ꢂ4c sr
• xn = x n%u n = 1
• xn = xn-1 * x n%u n là sr nguyên tr
• xn = (xr)s n%u n = r * s v4i r là ꢂ4c sr nguyên tr nhp nhHt
cKa n và s > 1
¢ Ví d0: n = 15
• 15 = 3 * 5, khi Čó x15 = (x3)5. Êp d0ng thu,t toán Č1 tính
x3 và c5 v4i c = x3.
• x3 = x2 * x, áp d0ng thu,t toán tính x2
• x2 = x * x
• c5 = c4 * c, áp d0ng thu,t toán tính c4
• c4 = (c2)2
• 2 phép nhân tính c4, 3 phép nhân tính c5, 2 phép nhân tính
x3. V,y 5 phép nhân tính x15
39
Gi i thi u
• Phân tích và Čánh giá các thu,t toán
¢ D8a vào các tính chHt cKa thu,t toán
¢ Ch6ng minh s8 Čúng Č:n
¢ ꢆánh giá Č= ph6c tꢄp
40
20
Tải về để xem bản đầy đủ
239 trang
16580
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thuật toán nâng cao - Nguyễn Thanh Bình", để 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:
- bai_giang_thuat_toan_nang_cao_nguyen_thanh_binh.pdf
- TrangBia-TTNC.pdf
