"!$#&%'(#*),+-/.1032547698'(#:%;-=<>#6@?BA

CEDGFIHJLKJNMPOQDSR&TUWV&JNMXZY\[5]/^=[$_/`E`a_cb$de]gfih>jf>_/`Edek>lnm op"q r sutwvGxcyz|Ncz\~xt,/7qSq\q\qSq\qSqSq\q\qSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq p"q r@q tw@twIycy|z\|v/z qSq\q\qSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq p"q r@q tw@twz7u,¡ ¢,£3¤¥§¦ ¨ecytw©,yªv«v twIc¬"/v«­cz\cz|7zc/z$® pp"q r@qp ¯°±ct"cz\czScytw©,yª,vv t,@¬@§,v«­§z§c|N7,||­§zLqSq\qSq\qSq\qSqSq ²p"qZ³´t"z°µ z|¶x§ctwv«,@·¸qSq\q\qSq\qSqSq\q\qSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq ¹p"qº¼»u©,t,y±cv«zScz\~t5¬"Igtw@yNzS5,7cnc½/c|¾tw@yNª±§zv«9q\qSq\qSq\qSq\qSq\qSqSq ¹p"qºp¼¿ytw©yª,v«v tw@¬@§,v«­cz\z¶cyt,x§Àv«z|¾Á t,cv«|twq\qSq\qSq\qSq\qSq\qSqSq ¹p"q  ¯c§7twc|W§z\ª±§Ãcz|NczSv yz|ÄqSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq Åp"q Âcq tw@twc@|z°yÆÇgtw@yÆÇy7©wcz°yN/@yz ¨ey7@y|z$®ÈqSqSq\qSq\qSq\qSq\qSq\qSqSq 7rp"q Âcq tw@twIycy|zG7zSv«7vt,y|twÉqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq wp"q Âcqp tw@twE¨3cv«,§ze®Ê7zScytw©yª,v«v tw@¬@§,v«­cz\7,||­§z9q\qSqSq 5pp"qºË¼»¾yxcyz7|¶x§§,yz|Nczyz7ª±czyª±cz\t,cv c·ÌqSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq $¹p"qº²¼¿yt,x§À7v«z\ctwv«v|Wwt5¬,©wz@yÈqSqSq\q\qSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq $¹p"q¹ZÍ>zScyt,x§Àv«z\czS|,GÎctw|Ïq\qSq\qSqSq\q\qSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq $¹p"q¹q tw@twc@|z°yÆÇgtw@yÆÇy7©wcz°yNy7@y|zq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq $¹p"q¹q tw@twz7Scytw©yª,v«v tw@¬@§,v«­czq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq ,rp"qºÅ¼¿ytw©yª,v«v tw@¬@§,v«­cz\z¶cytw©,yª,vv t,Сtwctwc§zzÑq\qSq\qSq\qSq\qSqSq ,rp"qºÅ"q Í,c©,©,z\Ðetwc°twccz7PqSq\qSqSq\q\qSq\qSqSq\qSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq wp"qºÅ"q Í,c©,©,z\Ðetwc°twccz7|Òy°W@|q§,c©,©wzSctw|ÒyÓq\qSq\qSq\qSq\qSq\qSqSq wp"qºÅ"qp Í,c©,©,z\Ðetwc°twccz7n7z\°,,§tw½=$yz7||zc|zPqSq\qSq\qSq\qSq\qSq\qSqSq wpp"qºÅ"q  Í>zc|¾7wz7Scytw©,yª,v«v«twIc¬"/v«­czqSq\q\qSqSq\qSq\qSq\qSq\qSq\qSqSq w²

VGV&DGOQOQDSR&TÏKID\O T½J

@,ª±§§yzS§y7cz¾cczccyt"ª±cz° °¥¢¥§£z°Nycy|zΫy7|t,@twÁ c§ytx/À7vz• ª§ zIcyt,x§Àv«zÎ9y|twc@yzz |twc|ÒÆÇcyt,x§Àv«z|" ½ ª¡ !° ¨3|v«,yz7|,cyt,x§Àv«zSc,e®ªq• ytw@z#",y7@y|zv«z$"w|t,@twcz|1|twc|ÒÆÇcyt,x§Àv«z|¾¨3|,cÐ/|@z´cyt,x§Àv«zWz|Òy@%",§­czn7,|Wtw7,czScyzzv«zN|twctw=®ªq• &ª('°¡¥ z7|I|twctwc|cz|I|twc|ÒÆǧytx/À7vz7|gtw@yt,xcz7cyÉ|tw@tw*c:§ytx/À7vzc,3q³´zz1|Òyª©wzycy|z1cyt"c§©wcyª,z7vz7cz|&,©wt,y±§vz7|>7,y|nzÐe,zv«z7t,vcyƱ§zc|x§z|q*)tw@zÐetw|"gtw@y¶­§zN3Áº,©wt,y±cv«zWy7|cª |tw´zµ«5,z#"§cz¾twcctwv ,+ z7@yzNctw

- yz||Ð3,z."§Î|7t,yN­czSz7|¶cz°y|W|twc|ÒÆÇcyt,x§Àv«z|N©wcy|¶|twz7Se¥/¥¢¥/£3 z|Wcc|Wcz7|,@yz7|q*0 Áº,@yz|Nv«t|"/c§zG$§cyt"ª±cz\c@|zyÆÇgtw@yÆÇy©wczy¾7zSy7@y|@SgzcNtwcccyzGΧz|©wt,y±cv«z7|cz°µ 57z|t,y|­§z´Nc7twvgtw|tw\y7@y|z´7t,§ccζy7|twc@yz*1@ 2" 43°e §Iv - vz\|twc|ÒÆǧytx/À7vz65t,c¾,c||>t,y|­Á n¬½cy7|zc7z\cz 7@ 89='!:° ,;/ °° ªq =< az·"z7v§z«||­cz«z7|Ò\z«7,c1§z|S§t,vGxcyz7|\cz«~xgtw§,7%"­cz«ctwc|\z°·c,v«czytwc|§c|z7 c°ª, ÎIIcyt"ª±§,cz |ztwqsutwc|Sz°yytwc|,ty|­cz#"ÎI3Áº,cz §z |Òyc°@yz7|\§z«ctwcc7z|c§yt§y7z|"Sz7|ÒIgtw||x§z Á t,xczcyc,©wt,y±§vza§c|z°µ 7,7zaz¸?>53£ ¢¥§£½cz9yz5,7czy§z||tw@t,§|IÎEcz||twc|ÒÆÇcyt,x§Àv«z7|½c@+ÒÎEyzc7t,y|qA\§| cy|z7ªtw 7,||­§z§z§yt,©,yª,v«v $tw @¬@§,v«­cz."W |Òyc°@yzczctwcc7z|©wcyªzv«z7@|zz|Ò½c ªx§z7,B"z7­cz71z|ÒGtwc|ÒycC5yzv§1cz«Ð3#Dtwi¢ °¥4¢¥/£°q«¿1yGtwyz#"ctwc|Sz°yytwc|\­Á cczccyt"ª±czy7@y|zz°E° F°¥¢¥/£gz@,c|| - yzc|7zgtw@y°@z°yczy|twc@yz/c|zcy|Сtw| §v - vz\|twc|ÒÆǧytx/À7vzwq sut,twc|­czW7z°z 5ccyt"ª±cz°¦¶czWcytw©yª,v«v tw«@¬@§,v«­czNÁ z|Ò/,|1cy|z7zW/§|1twc|z|´v "cz|Ê­c§yª,z7´czNtwc7z°ctw z°´Áº,§,¬@|z¾Áº©wt,y±cv«z7|¾qqq /yz¾­czN7z| yÐe°yz§z|yzgtw|zI©w7c°yª,zv«zI|cyIz/yª§©wv«zavgyªÐ\zcyt"7c@yª,czcytw©,yª,v«v«twq ¿1y7twyz#">§,c|\z7,@yz§9/yª§©wv«z«czG=FH,¢ ¢,£3¤¥3°¥£3Ç¥§¥I!?"§c|cy7|v«z\§,c|z|S,c©©wz7|Ðetwc°twccz7|§t,a|Òy°|"n7z°zÐ3#Dtw9c!JgyzzÁº$xty§z°yS§yt,©,yª,v«v $twa@¬"Æ/v«­czuz|ÒÊÐetwc§,v«zª,z#""|ctw¥=° ¢eF°q "t,§©wctwc|´/yÊtwyz­czS³´t,yv«zB"@Í>z|z°y|twz°K z|ÒScy|z7z\z°zccyt"ª±cz."n­Á |Scgz7zu§@FL,S|Òyª©wzy7@y|z7zF°¥c 8°¥§£3q

sut,zʳ´z°z|z7°t,Á z|ÒW=|Wcy7|zz\§,c|NzSv ,czÇqX! 3o "]$#Çlbd¡]gfi[&%('l[*)5d,+/m-)5d3`/.0#¡m1(235476985:;296<=?>@BADCFE;GIHKJLCFE;GIH8(69MI:ON

