Giáo trình Thuật toán nâng cao| Giáo trình môn Cấu trúc dữ liệu và thuật toán| Trường Đại học Bách Khoa Hà Nội

Giáo trình Thuật toán nâng cao| Giáo trình môn Cấu trúc dữ liệu và thuật toán| Trường Đại học Bách Khoa Hà Nội. Tài liệu gồm 239 trang giúp bạn ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem.

 



 

!"#$%&'
($%&
)*+' ,
- ,%% ,
.,/0($%&0 1
2

34 5
6!789: ;<
= >6>?!>"@AB 5C
$?@7B <
1 D ?/'/@/$@B <E
F=?/!>!!B <G<
,!"!?@@/"!7B GC
F"?&B 2EE
,AAH?>&&"7@"!7B2GG
I4>&)JK ?)L!>"@@B ;;
,AH>AM ?>>A!"!7B;N<
;

,>"4<
O!:&&
,>"4
!1' &!=KP 'P ,

%9!
E
 
<Q R/"!7SQTQ!@SQUQI@7@7S
VQVQV'@7SW)@77<GGCQ
Q >@/@XY@7@Z"!@7SWL3/@"SWQ[SQ
\/@'ASU/7@@@"S<GG2Q
2Q 7!>"@AYSWQX@"SU[RIS CCNQ
;Q X7@7/"!7SZ"]@/.QZS^UQ
T>]SZ//7L_@7"@S<G`2Q
EQ Z"!Z"77/!>"!"@ASR
)&@SI@@@7Sa'@7]@A7S CC<Q
NQ @Z]!>@)!!S."!@ SXQS
Z//7L_@7"@S<G`<Q
5Q "#R@@Q
N
 
Wb'#&
 7
- ,' ,?&/&/B
- ,&%c\@?\@7]!B
,/P?@@"!B
d#J
!1' &'P KP
W ' (+>e>>&f+H '+ /0
0 1
 ' >*+(>>'+ /0
T'#8 !%!""#$%KP
%$(
g<C% C
>( "!(
 



 
`

!(,h,?"!B
," !=/iADe&(>
/0#/j "'k!l(>>!=
'HP
T'HP
!!=>e>>($%'HP
3(>>A
m&AmnCop ' AD
3(>>A
E
m&A
;
mA
2
m/A
m@Am]nCoO
(>>c$
!!=(>>
)*&(,'e
e" q,&k!=j ",>

G

,
K 0+,,> 
?>B'  ?>B
,l"  ?@BS
% !"'4
!/j "'
<C

,k=7r
He!
s
3
,h
*!,
++>*
3(>e&,H
s
<<

+HK,
+c$
+j
+,>k
+$(
<

+c$?<B
,>(>/0H( !t/j
"'6 u " !=!t/j "'
0 1
.+ /0
[:>A%>v/J!=/i D
Xj "' o <;2E
%$( o< 2;E
<2

+c$? B
)e>>
[7>Jw "#%>g $>(S
%96 8  c'D + 9
Xiil7:>A%>
,O c$x

.+ /0 /j "'o <E;2
4<o <;2E
4 o 
<;2E
42o< ; 2E
4;o< 2 ; E
<;

+j
,>(/g7!=7r&4A
D
.+ /0
,O /gx
,>
y"@ ? CB
nz
@/y"@
<E

+,>k
,>(lq( q{
| !b&48S&4%>@7{l8>(
lAD}
.+ /0
,O ,>kx
4<oAnC
4 ovA"#<q(!AAr<
42o] ?A~L S •B@
4
<N

+$(
,>(7w /0$( €#!
+

= 4
.+ /0
,$(ex
<?B
&@
>n<
] ]! < /
>n>•
@/]
@/
 ?B
&@
] ?nCB@?<B
@"7@
@?•?L<BB
@/]
@/
<5

q( ,?<B
O Pq( ,
6
j 8 #
j6
#l>j 8 #' + 
[e€ rSj (Ss
T6
+ 
j ƒSj Ss
<`

q( ,? B
>e>>q( j6
j ( 8h)7"%l>j 8 #
]?PB@
s
@"7@
s
@/]
] s ]! s  s /
s
@/]
y"@ ?B/
s
@/y"@

<G

