14

Click here to load reader

(ISIA 5) Cours d'algorithmique (1995)

Embed Size (px)

DESCRIPTION

Lectures given at ISIA, Ecole des Mines de Paris (1995)

Citation preview

Page 1: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � ���������

���! "�$#&%('*) +-,/. 0 +-12 3%�,�4"%�5617+-,+84 9;:(�$,<,�+ #7+ =?>*) @A:(+8B7%C4ED+

FHGJIKGLFHGNM�G

OQPSRAT�UWV

X-Y�Z\[8]_^`GLacbedgfih�dj[`klh�m"npo?bqZ?Grbq[8Y�bsZ?GutCY

vxw�wzy{|{~}C�(�(���e}C�(�(�

Page 2: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �������-�

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

�<�*4x ">2#&1E=/4�%(>*�

��[ @E�� "��#E%('*) + dgh����p[?d�� �d���o?m��?mxfem<�"bedx�6hH]�oE�d���Z�Z<f���m"Y�bqo/���bq�3�?dx���/�Hbefibih��d�npm��8Yl]�m"[?h���Y��?bqY�d �8[?d¡h�mxfs�/�Hbem"[¢Z<f£�"m"Y�b£��o8��bs���¤d¥Z¦�8[;n8Y�m"§¤f ¥d���d¨�?m"[8[E�d\G© ª bJ«?bih�d�Y¬n`m"�8Y­Y��d��3[?d�Yc®��_Y�b�n8Z\Y¯tC�?h�bem"[`°_G© m�[�d�±8Zx��bs[?d²fsZ´³*µ�¶j·/µ�¸?¹º¹»¸?¼�½(¶?¾ ¿?À3¾Á¸¤¹º½(Â<Ã�Ä

��[¤d�Å +-17 3%�,j4"%�5Æ12+ dgh��Ç�8[?d¡� �d���o?m��?d´�!ÈLZxn8npY�m�±?bs��Z��Hbim�[É�3�?bnpdjY���d��Æ�!ÈLZÊ«�mxbsYQ�8[¤d&h�mxfq�/�Ëbim"[�Z\n8n8Y�m�]�o&�dgdE�!ÈL�8[¤d&h�mxfq�/�Ëbim"[¦m�n/�HbJ���Z<fidÌd�[��8[��Hd���n¤hE��dgbifefid��8Y­�3�?d¨[&�d�]�dgh�h�b��Hd�Y�Z<b-fidS]gZ<fq]Ê�?f!��ÈL�8[?dh�mxfq���Hbim"[Ím"n/�Hbs��Z<fidxG© m�[ÎY�d��3ZxY��?djY�Z´fed�Ï"¶?À�¸"·pÄ�Ã-µ�¿`ÄÎÐg¶¤¹º¹WÄѵ�Ð�Ä

Ò�dgh =8:(��,z,�+-, #7+ =¤>*) @A:(+8B7%C4ED+ n`d�Y���d����Hd�["�Ó�?dW]�fsZ<h�h�d�Y�fsZ�?bJÔ�]g�?f£�?�dÕ�¤dgh²npY�m"§?f ¥dj��dgh¬d��S�?d¡�?m"[p[?d�YÌ�?dghÍÖ�h�m\fq�/�Hbem"[?h×Zzf��"mÑ�Y�b���op��bq�3�?dgh7]�m"���¦�8[¤dgh�Ø ¥Z²]�d�Y���Z<bs[?h7n8YÙm"§?f ¥d���dÊh�«?bsZ×�?dghQ�_Y�Zx[?h��tÚm�Y���Z��Hbem"[?h¬Z\n8n`dgf��dgdgh ÛD+-#E1E=/4"%(>*� Zx�E�d��3�8Z��ËdghgG

Page 3: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �������-Ü

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

�� ">Á'Á "��) ) �Ý4"%(>*� #ÆÞ&�7��) %5Æ17+

© d�±�dj��n?fidS�?dßnpZxY�Zx�?b£�3��dxG© befifs�?h���Y3�d×npZxYÛfsZ¦�¦�¤f��Hbsn?fibs]gZ��Hbem"[àh/�d�Y�bed²�?dÇá ��Z���Y�bs]�dghgG

â �äã â �¨ã åzå<å�ã â æm"[ n`d��/���?m�[8[?d�Yß�p[?d�� �d���o?m��?d �?d�]gZ<fs]g�?f¯�3Y�çZx]�d�Zx�/± n8Z\Y�d�[3���o&�dgh�dghÊè

â � â � â Ü â énpdj�/�cZ<bs[?h�b&çd��_Y�d¨]gZ<fq]Ê�?f��dßnpZxY�è

®�®�â � ®�â � â Ü °�°�â é °�êm"�Îd�[p]�m"Y�dSn8ZxY

®�®�â � â � °_®�â Ü â é °�° å© ë æ ì �æ�í �<î � ææ�ï tCZÝð]�m�[?h�n`mxh�h�bs§?fidÊhÉ®ZxY�§8Y�dÊh¦h���YÙbq]_�Hdj��d�[\�Ó§?b��[8Z<bqYÙdgh ¥Z�á»[?ñ×�8�?h_°��?dEn8ZxY�dj[\��oE�dÊh�d�YÝfed7�Hm"�/��G ¥M ]_opZx�3�?d7hH]�o&�d���Z�?dß]gZzfq]g�?fò�8m"[Ínpdj�/�cfq�¤bÁZ<h�h�m�]�bed�Y¬�8[Í]�m$ç�/�jè?fid´[?m"�¦§pY�d¨�?dß� �?fJ��Hbqn?febq]gZÑ�Hbim"[¤hlYÙd��3�?bih�dÊhcn`m"�8Yó]ÊZ<fq]g�¤fid�Y¬]�d²n8YÙm/�p�?b���G

© ]�m�ç�/�E�E�d�n`d�[p�8Zx["�7�8�¦hË]_oE�d���Z¤Gxô²[Ó�&�dgh�bqYÙdÌ��bq[?bs��bih�d�Y¯fedÌ]�m$ç�/��?dgh¬� �?f��Ëbqn?febq]gZ��Ëbim"[?hÊG

Page 4: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � ������� é

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

�� 3%��E=8%(@¬+ #2+ :(� �� ">Á'Á "��) ) �K4"%(>*� #¯Þ&�2�$) %�5Æ12+

© m�[õY3�dgh�m"�8���?dghSn8Y�m"§¤f ¥d���dgh¨n8ZxY��Hbidgfehßd��Sm"[�]�m"�¦§¤bq[?d�fidÊhßY3�d��hH�?f��_Z��Hhcn`m"�8YAm"§/�Hdj[?bqYAfqZÕh�mxfq�/�Ëbim"[;ö-[8Z<fid\G© �Ì[?dÍh�d��?fed�tCZÝð]�m�[ �?d»]gZ<fq]Ê�?fid�YÓâ � ã â � �2â � ã â Ü �AGqGqGq�â æ<÷ � ã â æ G-ô²[»]gZ<fq]Ê�?fid�fidÊhl]�m�ç�/�HhcZzh�h�m�]�b��dgh ¥Z�]�o8Zx�3�?d×npZ<bqY�d�?dß��Z��_Y�bq]�dÊhó]�m�[?h/�d�]g�/�ËbJ«�dghÊG© np�?bih7m"[Ó]gZ<fq]Ê�?fidcfedghE]�m$ç�/�Ëh7��bq[?bs�¦�8��hÆ�?dä�¦�?f£�Hbqn?febq]gZÑ�Hbim"[��?d��Y�bqn¤fid��Hh�]�m"[?h��d�]Ê�/�HbJt�hS®�â � â � â Ü °Û�¤dß��Z���YÙbq]�dxèø�ù â � â � â Ü�ú ì ��bq[!û ë ù ®�®�â � â � °�â Ü ° ú ê ë ù ®�â � ®�â � â Ü °�° úü

© np�?bih n`m"�8Yß�Hm"�/�Ëd�h�m"�?h��hË�?b��Hd»�?d�ýþ��Z���Y�bs]�dgh¡]�m"[?h��dj]g�/�Hb�«�dghg�d���]<GqGsG

Page 5: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �������-ÿ

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

� � ��:('Á>Á 3%C4 Å ) +

��>Á �� èJì � 4x> á #7>��>Á �� èJì ��� � 4x> á #7> ø��� �ù � ê � ú èJì ��� ���>Á �� èJì � 4x> á #7> ø��� �ù � ê � ú èJì � ���>Á �� èJì � 4\> á � � #2>��>Á �� è�ì � 4x> á � �à#7>��>Á �� èJì ��� � 4\> ��� �à#7>�¬+`'*%�� è�ì ø��� �ù � ê � � � ú � ø��� �ù � ê ��� � ú � � ù � ú�� � ù � ú�� � ù ��� ��� � ú �%�� �� ø��� �ù � ê ��� � ú 4 Å +-��ä+`'*%�

ø��� �ù � ê ��� � ú èJì �� � �! " �#� � ù � ê �$� � ú èJì ���+-�E#%�

+-�E#%�

© MÌf£�"m"Y�b£��o8��d¯d�['&Í®á Ü °Ýd��Ád�[²dghËn8Zx]�d7� �d���m\bqY�d �3�8Zx�8Y�Z��Hbq�3�?d\GÒ�dßn8Zx�3�?d��ß®�â ( ã åzå<å�ã â )g°EZÕfed×��dgbefifidj�8Y¬]�m$ç����è

*+* â ( ã â ,.- (0/1/ -325476 (98 )!:i÷ �<; * â ,=- (>/1/ -3254?6 (@8 )!: ã â ) ;;

Page 6: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �������BAW

WW

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

C 12+-:�5Æ12+-,W���! "�$#E% '*) +-,

D ª b�«?bih�d�Y n`m"�8Y�Y��d��3[?djY�è�m"[ �?b�«�beh�dW�8[ npY�m"§?f ¥dj��d�d�[ h�m"�?h��n8Y�m�§?f ¥d���dghÊG6ôS[ tC�?h�bem"[8[?d�Z<fem"Y�h�fedgh�h�mxfs�/�Hbem"[?h��?dghÓh�m"�?h��n8Y�m�§?f ¥d���dghÌ®��_Y�b��¤d�[x«3dgfim"npnpdÇ]�m"[\«�d�±?dx�KGqGqGJ°

DFE beh�d�]_�Ëbim"[3� ª �d�]�bs��Z��Hbim�[!è8m"[W]�o?d�Y�]�o?d ¥Z �dgfibs��bq[?d�Yc�¤dghÌ�?m"[3�[E�dgdgh����¤bl[¤d�npdj�3«�d�["�;n8Z<hÓtCZ<bqYÙdõnpZxY��Hbedõ�¤dWfqZ h�mxfq���Hbim"[�GG ±?d���n?fed²]gZzfq]g�?fed�Yófed²ý { n?fq�¤hcn`d��Hb��Í�dÊfË�d���d�["��G

ø ®(áÆ°Ûì HIJ IK&à®L��° h�b$á M ý&à®(áÆ° � &à® éÿ á6° h�bs[?m"[

I/mxb£� ø ®(áÆ°Eì &à®(áÆ°_G

DFN d�]�o?d�Y�]�o?d*d�±8o8Zx�¤h��HbJ«3dxègm"[¨n8ZxY�]�m"�8Y�h$�8[��3Y�Zxn8o?dÆ�?dQ�Ëm"�/�HdghfidÊh�n`mxh�h�bs§?bifeb��¤�dgh�d��Óm"[ ��ZxY����¤dº]�dÊfifidÊh����¤bóhHZ��Ëbih�t�m"["��[?mxh]gY�b£�?�d�Y�dghÊ�/d��_]<GqGqG

Page 7: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �������$OW

WW

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

0 +-17 3%,�4"%�5617+�Pä: + Q*>-Þ*�!'Á+-17 #7+ =?>*) ) +` 3=?+

R6Y�m��3«�d�Y7�8[�]�bsY�]g�?b£�cn8Zzh�hHZx["�­�8[?dät�mxbihän8ZxY¯�Hm"�/�ËdghEfidghÛ«�befifedgh×®(á«�befifedgh�°c�?dÌtCZÝð]�m"[ ¥Z ��bq[?bs��bih�djYÛfid´]�m$ç�/�ä�8�º]�bqY�]g�¤b���G© h�mxfq�/�Ëbim"[²d�±¤n`m"[¤d�[\�Ëbidgfefid7d�[S&à®�T æ °_G�MÌf£�"m"Y�b£��o8��d¯�¤d6Y�dj]_o?djY�]_o¤dd�±8o8Zx�?h��ËbJ«�dx�~§8Zx]�^z�_Y�Zx]�^\bs[/�`�¤§8Y�Zx[p]_o3��Zx[8�3��§`m"�p[8�!�`GqGqG© m�[É�E�dÊh�bqY�d ]gZ<fs]g�?fed�Y�d�ÔÓ]gZ\]�d���d�["�Ì�8[?d�h�m\fq�/�Hbem"[¢Z\n8n8Y�m�]�o&�dgdxGU6Z<hän?fq�?h�]�m$ç�/�Hdj�?h�dS���¤dß�?d��/±�tÚm\bih¬fòÈNm"n/�Hbs��Z<f�èm"[º]gZzfq]g�?fed×f�ÈLZ\Y�§8Y�d×YÙd�]�m"�3«8Y�Z\[\�ä�?dßn`mxbs�?hÌ��bq[¤bq��Z<fÆ®WVYX0Z[X>\^]�\_a`cb Z�Z[X>Zd�egfih+h�°_GE m"Y�[¤dÕbs[3tj�djY�bid��pY�d��8�þ]�m$ç�/�Çn8ZxY¨f�ÈNM Nkj n8�?bihÇm"[¢n8Z\Y�]�m"�8Y��²d�[n8Y�mÑt�m"[8�¤d��8Y�èÆm"[ m"§��Hbid�["���p[ ]?l8]�fidÉ�?dºfem"[/�3�?dj�8Y�§`m"Y�[E�dgdÍn8ZxY�?d��3± t�mxbih�fid ]�m�ç�/���?d f�ÈNM Nkj GSô²[ hH�8n8npY�bq��d Zzfim"Y�hà�Ëm"�/�Hdghfidgh�m�]g]g�8Y�dj[8]�dgh�� �?f��Hbsn?fidÊhõ�¤dgh»«�befifedgh �8Zx[¤h�]�d n8ZxY�]�m��8Y��Wd�[]gY��d�Zx["���¤dgh�Y�Zx]g]�m"�8Y�]�behgGEô²[ �¤bq��bq[��?dWZzbq[?h�bcfsZ ]�m"��n?fed�±?b��¤�d ¥Z&Í® � fim<�­áÆ°&d�[ÍZal/Z\[\�­�8[?dSh�mxfs�/�Hbim�[àZxn8n8YÙm/]�oE�dgdxG

© j �?f£�Hb��_�8�?dghW��ÈLo?d��8YÙbih��Hbs�3�?dgh�]�m"[p[/�?dÊhºZx�nm�m��8Y��!ÈLo��?bòG E m"Y�[?dbq[3tj�d�Y�bed��8Y�dÇ]�m"[8[��?dSnpm��8YÛfòÈLZxn8n8YÙm�±?bq��ZÑ�Hbim"[��/d��_]<GqGqG

Page 8: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �������BoW

WW

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

9º: �$,<,Ñ+` :(+-,à@E ">��Û:?p+-) +-,

© ]�m"��n?fid�±�b£�?�d²�¤dgh¬n8YÙm"§?f ¥d���dÊhgG© ¥M n8ZxY��HbqY7�!È �8[?dÌ]�m"��n¤fid�±?b��¤�d����pZx�8Y�Z��Ëbq�3�?dx�3fidÊhÛnpY�m<�3Y�Z\����dghbq��n?fsZx[\�_Zx[\��fidÊhÁZ<f���m"Y�b��_o8��dgh�[¤dQh�m�[\�$�/�HbefibihËZx§?fidÊh6n`m"�8Y��8[c�3Y�Zx[8�[?m"�¦§pY�d¨�?d²�¤m"[8[E�dgdghÊG© E d�Zx�8]�m"�8n��?dÌn8YÙm"§?f ¥d���dÊhE�?m"["�EfqZ¡��dgbifefid��8YÙdlh�m\fq�/�Hbem"[ºZzf��"mÑ�Y�b���op��bq�3�?d �$=/4"17+-:�:(+ dgh��äd�±8n`m"[?d�["�HbidÊfifid\G© ôS[�[?dÌhHZ<b��­n8Zzh&hÊÈNbifKd�±?bih��Ëdl�p[?dÌh�mxfq���Hbim"[;n`mxfql8[?m���bqZ<fed²n`m"�8Y]�dgh¬npY�m"§?f ¥dj��dghgG© G7[\«?bid¡�?d¡]�fsZ<h�h�d�YÌfidÊhßn8Y�m�§?f ¥d���dghÎÖ(tCZx]�bifedgh�Øþ®(�?d¡]�m"��n?fed�±?b��¤�dnpm\fql8[?m"��bsZ<fid�°¯Z\�3±¦n8Y�m"§¤f ¥d���dghSÖ��?b�ÔÓ]�bifidÊh�Ø�®(�?d­]�m"��n?fed�±?b��¤�dód�±��npm�[?d�["�Hbidgfefid�°�G© Ò�bs��b��Hd�rpm"�¤dxGsUÆZxYEd�±?d���n?fid\è�xG$RÆY�m"�3«�djY&�p[º]�o?d���bq[��?dSt ¥Zvuà�?dß]�m�ç�/�­bq[3tj�d�Y�bed��8Y ¥ZÓâ GT?G$RÆY�m"�3«�djYc�8[õ]�o?d���bs[��?d�t ¥Zwu¢�?d ]�m$ç�/�ShH�8nE�djY�bid��pY ¥ZÍâ G� dgh��An`mxfql8[?m���bqZ<f-Z<fem"Y�hE�3�?dcfedghEh�mxfq���Hbim"[¤hÛ]�m"[8[��?dgh7n`m"�8YT h�m"["�­d�±8npm�[?d�["�HbidgfefidghÊG

© E dgh�mxbs[W�?d×hHZÊ«�mxbsYäh�b��Hm"�/�¨n`d��/�Ìh�dStòZzbqY�d�d�[º�Hdj��n?hcn`mxfql8[?m<���bqZ<fòG ª Èrm ¥��fsZÕ�3Y�Z\[8�?dS���¤dgh��Hbem"[à�?d¨f�ÈNbs[3t�m"Y���Z��Ëbq�3�?dxè

x ì y xwz

Page 9: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �������B{W

WW

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

9;:(��,z,�+-, x +84 y x

© ôS[àZxn8n`dgfefid ]�fqZ<h�h�d�x f�ÈNd�[¤h�d��¦§¤fid��?dghÌnpY�m"§?f ¥dj��dgh¬�3�?b*n`d��3�«�d�["�¨çd���Y�dÌY3�dgh�m\fq�?hAn8ZxYE�8[�Z<f£�"m"Y�b£��o8��d #ÎD+84x+` 3) %��&%�,�4x+ �¤d¬tCZ��ð]�m"[ºn`mxf|l8[?m"��bqZzfidxG© ôS[²Zxn8n`dgfefidE]�fsZ<h�h�d}y x fòÈNd�[?h�d��¦§?fed¯�?dÊhÁn8Y�m"§¤f ¥d���dghK�3�?b"n`d��3�«�d�["��çd���Y�d×Y3�dÊh�mxfq�¤hlnpZxYc�8[WZ<f£�"m"Y�b£��o8��d �7>*� #ÎD+84x+` 3) %�E%�,j4\+�?dÌtCZÝð]�m�[În`mxf|l¤[¤m"��bqZ<fedxGÒ�d [?m"[ �E�d��HdjY���bq[?behH��d�n`d�Y���d��Í�?dþ]�o?mxbih�bqYà�8[¤dõbs[?h���Y��p]_�Hbim�[n8ZxY���b$�8[Îd�[¤h�d��¦§¤fid¨ö-[?b��!Èrbq[?h��_Y��8]_�Hbem"[?h¬�HdÊfÁ�3�?dßf�È Z<f��"m�Y�b���op��d]�m"[\«�d�Y��"d�«�d�YÙh¦fqZþh�mxfq���Hbim"[ h�bódgfefidWd�±?bihÙ�Hd ®Cd�[ n8Y�Z��Ëbq�3�?dWZÊ«�d�]�8[?d²bs[3ö~��dSn8Y�m�§8Zx§?befib��¤�d�~J°U7Y�m"§?f ¥dj��d'�����Wè/hËZ��Hbih�ö~Zx§?befib£�?�dÕ��ÈL�8[?dSd�±8n8Y�dgh�h�bim"[à§`m3mxf��dÊd�[8[?dxGI/mxb����º®�� � ê å|åÚå ê���æÑ°¬�8[?d×d�±8n8Y�dÊh�h�bim�[õ§`m3mxf��dgdj[8[?d ¥Z�á «xZxY�bsZx§?fidÊhgGG ±�beh��Hd���bifÁ�8[¤dlbs[?h���Zx[p]�d²�¤d��Çì ®�� � ê åÚå|å ê���æÑ°E���¤b!�?m�[8[?dS�º®��Ñ° ¥Z� f b X1z© MÌf£�"m"Y�b£��o8��d�[?m"[ �&�d��Hd�Y���bs[?bihÙ�Hdàfibs[&�d�Z<bsY�d���Z<bih�Zzf��"m"YÙb���o8��d�&�d��Hd�Y���bs[?bihÙ�Hdld�±¤n`m"[¤d�[\�Ëbidgf�~�~�~#ÎD+��A1¯4@¬>*17 w�»#7+ � p� á ���$% "+���� ë�� &���� ®!� ���B� êa� � � t ° �,<% �º®��Ñ°7ì � ���B�E��:(>Á 3, � dgh��ähHZ��Hbeh�ö~Zx§¤fid

,z%��2>*� � [?m"[ÎhËZ��Hbih�ö~Zx§?fed ��H,<%L��ó�

Page 10: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � ����������W

WW

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

� D+-#&1E=/4�%(>*� ��>*:òÞ&�7>*) %(��:(+

© U d�Y���d��­�?dSY�dgfebid�Y­fqZ��?b�ÔÓ]Ê�?f��¤�dS�?dghän8Y�m"§?f ¥d���dghAd�[\�_Y�dÌd��3±!G© m�n&�d�Y�Z��Hdj�8Y¯�?d ÛD+-#E1E=/4"%(>*� � ÛD+-#&1E=/4�%(>*� @¬>*:CÞ7�7>*) %(�$: + �GqGqG��[�npY�m"§?f ¥dj��d%� � dgh��An`mxf|l¤[¤m"��bqZ<fed���d�["�EY3�d��8�p]_�Hbq§¤fid ¥Zß�p[�n8Y�mÑ�§?f ¥d���d�� � h�h�b-bifKd�±?bih��HdÇ�8[?d¨Z<f£�"m"Y�b£��o8��d¨n`mxfql8[?m"��bsZ<f�Y��dgh�mxf�«zZ\[\�� � �Ñ�/�HbefibehHZx["�E�8[�Z<f���m"Y�b��_o8��dAY��dgh�mxf�«zZ\[\��� � �<�?dA]�m���n?fid�±?b£�?�dÛn`mÑ�fql8[?m"��bsZ<fidxGI/mxbidj[\��è� � Pc9;%( 3=81E%C4�0 ��) %:C4\>*�&%(+-�k� RÆY�m"�/«�d�Y��8[ ]�bsY�]g�?b£�ºh�bq��n?fed

�3�?b�]�m"��n8Y�d�[p�¦�Hm"�?h­fidgh¬h�m"����d��HhA�!ÈL�p[Ó�3Y�Zxn8o?dÇ�?m"[8[E�dxG

� � P­�� ">��A:7p+-) + #ÎD+-=p%,z%(>*�&�7+-:W� �G6�_Zx[\�$�?m"[p[&�d6�8[c�3Y�Z\n8o?dÆ�?d«?bifefidghÇ«xZ<fq�E�dÓ�?dghÇ�?bih��_Zx[8]�dghSbq["�Hd�Y�� «�befifedghg�Á��Y�m"�/«�d�Y¨�8[¢]�o?d����bq[¡n8Z<h�hHZx["�6npZxY$�Ëm"�/�Hdgh fidÊh «?bififedghE�?dAfim"[��3�?d��8Y bq[3t��d�Y�bed��8Y�d¥Z¡�8[?dß]�m"[?h���Z\[\�Hd�ö?±E�dgdSâ G

Page 11: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � ����������

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

� D+-#E1E=/4"%(>*� :�%��ÎD+`��%( "+

N �dj�8�8]_�Hbem"[;�?d�� � ¥Z�� � èD MÌh�h�m�]�bed�Y ¥Z¦]�o8Zx�3�?d¨h�m"����d��ó�p[?dc«?befifid\GD I/b$�?d��3±�«?bifefidgh¨h�m"["�äY�dgfib��dgdghcn8Z\Yó�8[?dÇZxYÊçd��Hd\�"«xZ<fs�?d�YófsZ��?bih����Zx[p]�dlbs[\�Ëd�Y��C«?bifefid�n8Z\Y��x��m"��T¡h�bq[¤m"[!G

D G ±?d�]g�/�Ëd�Y��8[ Z<f���m"Y�b��_o8��d�Y��dgh�mxf�«xZx[\��� � hH�8Y�f�Èrd�[?h�d�� §?fid�?dghó«�befifedghßZÊ«�d�]Çâ ì áEGKô²[ºm�§/�Hbidj[\�ch�mxb��S�8[à]�o?d���bs[º�?dfim�[/�3�?d��pY7á¢h�mxb£�ófsZ´[¤m"[3�d�±?beh��Hd�[8]�dl��ÈL�8[¦�HdgfK]�o?d���bs[!G3I/b`fed]�o?d���bq[�d�±?beh��Hd×Z<fem"Y�h¬m�[ºZ¡�8[º]?l8]�fed×o8Zx��bef��Hm�[?bid�[�G

ÒÁZ´��Y�Z\[?h�t�m"Y���Z��Ëbim"[�®(Y3�d��8�p]_�Hbim�[`°¯h�dÌtCZ<b£�cd�[��Ëd���n?hAfibq[E�djZ<bqY�d\G© F�]�b2Y��d��8�8]��Hbim"[���Y�b�«�bsZ<fid\�Q��Zzbih²fsZàn?fs�8n8ZxY��Õ�8�É�Hdj��n?h²fedgh×Y3�d���8�8]_�Hbem"[?h ¥Z¦�?dghän8Y�m"§¤f ¥d���dgh e3¡ ` h _ [?d¨h�m"["�cnpZ<h¬�?bsY�d�]_�Ëdgha~�~�~

Page 12: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � ��������(�

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

�� ">��Û:?p+-) +-, y x�¢ #E%3£ =8%�:(+-,º+84 y x�¢ =¤>*) @A:(+84",

G ±�beh��Hd��(�Ù�bifÇ�?dgh�n8YÙm"§?f ¥d���dÊh��?dwy x ]gZx[¤m"[?bq�3�?dÊhg�A�?m"["���Hm"�/�Zx�/��Y�dþn8Y�m�§?f ¥d���d��?d�y x fq�¤b²dgh��»n`mxfql8[*çm���bqZ<fed���d�["�àY3�d��p�8]���Hbq§?fedz© ¤�¥�¦ ~��[ n8Y�m"§¤f ¥d���d7dgh��}y x ���?bJÔ�]�bifed¬h�h�b��Hm"�/�Æn8YÙm"§?f ¥d���dA�?d=y x fq�¤bdgh��cn`mxf|l8[?m"��bqZzfid���d�["�äY��d��8�8]_�Ëbq§?fedxGRco&�dgm"Y ¥d���dä�?d�§¬ôßô�¨ �+©[ª«�xè��¬��� dgh���y x ���¤bJÔ�]�bifed¦®���o ¥dÊh�d�°_G© MÌbs[?h�b��Æh�bEm"[¢��Y�m��3«�d��8[?d�h�mxfq�/�Ëbim"[ npm\fql8[*çm"��bsZ<fidÍ�?d­�����Z<fim"YÙhÕm"[ Z��8[?d�h�m\fq�/�Hbem"[ n`mxf|l8[*çm"��bqZzfidàn`m"�pYS�Ëm"�/� n8Y�m"§¤f ¥d���d�?d%y xWG��[ n8Y�m"§¤f ¥d���dWdgh��Yy x ��]�m"��n?fed��;h�h�b²bef²dghÙ��y x ���?bJÔ�]�befid d���8Zx[?h�y xWG© ����� �pZx[?h¬y x ��]�m���n?fid��jG© N dj]g�?dgbefÝ�¤dÌn8Y�m"§?f ¥d���dgh�y x ��]�m���n?fid��Ëhgè«®²ZxY�d�lÓd��°¯<m"op[?h�m"[!èn?fq�?h��?d²±#���ÕY3�d�t��d�Y�dj[8]�dghgG

Page 13: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �����Ù���(Ü

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

C 17+-:�5617+-,W@E ">��A:7p+-) +-, y x�¢ =?>*) @A:(+84",

D hHZ��Ëbih�ö-Zx§?bifeb��¤�dS�!ÈL�8[¤dAt�m"[8]_�Hbem"[�§`m3mxf��dgd�[p[?dch�m"�?h2t�m"Y���dä[?m"Y����Z<fedl]�m"[³m�m"[8]_�ËbJ«�d ¥Zß��Y�mxbehÛfeb��¤�d�Y�Zx�3±Î�8Z\[?hA]_o8Z\���¤dl�¤bih´m�m"[8]_��Hbem"[!Gµ±��¶�����»G

D RÆY�m"�3«�djY&�p[Îh���Z\§?fid ¥Z � h�m"����d��HhA�8Zx[¤h¬�8[��3Y�Zxnpo?dxGD U7Y�m"§¤f ¥d���dE�8�×hHZx] ¥ZÌ�?mxhA®L·#Z b�`_?bn¸ ·�°_G\I/mxb£�¬¹ �8[´dj[?h�d�� §?fid�!ÈNdj[\�Hbed�Y�hÁd�� �p[ßd�[\�Ëbid�YÁ�?m�[8[&�dx��d�±�beh��Hd���bif»º ¼ ¹ �Hdgfifedó�3�?d½¿¾À+Á tþì z

D §Âl8]�fedßo8Zx��bef��Hm�[?bid�[D�à mÄl/Z��"dj�8YE�?dß]�m�����d�Y�]�dD §Ûmxfem"Y�bed�Y´fedgh¦h�m"����d��Hh��!È �8[ �3Y�Zxn8o¤d ¥ZÉfòÈLZ<bq�¤dà�?dw±�]�m"�3�fidj�8Y�h×�?d h�m"Y��Ëd��3�?d��?dj�3±õh�m"����d��Ëh²Zx�nm�Z\]�d�["�Hh²Zzbid�["���?dgh]�m"�¤fid��8YÙh¬�?b|Åä�djY�d�["�HdghgG"ý�]�m"�?fidj�8Y�hÛ�Ëm"�³m�m"�8Y�hän`mxh�h�bs§?fid�n`m"�8Y�8[��3Y�Zxnpo?d²n¤fqZx[8ZzbqY�d�® d�±!G8��Zxn3����m"[8�?d�°�G

D U7Y�m"§¤f ¥d���d��?d¡n8ZxY��Hb��Hbem"[!è�h/�d�n8ZxY�djYc�8[Wd�[?h�d�� §?fid¡�!Èrd�[\�Ëbid�Y�hd�[;�?d��3±Îh�m"�?h��dj[?h�d�� §?fidghä�?dS�Wçdj��dch�m"����dxG

Page 14: (ISIA 5) Cours d'algorithmique (1995)

� ��

�������� �������� � �����Ù��� é

WW

W

vers

ion

page

htm

lco

pyri

ght 1

996

Nie

lsen

Fra

nck

� � ) Þ&,j4�p+` "+�P x ì y x Æ

© �/Y�Zx[8�?dS�3�?dgh��Ëbim"[à�¤dlfòÈLF�[3t�m"Y���Z��Hbs�3�?d�®3RÆ�8Y�bs[/�¦MÈÇcZxY��?h_°© Z\� �E�d�npZxY����Hm"�/�Ófid»��m"[8�?d;n`d�[?hHZzb����3�?dÍfqZ Y3�d�n`m"[¤h�d �d��_Z<b��¤�¥�¦ ®ÊÉ �+��Z\[?h�°_G8M¨�³m�m"�pY��!ÈLo��?b�fedghc�"d�[?hÌn`d�[?h�d�[\�l���¤d×fqZ�Y3�d��npm�[?h�d²dÊh��ÌË ¤ Ë�G© Í �8Zx[8�Ìm"[lh�dQ��Y�m��3«�dÆ]�m"[3tCY�m"["�¤�d ¥Zó�p[²n8Y�m�§?f ¥d���d$y x ��]�m"��n?fed����m"[ ]�o?d�Y�]�o?d ¥ZÎ��Y�m"�/«�d�Y²�¤dgh¡Å +-12 3%�,�4"%�5617+-, �*]zÈNdgh��Ù� ¥Z����?bsY�d��?dghZxn8n8Y�mj±?bq��Z��Ëbim"[?hÊG© ª m"[8[?djY��?dgh�§`m"Y�[?dgh�hH�8Y�fedgh;Zxn8n8YÙm�±?bq��ZÑ�Hbim"[¤h�Z<bq[?h�bä�_Y�m"�3�«&�dgdÊhgG�ô²[�]_o?djY�]_o¤d�§?bid�[ �d�«?bq�?dj����d�[\���?dgh¨o?d��pY�bih��Ëbq�3�?dgh×n`mxf|l3�[*çm"��bqZzfidghgG

© Ò�bs��b��HdÊh¬��o&�dgm"Y�bs�3�?dgh¬�¤dghÌ��Zx]�o?bq[?dÊhgGµU7Y�m�§?f ¥d���dgh­Y�d�[p]�m"["��Y��dghd�[ºn8Y�Z��Hbq�3�?d\G© E dgh�mxbs[º�!È Z<f��"m�Y�b���op��dgh�Ö�npY�Z��Hbs���¤dgh�ئd��cn`d�Y�t�m"Y���Z\[\�HhÊG