56
a := b +2 a := b +2 a := (a + 2) * b

+2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

  • Upload
    others

  • View
    3

  • Download
    0

Embed Size (px)

Citation preview

Page 1: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

1 2�3 4658793 7�:<; =

>@? ACBEDGF�?IHKJ LNMPOQDEJ ?SRTJVU,F�?IFXW0YGD JZA�F[]\_^E`badcfeda�g]hji k�l inmGopcqiKrjrje!\S[>sJVA ?nU,FXW0YGDbAutwvV?�xyWzA{v|JZA x0YdtXA LEJ A{YGD J}HKvZU|OKF~W0Y�D A�YGD�F ��d� � D v<�n?�x�OEJ8x�M�J}HE�qtwJZA~A{W0YGD LQ?nDbANx�M�JVDG�pW�t~YGDbDEJV� JZD�F�U�YGOKt?dDGF�p� >�M�JZDG�KW�twY�DbDEJZ� JZDGF�JZACF@� YpLEW0�Qv �Zx�?��d?�x0JZOEt�LqJ�x�?��n?StwW�?��bxyJ

LEJ<�pWyJZDGF `ba�h9��inmGopcqiKrjrje!\S[�� ���HKJZ� �bx0J �

�s�S� �}�V�V�I� �� K¡,¢X�C�£��¤¦¥§� �¨�S� �Z©�ª�«,¬­9�V®�¯��S° ­9�V®�¯²±K° ­9�V®�¯³�S° ­9�V®�¯´±p°

µ ¶,·a := b + 2

¶<¸ ¶,·¶,·

a := b + 2¶<¸ ¶,·

¸ ¶,·a := (a + 2) ∗ b ¹ · ¶,·

Page 2: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- '

&

$

%

��� ; � :�7�� � 4

� D ?�x�dYdtwW'F�b� J JZACF U<YG� �TYGA{v �� LNMPOQD DEYG� )ObD A�BE� �TYdxyJ��� LNMPOQDEJ A{�TvZU<W0�fU£?IFXW0YGD U<YG� �TYGA{v|J� LNM ObDEJ �f?St{F~WyJ � ����������� � DqYG� A�� F�Bp�TJZA LEJZA �f?St?d� �<F~twJZA��

U<YGDQLEW'FXW0YGDbA ��ONM�W0xzAu�Gv�t~W��QJZD�F� LNM ObDEJ �f?St{F~WyJ � ����!#"%$'&($�� �n?�xyJZOKt�U£?�xzU£OEx0v|J ³t~J<F~Y�OKtXDEv£J��s�f?�t

x M ?�x)�dYntwW�F�b� J*�TLEv�� DEW0J JZD + Y�DbU,F~WyYGD LEJZA��f?�t?n� �<Fwt~JZA� LNMPOQD U<Ynt~�]A U<Y�� �TY�A�v� LNM ObDEJ �f?St�FXW0J ,-�/.�")&�0/&($213��� ,-� 4(&50613&-7�"8� � DqYG� A J�F F�Bp�TJZA

