Bài giảng Thuật toán nâng cao

***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 thoán - Các kỹ thuật thiết kế thuật toán - Vận dụng giải quyết các bài toán cụ thể ***Nội dung: - Giới thiệu - Chứng minh tính đúng đắn - Độ phức tạp - Đệ quy - Chia để trị - Quy hoạch động - Thuật toán tham lam - Quay lui - Thuật toán xác xuất - Lớp các bài toán NP đầy đủ - Thuật toán xấp xỉ

pdf239 trang | Chia sẻ: diunt88 | Lượt xem: 2860 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Bài giảng Thuật toán nâng cao, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
                         !"#$ %&' ($%&  ) *+ '   ,  -  , %%  ,  .,/0($%&0  1 2    34  5   6! 789: ;<  = > 6>?!>"@AB 5C  $?@7B <    1 D ?/'/@ /$@B <E  F  =?/ !> !!B <G<   , !" !?@@/ " !7B GC  F "?&  B 2EE   ,AAH?>& &"7@ " !7B2GG  I4>&)JK ?)L!>"@@B ;;   ,AH>AM ? >>A!  " !7B;N< ;    ,>"4<  O!:&&     ,>"4   ! 1'   &!= KP 'P  ,    % 9!  E     <Q R/ " !7SQTQ!@SQUQI@7@7S VQVQV'@7SW)@77<GGCQ Q >@/@XY@7@Z" !@7SWL3 /@"SWQ[ SQ \/@' ASU/7@@@  "S<GG2Q 2Q 7!>"@AYSWQX @"SU[RIS CCNQ ;Q X  7@7 / " !7SZ"]@/.QZ S ^ UQ T>]SZ//7L_@7"@S<G`2Q EQ Z" !Z "77 /!>  "!"@ASR  ) &@SI@@@7Sa'@7] @A 7S CC<Q NQ  @Z]!>@) !!S."!@ SXQ  S Z//7L_@7"@S<G`<Q 5Q " #R@@Q N     Wb '#   &    7   -  ,  ' ,?&   /&/B  -  ,&%c\@?\@ 7]!B   ,/P?@@ " !B  d#J   ! 1'   &'P  KP  W   ' ( + > e> >&f+ H '+ /0 0  1    ' > *+ (> >'+ /0  T'#8  !%!""#$ % KP  %$(  g<C% C   > (  " ! (                    `     !( ,h ,? " !B   ," !=/iAD  e&(> /0#/j "' k!l(> > != 'HP  T 'HP   !!=> e> >($%'HP  3(> >  A m&AmnCop ' AD  3(> >  AE m&A; mA2 m/A m@Am]nCo O (> >c$   !!=(> >   ) *&( ,' e    e  " q ,&k!=j ",>   G      ,   K 0+  ,,>  ?>B'  ?>B   ,l"   ?@BS %    !" '4 !/j "' <C      , k=7r  He!  s  3    , h    * ! ,  + + > *  3( > e  &, H  s <<     +  HK  ,  + c$  +  j   +   ,> k  +  $( <     + c$?<B   ,> (>/0 H( !t/j "' 6   u " !=!t/j "' 0  1  .+ /0  [:>A%>v/J!=/i D  Xj "' o <;2E  %$( o< 2;E <2     + c$? B  ) e> >  [7  > Jw "#%> g $ > (S % 9 6 8  c'D +  9  Xiil7:>A%>   ,O c$ x    .+ /0 /j "'o <E;2 4<o ↔ <;2E 4 o <;2E 42o< ;↔ 2E 4;o< 2 ; E <;     +  j    ,> (/g7 !=7r&4A D  .+ /0   ,O /g x  ,> y "@ ?≠ CB nz @/y "@ <E     +   ,> k    ,> (lq(  q {  | !b&4 8 S&4%> @7{l 8 > ( lAD }  .+ /0   ,O  ,> kx 4<oAnC 4 ovA"#< q(!AAr< 42o] ?A∈~L S B @  4 <N     +  $(   ,> (7w /0 $( €#! +      =  4  .+ /0   , $( ex <?B &@ >n< ] ]! < / >n>‚ @/] @/  ?B &@ ] ?nCB@?<B @"7@ @??L<BB @/] @/ <5     q(  ,?<B  O  P q(  ,     6  j 8  #  j    6  # l>j 8  #' +    [e€  rSj (Ss  T   6  +    j ƒSj Ss <`     q(  ,? B   > e> >q( j    6  j ( 8 h) 7 "% l>j 8  # ]?PB @ s @"7@ s @/] ] s ]! s  s / s @/] y "@ ?B/ s @/y "@  <G     .+ /0 <  O  O  P/  QJ q 9'<EvYQ 9  J> ( 8  % 1 O  1 "Hl "  9 J!=    Hx C     .+ /0 <  3(> >    9 A%> => 'vY @ 6 8 &H„Q[ OS!b J"H  9 !f  vY @ 6 8 g $ > (Q   l>AH Ho> (!f<EvY   l>&  o( 7w AAH"H"    S> (!f`vY  % j" vYr…" l7w /0SJ P"J!f vY ==   <     .+ /0 <  3(> >I 7.@ 7   9  vY1 !f != t #  %! !:S 9 O " J"H  % S 9 "&pvY'g !fS 8 !fvY != t #  ==+++       .+ /0 <  3(> >PAw "†   9 7:>A%> =>  @ 6 8  P/K   9  ‡%>'vY @ 6 8 #  %"!f vYg 7 > ( 7{   l"l+   Wf vY @> e> > !%! D> *   l>AH Ho;"J!fvY   l>&  o2Q N  3(> > u O † M   9  A#!f vY"H =+++  2     .+ /0   , * 7r #   , * :W- EN5 < 2;  N` <5C< <<2; EN5 NGGN5` ;     .+ /0   , *Z EN5 < 2; EN5 <<2; <5C<  N` NGGN5`  E     .+ /0   , *ˆL,>  [7 = $(  ,x ` ; C < < ` < E < ; < < C C 5 C N C E EN5 <  2 ;      N     .+ /0  %!7r > Y> *' =l 8    , * :W- '  , *Z P7w /0 Y> *' Y>=   ,ˆL,>7w /0 Y> *' C> Y>=  [r > Y>> 0  ='7r  j 7r K !b7r #  [r > Y> *&k!'4!' "J"l" 7r  j 7r K  !b7r #  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 Cf &#  ‹fo 9  > Y> *K  7r #O   j 7r &f;> Y> *K  7r #O h  j 7rQ %>0S > Y> *K  7r #O h  j 7r &f;> Y> *K  7r #O h; j 7rSs  J * 7r #o ' &Q3 I ' V " j  ' > (K 7r Se8 &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&IBm V&V & n? I<Ch m VB?&I<Ch m&VB n I&I<C m I&V<Ch m V&I<Ch m V&V n I&I<C m? I&V m V&IB<Ch m V&V 1  * ' &&fj K  ' &SJ7w /0;> Y> * 2C     .+ /0   , *‰   1 D Š  3(!7r > Y> * ' &&fj K  ' &g ; ArŒ2  [r > Y> *7w /0&f ,l  " !CQEG '4≥ !   * 7r #  "4S ,l     e ,4 qo >n I&I $n V&V n? I m VB?&I m VB Oo & n I&I<C m? I&V m V&IB<Ch m V&V n>L $B<Ch m$  2<     .+ /0   , *‰   1 D Š CEN5< 2;  * 7r&4/D %$( CE< ; NC CE2; <5C N5< `C; N52; C 5` NGGN5` CE2;  * 7r&4/D %$( C2 C C; < C E2 < <E E; C C <5C 2     .+ /0 2o+ A  .o!=7r #A' !=7r #  *!  V onA   ,e( %nC & n< &'& nA &% % % <  nA &%  22     .+ /0 2o+ A   , D > *  3(!7r > Y>  ‹fo7w /0%$(    #:o%h nC A nAh Ah %  A nAL< A      A2E nA2; A  A2; nA<5 A<5  A<5 nA<N A  A<N nA` A`  A` nA; A;  A; nA A  A nAA 2;     .+ /0 2o+ A   , D > * * Q  !b&+ D > * ‰ < Š &f+ [‡ ‰ C Š &f+ ‡ 2Q ‡ q>+ [‡&# H ;Q %$(o + AO [ M " &  > e ‡ M "  *'4A :Jg A  2E     .+ /0 2o+ A   , D > * 1/&f/i D > *o@L<@L s@C %@L< nC & n<hh nC &'& nA &% % % L  C n %@ n< & nA &% &% 2N     .+ /0 2o+ A   , D > *  .+ /0on2En<CCC<<? B 5A2E< EA<5< 2A`C A;C <A C CA< 7r > Y> *@  25     .+ /0 2o+ A   , D > *o( +  1/ D > *K o  3( 7w  9  $   + AQ3Ž" 'D + &+&#r…? HB&1/SŽ " %$( r …OlQ JoŽn>S> nAnAZ>  O  (vK ZŽL<  ZŽL< n<Q  % ZŽL< &f[‡Q.,ŽL< nŽ A  ZŽL< nCQ  % ZŽL< &f[Q.,ŽL< nŽ (  l>oŽL< nŽ AZŽL<  .,o>L AZ>LB AZ>LmZ>L<  k €o  = =           ==  =  2`     .+ /0 2o+ A   , D > *oO (> >r ex    + A<E <Q n<En<<<< Q [‡ [‡ [‡ [‡ 2Q [‡ [‡ [‡ ;Q :J&fAS 9 OoA SA2SANSA5SA<;SA<E .,S 9 7w /0N> Y> *  #S 9 O  1 + A<E &fo A SA2SANSA< SA<E nA< A2  M "  u J7w /0E> Y> *  2G     .+ /0 2o+ A  ) e> >47r  A nA%n<  A nAL< A%" 7r #r  A n?AB7 %n7'4"47r #r  p  H K ' 7<  .+ /0on<E  /0 ,1 +  A2 ' E'4nA2Q  A2 nA AS>/0 ,+ A  A nAA  E n; S>/0 ,+ ;  ; n? B  > Y> *+ ;S2> Y> *+ ES > Y> *+  A2Q.,E> Y> *+ A<E ;C     ) *+ '   ,  X8 '+  HK  ,   6! 789:   = > 6>         !                 ; "     1! 789:   u  k , %$( ! l7 !=7r&4 8     $(    €# ,7w /0 K !+      =  4  ;2 # $       8 !  1! w ?@7B   8  ,#,>/j "'' $  7%$(  I† %   6! 789:?@@77>]B   6! k , %$(9'4 !/j "' ;;    L O  8  L  1 >/0   , > 6> L &((! + 9 :  L ((!+ 9 : Le( e LX  8   () *"+ ,    ;E         W=' !  PP' ,P   K  ,  A ,   9  +  , ;N    %      PP ?>@/7B  +  H! /j "'> ( ( !i  T,P ?>7/7B  +  H! %$( K  ,> ( ( !i  .+ /0   ! D   p  H!( bA~<QQ >@/7o≥ < >7/7o!n!?A~‘<≤ ≤ B  ;5 $      K  ,  " ,>  !" #$%& '(  ,  $    8   ,  c   ,"9%r… K  O  ( !i ,P ;`  &    ‡ , ? 77@B  " !=*" !( &=# K   ,  .+ /0 ’AC“ AnAm ’A“  A ,l7w /0   6! 789:   9  +  ,  .%"  ;G      [w /0A ,1  9  +  ,  .+ /0 !?A~<QQB &@ ’≥ <“ !nA~< ’!nA~<“ ] ]!  / ’ ≤ ≤ “ ] ?!A~B @ !nA~ @/] ’!n!?A~<SA~ SsSA~B“ @/] @?!B @/ EC          6! 9:!=> J?>  "@@77B   6! k /j "' ( !iPP %$(  ,7{  ( !i ,P   6! 9:> J? "@@77B   6! k ,9:!=> J'  , /g  &4  6! 789:  ) *+  K  ,  ) *+ 78 (  fK !b&4Aw"†% K   ,  E<         †   ) L PP  F L ,P  Z L  ,  Z9:%'4/j "' ( !i) Z7{   %$(  ( !iF  /g7 !=7r&4Aw "† j   †  ’)“Z ’F“ E         &4e&(  ‡D PP ' ,P   9  +  ,&k  ” #!A , "#$ % K  ,7    PPl ( !i  A ,r…> (&  ! ,P   6! k!b&4Aw "†S ,g A  ,4Aw"†%A ,7 Aw "†  E2  '(          W=7r $: H9" e &(  I J8  I Ph{    I "q> E; )(    Xi" J8 Z ’)C“ R< ’)<“ s ’)L<“ R ’)“ s ’)L<“ R ’)“ F: % )  )C ’)L<“R ’)“Sn QQ )  F  ’)“Z’F“  M "o % LPP) &  !A , J# L!b*" &  !A ,%>  @ LA ,r… &  ! ,P   L/i" J8Z 9  EE )(     .+ /0  T &%A'  ,  De6 ' &QT c D &%A' Q  )n’An Sn&“  Fn’An&Sn “ ’An Sn&S!>  O  D“ !>nA ’An Sn&S!>n “ An ’An&Sn&S!>n “ n!> ’An&Sn S!>n “ EN )(     I PZ ’)C“ ] ?B @ ’S)C“ R< ’S)<“ @"7@ ’•S)C“ R ’•S ) “ @/] F: % )  )C O  D ZX )<  F •ZX )  F  ’)“Z’F“  M "o % LPP) &  !A , J# LO  1lD   L(   P &  ! ,P   L" PZ 9  E5 )(      .+ /0   ! D  p  HK  ' &'4 ≠ & >@/7o ≠ & >7/7o!n!? S&B I Z ’ ≠ &“ ] ? –&B @ ’ –&“ !n ’ –&S!n “ @"7@ ’ &“ !n& ’ &S !n&“ @/] ’ –&S!n “&  !!n!? S&B ' ’ &S!n&“&  !!n!? S&B .,’>@/7“Z’>7/7“ E` )(     W=" 'Œ"q>"9  <Q %O /gSO  ( !i ,P Q O /g 7 !=7r&4 j   % u +  H<9  u " )*+ , -  9:!=> Jl 6! &f$ >  q#!#$./0,  9:> JJ 6!  #!  ,'1  EG  * %+   D  M W=#!#$./0, R" !=2 3  ( !io 9  &:J'Œ"q> Q $   "q>?6 "P9B &H&%'Œ"q>R" 9 2Q   p'Œ"q> ?6"P7 B  &H&%'Œ"q>R > (&  ! ,P  I "q>Z ) ’R“ y "@ ?B/ ’SR“ !n ’R“ @/y "@ ’•SR“ F AD l&H&%'Œ"q>S M "i  6! l ,9:!=> J NC  * %+    .+ /0   ! D   p  H!( bA~<QQ >@/7o≥ < >7/7o!n!?A~‘<≤ ≤ B !?A~<QQB &@ !nA~< ] ]!  / ] ?!A~B @ !nA~ @/] @/] @?!B @/ !?A~<QQB &@ n<S!nA~ y "@ ?– B/ nm< ] ?!A~B @ !nA~ @/] @/y "@ @?!B @/  N<  * %+    .+ /0 )o≥ < Fo!n!?A~‘<≤ ≤ B !?A~<QQB &@ n<S!nA~ ’!n!?A~ŽSŽn<QQB“ y "@ ?– B/ ’–S!n!?A~ŽSŽn<QQB“ nm< ] ?!A~B @ !nA~ @/] ’!n!?A~ŽSŽn<QQB“ @/y "@ ’nS!n!?A~ŽSŽn<QQB“ @?!B @/ -./"0123 Rn’!n!?A~ŽSŽn<QQB“ -453 L %n<S!nA~< R9 L %–S7   8   *'Œ"q>SR't9 L %nS!n!?A~ŽSŽn<QQB  + " ,P N ,   1  6! 'Œ"q>/g7 !=7r&4"q> j S u JAD  !/g?@! ]B  D  M  T!o→8" !/g%O  ( !io <Q"(! Q%P9 ?>BCS%?>BnC P 7    ,AY  &
Tài liệu liên quan