P;Q AR9RTSVU9UWAR9RYXZ([O3\2 P296(N3&:;2(E56(2]X

P;Q EO37E296(N3&:;2(E56(2^<=&>@_A`;X5Jba<=?>c@_A`7dOJ

e Q Ee Q E

f #e^/]=[db\g` m oih tw@twI§@yzv«z7Wy7@y|zSc5§cnÀv«zS§t,vGxcyzGcz\~&xgtw§,7

Í Á ,©wty±cv«zIcy|z7zc§z|tw@tw9/@yzv«zSy7@y|wz«ca5,7ccnÀv«z§t,vGxcyz«cz~xgtw§,73qÍzzv§|NÁ z·@ctwIz7|ÒNcyW/yNz|N7­§t,§|WczSy7@yyzc7zS|cw,z|

ÆT (n) = T (n − 1) + T (n − 2) + Θ(1),

|n > 1Æ

T (1) = Θ(1)ÆT (0) = Θ(1)Í&|tw@t, cz«z|\7­§t,§|gzyvz\cz«7t,§@yz ­§zzzv§|\Á z·@ctw z|ÒG, v«t,c|z·"gtwczzÇq:¿c| §y|v«z7$"¶z7Wgzc - yzv«twytwv«v«z|c7q )t,cÁºxgt,yB"Wct,twc|­czG«Ð¡twctw

T (n)ctwc/¾z\zv§|NÁ z°·@7@twz|Ò¾v«twct,t,§­cz."/,Á z|ÒÆ ÎƤcyz

n1 ≤ n2 ⇒T (n1) ≤ T (n2)

¨3wÁ z7|Ò¶©w7c°yª,zv«zWzS7,|¶czz7z|WСtwctwc|®ªqÊtw¾t,y|cz°

dz7|Wtwc|Òª,z7|,||t"z7|"yz|Ògz7°zv«z$"n,yª7,,&cz7t,v§z°·@

Θ(1)cz

T (n)z°

T (0)q@§gtw|t,§|S,c||%"t,cyW|v/kj§z°yN3Áº,§,¬@|z."§­§z

nz|ÒWcIctwv\x§yzu=yG¨

n = 2 ∗ kgtw@yWc½7z°yª,

k®ªq I,t,y|z|Wyztwc|N|c,,z7|6

T (n) = T (n − 1) + T (n − 2) + c

≥ T (n − 2) + T (n − 2) + c

= 2T (n − 2) + c

≥ 2[2T (n − 4) + c] + c

= 22T (n − 2 ∗ 2) + 2 ∗ c

≥ 22[2T (n − 2 ∗ 2 − 2) + c] + 2 ∗ c

= 23T (n − 2 ∗ 3) + 3 ∗ c

. . .

≥ 2kT (n − 2 ∗ k) + k ∗ c

= 2kT (0) + k ∗ c

= 2k ∗ d + k ∗ c

= 2n/2 ∗ d + n/2 ∗ c

≥ 2n/2 ∗ d

zI7t,§@NctwcG­cz T (n) ∈ Ω(2n/2) = Ω((√

2)n)ql

monprqtsvu wyx;uz|w~7u*z|c*|DDvpw|yx(Dsup&*p*|Dz|Dqt|p*~*svuyux(*|T (n) ∈ Θ(rn)

r = 1+

√

5

2

|yws~*~7|yz0z|p&*|5

fib(5)

fib(4) fib(3)

fib(3) fib(1)fib(2)

fib(1)

fib(2)

fib(1) fib(0) fib(1) fib(0)

fib(0)

fib(2)

fib(1)

~©w@yz #¿1y7|zc7zSÁºcgz7|N|@gzygtw||Wgtw@yNzS5,7c§z <=?>@J

³´z ,©wt,y±cv«zIz·"gtwczz%"´§t,§#"Êz|Ò cz°µ 57z#"Êz° zÎ 7,c|zczacy|z7czI§za 7@ 8=ª'!:° N ,;/ °° ",Á z|ÒÆ ÎƤcyzu­nÁ ccgz7§gtw@y´c§zWw,z7@y´cz A ctwcczNgz7@ - yzNzJgzc/c|zcy|Ðet,|"&z ­cz 7zz|Ò§|ÒyÎ~©w@yz#"­§1yzcy|z7z3Áºyxcyz §z|cgz7|Ggtw@y<i=?>@OJ qX! "]$#Çlbd¡]gf _9+=m(' .&[5]/^=[$_/`E`a_cb$de]gf hj>f>_=` d3knl>mh>m;)?'wm@f>h_=f/b5m Í Á ,©wty±cv«zucy|z7zNc§zN|tw@tw«y7@y|z¾7zNv«v«t,y|tw c 5,7c§c

nÀv«zNctwvGxcyz§z~xgtw§,73q < 9ªx§z7, ,@·@,yz Z z7|Ò\@|gtw@y«° e z|Gcgz|Sy7@y|С|G¬,§ +ΰzJgzc|"1wÁ z7|ÒÆ Î$Ƥ§yz."gtw@ycyzccyzz7E§tzz7|y©wcv«z|gtw@yz7|­cz|cÉ$§gzc +ΰzJgz7°cz$"1ctwc#"1gtw@yz|­cz7|t,Éc@+ÒÎ7,7czy|cªt,yyz|Ògtwc/7q 0 nÁ ,@yz7|Wv«t,|"§zªx§z7, Z + twcz\cIyFLwz\|zvGx§$x/zÎzcnnÁ c§z¡ ¢ °q¿tw@y,§,¬@|zyzazv§|Á z°·@7@t,*§z zza|tw@tw7z v«7vt,y|twB"\SÐ3cItw@nÁ xgt,yy5|z°y­cz¶ÇÁ yxcyz¶cz7|cgz|&y7@y|Ðe|¶¥4N ª¢ /¢ 7 £ 7@£ 9W °("!; F1@ = °¥/£

# ¢%$ H7@F'&q1Íyª,|tw z7«z|ÒÊ­nÁ ccgz <=&>%(5@_A%)-Z J cz¶wS©wcyz°y Á ,@yz7|´$§gz|1y7@y|С|!;« ª * ° £ ¢G=F°%:°F 3¡ !;(+* ¢2H#"¥/£ A ° ª£WF°¥¥/£3°qG0anÁ ,@yz7|v«t,|"nzyª,c|Scz7||twc|ÒÆ yxcyz7|¾czSrj§©w@yz °¥/£Ê¢$H7/ ¨eytw§­c7|®ªqÍ Á yxcyz\§z|ucgz|Wy7@y|Ð&gtw@y <=?>,(5@_A%) Z J |zyªz>­Á c|ÒyΫ j§©w@yz"q AS,c|¾zzj/©,cyz#"$tw\|@ct,|zt,cnÁºxgt,y\­czz7|>cgz7|ny7@y|С|n|z Сtw>§,c|>3Á t,y@yzcc­c1/§|nzt"cz§z\ÇÁ ,©wty±cv«z "/wÁ z7|ÒÆ Î$Ƥ§yz."§ÇÁº$§gz>cj§c||.- X |c@n§z\ÇÁ czncj§c||,/- d q 0 c|cz#"z|Êcz| <=?>,(5@_A%)-Z J ­§/|t,ÊÎ\ÇÁ yz7@yÊczNyzª§©,z|Ê,@·«twc|´yytwcc| yz°§y|zzÊcz7|cz|­c 7t,yyz|Ògtwccz7ÎÇÁ ,,/$twEÁ c'y©wcv«z A ­c nÁ =|zc7t,yz° yzc7twy#"§t,§uctwÊ3Á °w,§tw ,\©w7c°yzyÊÁ ,@yz7|Êcgz|¶Î <i=?>%( £ ­c/,\v«z°yzuÎ +Òt,cy Z,0A 1 7z¾w,z7@y c§yt§y7zG¨3cz7@·@À7v«z¶/yzWczWu§yt7ccyz <=?>%( ®ªq1¿y 7twyz#"z7| cgz| <=?>%(5@A%) Z$J­c§z|tw¾=|Î3Á °yz@yczGz7|¾yz°ª,c©wz|ut,yyz|Ògtwc§zSÎ cz|u5,|¾t2«wzcy A c +ÎS°,,cz ¨ Z,0A 143_R 1(Z P65 896(e Q E Q ®´z°Wt2Izuy7|cª$Wgzc - yzyz°tw@yc§zSÐ37D7tw½v«v«cz /§|¶t,§|¶z|¶5,|"czScz@·@Àv«zScgz7nÎ <=?>,( ¨37zccj/c||,7- d ®wGtw7+Òtw@y|¶7tyyz7|Ògtwc@yz\Χczncz\zSB¬z#"c|,cÐgtw@y¾zS7,|WczSx=|z <i=?>%(5@ S8) Z J q

A\§|Szx/@\cz«Ð3,z°y\ÇÁ ,§,¬"|zyGcz«3Áº,©wt,y±cv«z#">±§,c §z|\y7|\cct,ª,Gc cz«,cct,/y\ca§t,vGxcyz §c­§,GzI¥;"°½cz«3Áºcgz,§­cz7117t,yyz|Ògtwcq»uc|%">cczw,z7@yNcz = |@yN§yScc­§z\­Á n|Á ,©wNc = Àv«z\czcIB¬"gzS§c­c¨3©wcyªNÁ ,@yz7|cz|´tw yzt,cy§,Êc y7|cªÊczuÐe#D7t,vv«7cz®ªq twc|Òªzc|g­cz¾z¾ctwvGxcyz¾t,ª,nÁ cgz7|´Î <=?>,( |z°yªSnÁ t,y@yzΘ(n)

5 A cz|c§yzv«zy1B¬"gz." A`7d cz|1c czc·"Àv«z¶B¬"gzwq

p

1(235476985:;296<=?>@BADCFE;GIHKJLCFE;GIH8(69MI:ON

ZO` A E;GIH 0_SCA 113&:;2K=O`bS Z ATe9Z Q 296Z,0o=1O` 1(Z P65 896(e Q E Q ¢#!" 2§°Ç¢#! /¢8+&¥ §7 >¢¥/£§¢ '°£3F6"¥° £ ¢,£

e Q E296(NO3&:O2(E5692^<=&>%(5@BA%) ZKJ

e Q E

1(235476985:;296<=?>%(5@BAC E;GIH ) ZcCFZ5292(Z 01^37e E;GIHKJLCFE;GIH8(69MI:ON

P;Q Z,0A 143_R 1(Z P 5 896(e Q E Q Z9[O3\2 P * ¢; <=?>@_A J ¢ # £ ¢#9? 296(N3&:;2(E56(2TZ,0A 1

e Q E

F°2°¢; # <=&>@_AJ! P;Q AR9RTSVU9UWAR9RYXZ([O3\2 P- O`^X

P;Q EO37E- X"O`b<=?>%(9@BA`;X ) ZKJ- dO`b<=?>%(9@BA`7d ) ZKJ- O` - X a - d

e Q EZ,0A 1O` -296(NO3&:O2(E5692 -

e Q E

f #¡^/]=[,db*g&`am$h tw@t, y7@y|z 7z«v«7vt,y|twi¨3@|,caªx§z7,=®¾gtw@yGz 7,c§nÀv«z\ctwv\x§yz\cz\~xgtw§,7

Â

fib’(n, A)

fib’(n−2, A)

fib’(n−1, A)

1

2

fib’(n−4, A)

fib’(n−3, A)

fib’(n−2, A)

fib’(2, A)

fib’(1, A) fib’(0, A)

n−2

n−1n

fib’(3, A)

n−3

fib’(1, A)

1

n−4

n−3

n−2

~©w@yz »¾yxcyz\cz|Ncgz7|Wy7@y|С|Nz½§y|z§z\cz\v7v«ty|twgtw@y <=?>%(9@_A%) Z J

Ë

§t,§SÇÁ ,§,¬"|z\|§wzgtw@y¾3Áº,©wt,y±cv«z <=?> • Íxgtwc7z 13&:;2 gtw@yNÇÁ c|$twcz Z §,c|Ncyt"7c@yz <i=?> z|Ò Θ(n)

q• Í>zyª7,,&zJz°§§,c|ª±§,7cczcz7|uc|Òª,cz7|cz <=?>%( "1 ªW¥ 9H,¥= !«£3¢7>,¢ °£ /¢¥§ 6!° ¢;º S" ª 3ª ¨e§c|­nÁ >|z°yª7twv§\§,c|NÇÁ z7c|zvGx§z|N§z|¾cgz7|®"/z|Ò

Θ(1)q

y$"1twv«vztwEÇÁ @ cy77czv«v«z$"1t,É,@yª Θ(n)cgz7|czcyt"7c@yz <=?>%( qÍ>zzv§|¶t,ª,gtw@yNz°·@7@z°yN3Á z§|zvGx§z\cz7|Ncz|NΧyt7ccyz <=?>,( |zyªctwc

Θ(n)q

ASzNz7| cz7@·gtw|""tw gz7@´ctwc¾7t,§@yzu­§zN3Áº,©wt,y±cv«z <=?> z|ÒÊcz¾twv§z°·@¾§7,yzΘ(n)

qX! X ^%b*g>]nh>mahm-.&[5]/^=[$_/`E`a_cb$de]gf hj>f>_=` d3knl>m-. #Çl)W'9#e_)?)5d3knl>m Z,0X 1 RKX Z,0S 1 RKX Z,0d 1 RTd Z 0 1 R Z,0 1 R Z,01 R

~&©w@yzp y@yz\czS§j§ct,cz7|W77v«z|Ncz Z gtw@yN§cz>Î <i=?>@OJ §,c|N3Áº,©wt,y±§vzÍ&Icyt"ª±§,cz°ªgzt,cyzEyyzyÎIIz°y|t,E,||­czczIcytw©yª,v«v twE@¬@§,v«­cz7twc||ÒzNÎStwc|Òycyz¶z¶ªx§z7, Z ¢¥c c£3 ºe czÊy7@y|@."wÁ z7|ÒÆ Î$Ƥ§yz."Îuyzv§y z¶ªx§z5,§zWÐ3#Dtw¢ ¥¢¥/£¨e§cFL´­cz ¥¢¥/£"7t,v«v«zNt, zNÐ3´z7Wy7@y|@$®"z°´zW§,c|§at,y@yz ­c1,||@yz­czz|t,|t,§|Scaªx§z5, ­§1|t,Syz7­c|z|Sgtw@y\7,cz°y\,,z@yGΧcz«gtw|tw ctwcc7z¥/£ # £ ª¢#! ° qÍI~&©w@yzpcy|z7z«§cz«yª,z«cz«ÇÁ tycyz«§,c|z7­cz7Wz| 77v«z|cz Z |t,cj§§| gtw@yc cgz7NÎ <i=?>@OJ "¶czv - vz­czzcz7, czy7@y|tw½$z7´gtw@yÊcj/cyÊ7z°Ê77vz7"twc|´z7|Ê,@yz7|Êcgz| y7@y|С|ÊÁº$§/yª||,Ê/,|/§|G7z°zyª,z t,yyz|Ògtwc§z§t,§ÎIcz7|cgz|\gtw@yGz|­cz7| Z,0A 143_R 1(Z P65 896(e Q E Q °ª,"yª,%"§,Á z|ÒÆ ÎƤcyz#"ct,cyNz7|­§z|Wzy7|cªN7tyyz7|Ògtwc§,Ngtw@y A °ª,Wc@+ÒÎ7,c,qA\§|1Sv«°±ct"czW7,||­§zWcz¶§yt,©,yª,v«v $tw«@¬@§,v«­§z#"tw twc|Òyc§t,§Wc§z¶ª$x/zN­c7twz7z7||tw@twc|1c·\|twc|ÒÆÇcyt,x§Àv«z|z°yv«7c,yz|qAz/c|"wzzª$x/z´z|Òtwc|Òycz czÐ3#DtwÎz\­Á t,I|tw¾,||@y\­czS|tw@tw½nÁ c|t,§|ÒÆÇcyt,x§À7v«z\|t,W§ +Î7,czz¶cy7|zz/§|ªx§z½Ev«twv«zt2Ezzz7|Òctw - yz@|zwq 0 EÁº,@yz|v«t,|"|´twE|zyÐeÀ°yzÎÇÁº$yx§yzcz|cgz| ycy|Ðe|"¶tw twc|Òy§aªx§zczÐe#D7t, ¢ ¥¢¥/£ 5 ,Á z|ÒÆ ÎƤcyz#"¶cz7|§ytx/À7vz7|N|v/z7|>7° Sz|Wcyt,x§Àv«z|Ntwv§z°·@z|q

1(235476985:;296<=?>@ AC E;GIHKJ C E;GIH 8(69MI:ONZO` A E;GIH 0AOa$X 1 ¢'! §7" ! S #1c£3Ç¥§ e¥/£Ç¢eF° Z,0_S 1O`^X ¥§3£3Ç¢#¡ ¢,£3¤¥(/7"9 ='!:°(° G '¢ Z,0vX 1O`^X13&:;2K=O` d Z ATe9Z Q 296

¥§ £3?;£3Ç¥ ¢ F°¥¢¥/£ G¢ £ ¢'! Z,0o=1 O` Z,0 =(`;X 1 aZ,0o=(`7d 1

e Q E296(NO3&:O2(E5692TZ,0A 1

e Q E

f #¡^/]=[,db*g&`amXh tw@tw«ctwy7@y|zN7z¶ª$x/z5«7t,§|Òyc§zWÐe#Dtw«,|7zc§,zG¨e§yt,©,yª,vÆv t,@¬@§,v«­§z\||­cz$®´§I5,7c§nÀv«z\ctwv\x§yz\cz\~xgtw§,7

²

Í Á ,©wty±cv«z\p\cy|z7zcczS|t,@tw½||­czcz7,ccnÀv«z§t,vGxcyzSczu~xgtw§,7ÎÇÁºczÁ §cz$§cyt"ª±czczGcytw©,yª,vv t,9@¬@§,v­cz,qBz|Ò,ty|uÐ3,zczGwtwy­czz\z7v§|nÁ z·"7@twI|z°yª«czS7twv/z·"

O(n)q

D]; y

twyWcz°ycÀ°yzu|z7°tw|cy¶G§yt,©,yª,v«v $twÐetwc°twcczzuz°ÊGcytw©yª,v«v twc¬"/v«­cz,q Y ^ _^$yr $! "LYy

"z°twItwv«|zwq #-O$ Y%; & '() O *Y ,+,$;y y5-;

Íz|S,©wt,y±§vz7|¾x=|7||@yS cytw©,yª,v«v«tw9@¬@§,v«­cz|tw|tw@z7S@||ugtw@yuy7|t,§@yz§z|1cyt,x§À7v«z| * g£3¡e °¢,£3¤¥;",Á z|ÒÆ ÎƤcyzWcz|cyt,x§Àv«z7|§,c|z7|­§z|1ÇÁ t,x + z7°Ð/z7|Ò§z¶Á §z@Ækj§zyccztw§c|z7@y||tw@twc|­c&||Ðetwzyª,c|uyÀyz| * g£3e ¢#e£ "=§t,§v«§v«|¨3twv ·"v«|,$"/|zt,zS5|®Êccz\zyªcz\СtwctwIcz\t/.@7qÍ&|Òyª7©,z gtw@y@|zycytw©,yª,v«v«twE@¬@§,v«­§za¢ °¥4¢¥/£yzgtw|z½t,y||@yz7|§yc7=z|¾°ªgz|W|§wz|,q&Bcz7tj/z°yGz|\7yª,°y|Ò­cz|\nÁ c§z |t,@tw t,cv ,z¨Çν3Áº,§z Á §cz Сtwctw cz«7t/.@ccyt,cyz®ªq"q Aj§cyy7@y|zv«z \|t,@tw t,cv z¾Î\cczNc|Òª,c7zNc cyt,x§À7v«zNz cztj/,Êz7|cz°y|\|twc|ÒÆÇcyt,x§Àv«z|νy|twccyz¨e/yGz°·@zv§z#"νÇÁºcz Á 7­§twc|Sy7@y|z7|Gccyt,Æcyz7|Wt,ÎÇÁ ,cz\Á cczGccyt"ª±§zy7@y|wz\§@|z°yÆÇgtw@yÆÇy7©,§z°y°®ªqp"q&Bcz7tj/z°yNccz\|Òyc°cyzScz\ctwccz7|N,@·@,yzG­cgz°yv«z°yª§zSv«v«t,y|zyNz|N|twctwc|,@· |twc|ÒÆÇcyt,x§Àv«z|ÊzÊc°zyv«czyÊczu­cz7z¾Ð3#Dtw7z°z¾|Òyc°cyz¾czuctwccz7|´§z°"yª - yzyzv§z«gtw@ygz°yv«z°yz cz7,7cz°yI,,z@ynÁ c§z |tw@twEt,cv zcz Ð3#Dtw¢ F°¥/8¢¥/£?">,Á z|ÒÆ ÎƤcyzz79yzv«twª,Scytw©yz7||z7vz7\§z|S|twc|ÒÆǧytx/À7vz7|\|v§z| + §|­nÁ ,cyt,x§Àv«zS©wt,x/,n§,3qB%"=tw=$yz,c||&czc°zyv«czyuz @¢F ºe ª °¢$H cz«|Òy§°@yzczG§t,§cz7|qAS,c|1zW7,|Á c«,©wty±cv«z¶§z´§yt,©,yª,v«v $tw@¬@§,v«­czWyªÐ ",wÁ z7|Ò1z7||zzz7v«zz|ª±c7v czyzv§||,©wz­c&, cz°yv«cz°yS|Òyc@yz§z3Áº,©wt,y±§vzwqÍ>zcy§/,yª7,,N§z3Áº,©wt,y±cv«ztwc||Òz9,t,y|IÎ yzv§yIz°/y7t,cyy½ |Òyc@yzczctwcc7z|cz½|t,yz­§z½3Á twÉczIczv ,ccz +v ,|c'y7|cª$­§ÊÁº/,|z7ct,yz½½7,7c Êz7Áº,@yz|¾v«t,|"=Ðe,@¾§t,§Gz°·c,v«czy¾z| ;°¥¢¥4° ¥§¥gF° GzyzGz7|¾v«z|¾cz|Òy§°@yz\czSctwc§z|Wgtw@y¾c°zyv«czyNz\|ª±c7v «czyz7v/||,©,zwq

Âcqnc|y#"/twc|Òycyz"¥10|tw@t,t,cv z\Î/yyN§z|NcÐet,yv $twc|N7,7cz|q32)tw@zÐetw|"ÊzI§zI|tw /,|twc| z7|cyt,x§Àv«z| Á t§v«|$twi­cÊz@z - yz½y|twc|ÎÇÁºcz½cz½cytw©,yª,v«v«tw'@¬@§,v«­czwqaÍ>zcyt,x§Àv«zIÎy|twccyzctw|$|Ð3yzz(=e¥1;

* g£3e ¢#º3£ St,cy¾­cz\|twctwt,xcz§zS/yNcytw©yª,v«v tw@¬@§,v«­cz\|t,¾t§v ,zwq4 %651fd¡b$de]gf*o Y\[,d3fL'd,.1mh$7] .>b$dÇ`a_ #3d¡b7m §yc7zGnÁ t,cv * ¢º !; # "¥='!:°( ª "¥ #1@£3¤¥;g£3e¢#! # "¥ e¥§ ª£ ¢¥ 7 ='9:6;@£N£ 7 7@ £3F'£°¥ / # §¢°£3e #1c£3Ç¥§ g£3e ¢#!° ¢7 7" ?8!='!:°(° 8:9 zLsu ;| qt?*|DD|ypw ?I uz=< svu w ~*z&u|y*z&wuvp*D~&wuDsvz|yD~7u*z|y 9 zy s?>vu w &p*@>yp&ysz|y |ypw

5 u&|ypwu A*|y%BDC6E*||y z?wup*x*~*svp*y|ysu|yD|pw-F Gz?wup5HJIvwp&$?&| ~7* uD~*zu A*|y zs~*y|ypwsvwupD*|y$sz3>vu wK* |yyx*sp&~*z&u|y* *||L?|yD~&z|y ?*|Lp*&~*|ypDM

wp*x\p*v*p*v*Lpw|ypwvp* *|*w|Dup*|yz|yJN&w&|y|ww|0vz&wupIx*sp* p*y|ysu|yD|pwu*|ypwu A\|yzsDz&wuvp|yzz|M!(OyD|

¹

"=z¾§yc7zuÁ t,cv«,u|Áºc§­cz."c,ty|¶t,gz7@¶@|z°y¶Gcytw©,yª,v«v«tw@¬@§,v«­czt,cy>7twc|Òycyz§cz|twctw\t,cv«,z1/yz´­§z#"5y7@y|zv«zz>§z1Ð3#DtwG,|z§§,z#"ª±/,­cz|twc|ÒƤ|tw@t,|zyªt,cv zSz¾­Á n|@µ«NÁ czkj§zyNc§z\|t,@twyx§yª,yzwq

³´t,yv«z "Íz|z°y|tw z K z|Ò´z°·"cyv«z´z¶cyc7gz¾Á t,cv ,Nz §|,¶­nÁ c«§ytx/À7vz 3°¢3£¢/¢¢e£3@¥ )]gl) )°b5[lL',b$l[5m ] .nbd3` _i#em |¶ccz|tw@t,Ét,cv zI,Ecyt,x§Àv«z½twvgt,yz§z|N|t,@twc|Nt,cv«,z|¾,@·½|t,§|ÒÆÇcyt,x§À7v«z|q< cyt,x§Àv«z z7|ÒGctwc c xgtw 7,cc§\t,cyGccz |twctw x/,|z |@y½cytw©,yª,vv t,E@¬"Æ/v«­cz\|nz|Ncz@·½7t,§ctwc|N|cw,z|N|twN||Ðe,z|,qNÍ>zcyt,x§Àv«z\Ð3,¾c/yªÃyz l&fnm )]glL) )°b$[lL',b$l[5m] .nbd3` _i#em "qNÍ>z¾§ytx/À7vzStwz hm() )]gl) .[$] #@`am;) )5l.1m"[\.] )%() ¨3wÁ z7|ÒÆ ÎƤcyzS­cz3Áº,©wt,y±§vzy7@y|Щw§À°yz/c|zcy|NСtw|Wz|Wv - vz7|W|twc|ÒÆǧytx/À7vz7|®ªq

"¶cyz7vÀ°yz 7t,§ctw\nÁ z7|Ò>/,|||Ð3,z."W|tw@t,Gt,xcz"cz/y&cG,©wty±cv«z czcytw©,yªvÆv t,c¬"/v«­czSt,cyyªu,ty|G¥ §¢ °£3g£3e¢#!qÊ¿1yutwyz."/|> cz7@·@À7vzGtwc§twnÁ z7|Ò /,| ||Ðe,z#"ÇÁ c|tw Á c,©wt,y±§vz¾czWcytw©,yª,vv t,@¬@§,v«­czNgtw@yyª,Ê,t,y|- yztwc|cyz7t,v«v«zczÇÁ¡7>#°7 I1"zE7z|z§|­Á t,'twc|Òy§yª,§ ªx§z7,Ecz7||twctwc|zyv7cyz|" v ,|«­czª±§,§czcz½z7||t,@twc|§z|z°yª,@|zI­nÁ c§z|z7cz½z°§c­czÐetw|q Y¾_/[5mcf/b\g()m'oih »¾§§7x§\czScytw©,yª,v«v«twIc¬"/v«­czS|z7tw9³´t,yvz7 °£¶¢# ; y$-; /^ TY%;y$

¿yt,x§À7v«z*vc§z°yNcczª±§ÃczczSv«yz7|Êz½v«cv«|,Wzu§t,vGxcyzt,ª,gÁ t,gyªtwc|q¿ c|&cy7|7v«z$",ª&ctwc§´c§z´|cz´cz´v y7z|A1, . . . , An

","Ðe,@ytw@z°y +* FFNg£3e¢#/§|z7­cz7Nz| cyt"c§|czv y7z|§z°"yª,z7|Á zJz°§z°ygtw@yv«§v«|z°y½zctwvGxcyzt,ª,nÁ t,gyª$twc|q BÐe,@"cz7vv«z7yz|Òz°zy3Á t,y@yzcz|v $yz7|§,c||§z."v ,|tw9gz@wyzyÇÁ t,y@yzcz7|t°yªtwc|z + tw§,«7zÇÁ¡¢ ª °Ç¢,£3 >5e£ "1wÁ z7|ÒÆ Î$Ƥ§yz."1zE/yz±c|,cz§ Jgyzz7|WÐ3#Dtwc|Nz7|Wcwzy|¶§yt§c|q 01·@z7v/z 1tw1z7|1­§yz´v yz||c,,z7|W¨3¾©,§zÊcx/,|cc­§zʾª,zÊczÊuv y7z$®

A × B × C × D20 × 2 2 × 30 30 × 12 12 × 8

AzÐe#DtwE©w§°yª,z."1zcyt"ccÁ cczv yzczª,z i × j/yc§zv yz

j × kc7z|ÒÆ|z

i × j × kvc§5twc|cz x/,|z,q A J°yzz|GÐ3#Dtwc|cz /yz7±c|zyz7|Gvc§7twc|§zv ,ccz°ytwuctwcScz7|W§t,vGxcyz7|Wt,ª,@·cz\vG§§5$twc|Nc!Jgyz|

A(B(CD)) : 30 × 12 × 8 + 2 × 30 × 8 + 20 × 2 × 8 = 3680((AB)C)D : 20 × 2 × 30 + 20 × 30 × 12 + 20 × 12 × 8 = 10320(A(BC))D : 2 × 30 × 12 + 20 × 2 × 12 + 20 × 12 × 8 = 3120

sut,z Í Á t,x + z7°ÐNczI3Áº,©wt,y±cv«zIÎ9c°zt,cgzy«Á z|Ò §¢ ½cz½vc§z°y z7|v $yz7|v ,||v§zv«zuczScz°yv«cz°yNÇÁ t,y@yz\t,cv ,ncz\vc§5twc|q Í>z7|N$y©wcv«z7|W§z\3Áº,©wt,y±§vz|tw¾ctwc\c§­cz7vz7¾z7|¶ª,z|Wcz7|Wv yz|q

Å

1(235476985:;296 =?A7H@cC \A7E;GIHJLCFE;GIHZ92\:96;E9N P ° ¢,£32 # £31º2G ¥§£

1

n¤¥g¥9F!?@¡ °

¢ £ ¢ I! ¢ ¢,£32i° £ ¥§¥= §¢

i−1 × i

1(296O4(37E98 Q N Q 3IETR40

0

)1

) )n−1

)n1

8(69MI:ONA O`\A9H@$J9`;X2(6(NO3&:;2;E5692 =?A!7H (9@ ) X )FAYJ

e Q E

1(235476985:;296 =?A7H (5@"cC" \A#7E;G5H )= )"$C EOGIHKJLC EOGIH1(296O4(37E98 Q N Q 3IE

= IR$ % $ \A(H@ J8(69MI:ONPOQ = R9R$ Z9[O372 P ¢ S£3 >7¤¢# 296(NO3*:;2(E5692 S

e Q E

¢ G ! & =?A!O= $ O` a ∞ (' ¥ >¢ °F !¥='°F\e¥§¡ " !"e * = 1i3&:;2 ) ` =bZ$i`;X e9Z Q 2(6 * >7e ,+1¥ ª§ ¥ .-« °7@ ?8!='!:°(° !? * ¥9° 7@£ªF" ª >7°¥/£A9>;=/) O`0 =&A!7H (5@ ) = ))KJ F2\ °7@ ?8!='!:°(G?@ ª 3 A9>1)$ O`0 =&A!7H (5@ ));a$X)$ J * ?2:\ 7@ 89='!:G?@ 3 '°¡¥°2+¥ ª¥c¥g¢3£ !G¥='°F \ £3 º2ª¢,£3Ç¥§ SF!"e ° §7@!° °7@ ?8!='!:°(° ' ¥E!° Gª('°¡¥ ¢7>743 °¥ ¢ 77@£ ¢¥/£ ¢7" ª ª*!G¥g('°F * §ª¢,£3Ç¥§ F!?@¡ ° /7"S £31º%° !° G?«¢,£3%° !" £¥/£ °£Ç£ ª § ªe£3¤¥ A9>;=/)$ O` A(>!;=5)^a A9>!1)$ a @ 0o=(`;X 1 6,0.) 1 6 07$ 1iJ

(' ¥ >, $ \ ª \¥g7 >7ª¢7ª £ ¢,£ £e¥ 3°°2?@¢7¡¥§e @ & =?A!;= $ O`0 Q E & =?A!;= $8)FA9>!O=/)$8

e Q E

9' ¥ ¢ 3¢3£ ¢ >7e ªÇ¥/8@'°¡¥g¢e °¥§7@\£ 7@ 6!° ) § ª 2'! £¶¥ ¢£37 >,G!\e¥ce ":+1¥9F£ 7"¥ \¡¥§e @ ª\° F £ ¢,£H.'ª¢# 2(6(NO3&:;2;E5692 & =?A!;= $

e Q E

f #¡^/]=[,db*g&`am<;h »u©wt,y±cv«zWy7@y|Ðgtw@y´v«cv«|z°y¶zuctwvGxcyz¾czuvc§5twc|ÊÁ ccz¾|yz§z\v«yz7|

=

X ;3o "]$#Çlbd¡]gfih&d,+>d)m"[ .]gl[ ª[&%^gf>m"[ .&l[5m [*%('l>[\)5d +=m ÍÁº,©wt,y±§vzÂ@|zv±ct"cz§@|z°yÆÇgtw@yÆÇy7©,§z°yycy|zgtw@yuy7|t,§@yzz§ytx/À7vz§Iv«cv|twcctwv\x§yz\Á t,gyªtwc|Wgtw@yNvc§7twÁ ccz\±§Ãcz\§zSv y7z|q ¿tw@yy|twccyzzcyt,x§Àv«zczytw@z°ySzctwv\x§yzt,cv ,§zvc/7t,§|uyz5­c|z7|gtw@yvc§z°y«z|v yz|

A1

"¶q7qq"An"1twE,7,7cz°y$"gtw@ytwc|z|

kgtw||x§z7|zyz

1z°

n"zctwvGxcyz«t,cv«,1czvc§7twc|Sgtw@y\Ðe,yzzcyt"cc\7zz/yz±c|,©wz

(A1..Ak) ×(Ak+1..An)

q Eª±ctw|yªzc|§zz k­c v«cv«|zzctwvGxcyztª, czvc§5twc|I¨e/yc/7t,§| y°gz| czN\|Òyª©wzNc@|zyÆÇgtw@yÆÇy©wczyÊ7z¾c!Jg°yz7|

k"§§|´z«yz±cz°y±§,|tw@t,v«cv ,zS/yv>z7|Wcz°y|z7|W|tw@twc|¾tx§zcz7|®ªq

"!#$% !

&' "!#!&' )(* (

)(*+( -,'$. ,

),'/,0 1#$

.% ,&' "(#+,0.% (

&' )(*$(&' -,'+,0

&' 12.3 (& 1!2(.% !

&' 1!2!&' "(#$(

& ),*4.% ,

&' ),*+,&' 12

.3 ,& 1!2$,

555& ),*4

5556% !

$! 555 )(*$ 555

6% ( +( 555 -,'$ 555

6% , /,0 555 "#$ 555

~©w@yz\Â *0·@zv§zSÁ z°·@7@tw½gtw@y =?A!7H (9@&X ) OJ y7@y|Ð

¿1$yIz·@zv§z#"u|@cgtw|twc|­Á twc7|yzavc/z°yz7|½v yz| Z X " ZOd " Z " Z " Z q¸»zEv«°±§t§z§@|z°yÆÇgtw@yÆÇy7©,§z°yI§87Çwz9c§­c7z/c|½±/c$"Nz|I$§gz|y7@y|С|IÎ =?A7H (

r

|zyª,z7¶,t,y|Êz7@· c§­c7|ÊÎG~©w@yzuÂcq t,Ê,yz7v«zW­cz¾7z°yª,§|´czuz7|Êcgz7|´twc"ªx§zv«z¾|zyg°zyG¨37t,v«v«zS~xgtw§,7¡®"cyz7c§,NÇÁ ,©wty±cv«z\cz°µ 7,7z,qsut,z.Íz §t,vGxcyzcz ¦ cz°wcczz·"cyz||tw9 )^R ¦ cc­czzcwz5,Ecz Iy7@y|t,nqÍz|cz7@· cz| $=?A!IH ( |twc|c§z zzz°·"cyz7||twE|twzc· Ðe,|\gtw@yzz«,,z7@ycz )§t,§czwqBcz|Ò1t,||x§zW§zÊcytw@z°yu¨3v ,|ctwc|czWzWСzytwc|=|e®&­§z¶u7twv/z·"¶§zW3Áº,©wt,y±§vzy7|cªz7|Òz°·"gtwczz7z,qu¿ §|¾cy7|v«z$"gz§t,vGxcyzt,ª,cz/yz±c7|,©,z7|¾t,cy

nv«Æyz7|«z@ - yz§°y«=$yz|7­§twc| §zIy7@yyz§z|§wz|9¨ ³´tyv«z7 z°,Çq!"S/= =Â"®"

kyzcy|z7ª,¾z7|Wc!Jgyz|Wgtw|Wcz\tw@§cyz\czS|7­cz§zS§z\v«yz7|6Æ

P (1) = 1ÆP (n) =

∑n−1

k=1P (k)P (n − k)

|n ≥ 2

Í&|tw@t, cz7z°z7­§t,aczy7@yyzc7zz7|ÒP (n) = C(n − 1)

"nt2C(n)

z|Ò\znÀ7v«z77v«z¾czS|5­czc7zScz7|S¥g('°F° ¢,£ ¢#¢¥9cj§czS7t,v«v«z\|c

C(n) =1

n + 1Cn

2n

∈ Ω(4n/n3

2 )

X ; "]$#Çlbd¡]gfi[&%('l[*)5d,+/m_9+=m('` %c`a]=[d)_cb$d¡]gf ÍÁº©wt,y±cv«zË z|ÒucczG|tw@t,ycy|zGcz7|z7c§,zI¢7>7 ° e ¢,£3Ç¥9gtw@y |twctw,cyt,x§À7v«zucv«cv«|tw§ctwvGxcyzÁ t,gyªtwc|´gtw@y¶vG§§5$twÁ cczu±§Ã§zuczv yz|q³´twv«v«z\§,c|NÇÁ z·@zv§z\c7,7cnc

nÀ7v«z\ctwv\x§yz\cz\~xgtw§,7 ¨ ztwp"qºr@qº®"§«twvÆ/z·"NczNz´,©wt,y±cv«z¾7wz7Nv«v«t,y|tw z7|Ò @cz7v«vz7´§Ð¡yz7@yzNÎ\z7zNcz¾3Áº,©wt,y±§vz/@yzv«zNy7@y|Ð "§§c|­czSt,cyNctw@§z\ctwccGÁºy©,§vz7| = z° $ "§zSyª7,,n,||t"GÁ z7|ÒzJgzc ! * "¥G ? ! 3¡ ªq³´twv«v«zN§,c|´3Á z°·@zv§zNcz|´ctwv\x§yz| §zN~xgtw§,7%"S7twv/z·"NczNÇÁ ,©,t,y±cv«zNgz@ - yz§°z°yv«cSz,§,¬@|Wz§t,vGxcyzSt,ª,gnÁ cgz7|W§|Òc°|NÎ =?A7H ( §,c|Wz|­cz7|WzS7,czSÇÁ 7Jgz7°ªtw Î 0 = 1%07$ 1 |tw\zJgzc| ½v«v«t,y|twacz7|\$y©wcv«z7|Sc +@c|,½,t,y|,||@yzyN­§zuª±§w­czutwvGx§§,|twIÁº$y©wcv«z7|¶czu©wcyz°yªG7z¾yª7,,gczu5,7c=c½vcvcv z°nÁ 7Jgz7°ªtw­Áº,I§§|Wc§zSÐet,|q

ª,Gctwc§ z«cyt,x§Àv«z c, 7zz|\xgt,ycz| X z A "&z ctwvGxcyz tª,nÁ c|Òª,cz7|e 8£3e¥°£° SczSÐetwc°tw =?A!7H ( §,c|Wz|­czz|¶z5§gcz & =?A!;= $ |z°yªzJgz7°cz|Ò Θ(n2)¨ $=?A!IH (5@= )$J t,cy = z° $ ,y´cz1Î A ®ªq y$"@ÎGª±§w­cz¾Ð¡tw|Ê­cz¾zNyª,zv«z´gtw@yÊccz=yzGÁ y©wcv«z| = z° $ ctw - yz\zJgz7°cS/yzG­cz\|twy|§ª¾Á =|¾zc7tyz\\7,c#"tw9zJz°§z¨3/§|uz§yz7,|®Wcyª7,,cztwv§z°·@

Θ(n)"Î|7wtwy$"z|ucz°y|z7|u°yªt,§|§zI9xgtwc7z 13&:;2 q ;gz7@ ctwcz;twc7cyz­cza7twv/z·"Ic;zv§| Á z°·@7@tw;cz

$=?A!IH ( z|ÒΘ(n3)

q¾Í«xt,§zGnÁ c,|Òtw/§|u«§yt7ccyz $=?A!IH ª,Θ(n2)

"gtw9§t,§Sx§z7­§zSzN,©,t,y±cv«z\z|ÒNcz\twv§z°·@\@x/­czΘ(n3)

q

,

1(235476985:;296 =?A7H@cC \A7E;GIHJLCFE;GIHZ92\:96;E9N P ° ¢,£32 # £31º2G ¥§£

1

n

¢ £ ¢ I! ¢ ¢,£32i° £

i−1 × i

1(296O4(37E98 Q N Q 3IETR40

0

)1

) )n−1

)n1

8(69MI:ONA O`7A9H@ J9`;X O` A E;GIH 0A 1%0A113&:;2K=O`TX Z A%)"$O`^X Z A^e9Z Q 296 0o=1%07$ 1O` 1;Z P65 896;e Q E Q

e Q E296(NO3&:O2(E5692 =&A!7H (5@ ) X )FA%)YJ

e Q E

1(235476985:;296 =?A7H (5@ C" \A7E;GIH)= )$CFE;G5H )DC Z5292;Z 0A 1,0A 137e E;GIHJ C E;GIH

8(69MI:ONP;Q 0 = 1%07$ 1 3_R 1(Z P65 8(6(e Q E Q Z9[O372 P296(N3&:;2(E56(2 0 = 1%07$ 1

e Q E F°2°¢;¢7>#F 9 ¢2H#"¥/£3 = £ $ P;Q = R9R$ Z9[3\2 P& =?A!;= $O` S

P;Q EO37E& =?A!;= $O` a ∞13&:O2 ) O`=bZ$`;X e(Z Q 296A9>!;=/) O`0 =?A!7H (5@" ) = )) ) YJA9>!1)$ O`0 =?A!7H (5@" ));a$X )"$)YJA9>!;=/)$ `A9>!;=/)a A9>!1)$a @,0o=;`;X 1 ,0.) 1 ,07$61iJ& =?A!;= $ ` Q E & =?A;= $)BA9>;=/)$

e Q Ee Q E 0o= 1%0 $ 1O` & =?A!;= $296(NO3&:O2(E5692 & =&A!;=$

e Q E

f #¡^/]=[,db*g&`am$h »u©,t,y±cv«zuy7@y|Ð&z7° e ¢,£3Ç¥gtw@yWv«cv«|z°yNzSctwv\x§yzSczSvcÆ/7t,§|WÁ ccz\|yz\v yz|

7

0vX 1%0X 1 R S 0yd1%0d1TR S 0 1%061 R S 0 1%0 1TR S 0 1%01TR S 0 1%0 1 RKX 0 1%0 1 RKX 0 1%01TR;d 0yd1%0 1TR;d 0yd1%0 1TRTd 0d1%0+1 R(d 0vX 1%0yd1 RKX 0vX 1%0 1 R 0vX 1%0 1 RTd 0vX 1%0 1 R

~©w@yzË ycyzScz\cj§ctwI§z|Nv«z|Ncz t,cy =?A7H (5@ ) X ) ) $J [h[$mhm9hL%65f&dbd¡]gf mblbd#3d)_cb$d¡]gf h>m()W%;# %c`am@f=b&) hm Í&u~©w@yzN˾c|Òyz¶3Á t,y@yz¶§,c|1z5­cz@z7|c!Jg°yz7|77v«z|1cz |t,1cj§c|gtw@y1cczcÎ$=?A!IH (5@ ) X ) )$J q Itwc|Òªz"cz7vv«z7N­czSÇÁ twIczSctwN7,7cz°yN­czSz7|Êgtw|twc|§zv y7z zz7|¶­cz =IR$ q ½twc|ÒªzS§||n­§z|gtw½7,czz|¶v«z7|¶cz §,c|ÇÁ tycyz\|cw,$"§tw½yz|Òz°zyªz7|Wcgz§§,cz7|Wcz\ctwcc7z|¾$§cyt,cy7z|,q 7,7cztwc|Nz7| 0 = 1%07$ 1 z7|N­cz $`5= R S"q Ðe,NczSv - v«zSgtw@yNz| 0o=1%07$ 1 z|¾­§z $`5= RYXp"q&Bcz7vPt,cyNz| 0 = 1%07$ 1 z|N­cz $`9= RTdÂcqNz°wq³´zz97yª,°°y|Ò­§z9|z°yªÉc|7zac°yz@yz7vz7§,c|IÇÁ ,©,t,y±cv«za§z9cytw©yª,v«v twc¬"/v«­cz\,||­cz¨Ç,©,t,y±cv«zG²®ªq

X ;X "]$#Çlbd¡]gf hl `a_=fl>m;# G_(+/m('B.&[5]/^=[$_/`E`a_cb$de]gf hj>f>_=` d3knl>m-'9#¡_i)?)5dek>l>m suttwc|n/y M [i][j]

zctwvGxcyz vcvcv cz vG§§5$twc|nyz5­c|>gtw@yvc§zyz|v«yz7|Ai+Òc|­ÁºÎ

Aj"t,y|­cz

i < jq Ícyt,cy°y7@y|wz½§z°,, - yz½|$|Ð3z=$y|tw@twt,cv ,z\|zyªctwc\«|cw,z

M [i][i] = 0,gtw@y

1 ≤ i ≤ nM [i][j] = min

i≤k≤j−1(M [i][k] + M [k + 1][j] + di−1dkdj),

t,cyi < j

¿ycgzÁ t§v , ª,>ctwcczccz |t,@twSt,cv«,zN¨e=$yz°·gq!" A1((((A2A3)A4)A5)A6)®t,cyccz´|cz§z|·\v«yz7|®",t,y|Á vgt,yz´­§zz|twc|ÒƤ|tw@t,½¨e/y&z°·gq!"

(A2A3)A4

®gcz°"yªz7z¶§|| - yz´t,cv ,zwq³´z7gz7@ - yz cytw@ /y ª¥/£3¢2°£3¤¥ |Á @z°·@|Òª,&§/yz±c7|,©,z/c|´7twctwv«­czNgtw@y´c§zN|twc|ÒƤz·"cyz||tw9¨e=$y´z·=q9"A2(A3A4)

®"",ty|´/|cµyª,´czNyz7v/,zy7z°z|twc|ÒƤz°·"cyz7||twɧ,c|I/yz7±c|,©wz©wt,x/, gtw@ytx§zcycczv«zz@yz|tw@tw:¨e/yz·gq!"A1(((A2(A3A4))A5)A6)

®ªq Í>z §yc7zÊÁ t§v ,Ê°ª,&wx§z´z7¬,1cj§§1ccz´cyt,cy°Ê7yª,°y|,¾|twctwt,cv ,z."cgyz|Òzzc|czSÎcj/cyWcI,©wty±cv«zS­c=gzyvzyªcztwc|ÒycyzczÐ3#Dtw½,|7z@Æ/z\«|tw@twqÊ¿1y¾«Ð3#Dtw§t,¾z7|N7­§twc|Wy7@y|wz7|N|tw¾cj§cz|"=t,gzc¾twc|Òªz°y

7p

Y\[,d3fL'd,.1mh$7] .>b$dÇ`a_ #3d¡b?% .0#3lL)m@fihL%b7_=d#)"@cgtw|twc|u­czSÇÁ tw,¾ccz\|tw@t,t,cv z#"/,Á z|ÒÆ ÎƤcyz#"§c/yz±§|,©wz\t§v ,gtw@y¾z7|nv«yz7|

A1, . . . , Anq Ec|yz,t,y|Gv«twyz°y­§z Á vgt,yz­czz |twc|ÒƤ|tw@t,'@|z/§|Wz°zS|t,@tw½t,cv zS|z°yªzzS,c||nt,cv«,z,q*0IÁº,@yz|Wv«t,|"c§t,§|WÐe,@Nvtwyzy­cz\z7|W|tw@t,§|¾,@·½|t,§|ÒÆÇcyt,x§À7v«z|¾|twN§z7||,yz7vz7¾t§v ,z7|Wz7z|N,c||Çq

¿tw@y - yzu§c|¶7t,§°yz°$"c|ccgtw|twc|Wctwc\­Á tw,WcczS|yzSczS|·v $yz7|A1, . . . , A6

zW­czzS/yz±c|,©wzSt,cv >|t,¾z\|cw,$(A1((((A2A3)A4)A5)A6))

"t,u,ty|¾z\|twc|ÒÆǧytx/À7vzczGvc§z°yuz7|Nv y7z|A2, A3

z°A4

qÊÍ«|twc|ÒƤ|tw@t,@|z/§|ÊG|tw@t,½t,cv ,zuz7|Ò((A2A3)A4)

q´@cgtw|twc|W­czuzz¾|tw@tw½czu|twÊ=|¶t§v ,zt,cyA2, A3

z°A4

qE¨ ³¾Á z|Ò´7czIcyz7@z/y7twyª,ctw tw zcv«twyzy­cz7z°zI|tw@t,ictw - yzt,cv ,z#"Êz |@ct,|,a|tw@tw ©wt,x/,zt,cv z,q ;,actwc|ccgtw|z°y­nÁ z7z§zÇÁ z7|Ò/,|"§c|Sv«twyzy\­cz7zz|ÒSvgtw||x/z=$y7z­czz77twccc\ΧczNtwyª,c°twq®§S|tw@tw((A2A3)A4)

Á °ª,1/,| t,cv«,z#"7zS|©wckj§z°yª,´,t,y|´­Á z·@|Òz6"¥¢7@£3FW/yz±§|,©wzN­§@|twvz7z@y$"ctwcW­ccczv ,cczWv«twc|1nÁ t,gyª$twc|"w=$yz·gq!"(A2(A3A4))

q y$"=|&tw@|,z°,@yz\=$yz7±c7|©wz§,c|uz\/yz±§|,©wzc,´¨3|@§gtw|t,cv ,¡®"N |tw@tw ©,t,x/,zy|§ª,z@|,½z°½,@yz/yz±c|,©wz§zv ,ccz°yª,$"GI!¢7@ ª "gvtwc|Á t,gyªtwc|¨3czG/yu Ð3#Dtwctwutw7t,vczzctwvGxcyzt,ª,>Á t,g°yªt,§|"gz7|ª,z|\§z|G,@yz|\|twc|ÒƤv yz|GÁº7¬,G/,|\ª±/§©,®ªq(0 Á ,@yz7|\v«t|"tw t,xczccyªGcczv«z7z7@yz|tw@tw:­czE|t,@tw czEq7qq|t,@tw­§zctwc|I7"twc||@cgtw|9t,cv«,z,q ¥/£3¢%£3¤¥³´twc7§|tw nÁ z|ÒN/,|¶gtw||x§zG­Á >z°·@|Òz\cv«zz@yN/yz±c|,©wzSgtw@y

(A2 . . . A4)|nz=$yz7±c7|©wz\Ð3,W/yzScI/yz7±c|,©wz\t,cv«,n©wt,x/,Çq

Y¾_/[$m@f/b\g;)m $h A°ª,|¶,cctwc§z| + §|Òtj/,¶z¾cy§gzuÁ t§v ,¾gtw@y¶vc§5twnÁ c§z\|°yz\czSv y7z|

°Â

Y\[$m@l+/m ._/[ 'w]gf=b5[5_/hd,',bd¡]gfASzNÐe#D7t,«/c|´z°·"§7z."tw\@|NzWyª,|twccz7v«z¶­c/|c´§,c|´\cyz@zW/c|´±§,@¨ecyzcwz=$y¾twyª,c°tw=®ªq

• tw Pz

Qz|Wcyt,gtw|twc|N|c,,z|

P |tw@t,©wtx=zSz7|ÒNt,cv ,z

Q |twctw,I|twc|ÒÆǧytx/À7vzGz|ÒNt,cv z

• Iwz7@Nv«twyz°y P ⇒ Q

• ¿tw@yu7zGÐ3,yz½¨ecyz@zG/yu7twyª,ctw=®"=tw|@cgtw|z ¬Q"=7z­c>, §t,§|NgzyvzyzGcztwc7cyz ¬P

P ∧ ¬Q ⇒ ¬P

• y$"§tw§z7||,yz7vz7 P ∧ ¬Q ⇒ P

• Atwc."ccz7|W§z@·½v/7t,§|¶cy77czz7|"§tw½gz7@Ntwc7@yzP ∧ ¬Q ⇒ P ∧ ¬P

³¾Á z|ÒÆ ÎƤcyzP ∧ ¬Q ⇒ FAUX

³´twyª,c°tw$BnÁ z|ÒN§t,§S/,|¶gtw||x§zG­§z ¬Q|t,W"yª,3q

Y¾_/[5m@f=b*g ()m Xh ¿z°Wyªcgz7|@y¾z|Wcyz@z7|¶/yN7t,yª§tw

­cz|zc|uz|uv«z7|«¢7 8@ ª " §zGc©wtw§,z½¨i < j

®Wtw¾xgz7|twnÁ - yz7,c|q ct,z,c||¶­czgtw@y7,cz°yM [i][j]

"1twE§t,7twy7,cM [i][k]

zM [k + 1][j]

gtw@yk ≥ i

z°k ≤ j − 1

q ÍÁº©wt,y±cv«z´²Wz|Ò&,t,y|>7zc,y7|cªczÇÁº$§§7tw\cz 7z°z1|Òyª©wz,qÉ5§|zcz WÐ37D7tw§t,¶|twW@|z|¶z7|Ê|tw@t,§|ʧz|Ê|twc|ÒÆÇcyt,x§Àv«z7|"cGªx§z¾z@ - yz¾yz7v/zW7c©wtw§,zu/y§,©wtw§,z°¦½¨

M [i][i]®"nÎ =$yyScz§c|©,yª,ccz#"gz7­czc7°yucy7cz7v«vz77qS¿1yz·@zv§z#"t,cyIc§zav y7zaÎÉ|·©wcz|IzItwt,§cz|"t,*,@yªÉcyz7v/||,©,z twv«v«za|c$"u = À7vz°yªtwIcz\xt,§zSz°·"zyczyzv§||,¾z|Nv«z7|Wcc­c|W/y =

0 1 2 3 4 50 1 2 3 4

0 1 2 30 1 2

0 10

½z°yyª "§t,y|­Á t,$xty§z°yªz|N,©,t,y±cv«z|¶/yªÀz|"/­czSz7twcccNÎcI7,cnczB¬"gz ¢7>#%3¥/£ "@z| 77v«z|´cz¾±§w­§zN§,©wtw§,z¾gtw@,,Ê|zN5,7czy´czuÐe#D7t,cc°zc§,z¨3ctwcz7I/yªÀz$®ªq ÍÁº/¬@|zcz3Áº,©wt,y±§vzz7|ÒNyz7zv«zucyzG¶tw Θ(n2)

°yªtwc|¾cz7|¾cz7@·Ixgtwc7z7|z·"z°ycz7|½¨ i=\H z = ®"1t,yyz7|Ògtwc§,«,E§t,vGxcyz½Á v«z|§zv $yzwq ³´±/7cczczz7|°yªtwc|Scz7v §cz«c9yª7wnÁ ,a§c|Θ(n)

¨eyzª±§z°yª±§zc vcvcv /yv«,9/c|n7Æv«z7|´ÎS3Áº,czNczNxgtwczNzycz¾z7¶,yx§z ) ®ªq twc7@ ctwc."twv«vzN§,c|S|twctw§y7czz#"/­§zSÇÁ ,©,t,y±cv«z\z|Ò

Θ(n3)q

7Ë

1(235476985:;296 =?A7H@cC \A7E;GIHJLCFE;GIHZ92\:96;E9N P ° ¢,£32 # £31º2G ¥§£

1

n

¢ £ ¢ I! ¢ ¢,£32i° £

i−1 × i

1(296O4(37E98 Q N Q 3IETR40

0

)1

) )n−1

)n1

8(69MI:ONA O`7A9H@ J9`;X O` A E;GIH 0A 1%0A113&:;2K=O`TX Z ATe9Z Q 296(' ¥ $1¥c3£ !° G¢ G 'ª¢ ¢ £ ¢'! 0o=1%0o= 1O` S

e Q E13&:;2i=*HO`^X Z A`;X e9Z Q 29613&:O2K= O`^X Z A`/ =*H$` = a =*H& =?A!;= $ ` a ∞13&:O2 ) O`= Z8$`;X e9Z Q 2(6A(>!;=5)$ O`0 0o=1%0.) 1 a 0.);a$X 1%07$ 1Ta @ 0o=(`;X 1 6 0.) 16 07$ 1iJ& =?A!O= $ O`0 Q E & =?A!;= $8)FA9>!;=/)$

e Q E 0o=1%07$ 1O` & =?A!;= $

e Q Ee Q E296(NO3&:O2(E5692 0X 1%0A 1

e Q E

f #¡^/]=[,db*g&`amh »u©wt,y±cv«zczcytw©,yª,vv t,ac¬"/v«­cz|,c|y7@y|@gtw@y\vcv«|zyz\ctwvGxcyz\cz\vG§§5$twc|NÁ ccz\|yz\cz\v y7z|

7²

Y\[$]/^=[5_=` ` m Y 4 .1]gl>[ # 7_ #¡^/]=[,db\g` mh>m .[$]/^=[5_=` ` _cb$d¡]gfh>jfn_=`Edek>lnm '9#e_i)?)5dek>lnm y'w_ # 'l # _i)?'wm@fh>_=f=b Í Á ,©wty±cv«zI¹cy7|zzccz |tw@twEtwv§x§z zGz·"7@ªx§z«nÁ c §yt,©,yª,v«v«z#"&y§,c|ct,ªt,½¯9¿*A ""gtw@yWcz°yv«§z°yWzSctwv\x§yzv«cvG§v §zvc§5twc|¶yz5­§|z7|Êgtw@yWccz±§Ã§z\cz\v $yz7|G¨37 "cgtw@yN|v§kj§zy$"§tw@|z\cz7|¶ªz7|W©w§°yz7|N,5$twyzv«z°®ªq b O yOLTO " $;yY

"z°twItwv«|zwq #-O *Y $ c==

z7cy7q

]§b7m h m()W)m;',b$d¡]gfL)W)5l&d +@_=f=b7m()fnm )]gf=b ._)W.&[&%()mcf/b5m() h_=f) #¡m9` _/fnl>m;# O *LK ^9 Kc

Íz\§ytx/À7vzc|,Îctw|u7t,§||ÒzÎ v $·@v«|zyz\°xg7cj§7z¦\gtw@w - yzt,xcz7zyzvÆ/||,Gc | z7cwzy|Szv«|q ¸ª±/,­cz«z7v z7|Ò\,||t"c 'ª¥g $ F¨3caz7z°ySgtw|Ъ®zWc§% «¨3§Izz°yWgtw|Ъ®ªqÍÁ t,x +ÒzÐz|ÒNczyzv§yNzS|,\Îctw|WczSÐ37D7twIÎv ·"v«|zyNzxcj§z."cv ,|¾|§|Wc/,||z°y¾zSt,c|Nv $·@vcv gtw@w, - yz\twz"I/§|WzS|,,q AS,c| 9zy|tw 3ª¢°£3¤¥§¥=¢eFcz7z½§ytx/À7vz."¶Wz7|Ò gz°yv«| czcyz§@yzc§zI/yzÁ czv ¨e=$yz°·gq9"&twE½ytw|@tw|\§z |cyz zGtw v«z°|zczv«z7c"t§,c|Gz |®ªqAS,c|Gz5,|">7twvv«z«twazz°yyªI,acyt"ª±§,a±§§yz.">1z7|Òt,||x§z«Á @|z°yG§ ,©,t,y±cv«z >¢t,cySt,xczcySc§z|tw@twat§v ,z¨3z°Szz7z7v/|c5yz|&twa©wct,yzzy&cy5x§zcz7|77v«z|"§§t,§\z½z7v/|

Θ(n lg n)|ntwtwvczSzz7v/|WcIy¡®ªq

AS,c|1z¶5|1ccyt,x§À7v«zʧ|,¶Îctw|r$Æ\¨78& 5¥g¢= °¢ ='9«¦Ò®"wzÊcyt,x§Àv«z¶z|Òc!Jg°yz7/§|Gv«z7|@yz t2 Á z|ÒG/,|\gtw||x/zcz«cyz7c@yz cczСyªtw nÁ cEz7vIq < z7vÑctwccz@N|t, - yzcc|¶/§|WzS|, ¨Ò5®"c|twNcz/,| - yzcc|G¨Çr®ªq ½z°yyª,Iª±§§yzS|cw,­Á cczu|tw@t,tyª,7zuÎG7zNcyt,x§Àv«zczutwc§c´=|¶c7z||,yz7v«zWÎGc§zu|t,@twt,cv«,z,qA\§|u7z­c&|c$"§t,§|S,twc|¾y7|twc@yzzG§ytx/À7vz."gtw@Áºxgt,yaÎÇÁ ,cz§zv«°±ct"cz§@|z°yÆÇgtw@yÆÇy7©,§z°y«y7@y|z ¨egtw@y«v«z@·'7twv§yzc@yzz½§ytx/À7vzz°«ÇÁ c7z½©w§°yª,zIczI|tw@t,g®"c§c|¾Î3Áº,§z\Á §cz\ccyt"±cz\cz§yt,©,yª,v«v $tw@¬@§,v«­§z,q

X$3o "]$#Çlbd¡]gfih&d,+>d)m"[ .]gl[ ª[&%^gf>m"[[&%('l[*)5d,+/mASzGÐ3,twycy|z§z|z7c§,z."=c@|zyÆÇgtw@yÆÇy©wczy«¨3ctwcG/,|uctw@z°µ 7,z®"=twgz7@¾yÆ|twccyz´zcyt,x§Àv«z z­Á §c­cÊÎN3Áº,©wt,y±§vz¶Å"q&suttwc|&­cz#"gtw@y&|v§kj§z°yWcy7|zªtwzu,z°yÎ 3Á z||z7z>§zG3Áº,©wt,y±cv«z#"=z7§Æ¤7yztw@yczG|v§z7v«z !'°¥g $ £ ,£ ¢#>° F £ ¢¥/£ nczyz°tw@yczSctwc/,|W|yzSÁ zv«|NÎc@yzt,cyWt,xcz§yNzy|cªWt,cv ÇqÍ>z7|¶z·/Æ5twc|N|@y¾|Òyª©wzS@|z\|twNcy7|z7z|W§,c|Nz|W7twvv«z7ª,yz7|q

)>yÀ||tw@z$"cz7|Ò@zWz°°yz7|| cz¶cyt"ccyzWccz¶z7zW|twctwy7@y|zW|v§zWgtw@yx/z7twvcyz7c@yzuz¾cyt,x§À7v«zuzÊtx§zcyʧczu|tw@tw½­c/t,cyyªGz§|czu§t,§|Ê©wc§z°yÊwzy|Êccz|tw@t, §§|«z°µ 57z ¨3cczСtw|«z½cyt,x§Àv«zz° z7|«7yª,°°y|Ò­§z|«czIa|twctwi¬,°v«z@·Itwvcy|®ªq

5¹

! "$#%&'#()*,+-.$/1023+5467!89":);<"=5>>>"?5A@B!893="+CDE/+CF

5G#D 4E0H(&4I 5 " )&'#KJL&,M79N@OPN+4QMRS(9("PT:&,MUPST$.7&$#,$/30233+

F

(V WD&)D$$D NJD&($ .X$(&,M79N@U>PN0Y$ZX1$)#3$ : G$15 T '#(&(X#3$##3! )& NJ$)#[MOPEMOPN+4QMR"SI/'"PT:#[MR5P,MRPTS9.+

F

L5#D ! '#.J4QM\&5TS!/'"3]/$P:4^MR"SG/XW3]$&P!:$T_S)`&N+$)#1$ _LS"1Ea$+4QMObTSTW(_]/PT:$% 5b_LSW#[MR5P,McbPT`W#[Mcb`/$P,Md_PT`ed&,MR]/P>&,McbP>&,Md_P+#3$ _LSW#3$EB#3$ _K0-% 5b_I+

F#[MRPEMd_PS"#1$ _K+

FF#3 TSW#[Mf/$P,MOP.+

F

!DD "D&NJ)#3$ TS"$ .U&N0-3+

! T )$ g75#% &'# $D 51<J4QMR"SI/XW3]/$PT:;h&EMR]/$P.0"=ji3=02&,MR5PN0"=Hkl="+

F;3h&,MO3]/PN0"=ai=02&,MOPN0'=XSmn$<=)+;<"==0o#3$ N0"=R# $D 1=L+

&

f #¡^/]=[,db*g&`am $h ¿ytw©,yª,vv«zI¯¿ AÌgtw@y«z½5§Êc;ctwvGxcyzIvcvcv czIvc§5twc|t,cyNc§zS|°yz\cz\v«yz7|

7Å

1(235476985:;296TM \A5<i= P G@DC E;GIH )O=5!0C 7A7EOGIH )>\A5<! C \AIE;GIH J C E;GIH

1(296O4(37E98 Q N Q 3IE\A9Hc@O=5(JbR8\A(H@_>7A5<(J R A

8(69MI:ON 7"u ª¡ º $ °1¥IF£ 7"¥u ªe!°¥/£9'ª°¥= $ u° £ ¢¥/£/§¢ ¢ °!£3Ç¥ * e£° 296(NO3&:O2(E5692 M P (5@BA%) )O=5! )F>\A5<!TJ

e Q E

1(235476985:;296TM P (5@)DC AGIH ) , @¢e¥3£° # £¥/£° * ¡¥1"DC AGIH ) 2 F° £ ¢¥§£ # ª'!°O=5! C \A#7E;G5H ) 9' ¥½ F,§ /!; !° ¶ !;°¥4° W ¥§£e¥4 ° # §¢°£3e "&> \A5<0C 7A7EOGIHJ C E;GIH

8(69MI:ONP;Q ^R9RTSVU9U )^R9RTS Z([O3\2 P296(N3&:;2(E56(2S

e Q E

P;Q =5!0.) 1 Z9[O372 P 7"G£37 >#°¢ #1c£3Ç¥ g£3e ¢#! /7"6@¥§% ¢7># !° 3£ X # ) ´¥9¥ 3£B§¢ S¡¥1"FG+* e£° ) §7@6@¥(/% F° £ ¢¥/£ ª¢S ¥(/% §¢ ª 296(N3&:;2(E56(2 M P (5@)$`;X ) )O=1! )F>\A 5<TJ

P;Q EO37EZ P9P 692(N@=5!0.) 1IRYJ(' ¥;@£ ¡¥1" +* 3£ ) ª*! 'ª¥g $ °¥ >¢7c£ ¢6;°¡¥ (' ¥ ¢¡¥ u #1c£3Ç¥§ § ª 2'! ¤e¥41@FN7¥g¥(+* e£° ) £>¥ @¡ ª3£ I!.!" ¢§°£ !G I!" 'ª¥g $ F°2:°FS °#@£3¤¥§ ª ª2'!2+1¥¥,* ¡¥1@£ §¢ +* e£° ) + F° £ ¢¥/£1¥ @¢¥ H ¥4 §¢ >X"O` M P (5@)`;X ) )O=5! )F>\A5<!TJ

* 2:°(G #1@£3¤¥§ ª 2'!,+1¥9¡¥1@£ +* e£° ) ¥ ! /% F° ª£ ¢¥/£ £ ee¥;§ ¥ ª¥§ °!;°¥F >idO` M P (5@)`;X ) K`O=50.) 18)O=1! )F>\A 5<TJ a > \A5<80.) 1

(' ¥9F£ 7"¥G¢«° I!"G #1@£3¤¥§¢*9 G½¢#£¥g¢,£3 >7° / ª2'9 296(N3&:;2(E56(2 (Zb>X )F>id

e Q Ee Q E

f #¡^/]=[d¡b*g&`am h »u©,t,y±cv«zSc@|zyÆÇgtw@yÆÇy©wczyWy7@y|Ðgtw@yNz§ytx/À7vz\§I|,GÎctw|¾r

=

X$ "]$#Çlbd¡]gf _9+=m('B.&[5]/^=[5_=`E`a_cb$de]gf hj>f>_=` dek>l>m tw W

zgtwc|Nv«·@vG§v gtw@w - yzS7t,z½=$yNzS|,wqÊtwnz\ctwv\x§yzt,ª,Á zv«|¨3tw|@cgtw|z­czGz7|Nzv«|"/czGv - v«z­§z\z|Wt,c|¾z°Nxg7cj§7z|¾,||t"|"=|twucv«°yt,|¾cz

1În®ªqÍ|Òyª©wz´t,cytx§zcy|tw@twv ·@v ,zWz|Ò1§zÊy|twccyzWz7|1czy|1|twc|ÒÆÇcyt,x§Àv«z7||§w|• B[k, w]

yt,cwzyN«Ð37D7twI§zSyz7v/y¾z\|,Gzc|,uc§­cz7vz7¾z|Nzv«|G#"g ">q7qq"k¨k ≤ n

®´|,c| +Ò,v ,|Nc°=||zy¾c½t,c|Nczw¨w ≤ W

®"ctwz@1y7|t,§@yz¶twc|17z||twc|ÒÆÇcyt,x§Àv«z|"@,t,y|S|t,@tw«t,cv«,zN,§ytx/À7vzWc,|zyªB[n, W ]

qWsut,twc|u­czz7>|©wctj/z­Á Ðe,@$"/gtw@yucgtwc|Wctwcc#"=5,7czy¾gtw||x§z°Æv«z7Wtwc|Nz|¶xg7cj§7z|Wgtw||x/z7|¶gtw@y

w = 0, 1, 2, 3, . . . , Wq

ÍuÐetyvcz´y7@y|zÊcyw,¾|tw@twt,cv ,z¨3c§­cz7vz71zÊxgcj§z®nz|Ò1u|c,,z

B[k, w] =

maxB[k − 1, w], benefs[k] + B[k − 1, w − poids[k]] si poids[k] ≤ wB[k − 1, w] si poids[k] > w

B[i, 0] = 0, pour i = 1, . . . , n

B[0, w] = 0, pour w = 0, . . . , W

Í&§z@·@Àv«z«§|z§zIСt,yvczgtw@yB[k, w]

yzcy|z7z«z«7,|\t2 zgtw§|\cz«3Á z7vk§°/,||zzgtw§|uyz|Òª,$"nctwctw9czctwu=|Sc7cyzÇÁ zvIq\Ícyzv«À°yz7,c|zt,yyz|Òt,§,7,|Wt2Izgtwc|NczSÇÁ zv

kczS§°/,||zS/,|Wzt,c|Wyz|Òª,$"/,§­czn7,|WtwIctwNc°zyvczy|>3Á z7vÄctw - yzScc|NtwIctwB"/zIÐetwc°twIcIxg§j§7z\,||t",q

6< ,©,t,y±cv«z y5,|,z7|5­§twc|&z7|Ò§y|zÊξ3Áº,©wt,y±§vz = 5 ct,twc|­cz´zÊ7,7cczB[k, w]

c7z||zu§§|´ÇÁ c|tw§z|´v«z7|B[k− 1, 0]

ÎB[k− 1, w]

"@ctwc¾z|Êv«z|§z\©wczScy77czzGÎ@ytwz\t,v«v7c$z7v«z¾,@Ƥcz7||c|q ³´twv/z·"S§zSÇÁ ,©,t,y±cv«z T (n) ∈ Θ(nW )

• Í>z´zv§|z|Ò1,yz7vz7ctwv«c´/y1z´yª7,,Ð3,1§,c|z7|&§z@·\xgtwc7z7| 13&:;2 vGxcy­c7z|¨3z| §z@·§yzv«Àyz| xgtwc7z7|´cz¾|zyz¶­§zWt,cyÊc|z°yÊS§yzv«Àyz¾©wcz¾z cyz7vÀ°yztwtwcczSzN|twWyz7|Ògzz7vz7Θ(n)

z°Θ(W )

®ªq• Í>zWctwvGxcyz¶t,ª,cÁ °yªtwc|1z7|Ò n×(W +1) ∈ Θ(nW )

qÍ>z¶yª7,,czJz°§¶§,c|±§,c§zcz7|Wyª$twc|Nz|ÒΘ(1)

q m@` _/[$k>lnm ;c«Á cÉzW,©,t,y±cv«zI­Á ¶z|Ò z'z7v§| = ;#89§#,¥g¤¢#¶=$y7zI­cz|tw zv§|\Á z°·@7@t, c°gz7c cz a ¢$H,¥§e£ /c ctwvGxcyz«yzD7 z y©wcv«z$"&z°Gctw cz«ª,zcz93Á zc7t"§,©,zcz7z°½y©wcv«z7q¶z­nÁ ciz7u,©,t,y±cv«z§c||z - yz§c|zµ«5,z­Á c'©wt,y±cv«z@|,cczccyt"ª±§z«xcycz z°§873z#"&z«zv§|Á z·@ctw gzcGczzcyyÀ7|Wvgt,yª,Wgtw@yNcz7|W©,yª,ccz7|¶wzcy|Wcz

Wq

#-O$ Y%; & '() O$O K-; ; =

A\§|NzG­cn|c$"§§t,§|¾,twc|Nv«twyz°yu­cz#"§/§|Nc,c©,©wz\Ðetwc°twccz7¥g¥9 £32°£ "/«7tyyz7|ÒÆt,§§,czz|Ò­§,|Ncyz°zz7yzz7| 7­§twc| §j§c||,ccz|tw@twiczIcytw©yª,v«v twc¬"/v«­cz«z°Szcytw©,yª,vv«z«cƤv - vzwq¯9,|tw@SnÁ xgt,yB">Ð3,@\twvcyz§@yzz ­nÁ z7|ÒS§,c©,©,z\Ðetwc°twccz7¥g¥9 £3%£3q

r

1(235476985:;296TM \A5<i= P G@DC AGIH )O=5!0C 7A7EOGIH )B> \A5<0C \A#7E;G5H JLCFE;GIH1(296O4(37E98 Q N Q 3IE\A9Hc@O=5(JbR8\A(H@_>7A5<(J R A

8(69MI:ON 9' ¥ @£3 ºe @¥4 $%:°( !H,¥ §7" 3°¢° ºe£° ! ª¢#!? G¢(>7ª¢% &:°FGº!H,¥M O` A TE;GIH,0AOa$X 1%0 ;a$X 11i3&:;2K= `TX Z A^e9Z Q 2(6M 0o= ) S61 O` S

e Q E1i3&:;2 `bS Z Te9Z Q 2(6M 0_S) 1 O` S

e Q E

1i3&:;2 ) `TX Z A^e9Z Q 2(613&:;2 O` S Z Te9Z Q 2(6P;Q O=5!0) 1 Z9[3\2 PM 0) ) 1` M 0.)`;X ) 1

P;Q EO37EZ P(P 692(N@ O=5!80.) 1 IR$JM 0) ) 1` (Z M 0.)$`;X) 18)F>\A 5<0.) 19aIM 0.)`;X ) $` O=1!0.) 1 18

e Q Ee Q E

e Q E2(6(NO3&:;2;E5692 M 0A,) 1

e Q E

f #¡^/]=[,db*g&`amh »u©,t,y±cv«z §z«cytw©,yª,v«v«twE@¬@§,v«­§z«gtw@yz §ytx/À7vzc |,Îctw|r

"

X 3o _=fn^/_§^/mÇ]gfL',b$de]gff>m;#³´twv«v«zWtwÇÁ u@«,±§§yz¾ "w§,c©,©wz¶cz¶cytw©,yªv«v twG4@F°(°¥/£Ðetwc°twccz 5 twc,c||§,c©©wzWc§5Ð;5 z7|Ò1c«,c©©wzÊx/,|Wcc­czv«z7|@yÇÁ @|t,«z1uv ,c§ctw§zS,,z7@y|Wz°N§zSÐet,§°t,§|"§ctwcx=|\|Òy°z7v«z\ " +* ?>,¢#1§¢,£3¤¥ * =F° ª¤¥§ qÍ&«Ð¡t,yv«zG©w§°yª,zÁ §cytw©yª,v«v«zСtwctwccz7>z7|Ò¾ctwcz7z\nÁ c§zG|yzczGc7$yªtwc|¨37twc|Òª,z|Nz°NÐetwc°twc|®"@/c|Nccz\z·"cyz||twÎ,,§z°y5&/"S JJJ5&LS JJJJJJ5&b!S JJJ

X _=fn^/_§^/mÇ]gfL',b$de]gff>m;# )°b5[,d,',bW+)7#e_/f>^/_§^/m9fn]gf )°b5[,d,',b c|Òc©wcz¶cz7@·G©,yª,ccz|1,||z|§z´,c©©wz7|Ðet,§°t,§cz|",|z7tw¾Ð3#Dtwctw1z|z°·"cyz7||twc|c|7z|Ntwv«v«zG$y©wcv«z7|N,@·IСtwctwc|W|tw¾°w,c7z|6

• Í,c©,©wzS|Òy° ⇒ z7|Ny©wcv«z|N|twNt,#+ tw@y|W,,§|"§v - v«z\|Á |¾czS|twN/,|Wc|7|q• Í,c©,©wzctw9|Òy° ⇒ z|S$y©wcv«z7|ugz7@ztw9ctw - yzG,,c|t,y|­czctw9@||"|ztw­nÁ c§z\ccyt"ª±§z\c§c©wz7z\tw½/yz||z7c|z\z7|ÒN@|zwq

_=f>^/_c^/m-)°b$[d',b |,,z@yNÁ cczSz°·"cyz7||twI@|7z7twvv«zG$y©wcv«z7WzJgzÐÁ z7|Ò¶/,|§j§cz¨e/yNz°·gq!"/|t,,,/$tw©,7cÀ°yz\ccz\zyyz@y¾Á z°·@7@twItwcczSxt,§zS;j§cz$®"=,t,y|Nzy7|cª$¾cz\Ðet,§°t,Á z7|ÒW=|Ncj§cÇq yª©wzG§zv|zz9tz7@"yz ¸$§gzÆÇ/yÆÇ,,z@y ⇒ tw9°w,czz7|y©wcv«z|«¢7>,¢¥/£N3Áºcgz7 "z7c|cz\twczz\Ðet,§°t,nq0·@zv§z<! R! Ta< @ (aXIJ< (" TRKX # RTS

@o<TSJ `9` BR A H - & =&A $9G & G= 3 @o<8( SJ `9` BR -6- 1 - @i=%$i=9= 7A G - SJ

A\§|3Áºcgz7 @ < SJ "n§cz|yz«;j/czÁºcgz|y7@y|Ðe|S|z°yª©w§°yzI¨e=|Scztwc§tw§z«zyv§,|t,'ÎIy7@y|tw=®ªqAS,c|GÇÁ cz @o< ( SJ "cczz°yyzcy\y7|cª,cz §@|tw§z u=$yur|z°yª«©,7c°y7z,q _=fn^/_§^/mfn]gf )°b$[d,',b :=z|Ò´t,||x§z¾t,cyÊcczuÐet,§°t,cz¾yz7z°twyÊc½$y©wcv«z7¶­cgÁ z7|Ò=|¾cj§§zNcz\­§,cv - v«zScyt"ccyzS§½y7|cª$7q Azc·|Òyª7©,z|¶t,||x§z|N§zSv«|z\z7It"z@"yz,qN»¾ccyt"±cz/yz||z§|z>twczz vv«7cz7vz7NÐet,§°t, °¢¥§ ¶>¢#1/Nz7|&y©wcv«z|q «°,,cz¶c y©,§vz7cc­czv«z7t,y|­Á ccz@z7yz5­§|§,c|Ðet,§°t,¨Ç$§gzÆÇ/yÆc7z||$®ªq⇒ < czz°·"cyz7||twa@|7z7t,v«v«z«$y©wcv«z7Sctw - yzz7c7§|cz§,c|Sccz½ " 2;°¥§ ¤¥¨3§,c|«c H.¢&¥n®ªq ' Í>t,y|­Á c y©,§vz7 z|Ò«c|."´tw;°w,cz½a|c|Ògz§|tw ¨3t,;Ð3,3¥4SzS©w#Dtw=®ªq

(?Ivwp&(?&| v |yw9z|iy ~*uzsvw|y&5*u|iK*sv >|*| |ws:; suz);v&w(y|yzs |yw9*p&iwsp&~*sv|ypw(~7&(z ?wuzusvw|** zsvp1>sJ>|v

,

"qN»¾ccyt"±czccc©wzz ½,c§'t,y@yz½nÁ ,,/$tw*¢=ÇGÁ z|Òrjc·@#" ,Á z|ÒÆ ÎƤcyzI­Á |@µ«¶cz¾yz|Ògz7°zy´z|Êc°gz7c§,c7z|Êczuctwcc7z|S¨3|=cczuz·§yz||t,½@|z "c,t,y|Êt,ctwzccyzS­cz |tw¾c|Ògtwcx§z®ªq⇒ Íz|9$y©wcv«z7|z°9 Ðet,§°t,gz7@z - yzE°wc7| °¥ §¢¢#I9:!Éz°ÇÁº$§gz,9z°ÇÁ cgz7|z«|Ò¬"§ª±@ytwc|zSgtw@yG||cyz°y\zyz|Òz°Scz7|c°zc§,c7z|§zctwc§z| ¨ ≈ cyt,Æccz@yC$7t,§|t,v«v z@y°®ªq

X X _=fn^/_§^/mÇ]gfL',b$de]gff>m;#´_(+/m;' %(+@_i#Çln_cbd¡]gfb._/[5m()?)mcl)m AS,c|Gc ,c©,©,z Сtwctwc§z§¢F° i¨3ctwct,x§|Òª,Gz|g£3ee ¢,£3Ç¥§ gtw||x§z|®c y©w@Æv«z7«Á z|Ò«°wcI­cz½|¶Êz|Ò >7ª¢¡¥/£SF!?@¡ P7cz´/y«§z7||°¦a¨Fª¢#I8 ' #8 ¥F§®ªq 0 nÁ ,@yz7|«v«t,|"´cczz°·"cyz||tw;c|7zItwv«v«zy©wcv«zz|Ò °wc7zaItw r9Ðetw|"Ê|zt, ­czÇÁº$y©wcv«z7¾Ðetyv«z77tyyz7|Ògtwc§,¾z|ÒN@|\twIctwB".+Ò,v ,|W§c|q < 9z·@zv§z|v§z uÇÁ z·§yz||t, < (-S Á z|Ò=|S,,§z§,c|S3Á °w§t,acz3Á z°·"cyz7||tw @o<8( SJbR9RKX ¦F">5ySz7zÁ z|Ò\/,|Sc7z7||yzgtw@yS§yt§cyz«zy|§ª\cz«3Áºcgz71Î ¨Ç­cyztw@ycztw7+Òtw@y|¾r "§ctwc\ÇÁ z·"cyz||twIz7|ÒNÐe,c||z® ⇒ §¢ SÁ z°yyzcyNcz\c"|t,I/yur@q< (" RYX # R S

@o<8( SJbR9RYX

< 9,@yzz·"z7v§z|v§zz7|Òucy|z7/§|u3Á z°·"yª,cz7t"cz| z7´,q\³´zGcytw©,yª,v«vz¥H°¥4:°F /¢ czSy7@y|@S;j§cz#"§/yz\­czSÇÁ cz>Î < Î@ytwzSczu C ¦czS|Á zJgz7°cz\­cz\|ntwc|z\=$yz HOGO= ¨3zS7t,§|Òyc°z7@yÊ C ¦z|ÒNc>,c||=$yz7||z@·/®ªq ]nhmI_i)/m;##No 01·@z7v/z\§|ÒyªNctw°w,§tw½Á c$y©wcv«z7`(` E IH C @ VC !(J !"$#&%'"(')#&*+ `(` %',%*.-/'*.-0)#&&12 3!54+" ! `(` E IH C76 5 68 9,4'3"4+":%"24%"<;>=2?'@BA CBDEF)G+H

9G @ VC 5 J R! `9`JI +3"9K-L)#&'*MN9*.-/OHOGO= @ 5 C !(JbR! ! `9`JI +3"9K$4*PQ-LRS!>% (T!&")#&%"(')#&O

<! R! VCF< @ TaKXIJ

9G @yH;G= @o<TSiJ9JbR9RKX

¿ c|¾cy7|v«z$"ggtw@ySÇÁ z·"7@tw§zzcytw©,yªv«v«z#"tw9zJgz7°czyª,uz|7;£3Ç¥§ |c"Æ,z7|6 9G @yH;G= @o<TSiJ9JbR9RKX`(` (G @yH;GO= @ S CF< @ S5a$XIJ(J9JbR9RYX`(` (G @o< @ S5aXIJ9JbR9RYX`(` (G @9@ S5aXIJ C @o< @ S5a0@ S5aXIJ9J9J9J R9RYX`(` @ S9a$XIJbR9RYX`(` X R9RYX`(` H -

ÍÁ °w§t,½/yz||z7c|zGz|ÒN@z

,p

• ¿tw@yNv §§§t,cz\|Òy§°@yz7|Wcz\ctwcc7z| §,£¥/£32I9¥/£¶;j§cz|q• ¿tw@yux§zv«t"ccy|zy7z°yª,§|Ncytw©,yª,vv«z7|uz7°y5ctw@/,©wzÐ3,x§zzyzzGcyt,Æccz@yNnÁ c§z\|Òyc°@yz\czS§t,§cz7|WzN|t,7t,§|t,v«v z@y7q

0·@zv§z n¿ytw©,yªv«v«z1gtw@y>Êyzª±§z°yª±§z1czctwvGxcyz|ncyz7v«zy|>ζÇÁºczcSyx/zÁ 01yªtw|Ò±cÀ7cz#"§y|z\§,c|WÇÁ z°·"yª,Ncz\t"cz | z7"q ]nhmI_i)/m;## ³Ê§nczS§t,vGxcyz7|Wcyz7vz°y|W/yNv«°±ct"cz\c°yx§zSÁ yª$tw|Ò±cÀ7cz`(` 1 1 - - = - X*S9S - & = - A & > - - & = - HOG ) KX&S9S - & = -

`(` 1 1 - \>;H \A= - A & > - - & = - *H - =\H & 7A;H =&AO< - =1 - G X&S(S HOG ) = @ X&S(SJ - & = -

`(` 1 1 - \>;H \A= - H 1# A & > - - & = - & - = \A;H - KX*S9S9SIH HOG ) = @ IR J @ - = @ X&S(S9SJ - & = - ;J

`(` e \A#\Hi= \A - =&A(= G - & = - C9C 0 Q AOH 1 - & = - R8 - =?>!76 - GIH \H\A 0d 1

- - =?>76 - G5H *H \A @ VC !;JR VC @ - =?>!76 - GIH *H7A @o<=7H - - !7Hi= ! # !(J9J

`(` P - = & - H 1# & !7H = ! 5G;=*H <i=7H - - !7H = ! C9C Q AOH ` 0 Q A;H 1 ` 0 Q A;H 1<i=7H - - !7H = ! R 0 U O` )FAIH@ & R9RTSJ 1

`(` e \A#\Hi= \A G1 i=;=7G= - HOG ) = C9C @yHK` M OJ ` 0 H 1 ` 0 H 1HOG ) = 0 1 R40 1HOG ) = @ VC !(JU R! VC H;G) $= !U IH - = R 0 1

- = C9C @yHK` M OJ ` 0 H 1 ` 0 H 1 - = 0 1 R40 1 - = @ VC !(JU R - $= U IH - = R! VC !

¿yt§y|W°yz7||z|• Igz@Wyª7wzy¾z7S|Òz¨egt,zzz7v«z°®´;j/cz\§ztwc|Nz7|WctwvGxcyz7|¶cyz7v«zy|q• ¿z°yv«z°I§cz9v«t"ccy|t,*©,z9§ §ytx/À7vz 'tw z@ ª7 !°Ezcyt"7z||c|cz ©w§°yªtw cz7|\ctwvGxcyz7|\§yzv«zy|Gc cyt"z7||c|Gcz|ztw ⇒ Ð3,z cz ±§,c©wz°yzcyt"z7||c|NczS|7z7°t,nqÍz\§z°ycz°y¾gtwuz|Ò¾/y7cÀyzv«zu°yz7||,7q AS,c|¾c§©w,©wz\cyt"7c@yª,>yª§tw@Ƨz%"§z7|W§z°y|Wcytw©,yª,vv«z7|¾­cgz°yv«z°yª,zNÁ t,xcz§yNz|Nc!Jg°yz7z|Ntwz7°t,§|Wcz\ctwvGxcyz|

$Â

§yzv«zy|Êcyt"ccz|ʧ,c|¶zt"cz ,| z65 z7@·«§c|´z°|Ê­cz7rwr "@z|7rwr\cyz7v«zy|"czc·7twv§y|Nz7yzS§z@·xgt,ycz7| 5|z°yª,zNyÀ|Wc!Jgyz|Nz7|Wcc|N§z|N,@yz|q »ucyz´z°·@zv§z 7,c"czÊWyª,czÊ7yyzÊÁ cctwvGxcyz´=$y1¾v«°±§t§z´cz´suzWtw@Æ K §±c|tw¨3z·"yªW§zSt"cz ,| wz7p®ªqÍ&v«°±§t§zWczNsuzWtw@Æ K $/±c|twgtw@y´zW7,7c§Á cczWyª,czN7yyzWz7|Ò cczNv«°±ct"cz\3£ ¢#8£3 >#GczS5§/y¢= e ¢,£3¤¥§ u /F° ª ># tw

ncctwv\x§yzSgtw@yNz5­czntw½z7@N7,cz°y √

ntwa0

"§cczGccyt5·@v twc,z¨e=$yNz·gq!"(n + 1)/2

®ªqtw

ai+1 = (ai + N/ai)/2q

»uty|"§|czS|c,,z ª¥;>#2H Szy| √n

a0, a1, a2, . . . , ai, ai+1, . . .

]nhmI_i)/m;##ÊX ³Ê§nczSyª,cz\7yyz/y¾v«°±§t§zScz\suzWt,cÆ K §±c|twz ,| z`(` 1 1 - \A - - G - i= & GIHi= 7A# - /G=?AIZ - A GO=bR @ GO= a @_A GO=;J9J d

\A - - Z - i= & G5Hi= \A#bA^RTG - i= & GIHi= \A - G - i= & GIHi= 7A# R G(S C & G @ - /GO=?A IZ - AJ G - i= & GIH = \A#G9SR @_AOa$X5J d

`(` 3*>;H \A$= - 5G - G(=?A85G -6- 1 - 8IG 1 (oG - i= & GIHi= \A *HTG ;H `(`6 - 1 ( -6- 1 - IG7># 5 *H !1# IHi=\H 1 ;G G # - G(=?A(49G -6- A # R -6- - Q AO< #]@ \A - - Z - = & GIHi= \A#bAJ

-6- 1 - Q AO< #]@ G9S CBG X]C G(JU G\>#]@ G(S` G XIJ IR # RTG XU IH - = R -6- - Q AO< #]@ G X]C G(J

`(` 3*>;H \A$= - 5G - G(=?A85G -6- 1 - 8IG 1 (oG - i= & GIHi= \A *HTG ;H `(`6 - 1 ( -6- 1 - - 5GIHi=%$ *H 5# IH =*H 1 ;G G # - G(=?A(49G -6- A # R -6- - 2 9GIHi= $ Q AO< @ 7A - - Z - i= & GIH = \A#bAJ

-6- 1 - 2 5GIH = $ Q A< #]@ G9S CBG$X C G(JU G\># @ G9S `bG X5J @ G\> G XIJ IR # R G$XU IH - = R -6- 1 - 2 5GIH = $ Q A< #]@ G X]CBG(J

A\§|§ ,c©,©wzEcyt"7c@yª,Gyª,ctwc§z%"Giv«t"ckj§7tw cz|9twc§twc|9cz°yv«§,­§,cacczccyt5·@v«twaz|Ò\7zcªx§ztw§t, ¨3z°yyz7@yuyz7zÉzyyz@y\x§|tw§z$®zyª@Æzyª,Ncz7|Wv«t"ckj§7twc|Wvgt,yª,z|¾,½cytw©,yªv«v«z,qDvup*0*| yvp*w&u|cz|c~*?>vsDD| x9y| 5 uz|yw~7u*z|*| qtsu|vx5~Iv*0yc&z|y zs~*?**_wupI *p\vw

*p EG *|-; svz|y* yvDD|0z|qtsvu w p*svw&|yzz|yD|ypw z ; svz*svwuvp~*s||*|v

,Ë

X ; Êd¡m@fL)_(+/m(' #e_/.&[5]/^=[$_/`E`a_cb$de]gf hj>f>_=` d3knl>mÍz|´z·"z7v§z7|Ê­c/|cwz7$"@zc7t,yzW§y|z|´z | z7%"c|Òyz7¶twv«vz7Êzyª,c| cyt,x§Àv«z|§zW§yt,©,yª,v«v $tw c¬"/v«­cz¾|Á z·§yv«z´|v/z7vz7ʧ,c|´c§©w,©wzNÐetwc°twcz/ctw |Òy°7q³´twv«v«zNtw 3Áº@cy77czv«v«z$"3,| zcz7|Ò c ,c©©wzW/yz||z7@·"c§zNСt,yv«zNczW,c©,©,z¾ctw|Òy°7q )>tw@z7Сtw|"7z|z°·@zv§z|gtw@y - yzw,x§z|czyz7­cÀ°yz7«­Á ccz½Ðetyv«z½Á °w,§tw§t,|Òyz#""ctwcN/,|´c7z||,yz7v«z´/yz7||zc|zwq´³´z|´z·@zv§z|t,cyyªz - yz¾z·"7@7|´§||x/z7Iz7 ,| z>­Á z7 "/cczzy|tw§cc©,z7z#"/v«,|Nctw½/yz7||zc|z."§§z | z7Çqf _ #,'l # hm() f>]g` &[5m;) h>mNd1]gfn_i'5'dÍ&Ðetwc°tw <=?> |§wzSgz°yv«z°Ncz\7,cz°yNz A À7vz\§t,vGxcyz\§zS~xt,/7 `(` E IH C 65AOG5) )(v=?A ;GIHi= 7A8 (79A^H;G\>!9G1 G 0o=1 *H AIH G 3 = <i=?>ARIHGRTG -6- G @ S)FAJY@

`9` <=&>@ SJ RKX@ S8) XIJ C

`9` <=&>@&XIJ RKX@&X) XIJ C

`9` <=&>@=(J R<=&>@=(`;X5Jba<=?>c@=(`7dOJ ) 1 - =bRYX GbA0\@= ) G 37@=;`;XIJ*a(G 37@=(`7dJ9J U =O` 0d A 161

J=?AG 3A

Í&¶Ð¡t,yv«z©,7c°yª,z1nÁ c§zc7yªt,\z°>§j§ct,\Á cSªx§z7,¨Çζcczcv«z7c|tw=®z | z7z7|ÒN|c,,zA & N;G\>9G1RTG - - G @:9 "9+&'"%'3"/):9 "99! '"%'3"J

%+*!54%'"+1&%%(8 ' +Q43:4

³´±/,­cz/,yz«¨¤$ÆÇ@/z®cz|Òzczu/,yz|Wc§­czÇÁ c§z°·czÇÁ 77vz7$"@|§@cz,,z7@y¶cz7z°¾77v«z7q A\§|¾ÇÁ z·"z7v§z­cn§yÀ7cz#"=z7|¾cz@·½§yzv«zy|¾77vz7|¾czG7z°z\|ÒzG§zS/,yz||tw«¨Çr "$®¶z°¨Ò#"$®"g­c>cc­czctwc­cz G%0_S 1 RKX ,t,y|u­cz G 0X 1 RKX q ¾§,SÎ «|Òz­c>|c$"/cj§§z\ztwvcy±§zc|twB"§zzScc­§zG­§z G 0o=1 R G 0o=;`;X 19a(G%0o=(`7d1 qsut,twc|N­cz\§,c|¾z°Nz·@zv§z#"§3Á °w§t,I/yz7||zc|z,||@yzG­cz\ª±§,7ccz7|W77v«z|N§ªx§z7, cz¾|z°yª\5§¾­Á , v«twv«zÊt2 §|zyª\c7z||,yzWgtw@y cyt"ccyzNzWy|§ª7qAzN§§|"ÇÁ °,,§tw/yz7||zc|zG||cyzS,c||>­czª±§w­czSz°·"cyz7||twIcj§§||,Nc½77v«zWc½ªx§z5,§zW|zyªS,,§zN­Á cczN|zczWz§c­czNÐet,|¾¨3,,/$tw/yz||z§|z ⇒ t, ©wÀzWÇÁ z·"cyz||tw«§c|"t,y|­Á twctwNÇÁ ,,cz°y$"§tw½yzv§,z\z H.¢&$¥9/yN,,z7@yWy|§ª,z®ªq ]m 'd¡m@f=b &dÇfn]g`Ed¡_ #ÍzS7tzµ zWx§ctwv«,nz7|ÒN§j§c>twv«vz\|c$"cgtw@y

0 ≤ k ≤ n

(

nk

)

=n!

k!(n − k)!

,²

Bnz|ÒWt,||x§z\czSv«twyzy¾­cz\z\t"z°µ z¶gz7@¾,c||>|Á z·§yv«z°yN§z\Ð37D7twI|c,,z#"§z­c>°@zScz\7,cz°yn!­cncz"zWyÀ|W©,yª,cIyª$/cz7v«z

(

nk

)

=

(

n − 1k − 1

)

+

(

n − 1k

)

pour 0 < k < n

= 1 pour k = 0 ou k = n

< czSv«|z\zIt"z7@"yz§yz7°zS§zSzzS7­§twIz7 ,| z>3Áº,@yz\|c,,z>=?AA S RYX>=?AA) U AR9R ) RYX

U IH - =R >$=?A @_A`OXIJ @ )$`;X5Jba >$=?A @_A`;X5J0)

¯ - v«zgtw@ycz«gzz7|S,,z@y|¨e/yGz°·gq9"n = 100, k = 10

®"z«zv§|GÁ z°·@7@t, z7|Ò\yÀ|7z¨Ç§ccz¾y°gtwc|zu|cy G - G\>=IG "@Gv ,ª±cczGcc§°/yzv«z7$"@cyÀ|´§c|z@y|¶v«"@z|nÁ z·"7@tw=®ªq < cz|tw@t,;czcytw©,yª,vv t,É@¬@§,v«­§z#"/y7t,yz#" z|Ò§c|zµ«5,zzcyz|­Áº,c|||v§z¨3zW|Á z°·@7@zScz\Ðe#D7t,­/|>v«v«czS|@y G - G7>$=IG ® >=?A%(FA )^RIH>^RTG - - G @9@ S8)-SJ )@A%))$J9J @

0\@(@= ) SJ ) XIJ UB=O` 0_S A 161a9a0\@(@= ) =(J ) XIJ UB=O` 0vX ) 161a9a0\@(@= )"$J )F> 37@=;`;X )"$`;X5Jba > 37@=(`;X )$J9J U = O` 0vX A18)"$ O` 0X ) 1 )FA5H @= R9R$J 1

J=?A> 37@A%))$J

l #b$d. #Çd,'w_cb$de]gfÉh!7lf>m '7gn_ f>mhm9` _@b$[d'wm()Í&|tw@twz | z7n|Á z·"cyv«z\|v§z7v«z¾7twvv«z\|c `(` E IH C 69A OG5) ) (v=&A ;G5Hi= \A ( 9A ;=*H @ \AiJ \H AIH G 363 = $=?A!IH TRIHA^R8\A9H8 `^X& RTG -6- G @9@*X ) XIJ )@_A,) AJ9J @

0\@9@= )/=(J ) SJ UB=O` 0vX A 161a9a0\@9@= )$J ) & !;= $=$J UB=O` 0vX A 18)"$ O` 0vX A 18) = $61J - & !;= $=$ R & =?A= & & 0 & 37@= )7)Jba & 37@ );aX ) $Jba %3637@=;`;XIJ %363 ) %363$ U ) ` 0o= $i`;X 161

=&A& 37@&X )FA J

w¹

4 Y\[5]0# @` mhl )_i' h>] ) oÍ&|tw@twz | z7n|Á z·"cyv«z\|v§z7v«z¾7twvv«z\|c > \A5< P G O=5!5OG O=1! >\A9< RIHA^R87A9H =5!>^RTG - - G @9@ S8)-SJ )@A%)O=5/OG J(J @

07@9@= ) SJ )-SJ U = O` 0vX A 161a(a07@9@ S) $J )-SJ U O` 0_S O=1!/OG 161a(a07@9@ ) ) $J ) >\A 5< )$J U ) O` 0X A 1 ) O` 0vX O=1!/OG 161J - >\A5< )^R=\< O=5 3637@ )`;XIJIR H \A

& G i= & & 0> 37@)$`;X ) $J )F>\A5<! 3637@ )`;XIJ a > 37@ )$`OX ) $` =5! 363I@ )$`;XIJ(J 1 > 37@ )$`OX ) $J

=&A> 37@_A,)O=5!5OG J

< §zI5yª°y|Ò­czvgt,yªzczz°z|t,@twB"Ê/yz­Á zzz|Ò7°yzI/§| ci,@Æ©,©wz/yz||zc·4"z7|Ò­cz º !° ½°(°¥/£3 cEªx§z7, F!?@¡ 6/7"= 7"eF 9° £ ¢,£$1¥g¢#> 37@_A%)=5!/OG J |z°ytw7,c|q 0 Á ,@yz7|¾v«t,|"= 7t,v§z°·@,|Ò¬@v§t­cz\y7|cª,z§z\|z°yª/,|W§z7||,yz7vz7

Θ(nW )v |Wgtw@yyª,W§@FL,NÁ - yzG­§z

Θ(n2)q

,Å