.+ /0 <
O <E=>O P/QJ
q9'<EvYQ9
J>(8% 1 O 1 "Hl
"9J!=Hx
C

.+ /0 <
3(>>
9A%>=>'vY@6 8
&H„Q[OS!bJ"H9!f 
vY@6 8 g $>(Q
l>AHHo>(!f<EvY
l>&o( 7w AAH"H"
S>(!f`vY
%j"vYr…"
l7w /0SJP"J!f vY
==

<

.+ /0 <
3(>>I7.@7
9vY1 !f !=t#
%!!:S9O "J"H
%S9"&pvY'g!fS8
!fvY!=t#

==+++

.+ /0 <
3(>>PAw "†
97:>A%>=>@6 8 P/K
9
‡%>'vY@6 8 #
%"!f vYg 7>( 7{
l"l+
Wf vY@>e>>!%!D>*
l>AHHo;"J!fvY
l>&o2Q N
3(>>u O †M9A#!f
vY"H
=+++

2

.+ /0
,*7r #
,*:W-
EN5
< 2;
 N`
<5C<
<<2;
EN5
NGGN5`
;

.+ /0
,*Z
EN5
< 2;
EN5
<<2;
<5C<
 N`
NGGN5`

E

.+ /0
,*ˆL,>
[7= $( ,x
`
;
C
<
<
`
<
E
<
;
<
<
C
C
5
C
N
C
E
EN5
<

2
;



N

.+ /0
%!7r >Y>*' =l8
,*:W- ' ,*ZP7w
/0< >Y>*' <E>Y>=
,ˆL,>7w /0< >Y>*' C>Y>=
[r >Y>>0 ='7r j 7r K!b7r #
[r >Y>*&k!•'4!' "J"l" 7r j 7r K
!b7r #

5

.+ /0
,*
N2<`C`<



2G;``<5
<G5;;2E

;G2N<;<
;N` `2
< 2;EN5
NGGN5`
#$oJ
4 %$(
*Su
J8>Y>
=' 
`

.+ /0
,*‰ 1 D Š
[r j 7r K7r #>(&k' >(&k
"- g
%7r j 7r K7r # #!'
7r Cf &#
fo9>Y>*K7r #O 
j 7r &f;>Y>*K7r #O h j 7rQ
%>0S>Y>*K7r #O h j 7r
&f;>Y>*K7r #O h;j 7rSs
J*7r #o' &Q3
I
'
V
" j
' >(K7rSe8 &
I
' &
V
" j'
>(K&

G

.+ /0
,*‰ 1 D Š
I
V
&
I
&
V
I
&
V
V
&
V
m
I
&
I
V
&
I
I
&
I
m?
I
&
V
m
V
&
I
Bm
V
&
V
•& n?
I
•<C
h
m
V
B•?&
I
•<C
h
m&
V
B
n
I
•&
I
•<C
m
I
•&
V
•<C
h
m
V
•&
I
•<C
h
m
V
•&
V
n
I
•&
I
•<C
m?
I
•&
V
m
V
•&
I
B<C
h
m
V
•&
V
1 *' &&fjK' &SJ7w /0;>Y>*
2C

.+ /0
,*‰ 1 D Š
3(!7r >Y>*' &&fjK' &g ;
ArŒ2
[r >Y>*7w /0&f,l
" •!
CQEG
'4 !
*7r # "4S,l
e,4
qo >n
I
•&
I
$n
V
•&
V
n?
I
m
V
B•?&
I
m
V
B
Oo
•& n
I
•&
I
•<C
m?
I
•&
V
m
V
•&
I
B•<C
h
m
V
•&
V
n>•<C
m?z >L $B•<C
h
m$

2<

.+ /0
,*‰ 1 D Š
CEN5•< 2;
* 7r&4/D %$(
CE< ; NC
CE2; <5C
N5< `C;
N52; C 5`
NGGN5`
CE•2;
* 7r&4/D %$(
C2 C
C; < C
E2 < <E
E; C C
<5C
2

.+ /0 2o+A
.o!=7r #A' !=7r #
*!
VonA
,e(
%nC&
n<
&'&
nA
&%
% % < 
n•A
&%

22

.+ /0 2o+A
,D >*
3(!7r >Y>
fo7w /0%$( 
#:o%h nC A
nA
h
•A
h 
%
A
nA
L<
•A
•
A
2E
nA
2;
•A
A
2;
nA
<5
•A
<5
A
<5
nA
<N
•A
A
<N
nA
`
•A
`
A
`
nA
;
•A
;
A
;
nA
•A
A
nA•A
2;

.+ /0 2o+A
,D >*
<Q 1/&f/iD >*
Q !b&+D >*
< Š &f+ [‡
C Š &f+ ‡
2Q ‡ q>+ [‡&#H
;Q %$(o+A
O
[M" &>e
‡M" *'4A
:Jg A

2E

.+ /0 2o+A
,D >*
1/&f/iD >*o@
L<
@
L
s@
C
%@
L<
nC&
n<hhnC
&'&
nA
&%
% % L  C
n•
%@
n<&
n•A
&%
&%
2N

.+ /0 2o+A
,D >*
.+ /0on2En<CCC<<
? B
5A
2E
<
EA
<5
<
2A
`
C
A
;
C
<A
C
CA<
7r >Y>*@

25

.+ /0 2o+A
,D >*o(+
1/D >*Ko
3( 7w 9$ +A
Q3Ž" 'D +
&+&#r…?HB&1/S
Ž
" %$( r
…OlQJoŽn>S
>
nAnA
Z>
O (vKZ
ŽL<
Z
ŽL<
n<Q% Z
ŽL<
&f[‡Q.,
ŽL<
n
Ž
•A
Z
ŽL<
nCQ% Z
ŽL<
&f[Q.,
ŽL<
n
Ž
(l>o
ŽL<
n
Ž
•A
ZŽL<
.,o
>L<
n
>
•A
Z>L<
n?A
Z>
B
•A
Z>L<
nA
Z>mZ>L<
k€o
=
=
==
=
2`

.+ /0 2o+A
,D >*oO (>>rex
•+A
<E
<Q n<En<<<<
Q [‡ [‡ [‡ [‡
2Q [‡ [‡ [‡
;Q :J&fAS9OoA
SA
2
SA
N
SA
5
SA
<;
SA
<E
.,S97w /0N>Y>*
#S9O 1 +A
<E
&fo
A
SA
2
SA
N
SA
<
SA
<E
nA
<
•A
2
M" u J7w /0E>Y>*

2G

.+ /0 2o+A
)e>>47r
A
nA%n<
A
nA
L<
•A%" 7r #r
A
n?A
B
7
%n•7'4"47r #r p H
K' 7•<
.+ /0on<E
<En2•ESO A
<E
n?A
2
B
E
Q •>/0,1 +
A
2
'
E
'4nA
2
Q
A
2
nA
•AS>/0,+A
A
nA•A
E
n
;
•S>/0,+
;
;
n?
B
>Y>*+
;
S2>Y>*+
E
S >Y>*+
A
2
Q.,E>Y>*+A
<E
;C

)*+' ,
X8'+HK,
6!789:
= >6>
| 1/239

Preview text:

! " # $ % & ' ( $ % & ) * + ' , - , % % , ., /0 ( $ % & 0 1 3 4 5 6 ! 78 9 : ;< = > 6 > ? !>"@A B 5C $ ? @ 7 B < 1 D ?/ ' /@ / $ @ B F = ?/ ! > !! B , ! " ! ? @@/ " !7B GC F " ?& B 2EE , A A H ?> & & " 7 @ " !7B 2GG I4> & ) J K ? )L !>"@ @B ;; , AH> AM ? >> A ! " !7B ;N< 2 ,> "4 < O! : & & ,> "4 ! 1 ' & != K P 'P , % 9 ! ; R / " !7S QTQ !@ S QUQ I@ 7@ 7 S VQVQ V '@7 S W ) @77 Q >@ /@ X Y@7 @ Z" !@7S WL 3 /@"S WQ [ S Q \ /@' AS U/ 7 @ @ @ "S 2Q 7 !>"@A YS WQ X @"S U[RIS CCNQ ;Q X 7 @7 / " !7S Z"] @/ .Q Z S ^ UQ T > ] S Z// 7 L_@7"@ S EQ Z" ! Z " 7 7 / !> " !"@A S R ) &@ S I@ @ @7S a '@ 7 ] @A 7S CCNQ @ Z ] !> @ ) !! S . " !@ S XQ S Z// 7 L_@7"@ S 5Q " # R @ @ Q E Wb ' # & 7- , ' , ?& / & /B - , & % c \ @ ?\ @ 7] !B , / P ? @ @ " !B d# J ! 1 ' & 'P K P W ' ( + > e > > &f + H '+ /0 0 1 ' > * + ( > > '+ /0 T ' # 8 ! %! " " # $ % K P % $ ( g > ( " ! ( N ! ( , h , ? " !B , " != /i A D e&( > /0 # /j " ' k! l ( > > != 'H P T 'H P ! != > e > > ( $ % 'H P 3 ( > > A m &A m n C o p ' A D 3 ( > >
AE m &A; m A2 m /A m @A m ] n C o O ( > > c $ ! != ( > > ) * & ( , ' e e " q , &k != j ",> ` , K 0 + , ,> ? > B ' ? > B , l " ? @ BS % !" '4 ! /j " ' G , k = 7r H e! s 3 , h * ! , + + > * 3 ( > e &, H s + H K , + c $ + j + ,> k + $ ( << + c $ ?, > ( > /0 H ( !t /j " ' 6 u " != !t /j " ' 0 1 .+ /0 [:> A%> v /J != /i D Xj " ' o < ; 2 E % $ ( o < 2 ; E < + c $ ? B ) e > > [ 7 > J w " # %> g $ > ( S % 9 6 8 c 'D + 9 4 ; 2 E 4 o < ; 2 E 4 2o < ; ↔ 2 E 4 ;o < 2 ; E Xi i l 7:> A%> , O c $ x .+ /0 /j " ' o < E ; 2 <2 + j , > ( /g 7 != 7r & 4 A D .+ /0 ,> y "@ ? ≠ CB n z @ /y "@ , O /g x <; + ,> k , > ( l q ( q { | !b & 4 8 S & 4 %> @ 7{ l 8 > ( l A D } .+ /0 4 4 o v A "# < q (! A A r < 4 2o ] ?A ∈~L S •B @ 4 , O ,> k x + $ ( , > ( 7w /0 $ ( € # ! + = 4 .+ /0 < ? B ? B &@ &@ > n < ] ? n CB @ ?] ] ! < / @"7@ > n > • ‚ @ ? • ? L@ /] @ / ] @ / @ / , $ ( e x q ( , ?O P q ( , 6 j 8 # j 6 # l> j 8 # ' + [e € r S j (S s T 6 + j ƒS j S s <5 q ( , ? B > e > > q ( j 6 j ( 8 h) 7 " % l> j 8 # ] ? P B @ s @"7@ s y "@ ?B / @ / ] s @ /y "@ ] s ] ! s s / s @ /] <` .+ /0 < O O P / Q J q 9 ' v Y Q 9 J > ( 8 % 1 O 1 "H l " 9 J != H x .+ /0 < 3 ( > > 9 A%> => ' v Y @ 6 8 &H „Q [ OS !b J "H 9 !f v Y @ 6 8 g $ > ( Q l> AH H o > ( !f v Y l> & o ( 7w A A H "H " S > ( !f ` v Y = = % j " v Y r … " l 7w /0 S J P "J !f v Y C .+ /0 < 3 ( > > I 7 .@ 7 9 v Y 1 !f != t # % ! !: S 9 O " J "H % S 9 " &p v Y 'g !fS 8 !f v Y != t # + + + = = < .+ /0 < 3 ( > > P Aw "† 9 7:> A%> => @ 6 8 P / K 9 ‡%> ' v Y @ 6 8 # % " !f v Y g 7 > ( 7{ l "l + Wf v Y @ > e > > ! %! D > * l> AH H o ; "J !f v Y l> & o 2Q N + + + = 3 ( > > u O † M 9 A # !f v Y "H .+ /0 , * 7r # , * : W- E N 5 < 2 ; N ` < 5 C < < < 2 ; E N 5 N G G N 5 ` 2 .+ /0 , * Z E N 5 < 2 ; E N 5 < < 2 ; < 5 C < N ` N G G N 5 ` ; .+ /0 , * ˆL ,> E N 5 C C C < E N 5 < < < C ; < < 2 E ` < ; C ; ` [ 7 = $ ( , x E .+ /0 %! 7r > Y> * ' = l 8 , * : W- ' , * Z P 7w /0 < > Y> * ' Y> = , ˆL ,> 7w /0 < > Y> * ' C > Y> = [r > Y> > 0 = ' 7r j 7r K !b 7r # [r > Y> * &k !• '4 ! ' "J " l " 7r j 7r K !b 7r # N .+ /0 , * EN5 < 2; `2 ;N` <;< ;G2N # $ o J 4 % $ ( * S u 2E J 8 > Y> <5 2G;`` = ' < N2<`C` NGGN5` 5 .+ /0 , * ‰ 1 D Š [r j 7r K 7r # > ( &k ' > ( &k " - g % 7r j 7r K 7r # #! ' 7r C f ‹ f o 9 > Y> * K 7r # O j 7r &f ; > Y> * K 7r # O h j 7rQ %> 0 S > Y> * K 7r # O h j 7r &f ; > Y> * K 7r # O h; j 7rS s J * 7r # o ' &Q 3 ' " j I V ' > ( K 7r S e 8 & ' & " j ' I V > ( K & ` .+ /0 , * ‰ 1 D Š I V • & & I V & & I V V V m & & I I V I & m ? & m & B m & I I I V V I V V •& n ? •B•?& •I V I V n
•& ••& ••& ••& I I I V V I V V n •& ••& B•& I I I V V I V V 1 * ' & &f j K ' &S J 7w /0 ; > Y> * G .+ /0 , * ‰ 1 D Š 3 (! 7r > Y> * ' & &f j K ' & g ; A r Œ 2 q o > n •& I I $ n •& V V n ? m B•?& m B I V I V Oo •& n
•& ••& B••& I I I V V I V V n >• L $B•[r > Y> * 7w /0 &f , l " •!CQEG '4 ≥ ! * 7r # "4 S , l e , 4 2C .+ /0 , * ‰ 1 D Š CEN5 • < 2; * 7r & 4 /D % $ ( CE < ; NC CE 2; <5C CE • 2; N5 < `C; * 7r & 4 /D % $ ( N5 2; C 5` C 2 C C ; < C NGGN5` E 2 < E ; C C <5C 2< .+ /0 2o + A . o != 7r # A ' != 7r # *! V o n A , e ( % n C & n < &'& n A & % % % < n • A & % 2 .+ /0 2o + A , D > * 3 (! 7r > Y> ‹ f o 7w /0 % $ ( # : o % h n C A n A h • A h % A n A L< • A • A2E n A2; • A A2; n A<5 • A<5 A<5 n AAA` n A; • A; A; n A • A A n A • A 22 .+ /0 2o + A , D > * 1 / &f /i D > * Q !b &+ D > * ‰ < Š &f + [‡ ‰ C Š &f + ‡ 2Q ‡ q> + [‡ H ;Q % $ (o + A O [ M " & > e ‡ M " * '4 A : J g A 2; .+ /0 2o + A , D > * 1 / &f /i D > * o @ @ s@ L< L C %@ n C & L< n < hh n C &'& n A & % % % L C n • %@ n < & n • A & % & % 2E .+ /0 2o + A , D > * .+ /0o n 2E n @ 7r > Y> * < A C A C < A; C A` C 2 A<5 < E A2E < 5 2N .+ /0 2o + A , D > * o ( + 1 / D > * K o = = 3 ( 7w 9 $ + A Q 3 Ž " 'D + &+ r … ? H B & 1 / S " % $ ( r Ž … O l Q J o Ž n >S n A n AZ> > O ( v K ZŽL< Z
ŽL< n % ZŽL< &f [‡Q ., ŽL< n Ž • A Z ŽL< n CQ % ZŽL< &f [Q ., ŽL< n Ž ( l>o ŽL< n Ž • AZŽL< ., o n
• AZ>L< n ?AZ>B • AZ>L< n A Z> m Z>L< >L< > k € o = = = 25 .+ /0 2o + A , D > * o O ( > > r e x • + An Q [‡ [‡ [‡ [‡ 2Q [‡ [‡ [‡ ;Q : J &f AS 9
Oo A S A2S ANS A5S A<;S A., S 9 7w /0 N > Y> * # S 9 O 1 + AA S A2S ANS A< S AM " u J 7w /0 E > Y> * 2` .+ /0 2o + A ) e > > 4 7r A n A % n < A n A L< • A % " 7r # r A n ?A B7 % n • 7 '4 " 4 7r # r p H K ' 7 • < .+ /0o n O A /0 , 1 + A2 ' E '4 n A2Q A2 n A • AS > /0 , + A A n A • A E n ; • S > /0 , + ; ; n ? B > Y> * + ;S 2 > Y> * + ES > Y> * + A2Q ., E > Y> * + A2G ) * + ' , X8 ' + H K , 6 ! 78 9 : = > 6 > ;C