LEJ FXYGOpF~JVA x0JVAN�n?�twW�? �bx0JZA9OpFXW0xyWzA{v|JZA¨�f?Stsx M ?�x�dYdtwW'F�b� J �v<�GJZD:9FOqJ|x0xyJZ� JVDGF �pW�LEJ��

� LNM ObDEJ �f?St{F~W0J 1;����$<06!�.=$<1>�5��� � WzDbACFwtObU,F~WyYGDbA twvV?�xyWzA{v|JZA �f?�tx M ?�x)�dYntwW�F�b� J �TY�OKt UZ?�xzU|Oqx0J�t x0J twvZA~OEx�F�?IF �@? ?St� W�xyJZA W�DbAA9FwtObU,FXW0YGDbA LEYdW'F �B�GOKtwJ|t x M�WzDbACFwtObU,F~WyYGDcqi(Cb\5DpcG[]inc inmGo � >sJ6t~vZA~OEx'F ?IF UZ?�xzU|Oqx0J�t �f?�t�x M ?�x)�dYntwW�F�b� JJZACF�x�?6�n?�xyJZOKt�LEJ�x�M�J<HK�qtwJVAwA{W0YGD inmGo LQ?dDbA¨x M�JZDG�pW0twYGDQDEJZ� JZDGFU<YGOEt?nDGF �E F�FHG#IJF�KMLJI NOLJI PRQ8KSIJFHGUT5VWKXF VYG Z L[VWKX\]GUT ^MG#P _a`BTb`#cZ deF�T�G#P _a`BT fWIYG `hgiG#jRFk`hFbKMLlI

Page 3: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

� U}twW�FOKt~J LEJZA ?�x)�dYnt~W'F�Q� JZA �E ^�� LlT5KXF��WZ G �QDqYG� LEJ x M ?�x�!YntwW�F�b� J� LJIWI�� G#P �QLEJZA~U}t~W0�EFXW0YGD LqJZA��f?St�?n� ��FwtwJVA �#PHfW^XFk`hF �fLEJZA~U}twWy�EF~WyYGD LbO twvZA~OEx'F ?IF vZU<x�?St?IFXW0YGD LEJZA��n?�twW�? �bx0JZA��V��� ]f[F

? ?St{F~W0J W�DbACFwtXOQU,F~WyYGDbA\ I ` ^�� LlT�K F��WZ G

1 4�� �N7 ��� 587�� ��4�� 4 5 ; = 7 ��� � 4

>�? A{vk��OqJZDbU<J LNM�WzDbACFwtObU,FXW0YGDbAInst1 ; Inst2 ; . . . ; Instn

Page 4: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- '

&

$

%

>¨JZA�WzDQA�F~tXObU,FXW0YGDQA U<YGDQLEW'FXW0YGDbDqJ|x0xyJZA �PkK�� \S[�� ` ^XLlT�P

� DbACF\ I PkK

PkKCond

` ^MLlT5PInst1PkK IYLJIInst2\ I PkK

PkKCond1

` ^MLlT5PInst1

PkK IYLJI PHKCond2

` ^XLlT�PInst2PHKSIYLJIInst3\ I PkK

Page 5: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

��HKJZ� �bx0JZA �E ^�� LlT5KXF��WZ G �qJVA�F ? ?�W0t��� LJIWI�� G#P �

a ∈ N �#PHfW^XFk`hF �

trueA{W

aJVA�F �f? W�tk�

falseA{WzDqYGD �

V��� ]f[FPkK �a ^T\ � �b� l�� ` ^MLlT5PT�GeFHLlf T�IYGUT C�c D]i �PkK IYLJI

T�GeFHLlf T�IYGUT � a�hKr!i �\ I PkK

\ I ` ^�� LlT�K F��WZ G

E ^�� LlT5KXF��WZ G �qJVA�F ? ?�W0t��� LJIWI�� G#P �

a ∈ N �#PHfW^XFk`hF �

trueA{W

aJVA�F �f? W�tk�

falseA{WzDqYGD �

V��� ]f[FT�GeFHLlf T�IYGUT �j�a ^T\ � �b� l��Q� �

\ I ` ^�� LlT�K F��WZ G

Page 6: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

E ^�� LlT5KXF��WZ G ��� vZLEW�?nD� LJIWI�� G#P �

a, b, c ∈ Z �#PHfW^XFk`hF �Q>�M�v|x0vV� JZD�F � vVLEW�?nD LqJ

a, b, cV��� ]f[FPkK

a > b` ^ML T�P

PkKa > c

` ^MLlT5PT�GeFHLlf T�IYGUT ^ adm � g����p� �

PkK IYLJIT�GeFHLlf T�IYGUT a �

\ I PkK

PkK IYLJI PHKb > c

` ^MLlT5PT�GeFHLlf T�IYGUT ^ adm �a����p� �

PHKSIYLJIT�GeFHLlf T�IYGUT g �

\ I PkK\ I ` ^�� LlT�K F��WZ G

Page 7: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

> M�W�DbACFwtXOQU,F~WyYGD twv|�Tv�F~W'FXW'�GJ � \5Dpc A£M�vZU}twW�F �_ Llf T

V ar �Ki Exp1

�Exp2

oQadc oQaEr �Ki Expr3� ` KST�G

� DbACF\ I _ Llf T

> M�J<HKvZU|OpFXW0YGD LNM ObDEJ W'FXv�t?SF~W0Y�D � \5Dpc t~J<�pWyJZDGF � ��d� � �n?�xzOqJ�t x0JVAuJ}HK�qt~JZA~A�WyYGDbA

Exp1, Exp2, Exp3

�� Y!W0JZDGF

v1, v2, v3

x0JZOEt6�n?�xyJZOKt t~JZA�� JZU,F~W��GJ ��p� � HKvZU|OpFXJ�t x�M ?SRTJVU,F�?IFXW0YGD

V ar := v1

�K�v3

JZACF A~OE�b� YGA�v �TYGA{W'FXW+ �? � � W

V al(V ar) > v2

x�M�W�F~v�t�?IF~WyYGD A£M ?Stwt��<FXJ �� � � WzDEYGD � HEvZU|OpFXJ�t x M�WzDQA�F~tXObU,FXW0YGD

Inst�fOEWzA���HKvZU|OpFXJ�t x�M ?SRTJVU,F�?IFXW0YGD

V ar := V ar + v3�fOEWzA JZU<YG� � JVDbU<J�t JZD � ?

Page 8: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

JZ� ?�t/��OEJ �� >@? �f?St�FXW0J � �f?St �f?nA LEJ

Expr3� JZACF Yd�EFXW0YGDbDqJ|x0xyJ � � W9J|xyx0J

JZA�F Y�� W�A�JExp3

�d?nOpF �d�� Exp1, Exp2, Exp3

A{YGDGF v��n?�xzOqv|JZA9ObDEJO+³YdWzAN� YGOKtNF~Y�OpF~J�?£�d?nDGFx M�W'F~v|t?IFXW0YGD � x0JuU<Yntw�fA LqJ x M�W'FXv�t?SF~W0Y�D �x M�WzDbACFwtObU,FXW0YGD

Inst�9DqJ

�TJZOpF )DqJ LEY!W'F�� � ?nA6� YKLEW��QJ|t x0JZOEt6�n?�xyJZOKt �� x0J U<Yntw�fA LEJ x M�W'FXv�t?IFXW0YGD DEJ LEYdW�F �f?dA � YpLEW0�QJ�t x�? �n?�x0JVOKt LEJ

x�? �n?St~W�?��bxyJV ar

� JZD A{Ynt�FXW0J LEJ x�M�W�DbACFwtXOQU,F~WyYGD � \5Dpc x�? �n?St~W�?��bxyJ LEJ U�YGDGFwt��dx0JV ar

DNM ? � ?nA6LEJ �n?�xyJZOKt �

Page 9: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

��HKJZ� �bx0J �E ^�� LlT5KXF��WZ G � � YG� � J���?StwtwvZA� LJIWI�� G#P �

n ∈ N

�#PHfW^XFk`hF � n∑

i=1

i2

W��q� DGFXW0J�t �� YG� � J �q� D�F~W0J|t �V��� ]f[F

� YG� � J ��� � �_ Llf T

i �Ki 1�

n� ` KST�G

� YG� � J ��� � YG� � J � W��_W\ I _ Llf TT�GeFHLlf T�IYGUT \_^j^Ti �

\ I ` ^�� LlT�K F��WZ G

Page 10: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �³�'

&

$

%

> M�W�DbACFwtXOQU,F~WyYGD twv|�Tv�F~W'FXW'�GJ � a�[:C �RD]i A|M�vZU}t~W'F �Fk` IJF � fYG

Cond� ` KSTbG

Inst\ I F��

Y��Cond

JZA�F OQDEJ J<HK�qtwJVAwA{W0YGD � �n?�xyJZOKt � Y�Ydx0v£JZDbDEJ> M�J<HKvZU|OpFXW0YGD LbO Cqa�[:C �RD]i twJ��pW0JZD�F � ��d� v<�d?�xzOEJ|t

Cond�p� A{W

V al(Cond)�n?nOpF � a�hKr!i x M�W'FXv�t?SF~W0Y�D A|M ?Stwt��<FXJ

�K� A{WzDEY�D J}HKvZU£OpF~J�t x�M�W�DbA�F~tXObU}F~W0Y�DInst

J<F twJVU<YG� � JZDQU<J�t JVD�

JZ� ?�t/��OEJ �� � x�? LEW�RTv�t~JZDbU<J LEJ x�? t~v|�Tv<FXW'FXW'�GJ � \5Dpc �Nx M�WzDbACFwtObU,FXW0YGD InstLEYdW'F � YpLEW0�QJ�t x�? �n?�x0JVOKt LEJ x M�J}HK�qt~JZA~A�WyYGD

Cond� � Y�DGFwt�?�W�t~JZ� JVDGF � x M�W'FXv�t?IFXW0YGD � \5Dpc � x0JuDEYG� �qtwJ�L M�W�F~v�t�?IF~WyYGDbA

LEJ x�M�W�F~v�t�?IF~WyYGD � a�[:C �RD]i Lqv|�TJZDbL LEJ x M�WzDbACFwtObU,FXW0YGD W�F~v�t~v|J

Page 11: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ���'

&

$

%

��HKJZ� �bx0J �E ^�� LlT5KXF��WZ G � ? OEWzA~AX?nDbU<J J � �� LJIWI�� G#P �

n ∈ N∗

�#PHfW^XFk`hF �True

A�Wn

JVA�F ObDEJ �]OEW�AwAX?nDbU�J LqJ � �False

A�W�DEYGD� �qJZD�F~W0J|t �V��� ]f[F

p := n�

Fk` IJF � fYG(p > 1) i(C ((p ^T\ � 2) = 0)

� ` KSTbGp := p/2\ I F��

T�GeFHLlf T�IYGUT(p = 1)

�\ I ` ^�� LlT�K F��WZ G

Page 12: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ��'

&

$

%

3 � 4u3 � �

� �e\ IWKXFbKXLJI N � D F ?��bx0J_?nO JZACF ObDEJ ACFwtObU,FOEt?IFXW0YGD LEJ LqYGD:9DEv|JZA ?nDQ?�xyY*�GOEJ ?nOpH ��JZU,F~JVOKtXA YGO � ?IF~twWzU�JZA LEJZA � ?IF�qvZ� ? 9F~W ��OEJZA �� D F ?��bxyJV?nO ? ObDEJ F�? W0x0xyJ JZD�F~W�|twJ DEY�D D OEx0xyJ J<F ObD F�Bp� J � OEWJZACF x0J F�BK�TJ U�YG� � ObD LEJ F~Y�ObA6A�JVAuv|x0vV� JZD�FA �� D LEvZU�x�?St~J ObDEJ �n?StwW�?��bxyJ F�?��Qx0JV?nO LEJ F�?�Wyx0xyJ

NJ�F LqJ F�Bp�TJ

Type� ?St �

� � `BT5T�`�� �d�z��� L � � Bp�TJ �� D F~J|x F ?��bx0J_?nO JZACF x�? ACFwtObU,FOEt?IFXW0YGD LEJ

N�d?StwW�?��bx0JVA LEJ

F�Bp� JType

��� D ?nU|U �ZLqJ � U<JZA �n?St~W�?��bxyJZA �f?St xyJZOKt t?nDh� YGOWzDbLqWzU<J*�]JZDGFXW0J�t LQ?nDbA

1..N� D DEY F~J|t?T [i]

�TY�OKti ∈ 1..N

x�M�v£x0vZ� JZDGF LNM�WzDQLEJ}HiLQO

F�?��Qx0JV?nOT�

>@? + Y�DbU,F~WyYGD FH` K ^S^MG NTableau −→ N

∗twJVDG�GYdWyJ

x�? F ?�W0xyx0J JZD�F~W�|twJ DEY�D D�Oqx0x0J LqJ A{YGD ?St �GOQ� JZD�F �

Page 13: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- � �'

&

$

%

� OEJ|x ��OEJZAut �=�dxyJZA �� � YdW'F

T, SLEJZA�F ?��bxyJV?nO H LEvZU<x�?StwvVA � k�l � JZACF KSIJFHGUT5VWKXF �

? ?St U<YGD�FwtwJ �QA�WNYGD A~OE�b� YGA�J F~YGObA�xyJZA�v|x0vV� JZD�FA LqJT

WzDEW�F~W�?b9x0WzA{vZA �

� �]?St{t�?£B �d�y� F�? W0x0xyJ � �uY*+ � Bp�TJ �W��q� D�F~W0J|t �_ LJf T e �Ki � � CqaEe!hjhji9� � �� ` KST�G

��� W��8��� � � W��\ I _ LJf T

� � D F�?��bxyJV?nO �TJZOpF ���GOKt~J�t U<YG� � J �f?St�?n� ��FwtwJ LNM ObD ?�x)�dY�9twW'F�b� J )LNM ObDEJ �qtwYKU<vZLbOKt~J*�]LNM ObDEJ +³YGDbU,FXW0YGD � �

E ^�� L T�KXF �WZ G �h+� LJIWI�� G P � � OQD F�? �bx0JV?dO L M�JZD�F~W0J|tXA �#PkfW^XFH`hF � x�? A�YG� � J LEJZAuv|xyJZ� JZDGFA LEJ �

A{YG� � J*��W��q� D�F~W0J|t �V��� ]f[F

A{YG� � J ��� � �_ LJf T e �Ki � � CqaEe!hjhji9� � � � ` KST�G

A{YG� � J ��� A�Y�� � J � � � W��\ I _ LJf TT�G FkLJf T5IYGUT r!\_^j^Ti\ I ` ^�� LlT5KXF �WZ G

������ Dj[ Cqa�g]hji a�D �Ki � iS[:C e!incfr e_[TebC eda�hKejr� �

a k�l � � ���

Page 14: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �´ '

&

$

%

� � D F ?��bxyJV?nO � ?St?n� �<F~twJ LNMPOQD ? x�dYnt~W'F�b� J IYG _ G#f[F �eF�T�GZ L@VWKX\�� LQ?nDQA�x M ?�x�dYdtwW'F�b� J �

E ^�� L T�KXF �WZ G �h+� LJIWI�� G P � � OQD F�? �bx0JV?dO L M�JZD�F~W0J|tXA�z�y� �V��� ]f[F�z�y� �

� � W������ � ��z�y� �

\ I ` ^�� LlT5KXF �WZ G

Page 15: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- � �'

&

$

%

� � D F ?��bx0J_?nO �TJZOpF �B�GOKtwJ|t¨U<YG� � J�twvZA~OEx'F ?IF9LNM ObD ?�x�!YntwW�F�b� J �� M�JZACF x0J A{JZOEx�UZ?nA Y�� YGD A|M ?nOpFXYntwW�A�J�t�? � ?SRTJZU,FXJ�t �dxyYd�f?�xyJ69� JZD�F ObD F ?��bxyJV?nO � OQDEJ �d?StwW�?��bx0J �

E ^�� L T�KXF �WZ G �h+� LJIWI�� G P � � ObD JZDGFXW0J�t �TYGA{W'FXW+ �#PkfW^XFH`hF � >¨J F�?��Qx0JV?nO LEJ F�? W0x0xyJ � LqYGDGF x0JZA

v|xyvZ� JVDGFA A�Y�DGF x0JZA � �qtwJV� WyJ�tXA JZDGFXW0J�tAWz� �f?�W0tXA DEYGD D�OExzA

W��q� D�F~W0J|t �� �f?�t{t?ZB �!�y��� Y*+@� DGF~WyJ�t �V��� ]f[F

_ LJf T e �Ki � � � � ` KST�G� � W������ � �_W�9 �

\ I _ LJf TT�G FkLJf T5IYGUT �

\ I ` ^�� LlT5KXF �WZ G����� k adcjcEa�� � ����� \ � � [:C e!inc k�l � � � ���

Page 16: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- � �'

&

$

%

��� ; � :�7�� � :�� � 4 4 3 �s4

E ^�� LlT5KXF��WZ G �q���GU|L� LJIWI�� G#P �

a, b ∈ N�h? JZO Wz� �TYnt�FXJ ��OEJ

a > bYGO

DEYGD � �#PHfW^XFk`hF � >¨J � ��U|L LEJ

aJ<F

bH � B-� � � t �q� DGFXW0J�t �V��� ]f[F

� � � YpL JZACF x M�Yd�Tv�t�?IF~WyYGD LbO U£?�xzU£OEx¨LbO twJZACF~JJZDGFXW0J�t � � �

H ��� ? �KB � � � �t ��� ? � YpL � ��Fk` IJF � fYG

r 6= 0� ` KST�G� H ��� B �

B ��� t �t � � H � YpL B ��

\ I F��T�GeFHLlf T�IYGUT �

\ I ` ^�� LlT�K F��WZ G� Y!W0JZDGF

xk, yk, rk

xyJZA �n?�xyJZOKtXA LEJx, y, r

x0YntA x�M�W�F~v�t�?IF~WyYGD LEJt�?nD �

k� � x�M�W�DbA�F~tXObU}F~W0Y�D D�Ob� v�twY FXv � �

� � Q G#IWP=G#Z ]^MG VYG P VWKYKSP=G#f T�P VYGxk

GeFyk

G#P F ^ Q G I cP=G#Z ]^MG VYG#P VWKYK P�G#f T�P VYG

aG F

b � �

Page 17: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- � �'

&

$

%

� OEx'FXW0�bxyWzU£?SF~W0Y�D �f?St ?nLQLEW'FXW0YGDbA AwObU£U<JZA~A�W��GJZAE ^�� LlT5KXF��WZ G ��� OEx���LQL� LJIWI�� G#P �

a, b ∈ N�

�#PHfW^XFk`hF � >¨J �qt~YpLbOEW�Fa bW ��t �q� DGFXW0J�t �

V��� ]f[F� � � JZOEx0J x�M ?dLbLEW'FXW0YGD JZACF ?nOpFXYntwW�A�v£J �

� �t ��� � �_ Llf T

i �Ki � �b� ` KST�G

t � � t � ? �\ I _ Llf TT�GeFHLlf T�IYGUT c\ I ` ^�� LlT�K F��WZ G

Page 18: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- � �'

&

$

%

� OEx'FXW0�bxyWzU£?SF~W0Y�D �f?St ?nLQLEW'FXW0YGDbA AwObU£U<JZA~A�W��GJZA ³�GJ�tA�WyYGD � �E ^�� LlT5KXF��WZ G ��� OEx���LQL �� LJIWI�� G#P �

a, b ∈ N�

�#PHfW^XFk`hF � >¨J �qt~YpLbOEW�Fa bW ��t �q� DGFXW0J�t �

V��� ]f[F� � � JZOEx0J x�M ?dLbLEW'FXW0YGD JZACF ?nOpFXYntwW�A�v£J � � �t ��� � �qW���� � �Fk` IJF � fYG e ��� g � ` KSTbG�

� � t � ? � W � �W�� � W � � �t � � t � ? �

\ I F��T�GeFHLlf T�IYGUT c\ I ` ^�� LlT�K F��WZ G

� r = a ∗ iJVA�F �bWyJZD x M�WzDG�d?StwW�?nDGF LqJ x�M�W�F~v�t�?IF~WyYGD �

� x M�W'F~v|t?IFXW0YGD � F~J�t� W�DEJ � �8x0xyJ A£M�J}HEvZU|OpFXJ J<Hb?nU,FXJZ� JVDGFb+³YdWzA �

� D JZD LEvZLbOqW'F ��ONM�JZD A{Ynt�FXW0J LEJ x�M�W�F~v�t�?IF~WyYGD � YGD ? � x�? +³YdWzAi <> b

+�?nOpH �EJ<F x M�WzDG�d?StwW�?nDGFr = a ∗ i

�pt?�W3�]LEYGDbUr = a ∗ b

Page 19: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ���'

&

$

%

JZU�EJ�tU�EJ LNM ObD v|x0vV� JZD�F LQ?nDQA�OQD F ?��bx0J_?nO �? twYd�bx)�Z� J � � YdW�F

TObD F ?��bxyJV?nO LNM�JZDGF~WyJ�tXA WzDEW�F~W�?�x0W�A�v �

� � ∀1 6 i 6 taille(T ) : T [i] ��������� �� Y!W'F

x ∈ N�

� D �GJZOpF AX?£�GYdW0t A�Wx

JZA�F v£x0vZ� JZDGF LbO F ?��bx0J_?nOT�

� � ��� ����������������� ∃i : 1 6 i 6 taille(T ) : T [i] = x

E ^�� LlT5KXF��WZ G � JZU�EJ|tXU�EJ � ?��bx0J_?nO �� LJIWI�� G#P �

x ∈ N�QObD F�?��Qx0JV?nO LNM�JZDGFXW0J�tA6W�DEW'FXW�?�xyWzA{v

T�

�#PHfW^XFk`hF � >¨J �TY Ydx0v|JVD∃i : 1 6 i 6 taille(T ) : T [i] = xW��q� DGFXW0J�t �bFwt~YGOp�GJ ��� Y Ydx0v|JVD �

V��� ]f[FFwtwY�Op�GJ � � +�?�x�A�J �_ Llf T e �Ki � � CqaEe!hjhji9� T � � ` KST�G

PkK ��� e! l m ` ^MLlT5P� FwtwY�Op�GJ � � FwtXOqJ\ I PkK

\ I _ Llf TT�GeFHLlf T�IYGUT C�cq\5D#"bi\ I ` ^�� LlT�K F��WZ G

Page 20: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ��'

&

$

%

E ^�� LlT5KXF��WZ G �q�8t{t~JZOKt� JZU�EJ|tXU�EJ � ?��bx0J_?nO� LJIWI�� G#P �

x ∈ N�QObD F�?��Qx0JV?nO LNM�JZDGFXW0J�tA6W�DEW'FXW�?�xyWzA{v

T�

�#PHfW^XFk`hF � >¨J �TY Ydx0v|JVD �y�z�W��q� DGFXW0J�t �bFwt~YGOp�GJ ��� Y Ydx0v|JVD �V��� ]f[F

FwtwY�Op�GJ � � +�?�x�A�J �_ Llf T e �Ki � � CqaEe!hjhji9� T � � ` KST�G

PkK ��� e! l m ` ^MLlT5P� FwtwY�Op�GJ � � FwtXOqJPkK IYLJI

FwtwY�Op�GJ � � +�?�x�A�J\ I PkK

\ I _ Llf TT�GeFHLlf T�IYGUT C�cq\5D#"bi\ I ` ^�� LlT�K F��WZ G

Page 21: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ��'

&

$

%

E ^�� LlT5KXF��WZ G � JZU�EJ|tXU�EJ � ?��bx0J_?nO �� LJIWI�� G#P �

x ∈ N�QObD F�?��Qx0JV?nO LNM�JZDGFXW0J�tA6W�DEW'FXW�?�xyWzA{v

T�

�#PHfW^XFk`hF � >¨J �TY Ydx0v|JVD∃1 6 i 6 taille(T ) : T [i] = xW��q� DGFXW0J�t �

V��� ]f[FW�� � � �Fk` IJF � fYG

i ≤ taille(T )� ` KST�G�

PkK ��� e! l m ` ^MLlT5PT�GeFHLlf T�IYGUT C�c D]iPkK IYLJIW�� � W � �

\ I PkK\ I F��T�GeFHLlf T�IYGUT � a�hKr!i\ I ` ^�� LlT�K F��WZ G

� >�M�WzDG�d?StwW�?nDGF LEJ x�M�W�F~v�t�?IF~WyYGD � JZACF � � Y�ObA xyJZA v|xyvZ� JVDGFA LEJt?nD � W�D + v|twW0JVOKt � x M�WzDbLqWzU<J U<YGOKt�?nDGF A{YGDGF LEW�RTv|twJZDGF�A LqJ

x ∀j ∈ [1..i[ : T [i] 6= x

�� >�M ?�x�!YntwW�F�b� J F~J�t� W�DEJ*� A{YdW'F �f?StU<J � OEJ

i = taille(T ) + 1J<F LQ?nDbA U<J U£?nA x�M�W�DG�n?St~W�?nD�F �qt~YGOp�GJ � ONM�Y�D DNM ? �f?nA F~twYGOp��vx��A{YdW'F �f?�tXU<J ��OEJ

trouveJZACF �pt?�W3��J<F LQ?nDbA U<J U£?nA Y�D ?

FwtwY�Op�Gvx

?nO t?nDh�i�

Page 22: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

E ^�� LlT5KXF��WZ G � JZU�EJ|tXU�EJ � ?��bx0J_?nO �� LJIWI�� G#P �

x ∈ N�QObD F�?��Qx0JV?nO LNM�JZDGFXW0J�tA6W�DEW'FXW�?�xyWzA{v

T�

�#PHfW^XFk`hF � >¨J �TY Ydx0v|JVD∃i : 1 6 i 6 taille(T ) : T [i] = xW��q� DGFXW0J�t �

V��� ]f[FW�� � � �Fk` IJF � fYG

i 6 taille(T ) i(C T [i] <> x� ` KST�G� W�� � W � �

\ I F��T�GeFHLlf T�IYGUT � i 6 taille(T ) �

\ I ` ^�� LlT�K F��WZ G

� � FwF~JZD�F~W0Y�D x0J U<YGDbDqJZU,F~JVOKt x0Y*�dW ��OEJ i(C LEJ x�M�W�DbACFwtXOQU,F~WyYGD � ���

JZA�F OQD i(C a�hj\ncfr �� >�M�WzDG�d?StwW�?nDGF LEJ x�M�W�F~v�t�?IF~WyYGD � JZACF � ? YGOKt x0JZA v|xyvZ� JZDGFA LEJ

t?nD � WzDh+ v�t~W0JZOEt � x M�WzDbLqWzU<J U�YGOKt?dDGFH�qYGD DNM ? � ?nA Fwt~YGOp�Gvx�

� >�M ?�x�!YntwW�F�b� J F~J�t� W�DEJ*� A{YdW'F �f?StU<J � OEJi = taille(T ) + 1J<F LQ?nDbA U<J U£?nA x�M�W�DG�n?St~W�?nD�F �qt~YGOp�GJ � ONM�Y�D DNM ? �f?nA F~twYGOp��v

x�TA{YdW'F �f?StU<J ��OEJ

T [i] = xJVA�F � t? W �TJ<F LQ?nDQA U�J U£?dA YGD ?

FwtwY�Op�Gvx

?nO t?nDh�i�

Page 23: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

JZU�EJ�tU�EJ LNM ObD v|x0vV� JZD�F LQ?nDQA�OQD F ?��bx0J_?nO FwtwWyv �? twYd�bx)�Z� J � � YdW�F

TObD F ?��bxyJV?nO LNM�JZDGF~WyJ�tXA WzDEW�F~W�?�x0W�A�v

� � ∀1 6 i 6 taille(T ) : T [i] ��������� �� D A~OE�b�TY�A�JT

F~twWyv U}t~YdWzA~AX?nDGF � � YdW'Fx ∈ N

�@� D �GJZOKF AX?£�GYdW0tA{W

xJZACF v|x0vZ� JZDGF LbO F�?��bxyJV?nO

T�

E ^�� LlT5KXF��WZ G � JZU�EJ|tXU�EJ � ?��bx0J_?nO��� LJIWI�� G#P �

x ∈ N�QObD F�?��Qx0JV?nO LNM�JZDGFXW0J�tA6W�DEW'FXW�?�xyWzA{v

J<F6F~twW0v U<twYdW�AwAX?nDGFT�

�#PHfW^XFk`hF � >¨J �TY Ydx0v|JVD∃i : 1 6 i 6 taille(T ) : T [i] = xW��q� DGFXW0J�t �

V��� ]f[FW�� � � �Fk` IJF � fYG

i 6 taille(T ) i(C T [i] < x� ` KST�G� W�� � W � �

\ I F��T�GeFHLlf T�IYGUT � i 6 n i(C T [i] = x �

\ I ` ^�� LlT�K F��WZ G

� J<FwF~J �GJ|tXA{W0YGD JZACF ObDqJ ?nLQ?��EF ?IF~WyYGD LNM ObD ? x�dYnt~W'F�b� J �qt~vZU<v69LEJVDGF � ��x0x0J F~W�t~J �f?St{F~W LEJ x M�YntXLEtwJ � � ?�W�AuYGD �TJZOpF +)?�W�t~J � WyJZO H �

Page 24: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ) '

&

$

%

> M ? x�dYnt~W'F�b� J ��OEW A~OEW'F Yd�l��t~J �f?�t � LEW�U�EY FXYG� W0J � �¨YGD LEv69U<Y�OE�TJ xyJ F ?��bxyJV?nO WzDEW�F~W�? xbJZD � A�Y�ObA � F�?��bxyJV?nO H ?nOpFXYGOKt LQO t?dD �� vZLEW�?nD �I� D U<YG� �f?St~J

x�d?�x0JZOEt9U�EJ|tXU�Ev£J*� ��x�M�v£x0vZ� JZDGF�LEJ t?dD �

m� vZLEW�?nD LQ?nDQA@x0JVA�W�DbLEW�U<JZA�LbO F ?��bx0J_?nO ��J<FH�nAwOqW'�n?nD�F x�? �n?�xyJZOKt

LEJT [m]

�sYGD W'F/��twJ x�? twJZU EJ�tXU EJ LQ?nDbA x0J � YGD A�Y�ObAA9�F�?��Qx0JV?nO �� D ?nU|U<YntLEJ�t�? x�? �bxzOQA �nt?dDbLEJ ?IF{FXJZDGF~WyYGD � x�? LEvZU}t~YdWzA~AX?nDbU<JACFwt~WzU,FXJ LEJZA�F ?�W0xyx0JZA LEJZA6A{YGObA � F�? �bx0JV?dO H J}Hb?n� WzDEvVA �

� >�M�WzDG�d?StwW�?nDGF LEJux�M�W�F~v�t�?IF~WyYGD � JZACF � � YGOpF�v|xyvZ� JZDGF LEJT

LEYGDGFx0J t?dD � D M�JZACF �f?nA6LQ?dDbA

[g; d]JZA�F LqW�RTv�t~JZDGF LqJ

x�

� >�M ?�x�!YntwW�F�b� J F~J�t� W�DEJ � � U Q?R��OEJ W'FXv�t?IFXW0YGD x�? F�? W0x0xyJ LbOA�YGOQA � F ?��bxyJV?nO J}Hb?n� WzDqv LEvZU}t~YdW'F ACFwt~WzU,FXJZ� JZDGFH�

� YGO �bW0JVD YGD ? Fwt~YGOp�Gvx

?nO t�?nD � � vZLEW�?nD LQ?dDbA ObDqJ W'F~v|t?b9F~W0Y�D � YGO �QW0JZD YGD FXJ�tX� WzDqJ ?£�GJZU ObD F ?��bxyJV?nO �pWzLEJ � J<F x M�WzD:9�n?StwW�?nDGF ?dAwA~OKtwJ ��OqJ

xDqJ �TJVOpF ?��b�f?St{F~JZDqW�t �

T�

Page 25: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

E ^�� LlT5KXF��WZ G � JZU�EJ|tXU�EJ � ?��bx0J_?nO �

� LJIWI�� G#P �x ∈ N

�QObD F�?��Qx0JV?nO LNM�JZDGFXW0J�tA6W�DEW'FXW�?�xyWzA{vJ<F6F~twW0v U<twYdW�AwAX?nDGF

T�

�#PHfW^XFk`hF � >¨J �TY Ydx0v|JVD∃i : 1 6 i 6 taille(T ) : T [i] = x� �PL �P� �q� DGF~WyJ�t �

V��� ]f[F� ��� � �QL � � F ?�W0xyx0J � � �Fk` IJF � fYG

d > g� ` KST�G�

� � � � � L � � � �PkK

x < T [m]` ^MLlT5P

L ��� � 9 �

PkK IYLJI PHKx > T [m]

` ^MLlT5P� ��� � � �

PHKSIYLJIT�GeFHLlf T�IYGUT C�c D]i\ IWPkK

\ I F��T�GeFHLlf T�IYGUT � a�hKr!i\ I ` ^�� LlT�K F��WZ G

Page 26: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

3 � � 4

�8YdW0t x0J � JZ� JZDGF~Y

Page 27: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

� 794 = �9:<; = � � � � �

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

� OqW'F~JVA LEJ �n?�x0JVOKtXA A�v|� ?Stwv|JVA6�f?St LEJVA��pW�t �GOExyJZA �v1, v2, ..., vk

>�? A~OEW�F~J �pWzLqJ JVA�F DEYnF~v|J ������� �>¨JZA �n?�x0JVOKtXA L MPObDqJ AwOEW�F~J DEJ A{YGDGFu�f?nA F~YGOKF~JZAuLbO � �Z� J F�Bp�TJ �>¨JZA�Yd�Tv|t?IFXJZOKtXA6J<F + Y�DbU,F~WyYGDbA A~OKt6x0JVA A~OEW'FXJZA A{YGDGF �� A�W i � J�F i � A�YGD�F�LEJVA J<HK�qtwJVAwA{W0YGDQA i � �~i � JZACF ObDEJ�J}HK�qt~JZAwA{W0Y�D

LEYGDGF x�? �n? x0JZOKt JZA�F x�? AwOEW�F~J "qa�h9��i �!� � "qa�h9��i �b�� A�W r JVA�F ObDEJ �n?St~W�?��Qx0J LEJ F�Bp� J A~OEW'FXJ r � e! JZACF ObDEJ J}HK�qt~JZAA9

A�WyYGD LEYGDGF x�? �n? x0JZOKt JZA�F xyJieme

v£x0vZ� JZDGF LEJ r

a k�l ��� C�c D]i ka � ��� C�c D]ig k�l a��wa�� �"!Qa#� kg � ��� C�c D]i � ��� C�c D]i � �"!Qa#�� k�l a�� ������� �%$�$ k� � ��� C�c D]i � $�$g ��& � �

Page 28: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

� ��� � � � ���

� Bp�TJ �qt~vZLEv��fDqW�� ������ � hKejrbC

� DEJ x0W�A�FXJ JZACF OQDEJ AwOEW�F~J JZDbUZ?nLKtwv£J �f?St � J<F �

>¨JZA +³YGDbU,FXW0YGDbA AwOKt6xyJZA6xyWzACF~JZA �� v<F�?nD�F ObDEJ x0WzACF~J �� []\SoTr � � � DEYG� �qtwJ LNM�v|x0vV� JZD�FA LEJ x�? x0WzACF~J � �� \So8� � � x�? AwOEW�F~J LEJVA�v|x0vZ� JZDGF�A LqJ � �� � � e! xyJ

iemev£x0vZ� JZDGF LEJ x�? x0WzACF~J � �

1 ≤ i ≤ nops(L)� � � e! � JZOpF �<Fwt~J � YpLqW��Qv �f?�t OQDEJ ?�RTJZU,F�?SF~W0Y�D� � � e ���� twJVDG�GYdWyJ x�? A�Y�ObA � x0WzACF~J +³YntX� v|J LqJZA v£x0vZ� JZDGF�A LEJ

t?nD �i�

j�QLQ?dDbA�x�? x0W�A�FXJ

L�

1 ≤ i ≤ j ≤ nops(L)� m e_[ � twJZDG��YdW0J C�c D]i A{W m JZACF ObD v|x0vZ� JZDGF LEJ � �

twJZDG��YdW0J � a�hKr!i A{WzDEY�D

Page 29: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

a k�l � ��� C�c D]i � � k132SoTr �4b� � �

2658�4b� � ��� C�7 D38 � �

4 ��& 9�: $ 94 � � ��� C�7 D38 � $ � ; � 2658�4b� � � ; � ��� C�7 D38 �%$ � ; � 4 � � ; � � ��� C�7 D38 � $ < 9�: ��& �%$ �>= � ��� ; 9< � � ���@? � � $ � = � � & A 1 < � C�7 D38& A 1 < � � ���@? � � 4�BDC!8< 9�: � � �E265GF <IH 9 JLKNMPORQ SUTVOXW Y[Z0Y]\ ^]WPQ � O_W`^ ZbadcNQE^< � � �fe & e $ge =ge �he ; 4 9�: � �he � 9� 265GF4 H eE265GF <IH � � �he � e �fe & e $ge =ge �he ;

Page 30: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ���

'

&

$

%

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

����� ^ �� Y]S`Y� W a � ������ � C!8� � WXc>^ \ �XZb^ W`a S`^ � J�Zb^]O � c � � J c SUT M � S � ^�� � J c S`^ � Y � Y Q a'Q a0MPW��� W ^]WXc ^]\ �_Z0^ ^]cNQ OXW`^ c O a'QE^ ^ W��[J S � Y ^ � J � � ^ Q �� ^]c�� MPW��,Q a0MPWXc ^ Q M � Y � JLQE^ O � c cEO � Z0^ c ^]WXc ^]\ �XZ0^ c �� "!$#&% : set −→ N

E 7−→ �[J � S adW_J�Z S`^ E

� '( ()*!+ : set × set −→ set

E, F 7−→ E ∪ F

� ), +-/.102%3.14�- : set × set −→ set

E, F 7−→ E ∩ F

� 5 ), 6'(% : set × set −→ set

E, F 7−→ E \ F

� %7'98&%�.:- : set × set −→ boolean

E, F 7−→ E ⊆ F

� ), : X × set −→ boolean

x, E 7−→ x ∈ E

Page 31: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 12�

'

&

$

%

3 4�57698 e;:=<>: e 8 e@?BA 4 C 4�57698 eED9A 4

3 F ��G �IH��KJ JLJ �MLNPO C F 3 H F Q

RTS <�BPUGF C7576 Dhe 8 A H F Q � O`^3 V M>W!NPM C F ��G �IH��KJ JLJ �IX �3 W=M RZY C R7[ C F � H �3 C R Z\]W=M V C C F ��G �KJ JLJ �3 C V U C R C F �)J�Zdc ^6 ?fe 8 A C V U C R 3 F Q � O`^? W=M 3 F Q � O`^? W=M C F �)J�Zdc ^

Page 32: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1�

'

&

$

%

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

��� a�� 3�� � W`^ ^! �� ^ c c a � W �E^ ZbZ0^ " � ^ S <�#%$ 3��'& ^]c� �)( ^ *badc�E^ � ��)( ^ ( c ^]\ �)*0^,+- N Y S < Y W=M 3�� . N W=M0/ R M . . N F

1 � � � �32�4," ��5 6 * 687 58( � R W 9 5 S <�#%$ 3��'& �G +:*;4 �,4 �=< 4 �)* 5 S < Y �� 58( 9 *>4 �?4@* 58� � R W

HA+ � � <CB * T < ( B � � � �D� < � ( W=M0/ 5 B � 5 6 � � � 6E5 +� < S <�#%$ 3��'&F5 B � �)(�5 * <CB � 5 * 5 B 6 * 687 58( � B R W:9 5 3�� B � ( � 5 � * � � 6 BB 5 * � ( *�T � � 9 � 5 9 5 *>4 * <>B � 5 +

Y R / < Y 4 R 4�5 6 ?HGEDIGKJ A 4 / 4�5 L 4

- N Y W W=M R . N / 4�5 / M W F R M . . N F / F G Q

Y R / < Y 4 R 4�5 N ?HGEDIGKJPO 4 / 4�5 L 4

- N Y W W=M R . N / 4�5 / M W F R M . . N F / F G Q

Page 33: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1�1

'

&

$

%

� � � � ��� ��� �A��� �)� � � � �H� � � �

� � ( �D� < � ( B �� 6 9 6 ( < 5 B � � � � * 5 B ( � �34 � < � ( B Σ5 � Π

�b

i=a

f(i)B T 6 � �=< � 58( 7 4 � * 5 < . . $ - $ W & G W 5 <����U & +

�b

i=a

f(i)B T 6 � �=< � 58( 7 4 � * 5 \ V #%$ - $ W & G W 5 <����U & +

� ∑

i∈E

f(i)B T 6 � �=< � 58( 7 4 � * 5 < . . $ - $ W & G W 5 30& +

� ∏

i∈E

f(i)B T 6 � �=< � 58( 7 4 � * 5 \ V #%$ - $ W & G W 5 30& +

a5 � b

� 5 �� 5 B=B < � ( B �?4 * 58� � B 58( � <���� 5 B

f(i)� 5 ��� 5 B BK< � ( � � ( � 58( 4 ( � i +

E� 5 �� 5 B B < � ( 9 � ( � *>4 �?4 * 58� � 5 B � �)( 58( B 587 �)* 5 � � * <>B � 5

< . . $ W�G W 5� ���� & F G��

M 4�5� 4 < . . $ 8�� W M ?HG W 578 ���M�M 8�& F Q H3 4�576 DIG 8 G�� A 4

\ V #%$ W M ?HG W 5 30& F ���

Page 34: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1

'

&

$

%

� � � ��� ��� �A��� � �����

/ R�� 5 B � �)(�5 � � ( �D� < � ( " � < � 58( � � < 5 �)(�5 B � < � 5 +

� * T 5 �� 5 B=B < � ( / R�� $ - $ W & G W 5 <����U & 4 � � � � �,4 * 58� � *>4 B � < � 5- $< & G - $< M ? & G���� G - $�U & +�*;4 B � < � 5 5 B � � < 9 5 B < U � <)+

� * T 5 �� 5 B=B < � ( / R�� $ - $ W & G W 5 R & 4 � � � � �,4 * 58� � *>4 B � < � 5- $ R ? & G - $ R 8)& G���� G - $ R M & +

R � 5 �� 5 B B < � ( � 5 * * 5 " ��5 S <�#%$ R & 5 B ��*>4 * <>B � 5 N R ?HG���� G R M�O- $ W & � 5 �� 5 B=B < � ( � � ( � 5 ( 4 ( � i �<IG U � 5 �� 5 B=B < � ( B �?4 * 5 � � 58( � <���� 5

/ R�� $ W�� 8 M 8�� W�G W 5 ? �� � & F G� G@?BDIG 8 �� 4�5 N ?HG � G J G D O 4

/ R�� $ 8�� W�G W 5 � & F 8 G� G@? � G@? L

Page 35: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1��

'

&

$

%

� � � � ��� ��� �A��� �)� � ��� � � ������ � �

3 �)( 5 ( B 5 7 �)* 5���� �)(�5 * <>B � 5 [x1, ..., xk]�

� �X −→ Y

� # �X −→ boolean

G + \ <�O $ - G 30& � 58( � � < 5 * T 58( B 587 �)* 5 {f(e) : e ∈ E}\ <�O $ - G �'& � 58( � � < 5 *>4 * <CB � 5 [f(x1), ...f(xk)] +

HA+ / R # R7[ $2O G 30& � 58( � � < 5 *�T 58( B 587 �)* 5 {e ∈ E : p(e)}/ R # R7[ $2O G �'& � 58( � � < 5 *>4 * <CB � 5 9 5 B 6 * 687 5 ( � B � N W O � 5 * B" ��5 O $ � N W O & �?4 � � Y V R

R 4�5 6 ?HG ?HG 8 G A F

# 4�5 N ?HG ?HG 8 G O F

\ <�O $ � � � � 8 G R & F 6 ?HG � G �9A\ <�O $ � � � � 8 G # & � G � G ����� ���/ R # R7[ $ � � � � ?HG R & F 698 G A

/ R # R7[ $ � � � � ?HG # & F N�8 G O

Page 36: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1��

'

&

$

%

� � � �:����� � � ��� ��� �A��� �)�

3 �)( 5 ( B 5 7 �)* 5���� �)(�5 * <>B � 5�� # �X −→ booleen

G + Y R \>N S R $2O G 30& � 58( � � < 5 *�T 58( B 587 �)* 5 {x ∈ E : ¬p(x)}Y R \>N S R $2O G �'& � 58( � � < 5 *>4 * <CB � 5 9 5 B 6 * 687 5 ( � B � N W O � 5 * B" ��5 O $ � N W O & �?4 � � - <�#�/ R

HA+ <�M . \ <�O $2O G 30& � 58( � � < 5 Y V R B BK<∀x ∈ E : p(x)

<�M . \ <�O $2O G �'& � 58( � � < 5 Y V R B BK< O $ � N W O & �?4 � � � � ��5 � � � �� � � B * 5 B 6 * 6 7 58( � B � N W O 9 5 �

Q + N Y \ <�O $2O G 30& � 58( � � < 5 Y V R B=B <∃x ∈ E : p(x)

N Y \ <�O $2O G �'& � 58( � � < 5 Y V R B=B < < * 5 <CB � 5 4 � 7 � < ( B �)(6 * 687 58( � � N W O 9 5 � � 5 * " ��5 O $ � N W O & �,4 � � Y V R

R 4�5 6 ?HG ?HG 8 G A F

# 4�5 N ?HG ?HG 8 G O F

Y R \>N S R $ � � � � ?HG R & F 6 ?HG ?BA

Y R \>N S R $ � � � � ?HG # & F N ?HG ? ON Y \ <�O $ � � � � ?HG R & F Y V RN Y \ <�O $ � � � � ?HG # & F Y V R<�M . \ <�O $ � � � � ?HG R & F - <�#�/ R<�M . \ <�O $ � � � � ?HG # & F - <�#�/ R

Page 37: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1��

'

&

$

%

� .15 � 0�� '". % �

� � 5 BF< � 6 � 4 � 5 � � B B T 4 ��� * < " ��58( � 6�� 4 * 587 58( � 4 � �34 ��* 5 4 � �< * B � ( � * 5 7 �87 5 B 5 ( B " ��5 � � � � * 5 B * <CB � 5 B +

� � 5 B < � 6 � 4 � 58� � B B � ( � 58( � 4 < � 9 5 B 4 * � � �=< �32 7 5 B � �� � � 6 9 � � 5 B � �\ <�O 4�5 O Y N [ $ - 494 O Y N [ R . V Y R G 3 494 / R & 4�4 / R F#9N [ <�# R G C 494 / R FC 4�576 A F- N Y R W=M 3 . N C 4�5 C V M>W!NPM 6 - $ R & A R M . . N FY R V Y M C FR M . O Y N [ 4

� 5 � �34 < ( B < � 6 � 4 � 58� � B � 58� � 58( � B 5 9 6 ( < � � 4 � � < � 9UT 4 � � � 5 B �� 6 � 4 ( � �)(�5 * <>B � 5 5 � 3 �)( 5 ( B 5 7 �)* 5\ <�O $ - G �'& 5 N / R�� $ - $ W & G W 5P�'& O<�M . \ <�O $2O G 30& 5 RTS <�#PU $ / R # R7[ $2O G 30&�5 3�&

Page 38: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1��'

&

$

%

� 587 � * 5 �(� 6 � 4 ( � *>4 * <>B � 5 9 5 B �� 6 � < � 4 � < � ( B " � � � < 9 < 5 ()(�5 B4 � 7 � <CB 9 5 B 5 � � 587 � � 5 � 5 ��=< 7 6 5 B 5 ( 7 < * < 7 � � � 5 B � * <CB � 5 9 5Q�� 58( � < 5 � B ( 4 � � � 5 * B �� 7 � � 58()(�5 7 58( B ��5 * * 5 9 5 B��� 6 � < �)< �34 � < � ( B �

4?9)9 � < � <�� � ��� ( � ��B � � � �� � � � 4 *:9 5 B �� 6 � < �)< �34 � < � ( B 58( � � 5 * 5 Q 5 � * 5 � B 5 � � 5 7 � � 5 �

4?9)9 � � � < � � <�� Q + + � � �� ( � 7 � � 5 9 5�� � � � B 9 5 � * � < 5 � ( � � B � B 5 * 5 � � � �� � � � � � � �� 58( B 587 ��* 5 9 5 B (��)7 6 � � B 9 5�� � � � B 4 ( B�� * � < 5 �

B 5 * 5 �D� � < �� � � < � � � � � B 5 " � < � <�� G +C+ ( � � B � � � � �2� �� * <CB � 5 9 5 B �� 6 � < � 4 � < � ( B " � � � < 9 < 58()(�5 B 4 � 7 � <CB 9 5 B 5 � � 5 7 � � 5 �

5 �� < 7 6 5 B 58( � 58( � < 7 � � � 5 B �7 4 � � ��� 5 �?4 * � � �� G � � � � � �

Page 39: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- 1��

'

&

$

%

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

� ��� () - )*!+ (% 0 � 4 '902%7)�� . %

� (�5 .�� #(0 .1%7%7) !+ 5 B � B � < � �� �)(�5 � � ( B �34 ( � 5� * 5 ( � 7 9 T �)(�5 �?4 �=< 4��)* 5 ��� B � 7 � � * 5 �� * T 4 ��� * < �E4 � < � ( 9UT ��(�5 � � 6 � 4 � < � ( �

� R � O Y R / /9W!NPM � NPO�� Y < W!NPM � R � O Y R / /9W!NPM �� * T 4 ��� * < �E4 � < � ( 9UT ��(�5 � � ( � � < � ( � � 9UT �)( 4@* � � � < �32 7 5 �

��/��Z\ ULN # R � $ � R � O Y R / /�W!NPM � G���� G � R � O Y R /�/9W!N�M �)&

� (�5 � (% - 02'(4 - )*!+ � 58� � � � � 5 �

%/) Condition ��� !$0 %Instruction%/), "!+ Instruction� %/)

- �� +- � '". Condition� ��) 0 .

Instruction� - �

Page 40: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- .�

'

&

$

%

� ��� !$02) -��(5 .

� ��� !$02) -��(5 . ��1� !+ ( � .1% �

. . .� � %7' � - �- �

. . .� � 8&' -

+ +C+ �+ +C+ 1 � � + +C+ �+ +C+ �

� � ����!$0 ) -��(5 .

1 � 58� � 5 �� � 6 � � � � 5 ( � 5 � � � � 5 �D� 5� � � � � � �32�4?" ��5 4 ��� 5 * � 6 � � � B < � �8* 5 B 4 � � �)7 58( � B 9 6 � � � <>B=B 58( �

B � �=< � � 587 58( �

Page 41: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

� �6.15 # �*.

� ��� !$02) -��(5 . � � 4 �D� � �=< 5 *� !+ ( � .1% �

n ∈ N+

� � %7' � - �- �n!

� � 8&' -%/) M 5 L ��� !$0 %

0 . -7!$'90 ".�0 ?%/), "!+

0 . -7!$'90 ".�0 M � C < [ N Y W R #%$2M ? &� %/)

� � ����!$0 ) -��(5 .

� 6 � � � � 58( � 5 �

0! = 1

∀n > 0, n! = n.(n − 1)!

� � � � �

�32�4?" ��5 4 ��� 5 * � 6 � � � BK< � � * 5 � 4 � 4 7 � � � 5 9 6 � � ��� � B � � < �D� 587 5 ( � �� 4 �D� � �=< 5 * � ( � → � 4��D� � � < 5 * � ( G � → + +C+→

� 4 �D� � �=< 5 * � � �

Page 42: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)-

'

&

$

%

� ! .�� 4 )*.1 +- 8&), ��+5 ) ���(

n

0

)

= 1(

n

n

)

= 1(

n

p

)

=(

n−1

p−1

)

+(

n−1

p

) BK<n > p > 0.

� ��� !$02) -��(5 . � � � 5 ��� < ( � 7� !+ ( � .1% �

n, p ∈ N, n > p > 0� � %7' � - �- � (n

p

)

� � 8&' -%/) O 5 L N V M 5 O � �*!$02%

0 . -7!$'90 ".�0 ?%/), "!+

0 . -7!$'90 ".�0[ N R -�� W=MLN=\ $2M ?HG O ? & M [ N R -�� W=M N=\ $ M ? G O &

� %/)� � ����!$0 ) -��(5 .

p × (n − p) :� ∈ N

� 9 6 � � ��� � B � � < �D� 587 58( � �32 4?" ��5 4 ��� 5 * � 6 � � � B < �� �?4 * 5 � � (�� * * 5 → 4 � � � � 9 5 � 6 � � � BK< � < � 6

Page 43: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- .1

'

&

$

%

� 0 ! 4 � � '90 . 0 � 4 '902%7)�� . .1 � �������

[ N R -�� W=MLN=\ 4�5 O Y N [ $2M 494 W=M1 R RZY G O 4�4 W=M�� R RZY & 494 W=M�� R RZY F. R / [PY W=O�� W!NPM: [ <�# [ V # R # R [ N R - - W [ W R M�� U>W=MLN=\]W <�# M G O : FW - M 5 O N Y O 5 L ��� R MY R � V Y M ? FR #�/ RY R � V Y M [ N R -�� W=MLN=\ $2M ?HG O ? & M [ N R -�� W MLNB\ $2M ?HG�O & FR M . W - FR M . O Y N [ 4

Page 44: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

� � 4 '902%7) �") - � %7'90 �*.1% - � 8 �*. ��' �

��� < 5 � ��( � 4 �)* 5 4 � �

� � � ���05 � * 5 �34��)* 5 4 � 5 ( H B � � B �34��)* 5 4 � � � �=< 5 � �32 4?" ��5 B � � B �34��)* 5 4 �� � � B < � ()(�5 � * 5 B H B � � B �34 ��* 5 4 � � �=< 6 B

32 44 6712 2312 1817 21 29 825131

12 1812 23 31 51 17 6721 443229 82

123112 18 51 23 17 32 82 44 21 67 29

12 17 32 82 44 21 67 293112 18 51 23

Page 45: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

� Y W - V /9W!NPM 4�5 O Y N [ $�� 494 < Y Y < � $ W M�� R RZY & &494 < Y9Y < � $ W=M�� R RZY & F

. R / [PY W=O�� W!NPM :�� R � N V Y M R V M � <�U # R < V � Y W � :�G: [ NPM�� R M <�M�� # R / \��=\ R / R # R \ R M�� / � V R � : F

#9N [ <�# � 494 < Y9Y < � G���� 494 < Y9Y < ��G � 494 < Y9Y < � G��� 494 < Y9Y < � G�\]W # 494 W M�� R RZY G W 494 W M�� R R Y F

W - � < W # # R $�� & 5 ? ��� R M Y R � V Y M [ NPO � $�� & FR #�/ R

\]W # 4�5 W � V N%$ � < W # # R $� & M ?HG 8)& F� 4�5 < Y9Y < � $=? ���\]W # G N / R�� $�� N W O G W 5 ? � ��\]W # & O & F� 4�5 < Y9Y < � $=? �� � < W # # R $�� & \]W #IG

N / R�� $�� N W O G W 5 \]W # M ? ���� � < W # # R $� & & O & F

��� 4�5 � Y W - V /9W!NPM $� & F��� 4�5 � Y W - V /9W!NPM $ � & F

Y R � V Y M - V /9W!NPM $��� G ��� & FR M . W - F

R M . O Y N [ 4

Page 46: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

- V /9W!NPM 4�5 O Y N [ $�� 494 < Y9Y < � $ W=M�� R RZY & G� 494 < Y9Y < � $ W=M�� R RZY & & 4�4 < Y9Y < � $ W M�� R R Y & F

. R / [PY W=O�� W!NPM :�� R � � � � <�M�� . R / � <�U # R < V � � Y W ��/�GY R � N V Y M R V M � <�U # R < V � Y W � [ NPM�� R M <�M�� # R /� #��=\ R M�� / . R � R � . R � : F

#9N [ <�# � 494 < Y9Y < � G W 494 W=M�� R R Y G�� 494 W=M�� R RZY G�� 494 W=M�� R RZY F

� 4�5 < Y9Y < � $=? �� � < W # # R $� & M�� < W # # R $ � & & FW 4�5 ? F � 4�5 ? F � 4�5 ? F� �>W # R W � 5 � < W # # R $�� & <�M . � � 5 � < W # # R $ � & . N

W - � N W O � � N � O ��� R M � N ��O 4�5 � N W O F W 4�5 W M ? FR #�/ R � N ��O 4�5 � N � O F � 4�5 � M ? FR M . W - F� 4�5 ��M ? F

R M . . N F� �>W # R W � 5 � < W # # R $�� & . N

� N ��O 4�5 � N W O F � 4�5 ��M ? F W 4�5 W M ? FR M . . N F� �>W # R � � 5 � < W # # R $ � & . N

� N ��O 4�5 � N � O F � 4�5 ��M ? F � 4�5 � M ? FR M . . N FY R � V Y M RTS <�#%$�� & F

R M . O Y N [ 4

Page 47: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

� �6'()�� ��� . (4 . 0 � 4 '90 %/)��") - � ) - � 0 ��- )*!+

[ N R -�� W=MLN=\�� � RZY 4�5 O Y N [ $2M 494 W M�� R R Y G O 494 W=M�� R R Y &494 W=M�� R RZY F

#9N [ <�# O>W # R G O < Y G Y R / 494 W=M�� R R Y F

Y R / 4�5 L FO>W # R 4�5 / � < [ � N M R � OI$ N M G O�O & F� �>W # R MLN � / � < [ � N R \ O����AOI$2O>W # R & . N

O < Y 4�5 / � < [ � N OLNPO�OI$2O W # R & FW - O < Y N ? O 5 O < Y N�8 O N Y O < Y N�8 O 5 L��� R M Y R / 4�5 Y R / M ? FR #�/ R / � < [ � N O V / ��OI$ N O < Y N ? O ?HG OL< Y N�8 O ? O G O>W # R & F

/ � < [ � N O V / ��OI$ N O < Y N ? O ?HG OL< Y N�8 O�O G O>W # R & FR M . W - F

R M . . N FY R � V Y M Y R / F

R M . O Y N [ 4

Page 48: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �'

&

$

%

� 0 � # �() �6'". 0 � 4 '90 %/) �

P

c

n=6

Page 49: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �

'

&

$

%

Q 6 �34 �05 B �

c/2

n−2

c/4

Appel Récursif

Page 50: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ���

'

&

$

%

� ��� !$02) -��(5 . � 9 5 B=B < (� !+ ( � .1% �( � 4 � � 5 ∈ N

��� � 7 � � 5 9 5 �E4 � � 6 B �1 � � � < ( � � * <>B � 5 9 5 H � � � � 9 � ()(�6 5 B � ∈ R

� �� ∈ R

� � 4 < * * 5 9 � �E4 � � 6 5 � 5 � (�5 �� � %7' � - �- �� <>B � 5 9 5 � � < ( � B � � < � (�5 1 � *�� � � ( 4 * 5 �

. R / /9W=M 4�5 O Y N [ $�� U�� < Y9Y R 4 4 W=M�� R RZY G� 494 # W / � G [ 494 - #9N <� & 494 # W / � F

#9N [ <�# � 494 - #9N <� G � 494 - #9N <� G� ? 494 # W / � G � 8 494 # W / � G �� 494 # W / � F

W - � U�� < Y9Y R 5 L ��� R M Y R � V Y M N OR #�/ R � 4�5�FN ? O F � 4�5�FN�8 O F

� ? 4�5 N� G N � G �AM [ O G N � M [ G ��M [ O G N �AM [ G �AO GN � M [� 8 G �AO G N � M [� � G �AM [� �AO O F

� 8 4�5 . R / /9W=M $�� U�� < Y9Y R Z8 G N � M [� � G ��M [� � O G [� 8)& F�� 4�5 N N � G �AM [� 8 O G N � M [�� 8 G �AM [ O G

N � M [ G �AM [� 8 O G N � M [�� 8 G �AO G � O FY R � V Y M N NPO $ � ? & G NPO $ � 8)& G NPO $ �� �& O F

R M . W - FR M . O Y N [ 4

Page 51: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ���

'

&

$

%

� � � � � � �F� � � � � �:� �

� 4 * � � * � � � 7 5 * � 4 * � � * (���7 6 � < " ��5

7 4 ( < � � *>4 � < � ( 9UT 5 � � 5 B BK< � ( B 6�� 4 * � 4 � < � ( 9UT 5 � � 5 B BK< � ( B� 5 6 � �=< � � � 5 9UT 5 � � 5 B BK< � ( 4 � � � � < 7 4 � < � ( � � � �34 ( � 5

1/4 + 3/10 1/4 + 3/101 × 5

4 × 5+

3 × 2

10 × 2

5�� 4 * ��� G ����� 5�� 4 * ��� Q � G � �

5/20 + 6/20� +IH X� � + Q

11/20� +IX X � ��������� ���

4 * � � * B * � ( � B � � � 58� � B4?9)9�� G � � ��� � � � + +IX � � � Q�� 5�� 4@* ��� G � Q � �6613313319248080001

2432902008176640000

� + � ��������� �������

Page 52: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ��

'

&

$

%

� 0 ) -��(5 � - ) �6'". �&!�- - ���+-/.

( � 7 � � 5 � � �34 ( � �m.10e

� � T 5 � � B 4 ( � � � 7 � � � � 5 �)( 7 4 < 7 �)7 9 5 M = 2 147 483 646� 2 <�� � 5 B � 231 − 1 �

� � 5 ( � 7 � � 5 9 5 � 2 <�� � 5 B 9 5 *>4 7 4 ( � <>B=B 5 5 B � * < 7 < � 6 C =

268 435 448 4 � 5 � 9 5 � * � B *>4 * < 7 < �34 � < � ( " � < B � < � +� � 5 � * � B � � 4 ( 9 � � � � 4 ( � � � BK< � < � 5 B � 0.1 eM

� * 5 � * � B �05 � < �� � � � 4 ( � � � B < � < � 5 B � 0.1 e−M + � 5 B * < 7 < �34 � < � ( B (�6 � 4 � < � 5 BB � ( � B � 7 6 � � < " ��5 B +

1 � � � * � 7 5 B 9 5 � � 6 � <>BK< � (5�� 4 * � � G � + ��������� ��������� ����� G G � G G � + ��� ��������� ��������� � G � �� 4 �

Page 53: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- ��1

'

&

$

%

Y R / � < Y � 4 � W W � / 4�5 � 4

RTS <�# - $=? � & F L �

� 4�5 RTS <�# - $ 8 � & F � 4�5 L ����� J� W W � / 4�5 ? L 4 � 8 � F L � L L L L

Y R / � < Y � 4

� 4�5 ? 8 � D 4 � 4�5 D�� 8 ? 4

� ? 4�5 � � � F � ? 4�5 � J L D � 8 J � D� W W � / 4�5 ? L F

� 8 4�5 RTS <�# - $ � & � RTS <�# - $ � & Fz2 := 0.670592745 10

9

� 8 � ? F L �� W W � / 4�5 � F

� 8 4�5 RTS <�# - $ � & � RTS <�# - $ � & Fz2 := 0.6703 10

9

� 8 � ? F �L L L L L �

Page 54: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� �����! #"%$�&'�)( * +,�,��$.-�/0/0�)- �)

'

&

$

%

� � �,4 ' � ��� ' �". �����(0�� ���,5 ����� � � �π � ε �������

� �������������� � � � 4 * � � * 1 <� � � � � � � � ε ∈ R

∗+

� � ��� �� � � � 6 5 * � � 5 * " ��5 |R − Π| ≤ ε

� tan(Π

4) = 1

5 � 9 � ( � Π = 4.arctan(1)

� 9 6�� 5 * � � �05 7 58( � 58( B 6 �=< 5 9 5 arctan�

arctan(x) = x −x3

3+

x5

5−

x7

7+ ...

� � � � �x ∈ [0, 1]

��(�5 4 � � � � < 7 4 � < � ( 9 5 *;4 B 6 �=< 5 5 B � �

Sp(x) =

p∑

k=0

(−1)k x2k+1

2k + 1

� T 5 � � 58� � � |arctan(x) − Sp(x)| ≤x2p+3

2p + 3

=⇒

π = 4.arctan(1) = 4.S(1) = 4.Sp(1)

4.1

2p + 3

� � � B +

Page 55: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� ����� �"!$#�%&�(' ) *+�,��#-,�././�(, � �

'

&

$

%

1

0,9

0,7

0,95

0,85

30252010

0,75

0,8

0 155

Page 56: +2 +2) b - Page d'accueil / Lirmm.fr / - lirmmboudet/Transparents.pdf+,, $.-/0/0)- ’ & $ % 1 23 4658793 7 :@? ACBEDGF ?IHKJ LNMPOQDEJ?SRTJVU,F ?IFXW0YGD JZA F []\_^E`badcfeda

�������������� ��������������� ����� �"!$#�%&�(' ) *+�,��#-,�././�(, � �

'

&

$

%

� �������������� � � 1 < � 5 � � � � 4 (� � � � � � � � ε

�)( � � � � 4 ( � � � B < � < � +� � ��� �� � � � ( � � � � 4 ( � � 4 � � � � < 7 4 � < � ( 9 5 � � < ( �

� 5 9 5 π

ε� � � B +

� � � � � � � � 4 ( � � B < � (�5 � � � 5�� � < 58(�� ��5���� < 5 � �� �� ��� � � �� �� � � � � � ��� 5�� � < 5���� � � � BK< ����5 � � �

� � � � � �������������! "$# %'&��)($*)+', -/. � � � �10 � 2���43 � ��563 ��� �10 ���43 � ��573 ��� 8 29�57: � 3 �;0 < 9=56: � 3 2� �;0 9�57: � 3?> ���43 � ��563 �@� 2

A � CB� � ���� � � � � ��� �A � .EDGF ��� � IH�� �