Centrale Informatique MP 2007

Thème de l'épreuve	Autour de la suite de Fibonacci. Un calcul de ppcm.
Principaux outils utilisés	récursivité, congruence, suites récurrentes, tas
Mots clefs	Récurrences, calcul matriciel, arbre, opérations sur les bits

Corrigé

(c'est payant, sauf le début) : - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)

Énoncé complet

(télécharger le PDF)

Rapport du jury

(télécharger le PDF)

Énoncé obtenu par reconnaissance optique des caractères

...: &&

@>...Ë@ @@ h@...n......@.... @@...og @@ .........n... @@...@...o@@_. PS.... 
@@...og @@ fin... @... @...@@...@@ : @@.........@@ @P@ @@@@B
@@...g@u@@@@@g@@ @... ...@............@... ......@......@.... @...@Q@@ 
......@@@...... @@.@@ @...@...... NQN T @ ... 3 @@...u@@@.... @@@ @ @

@@@......@R@ @...o...@@@@@@.@ @@@...@...@@@@u@@ ...@...... 
@......@@...O......@@ @@ @@p@@@@ä...@@ @ @@...@Ë@@OO ...m.O....
....+:\ @

:\ @@ @@...u@@@.... @@ @+:m\ @ ïâ\ êoe\ @@ @@...Q@@...@ @@o...@@@@gx@ @@@ 
@@@@@@ @......... î.O....
. ...+:\ : \ ... \ . .

A :\ T:\V H :...\ ... A : Ëo...... ËOQ @@...o @@OE...@@> ? ©...

@@p@@@op@@fi@ @@.........@Æ...OED - O....

.... @@@@......@@... @...E@@ @@@... @...@...@@@ @@@Q@@fi...

@ @Q@@@...... @... ......@o@ @...@@...@ @ fi@@@...............@ @@-......@@Q 
@@@@......@@... @......@@@ fi?@@...@@@@ @... @@@... @@@...@@@g

@ @@@@ @@ @@@@V :...............@@3 u.... @@.........@@ @@ o...@@oË :\ 
@@...@@...@@ @ @@@....@c...@ @@ % G.m.......

.@o...p@...@@ @...E@@ u@@u...@...@%@ @@ :\ @@...@@...@@ Ëoa @@......@...@@@ 
@@...O@@@@@

@@ @@@...Q @... @ ...@@...@@ @@ @Q@@@...... @... @@@@...p@m .oVW:...\ H 2% ... 
@...@Q... "7... w : ......@o...... Ëoa
@+:

:N....\ H @+:vm @ @@ ...AM ......V H ...\ @@ A :\\V H cv.... ......@@......0@ 
@@.@...o @>@@@n...o @@ Ê.OE....

.......@@@@m @@

@@ ...Ë@O @@ @...Q@u@@@@@g@@ @@.........@@ @@@.ä @@...Q @@ @@@@...@@....@... 
......@@......@@@ @@...@@...@@ @@@...p@@ @@...

@@@ @@@@oggs@ @oV @@......@...@@@ @@...O@@@@@ @@ @@@...Q @... @@@ ...@@...@ h: 
@ fiogg@@ @@@... ...@@...@@ @@

@n...@@@...... @@ @@@@@@@Q@@ @... @@@...@>@ @ ê\ @@ ...@@...@@ @@ @@@... 
@@@@u@@.OE@ ......@o@@@ ...@...o @@@...p@@.@

@@@...p...@@@.@ @.Ë...@...@@ @... @@@@oû .: W @... Ëoa @ @@... @@@0.8... @@ 
@@@oä @@ ......@@...@@...@@ @@

fi@>.........@....@...@ @@w@.... @@ :\ @@ ...@@...@@ @... ......@@@......@@@ 
mofi .H @@...Ë@@.... @......@>@@@ @@@ @@...@@...... @.m.......

.: @@ ...@.........@@@OQN@ @@ @......@@@@@@ä... @@.........o@@....

@... @@>@ :\ @@...@@...@@ Ëoa @@@......@@...OE@ @.........@@...@@@@ 
@...@A...Q@fi@ @@@...@@O@ @... @@@ @@>@o@m ...m.m.......

. \ @@ @@...u...@......@@ @... ......@@@@@u@@.@@ u@@@@......@@@ @@ :\ ......@@@
-@@o......@@ @ : @@...p@@ @@ @@.S@@ @@ ......@@@@ä... ofiw @>...@@@@@@ 
@@.........o@@.... @@@ @@...@@...... ...m.m.......

.:\ ......@@...@@...@@ @@@@@@@oeo@g ËS @@ ...@@...@@ @@ @n...@@@...... @... Ëoa 
Ë@ËEE

@@ @@@@@@ @...m ....m @@@n... @@ @@@p...@@@v @@@@...n... @@...u@u@@@@@g@@ @@ @@ 
@@@@@@@oe @@ @@@@o....
@ £\ @@ @@@...@> @... @@@@O@ "@......@@......@@O@ @p@@...@OE@O@ @ .m @@@@o.@ 
@@@@@...... @@@@@Ë@@@
@@ @@.........@...@.... @@@ ......@@OEE@> @@p...@@ @@... @@ @@@@@@@p@ 
@@@p...@@@@ @@... ......@@Æ......Ë @......... A....m.......
à+:\. |_l fik. " m+î\.

... Z @ : ......@o...... Ëoa @ .... H @ "0 H o\ @@o.........@...@@ @@... @@@... 
@...@OE@@ @@ ...@@@@On......m... @@ @u...@@ @@

:\ @@...@@...@@ @@ @@ow@.... @@@@@>...D - m....--

n_ _>_ ËË

N@@N @@...@Q@m - @...OEÈ@Q mÈoocoü

.@@...@p@@@@@...@ @@@...fiËæ...@ @@ @ fio%...@@ @@ u@@@p@... @@@

@@...u@......@@m .@@...Q@.... @@.........@OE@@@OQX@.@ @@@...fi@ow...@fi... 
@@@@@@@...@@@@@o@ @@@... @@...@@@D ...m.<.... .@......@@on...@@@u @......ü...@...@@...@@ @@ A@o...p@@...u@p@@_. @@@@V @@@@O@ @ fi@.@@@@@ @@ .@u...M@...Q@@O@ @@@@.........@@@ @@@ @@>@ @@@...p@@fi@ @@...u@@......@...u...@@... @@@ 
@@@@p@@ü@ @@@...fi@ooe...@ @@ @@@@oû ...m.<.... .Ap@@@@@@...@@@@@o@ @@.Ü@@ @o...... @@...8 @@@......@@@...@...@ @@@@u@@... @@@ @@ @.........@... : @@ @@@...p@@ ......@@@ @@ @@@oä @... @@@......@@.... .......@ Ëoa @@@......@...@@@ @@@... @@@ @@ @@@...@u@@@@@...@ @@@...u@@@goñ@ @.Ë...@...@@ @... @@@...@>m ?.<.... @@@...@@...@@......@@Q @@@...u@@@OE - <.-- ....... @@ @ @@ @@@@...@ -......@@@ @o...@...>...@ @... @@@@ @@@@@ @... @@...@-@-p@@b @ o...@@oË @ 
@@@@oe...@@@ É @ ... @@@--@qu

.@p...@@@ @@.........o@@.... @@@@@@ @@ @@...Ë @... @@@@O@ ......@o.@@@ ...S@O 
@@ ......@@@æ...@@.... @p@@...@@@@ @@

.@@@BË @... @:@@ @@w:@:@.@ Am:v© @@......@.@@ @@ ...@@@@...@>

@@ @:@@...@@@QS@@ Am:v® @@Ë@.OE@ @@@@...@> : @@ @@@BË @@...@ 
......@......@@-.Ë: @@ .. m @ÈE@MOE
.ËSQ H :: @@...o @...@@@g

@@...Q @@ EG @@ A:ê® H :: @@u0@ @.ËSOQ @@ A:ËQ H :: @@ A:@VQ H :: @@@@@oq

.@@@@...QOQQ@Ë@@ @p@@@ofi@@@ @@@ @...@@@ h@......@@...@>...@...@@fi@ @@@... 
@@@@@...@@ @@ @@

.«@@@@Ë@ @@ @@E@OE@Q@Ë... @B-@-ä@ @@@Ë@@@V @@@...@Ë@S\@...\@ @@@E@@.@Q@
A:VO @@@@E@@ @@.5 : @@ @@@...Ë@ N@@@ @@EE@@ @@@n... ...@@@......@@ 
@Sfi.:@w...@...... .. N @...QE@KOE

.@.........@... @@... @@ @@@...@p@@@@@...@
@@@...p@@@@oñ@ @@@...@@O@ @@ @@@@@@@oe @@ @@@@@o @@@ @@@@@...@@ @@ 
...@.........X@...Q@...O@ @@ @...@@...@@
@@... @@@D .......@@@@L @@ ...@ ...S@O @@ ...@ @@@ @... .EQ.EQ @ @@@.@ ...@...o 
@@ @oe@o... ......@@@...@@@.@...Ë...
@@ @@......@ ......@oË@o& @@...@Q...@@@@ @@@...p@@ @@ @@@@@...... @@@@@@@@@@ @@ 
@@.........@...@.... @@@ ......@@......@....
-@> @@@@...p@@ @@p...@@ @@ @@@E@@...@@ ...@o...@o @@ @@@@...fi@ooe...@fi@ 
A@...@...p@g@ @@@@@@@ @@@@...O@@
@@@ @@@@ ......@V @@......@@og@@@p @@@...x@...g@@0@ @@... @@@@Q@@O@ @@ @@ 
@@...@...n...@ä... @@ @@ .......p@@....n...@\...

.G@@fi@Q.Ê @@ @.......Ë@ @... @@ @@@Ë<-H @.--Ê@OE .@@Ë@@:@&\@@:N @:@È@ËÈÈ@@ @:@@ @@.fiî@& @@@@ @@ ...DÛF<ËOEOmÊ ... 95%... moa 4005 {Il/"? 08 HP UOISJSA - ...: && @>...Ë@ @@ h@...n......@.... @@...og @@ .........n... @@...@...o@@_. PS.... 
@@...og @@ fin... @... @...@@...@@ : @@.........@@ @P@ @@@@B
@@...g@u@@@@@g@@ @... ...@............@... ......@......@.... @...@Q@@ 
......@@@...... @@.@@ @...@...... NQN T @ ... 3 @@...u@@@.... @@@ @ @

@@@......@R@ @...o...@@@@@@.@ @@@...@...@@@@u@@ ...@...... 
@......@@...O......@@ @@ @@p@@@@ä...@@ @ @@...@Ë@@OO ...m.O....
....+:\ @

:\ @@ @@...u@@@.... @@ @+:m\ @ ïâ\ êoe\ @@ @@...Q@@...@ @@o...@@@@gx@ @@@ 
@@@@@@ @......... î.O....
. ...+:\ : \ ... \ . .

A :\ T:\V H :...\ ... A : Ëo...... ËOQ @@...o @@OE...@@> ? ©...

@@p@@@op@@fi@ @@.........@Æ...OED - O....

.... @@@@......@@... @...E@@ @@@... @...@...@@@ @@@Q@@fi...

@ @Q@@@...... @... ......@o@ @...@@...@ @ fi@@@...............@ @@-......@@Q 
@@@@......@@... @......@@@ fi?@@...@@@@ @... @@@... @@@...@@@g

@ @@@@ @@ @@@@V :...............@@3 u.... @@.........@@ @@ o...@@oË :\ 
@@...@@...@@ @ @@@....@c...@ @@ % G.m.......

.@o...p@...@@ @...E@@ u@@u...@...@%@ @@ :\ @@...@@...@@ Ëoa @@......@...@@@ 
@@...O@@@@@

@@ @@@...Q @... @ ...@@...@@ @@ @Q@@@...... @... @@@@...p@m .oVW:...\ H 2% ... 
@...@Q... "7... w : ......@o...... Ëoa
@+:

:N....\ H @+:vm @ @@ ...AM ......V H ...\ @@ A :\\V H cv.... ......@@......0@ 
@@.@...o @>@@@n...o @@ Ê.OE....

.......@@@@m @@

@@ ...Ë@O @@ @...Q@u@@@@@g@@ @@.........@@ @@@.ä @@...Q @@ @@@@...@@....@... 
......@@......@@@ @@...@@...@@ @@@...p@@ @@...

@@@ @@@@oggs@ @oV @@......@...@@@ @@...O@@@@@ @@ @@@...Q @... @@@ ...@@...@ h: 
@ fiogg@@ @@@... ...@@...@@ @@

@n...@@@...... @@ @@@@@@@Q@@ @... @@@...@>@ @ ê\ @@ ...@@...@@ @@ @@@... 
@@@@u@@.OE@ ......@o@@@ ...@...o @@@...p@@.@

@@@...p...@@@.@ @.Ë...@...@@ @... @@@@oû .: W @... Ëoa @ @@... @@@0.8... @@ 
@@@oä @@ ......@@...@@...@@ @@

fi@>.........@....@...@ @@w@.... @@ :\ @@ ...@@...@@ @... ......@@@......@@@ 
mofi .H @@...Ë@@.... @......@>@@@ @@@ @@...@@...... @.m.......

.: @@ ...@.........@@@OQN@ @@ @......@@@@@@ä... @@.........o@@....

@... @@>@ :\ @@...@@...@@ Ëoa @@@......@@...OE@ @.........@@...@@@@ 
@...@A...Q@fi@ @@@...@@O@ @... @@@ @@>@o@m ...m.m.......

. \ @@ @@...u...@......@@ @... ......@@@@@u@@.@@ u@@@@......@@@ @@ :\ ......@@@
-@@o......@@ @ : @@...p@@ @@ @@.S@@ @@ ......@@@@ä... ofiw @>...@@@@@@ 
@@.........o@@.... @@@ @@...@@...... ...m.m.......

.:\ ......@@...@@...@@ @@@@@@@oeo@g ËS @@ ...@@...@@ @@ @n...@@@...... @... Ëoa 
Ë@ËEE

@@ @@@@@@ @...m ....m @@@n... @@ @@@p...@@@v @@@@...n... @@...u@u@@@@@g@@ @@ @@ 
@@@@@@@oe @@ @@@@o....
@ £\ @@ @@@...@> @... @@@@O@ "@......@@......@@O@ @p@@...@OE@O@ @ .m @@@@o.@ 
@@@@@...... @@@@@Ë@@@
@@ @@.........@...@.... @@@ ......@@OEE@> @@p...@@ @@... @@ @@@@@@@p@ 
@@@p...@@@@ @@... ......@@Æ......Ë @......... A....m.......
à+:\. |_l fik. " m+î\.

... Z @ : ......@o...... Ëoa @ .... H @ "0 H o\ @@o.........@...@@ @@... @@@... 
@...@OE@@ @@ ...@@@@On......m... @@ @u...@@ @@

:\ @@...@@...@@ @@ @@ow@.... @@@@@>...D - m....--

n_ _>_ ËË

N@@N @@...@Q@m - @...OEÈ@Q mÈoocoü

.@@...@p@@@@@...@ @@@...fiËæ...@ @@ @ fio%...@@ @@ u@@@p@... @@@

@@...u@......@@m .@@...Q@.... @@.........@OE@@@OQX@.@ @@@...fi@ow...@fi... 
@@@@@@@...@@@@@o@ @@@... @@...@@@D ...m.<.... .@......@@on...@@@u @......ü...@...@@...@@ @@ A@o...p@@...u@p@@_. @@@@V @@@@O@ @ fi@.@@@@@ @@ .@u...M@...Q@@O@ @@@@.........@@@ @@@ @@>@ @@@...p@@fi@ @@...u@@......@...u...@@... @@@ 
@@@@p@@ü@ @@@...fi@ooe...@ @@ @@@@oû ...m.<.... .Ap@@@@@@...@@@@@o@ @@.Ü@@ @o...... @@...8 @@@......@@@...@...@ @@@@u@@... @@@ @@ @.........@... : @@ @@@...p@@ ......@@@ @@ @@@oä @... @@@......@@.... .......@ Ëoa @@@......@...@@@ @@@... @@@ @@ @@@...@u@@@@@...@ @@@...u@@@goñ@ @.Ë...@...@@ @... @@@...@>m ?.<.... @@@...@@...@@......@@Q @@@...u@@@OE - <.-- ....... @@ @ @@ @@@@...@ -......@@@ @o...@...>...@ @... @@@@ @@@@@ @... @@...@-@-p@@b @ o...@@oË @ 
@@@@oe...@@@ É @ ... @@@--@qu

.@p...@@@ @@.........o@@.... @@@@@@ @@ @@...Ë @... @@@@O@ ......@o.@@@ ...S@O 
@@ ......@@@æ...@@.... @p@@...@@@@ @@

.@@@BË @... @:@@ @@w:@:@.@ Am:v© @@......@.@@ @@ ...@@@@...@>

@@ @:@@...@@@QS@@ Am:v® @@Ë@.OE@ @@@@...@> : @@ @@@BË @@...@ 
......@......@@-.Ë: @@ .. m @ÈE@MOE
.ËSQ H :: @@...o @...@@@g

@@...Q @@ EG @@ A:ê® H :: @@u0@ @.ËSOQ @@ A:ËQ H :: @@ A:@VQ H :: @@@@@oq

.@@@@...QOQQ@Ë@@ @p@@@ofi@@@ @@@ @...@@@ h@......@@...@>...@...@@fi@ @@@... 
@@@@@...@@ @@ @@

.«@@@@Ë@ @@ @@E@OE@Q@Ë... @B-@-ä@ @@@Ë@@@V @@@...@Ë@S\@...\@ @@@E@@.@Q@
A:VO @@@@E@@ @@.5 : @@ @@@...Ë@ N@@@ @@EE@@ @@@n... ...@@@......@@ 
@Sfi.:@w...@...... .. N @...QE@KOE

.@.........@... @@... @@ @@@...@p@@@@@...@
@@@...p@@@@oñ@ @@@...@@O@ @@ @@@@@@@oe @@ @@@@@o @@@ @@@@@...@@ @@ 
...@.........X@...Q@...O@ @@ @...@@...@@
@@... @@@D .......@@@@L @@ ...@ ...S@O @@ ...@ @@@ @... .EQ.EQ @ @@@.@ ...@...o 
@@ @oe@o... ......@@@...@@@.@...Ë...
@@ @@......@ ......@oË@o& @@...@Q...@@@@ @@@...p@@ @@ @@@@@...... @@@@@@@@@@ @@ 
@@.........@...@.... @@@ ......@@......@....
-@> @@@@...p@@ @@p...@@ @@ @@@E@@...@@ ...@o...@o @@ @@@@...fi@ooe...@fi@ 
A@...@...p@g@ @@@@@@@ @@@@...O@@
@@@ @@@@ ......@V @@......@@og@@@p @@@...x@...g@@0@ @@... @@@@Q@@O@ @@ @@ 
@@...@...n...@ä... @@ @@ .......p@@....n...@\...

.G@@fi@Q.Ê @@ @.......Ë@ @... @@ @@@Ë<-H @.--Ê@OE .@@Ë@@:@&\@@:N @:@È@ËÈÈ@@ @:@@ @@.fiî@& @@@@ @@ ...DÛF<ËOEOmÊ ... 95%... moa 4005 {Il/"? 08 HP UOISJSA - ...: && @>...Ë@ @@ h@...n......@.... @@...og @@ .........n... @@...@...o@@_. PS.... 
@@...og @@ fin... @... @...@@...@@ : @@.........@@ @P@ @@@@B
@@...g@u@@@@@g@@ @... ...@............@... ......@......@.... @...@Q@@ 
......@@@...... @@.@@ @...@...... NQN T @ ... 3 @@...u@@@.... @@@ @ @

@@@......@R@ @...o...@@@@@@.@ @@@...@...@@@@u@@ ...@...... 
@......@@...O......@@ @@ @@p@@@@ä...@@ @ @@...@Ë@@OO ...m.O....
....+:\ @

:\ @@ @@...u@@@.... @@ @+:m\ @ ïâ\ êoe\ @@ @@...Q@@...@ @@o...@@@@gx@ @@@ 
@@@@@@ @......... î.O....
. ...+:\ : \ ... \ . .

A :\ T:\V H :...\ ... A : Ëo...... ËOQ @@...o @@OE...@@> ? ©...

@@p@@@op@@fi@ @@.........@Æ...OED - O....

.... @@@@......@@... @...E@@ @@@... @...@...@@@ @@@Q@@fi...

@ @Q@@@...... @... ......@o@ @...@@...@ @ fi@@@...............@ @@-......@@Q 
@@@@......@@... @......@@@ fi?@@...@@@@ @... @@@... @@@...@@@g

@ @@@@ @@ @@@@V :...............@@3 u.... @@.........@@ @@ o...@@oË :\ 
@@...@@...@@ @ @@@....@c...@ @@ % G.m.......

.@o...p@...@@ @...E@@ u@@u...@...@%@ @@ :\ @@...@@...@@ Ëoa @@......@...@@@ 
@@...O@@@@@

@@ @@@...Q @... @ ...@@...@@ @@ @Q@@@...... @... @@@@...p@m .oVW:...\ H 2% ... 
@...@Q... "7... w : ......@o...... Ëoa
@+:

:N....\ H @+:vm @ @@ ...AM ......V H ...\ @@ A :\\V H cv.... ......@@......0@ 
@@.@...o @>@@@n...o @@ Ê.OE....

.......@@@@m @@

@@ ...Ë@O @@ @...Q@u@@@@@g@@ @@.........@@ @@@.ä @@...Q @@ @@@@...@@....@... 
......@@......@@@ @@...@@...@@ @@@...p@@ @@...

@@@ @@@@oggs@ @oV @@......@...@@@ @@...O@@@@@ @@ @@@...Q @... @@@ ...@@...@ h: 
@ fiogg@@ @@@... ...@@...@@ @@

@n...@@@...... @@ @@@@@@@Q@@ @... @@@...@>@ @ ê\ @@ ...@@...@@ @@ @@@... 
@@@@u@@.OE@ ......@o@@@ ...@...o @@@...p@@.@

@@@...p...@@@.@ @.Ë...@...@@ @... @@@@oû .: W @... Ëoa @ @@... @@@0.8... @@ 
@@@oä @@ ......@@...@@...@@ @@

fi@>.........@....@...@ @@w@.... @@ :\ @@ ...@@...@@ @... ......@@@......@@@ 
mofi .H @@...Ë@@.... @......@>@@@ @@@ @@...@@...... @.m.......

.: @@ ...@.........@@@OQN@ @@ @......@@@@@@ä... @@.........o@@....

@... @@>@ :\ @@...@@...@@ Ëoa @@@......@@...OE@ @.........@@...@@@@ 
@...@A...Q@fi@ @@@...@@O@ @... @@@ @@>@o@m ...m.m.......

. \ @@ @@...u...@......@@ @... ......@@@@@u@@.@@ u@@@@......@@@ @@ :\ ......@@@
-@@o......@@ @ : @@...p@@ @@ @@.S@@ @@ ......@@@@ä... ofiw @>...@@@@@@ 
@@.........o@@.... @@@ @@...@@...... ...m.m.......

.:\ ......@@...@@...@@ @@@@@@@oeo@g ËS @@ ...@@...@@ @@ @n...@@@...... @... Ëoa 
Ë@ËEE

@@ @@@@@@ @...m ....m @@@n... @@ @@@p...@@@v @@@@...n... @@...u@u@@@@@g@@ @@ @@ 
@@@@@@@oe @@ @@@@o....
@ £\ @@ @@@...@> @... @@@@O@ "@......@@......@@O@ @p@@...@OE@O@ @ .m @@@@o.@ 
@@@@@...... @@@@@Ë@@@
@@ @@.........@...@.... @@@ ......@@OEE@> @@p...@@ @@... @@ @@@@@@@p@ 
@@@p...@@@@ @@... ......@@Æ......Ë @......... A....m.......
à+:\. |_l fik. " m+î\.

... Z @ : ......@o...... Ëoa @ .... H @ "0 H o\ @@o.........@...@@ @@... @@@... 
@...@OE@@ @@ ...@@@@On......m... @@ @u...@@ @@

:\ @@...@@...@@ @@ @@ow@.... @@@@@>...D - m....--

n_ _>_ ËË

N@@N @@...@Q@m - @...OEÈ@Q mÈoocoü

.@@...@p@@@@@...@ @@@...fiËæ...@ @@ @ fio%...@@ @@ u@@@p@... @@@

@@...u@......@@m .@@...Q@.... @@.........@OE@@@OQX@.@ @@@...fi@ow...@fi... 
@@@@@@@...@@@@@o@ @@@... @@...@@@D ...m.<.... .@......@@on...@@@u @......ü...@...@@...@@ @@ A@o...p@@...u@p@@_. @@@@V @@@@O@ @ fi@.@@@@@ @@ .@u...M@...Q@@O@ @@@@.........@@@ @@@ @@>@ @@@...p@@fi@ @@...u@@......@...u...@@... @@@ 
@@@@p@@ü@ @@@...fi@ooe...@ @@ @@@@oû ...m.<.... .Ap@@@@@@...@@@@@o@ @@.Ü@@ @o...... @@...8 @@@......@@@...@...@ @@@@u@@... @@@ @@ @.........@... : @@ @@@...p@@ ......@@@ @@ @@@oä @... @@@......@@.... .......@ Ëoa @@@......@...@@@ @@@... @@@ @@ @@@...@u@@@@@...@ @@@...u@@@goñ@ @.Ë...@...@@ @... @@@...@>m ?.<.... @@@...@@...@@......@@Q @@@...u@@@OE - <.-- ....... @@ @ @@ @@@@...@ -......@@@ @o...@...>...@ @... @@@@ @@@@@ @... @@...@-@-p@@b @ o...@@oË @ 
@@@@oe...@@@ É @ ... @@@--@qu

.@p...@@@ @@.........o@@.... @@@@@@ @@ @@...Ë @... @@@@O@ ......@o.@@@ ...S@O 
@@ ......@@@æ...@@.... @p@@...@@@@ @@

.@@@BË @... @:@@ @@w:@:@.@ Am:v© @@......@.@@ @@ ...@@@@...@>

@@ @:@@...@@@QS@@ Am:v® @@Ë@.OE@ @@@@...@> : @@ @@@BË @@...@ 
......@......@@-.Ë: @@ .. m @ÈE@MOE
.ËSQ H :: @@...o @...@@@g

@@...Q @@ EG @@ A:ê® H :: @@u0@ @.ËSOQ @@ A:ËQ H :: @@ A:@VQ H :: @@@@@oq

.@@@@...QOQQ@Ë@@ @p@@@ofi@@@ @@@ @...@@@ h@......@@...@>...@...@@fi@ @@@... 
@@@@@...@@ @@ @@

.«@@@@Ë@ @@ @@E@OE@Q@Ë... @B-@-ä@ @@@Ë@@@V @@@...@Ë@S\@...\@ @@@E@@.@Q@
A:VO @@@@E@@ @@.5 : @@ @@@...Ë@ N@@@ @@EE@@ @@@n... ...@@@......@@ 
@Sfi.:@w...@...... .. N @...QE@KOE

.@.........@... @@... @@ @@@...@p@@@@@...@
@@@...p@@@@oñ@ @@@...@@O@ @@ @@@@@@@oe @@ @@@@@o @@@ @@@@@...@@ @@ 
...@.........X@...Q@...O@ @@ @...@@...@@
@@... @@@D .......@@@@L @@ ...@ ...S@O @@ ...@ @@@ @... .EQ.EQ @ @@@.@ ...@...o 
@@ @oe@o... ......@@@...@@@.@...Ë...
@@ @@......@ ......@oË@o& @@...@Q...@@@@ @@@...p@@ @@ @@@@@...... @@@@@@@@@@ @@ 
@@.........@...@.... @@@ ......@@......@....
-@> @@@@...p@@ @@p...@@ @@ @@@E@@...@@ ...@o...@o @@ @@@@...fi@ooe...@fi@ 
A@...@...p@g@ @@@@@@@ @@@@...O@@
@@@ @@@@ ......@V @@......@@og@@@p @@@...x@...g@@0@ @@... @@@@Q@@O@ @@ @@ 
@@...@...n...@ä... @@ @@ .......p@@....n...@\...

.G@@fi@Q.Ê @@ @.......Ë@ @... @@ @@@Ë<-H @.--Ê@OE .@@Ë@@:@&\@@:N @:@È@ËÈÈ@@ @:@@ @@.fiî@& @@@@ @@ ...DÛF<ËOEOmÊ ... 95%... moa 4005 {Il/"? 08 HP UOISJSA - ...:...oemoem .: @:@>@@ @...Q@@æ......w@: @@ :D... @@ ...5@...@@ :@ @:o... @@@:@@@.OE@
@:o...p@...0@:@: @@ @:QËo: @... @:_@ :@:@:o...>... ....:o...p@...0@:@: @::fi@ 
@:@@ @... @@ ...@5OE - m.:

...: :...VO H ...... @ :o u@@:@@: : @@ @:fip@:0@ ...... ::@Ë@: @@ @@@ :: ::o: 
@:...@ :@:@:o...>... - D.:

@... H @... ::o: @: :@ :5@...@> @... @:@@... 6... @fi:...@@:_. m @@
......:@......@ @... ::o: G...û... @@ ...:@...@@ @... @@:Q@ @: :@ @::@...@> 
@@@:@:@.Ë@ @@... :@@:@@@:Q@OE - O.:

.@.........:@ @... @:@@ :o......@...@@:@m... @@...@QQ@ @:@@ :o...@@:@:o 
@......@...... @: D .... @:...@@:
@... @@ :5@...@> @... @oe:@:@ :...O>@ @@:Q...@ @@@ @@ @ËË:Ë@ @... 
:@:p...p@:0@@: @:@ËEoO - m.:

.... ...@@...... @@ @::@@:Ë@
@... ::@>:@@@:Q :@V @: :: @:@@ @:@@: 5@@>:o: :: :@:@@:... :o-@:@: @:@:::ÈO - <.= @@: @@ @::@@:Ë@ @... @:@...@@:O@@: :o @@ ?... ...:+dê :@ @:...@@: @... @oe:@:@ :o ...: @: @@@ @......Q...p...::: :o @:o...@ "dm... H @... @:...@ @......@...... @@ ?... ...dê @:...@@: @... ...@ fi:o:...oe . @@: @... @:@@ A@... "@@...V @: @:@@:... @:@@: 5@@>50: :: @:@@:... :o @@ @... @: @@OE @......Q.........ËË :o 
fi.:@Ë:@ä... @@ @... ...oe .
... @@:@>...:@ :8@.... @... @@ @...û... @...:@...@@ :o
"...@.@m @:@@ @:@@@:Q @:o...@ @@ ...:Ê :|æû... @...5@...@@ :...O>@ @@:Q...< ....m ...Ë @: @:@@:... @:@@: ...:@@ ::...@ @:fip@:0@ @@ @: @... @@ @ W @:@...@:@ @@@ :Ü%... @... @@ NH@@OE .........:@Q@@ :< @... @:@@E. @...5@...@@ ::2...: @... @@@ @...o...@...:@> @:: @:@@ @v...@o@@ :O 
........p@:@p... @@ @::...fi:ooe...@h

.@@...@...@:@Q:È@ @::o_.:op @:@@ @@@:@:@...@...p@ @@... @:...@ @@:o@ @@ 
h@......:@@OQ...:Ë@ @:@...::@:Q
@::@:: @... ......:@æ@ @@...Q:O@ ......5@@ @...@::@_. @:@...@:O@ @: @: @... 
fi@:ä............Ëoe...@ @@ ::o...... . ...@ V @
...@ @:@::@...:@@ @@ ...@ A......... ......@V :V 3 ...@V ... @@:@>...:@ :8@.... 
@... @@ @@::O@:o @:@@ @@...Q:O@ @@...

.: @@ @ ...... @@
Am H@ Am 63 @@...Q:O@ @@... @: @... @:@@ @>5@:...... :o à:... @...5@...@@ 
:...O>@ @@:Q...@ fi@...n...::@@...@ @@
«c:... V @... @:...@ ...@...... :@...Ë@ ...............@Q @:...Q @... @@ ô @@ 
@... @ ...@...w...@ 50 :5@...:@......:... :@...::@:Q @:@...::0:
:: @@ : @:...@ @...@...... 355 @:@...@:@R@ @@...Q:O@ @@... @:@@ @: @... @:@@ 
@@V...@o@@ @:@@ G...û... @@
...:@...@@ @... @@:Q...< .:@...::@:Q : @@ ...?... ...dê @@...Q:O@ @@@ @: @@@@:@...@...p@ @:@@ @@:@@: @@... :o... .@@:Efi:ooe...@ @@... @:@::@>OE@@.OE@
:@::::@:oeoä... @@ @@@... @@:@::@@ @: :o ... ...@... @@@... @@:OQ::......: @: 
@@@ :@...:Q...:@:: @@ :@v...@@......@
.::0: @:E@@:: :@ @@@.........p:@ @@@::0@ @@ @ËË:Ë@ @... .m ::@@:o....oä @@ 
@@:@o: m @@ "...
.:Ê@:o....oä @@ @@:@o: ......5@@ R@:@@: @::R@ @:fip@:0@ @:@@ @@:@o: @@ 
@:@@@@@og @: ::
fi@...Q...::@@...@ @@ .AA @......@:@ @... @:@> @......@@@.OE @... @@ ......È:@: 
@E@E-.Ë... @@ ...:...... ...«@Ë:@... ... @@ Ë@...
-:@......... ...... Ë@@:@......@:Q @@ ...5...@@ ...ËE@......@@Ë@>.@ ....5@@ 
...@......QS@: @:@@ @Ë:@...... @@ N:@@>...: @@...
@@@... @@ @:...@ .........@.... @... @:...@ ...@:...@ @......@...:QO:Q @...E@@ 
:@>:@@@:: @:@>...O@ @@:@o: @@ @:o...@@@:Qgs@
@@......@:@:@>@ @@ @:o...@@:o...@@ @... .@......... @...@:@:@>@ @@@ @@ 
@@@:@:@...@...p@ @@... @:...@ @.........@n... @:...: @:@::
-@@@...:p@ @@@@::...@...p@ @:: @@@@@og @:@@: @5...o@:...O @::0@:o 
@:@::@u@...Q:È@ @...o...::@@:@ ::...@
@@@:...p@...@ @@:@::@...@ @@@ @: @@@@:@...@...p@ @:@@ @@:@@: @@... @:@@ 
@:...@:B @:n...:@ :: @@ @@@ : D

@@: @@ @::......@:Ë@ @:: :@@.........p:@ @> :O R@...@@ ::o...... .@@:@@@@@:Q 
@...:@...@@ @@... :::::@...@::
:@ @:@@...o...gx@ :@ ...: h...... ... @... ::o: G...û... @@... @:@@ 
:@...5@...@@ @u...@:...:o@ :o "......:@::@@...@@.8... @:...m

.».m.mm.@m H @... fi@...QS:@@...@ @@ .iâà V : W EUR: @5@ ...@...... :@...@:@

n...Ê @:@.........n...

@:...@...::fi... @@ â ...... @:@@:o ::o: @@ : @@ m @:p:@ @æ:@... @:@@ :@ 
@...:Q::O@ @:@...::@:Q @@Ë::o:
@@@ ...@@:@@@...o:@ @:@::@@@...Ë@V @@...:@ @... âr: à:$: @@ ...:w: . .. S...: H 
:... @@ .........oe@fi@ ......

.: W @:@...@:@ @@... @:@@ @@ ::::::8 @...:...@...::: ...............@Q... 
@:...Q... @... fiZ ... :
::o: °.:@...:@...@@ @@ @:@Ë@:Ë@: @:Efi:ooe...@ :: :@@m...@:@fi@ @@ 
@.........:@Q @...E@@ @@ ......p@@....n...@......

Ë@QQ @@ ...:u...@u :D |...... @...Ë@ñ...

... u%m :@ @:@äofi @w@@...@@...@ @@ @......@@n...@@ @@ ...@ @@:@@@.EQ @@ @@@ËQ 
@@ Ë@...@E@Ë :: ::@
...5@...@@ @@ @.@Ë:@@..... @::...@ @:...@E :@ ...@......5@.@.: @... ...:@:ËE@: 
... @:@...:@ :: ......@...@@::@@...@æv :@n...

doc... H .: @@ hm o...:@o:: 808. :@...5@...@@ @@ @...Q@::o@...@: :8@.... @:: 
:@@ogo:m Q.O....
:: @@ @:@:@...... @@ @@ @.........@...... @... @:@@ 5@@...n...@...... :: 
@:@@.........Ë :o...Ë:o.... @:@@O .î:@@...n...@p @@@
@:@@ @...ä...::0@ @ @@...o...@...:@> @@ @:o...p@@@@ü@ @@ @:o...fi@@@ ?: 
...:VX@::VO :@ â. ......:@...:@...@@
:o...Ë:o.... @:: @:...:@@ fi@......:@@@@@Ë... :o...p@@:...@ @... @:@@ @@@ @... 
@@ @@@... @@@": @@ % GND...
.@. @@ @@>...@@@@@:@ @:@@...@> @@@ :@v...@@...@ Ë@Q @@@...@@... :: 
@:@@.........Ë :O

.@:o...fi@@@ ...:VO @:@@...@.... :@ @@. ......:@:ËSË

@@ ...: @@ @: @@:p:@ :@ @:@:@:Q & @>...p@:@p... :o...Ë:o.... @:: @:@:@@:...@:: 
@:...:@......... ...m.O....
.@......5@ @... @@ @@S:@... :@@@@...@@@: @@@ @:@@...@8@ @: :@

...@......@@:m... :@ @......@@:a... @@ @@S:@... @...:@:\@.Ë@ @@... 
...:@...:@...@@ ..........@:@...... @EE@:OE@Ë... :: @:.E@@ :O
..Ë. ......:@:Ëop@: @@ : @@.S:@ :@ @:@:@:Q moe :o...Ë:o....

@:: @:...:@OE .m H @: @@@ @... @:@@ @:@S@...s@@ :o......@@:...@ @Ë@@ Ë@Q 
@@@...Q @@ :O ...m.O....

.?@.........:@@: :@ @......@:Ëo.... @>5@.8... @:: @@@... @@:@::@@ @: :oV 
:o...@:@@x@fi@
@n...::@...... :@ ::@@:@:w @@ @:@Ë :: :@::oû .@. @:@@@...:OE@@ :o...u@...@: 
@... @:@::@...Q::...@ @:@5...@
-......Q:@ :@ @@. Ë@:Ë©Ë: @@ fi: @@ @: @@:u:@ :@ @:@:@:@... & :o...Ë:o.... @:: 
@:...:@......... .......D....

.Ê|S+Ë @@ â. @@:ÆËo: x:@@ @@@ @::::o@ @... @@ È+:3 Z ... : Ëo...... ::o:
:|S+â+ @@. H S+:@. ... @@:@Ë:@@: @@ :o...p@...@: @... ......:@OE...Ë> @@ "... H 
:|S@. H . . . H @. H 8.
@@ @ H @@. @@:Ë@p @:@...::@:Q @@ @. @p...:@ @... ...@M...... m A .: ::o: 
.........:@:3:...@:: @:@@...@:O@ :O

:o...@@@......@:@:@oe @:D - D....
........m.O.... :o...u@@:...@ @... @@ @@@:ÈË@R... @@ :@:@Q:ÈO 
.@...o......@...... @@...o: @@ ......B @... @:@>

......:o.... @@...o: @@ ......B :@ fi: @@ @:...@:...@... :o...p@@:@@@ä...@: 
@... @:@@: :@ ": :@...@:@ ::...@ ...... o...:@o::
@:@@: @... :@:...:Ë@p@@ @@ ......:@Ë@:Ë@Q @@@:ÈË@ :: :@@:@@@:Q@: @@ 
@:...::p@:oO G.O....

.@@:@@@@@:Q :o...u@@:...@ @... @@ u@u...:@@: @...
:@>5@:u@: @@ @5@...@0...:@Q-æ @@ ...fi :...... H 3... @: @...:OE@@ @... @@...:@ 
@... @:...@ :@>5@:L Ê.O....

....OE o...om...... @@ :5@...@> @... :@::O@ "@:@@@@@.8... @p@::o@:@fi... @@ 
@@...@...... < @.O.... ....fi :...... H ê3 @:...@ ...@...... ...... ......@......@ :: @:@@ ...DOÈ<ÊOEOKZ... ...:...oemoem .: @:@>@@ @...Q@@æ......w@: @@ :D... @@ ...5@...@@ :@ @:o... @@@:@@@.OE@
@:o...p@...0@:@: @@ @:QËo: @... @:_@ :@:@:o...>... ....:o...p@...0@:@: @::fi@ 
@:@@ @... @@ ...@5OE - m.:

...: :...VO H ...... @ :o u@@:@@: : @@ @:fip@:0@ ...... ::@Ë@: @@ @@@ :: ::o: 
@:...@ :@:@:o...>... - D.:

@... H @... ::o: @: :@ :5@...@> @... @:@@... 6... @fi:...@@:_. m @@
......:@......@ @... ::o: G...û... @@ ...:@...@@ @... @@:Q@ @: :@ @::@...@> 
@@@:@:@.Ë@ @@... :@@:@@@:Q@OE - O.:

.@.........:@ @... @:@@ :o......@...@@:@m... @@...@QQ@ @:@@ :o...@@:@:o 
@......@...... @: D .... @:...@@:
@... @@ :5@...@> @... @oe:@:@ :...O>@ @@:Q...@ @@@ @@ @ËË:Ë@ @... 
:@:p...p@:0@@: @:@ËEoO - m.:

.... ...@@...... @@ @::@@:Ë@
@... ::@>:@@@:Q :@V @: :: @:@@ @:@@: 5@@>:o: :: :@:@@:... :o-@:@: @:@:::ÈO - <.= @@: @@ @::@@:Ë@ @... @:@...@@:O@@: :o @@ ?... ...:+dê :@ @:...@@: @... @oe:@:@ :o ...: @: @@@ @......Q...p...::: :o @:o...@ "dm... H @... @:...@ @......@...... @@ ?... ...dê @:...@@: @... ...@ fi:o:...oe . @@: @... @:@@ A@... "@@...V @: @:@@:... @:@@: 5@@>50: :: @:@@:... :o @@ @... @: @@OE @......Q.........ËË :o 
fi.:@Ë:@ä... @@ @... ...oe .
... @@:@>...:@ :8@.... @... @@ @...û... @...:@...@@ :o
"...@.@m @:@@ @:@@@:Q @:o...@ @@ ...:Ê :|æû... @...5@...@@ :...O>@ @@:Q...< ....m ...Ë @: @:@@:... @:@@: ...:@@ ::...@ @:fip@:0@ @@ @: @... @@ @ W @:@...@:@ @@@ :Ü%... @... @@ NH@@OE .........:@Q@@ :< @... @:@@E. @...5@...@@ ::2...: @... @@@ @...o...@...:@> @:: @:@@ @v...@o@@ :O 
........p@:@p... @@ @::...fi:ooe...@h

.@@...@...@:@Q:È@ @::o_.:op @:@@ @@@:@:@...@...p@ @@... @:...@ @@:o@ @@ 
h@......:@@OQ...:Ë@ @:@...::@:Q
@::@:: @... ......:@æ@ @@...Q:O@ ......5@@ @...@::@_. @:@...@:O@ @: @: @... 
fi@:ä............Ëoe...@ @@ ::o...... . ...@ V @
...@ @:@::@...:@@ @@ ...@ A......... ......@V :V 3 ...@V ... @@:@>...:@ :8@.... 
@... @@ @@::O@:o @:@@ @@...Q:O@ @@...

.: @@ @ ...... @@
Am H@ Am 63 @@...Q:O@ @@... @: @... @:@@ @>5@:...... :o à:... @...5@...@@ 
:...O>@ @@:Q...@ fi@...n...::@@...@ @@
«c:... V @... @:...@ ...@...... :@...Ë@ ...............@Q @:...Q @... @@ ô @@ 
@... @ ...@...w...@ 50 :5@...:@......:... :@...::@:Q @:@...::0:
:: @@ : @:...@ @...@...... 355 @:@...@:@R@ @@...Q:O@ @@... @:@@ @: @... @:@@ 
@@V...@o@@ @:@@ G...û... @@
...:@...@@ @... @@:Q...< .:@...::@:Q : @@ ...?... ...dê @@...Q:O@ @@@ @: @@@@:@...@...p@ @:@@ @@:@@: @@... :o... .@@:Efi:ooe...@ @@... @:@::@>OE@@.OE@
:@::::@:oeoä... @@ @@@... @@:@::@@ @: :o ... ...@... @@@... @@:OQ::......: @: 
@@@ :@...:Q...:@:: @@ :@v...@@......@
.::0: @:E@@:: :@ @@@.........p:@ @@@::0@ @@ @ËË:Ë@ @... .m ::@@:o....oä @@ 
@@:@o: m @@ "...
.:Ê@:o....oä @@ @@:@o: ......5@@ R@:@@: @::R@ @:fip@:0@ @:@@ @@:@o: @@ 
@:@@@@@og @: ::
fi@...Q...::@@...@ @@ .AA @......@:@ @... @:@> @......@@@.OE @... @@ ......È:@: 
@E@E-.Ë... @@ ...:...... ...«@Ë:@... ... @@ Ë@...
-:@......... ...... Ë@@:@......@:Q @@ ...5...@@ ...ËE@......@@Ë@>.@ ....5@@ 
...@......QS@: @:@@ @Ë:@...... @@ N:@@>...: @@...
@@@... @@ @:...@ .........@.... @... @:...@ ...@:...@ @......@...:QO:Q @...E@@ 
:@>:@@@:: @:@>...O@ @@:@o: @@ @:o...@@@:Qgs@
@@......@:@:@>@ @@ @:o...@@:o...@@ @... .@......... @...@:@:@>@ @@@ @@ 
@@@:@:@...@...p@ @@... @:...@ @.........@n... @:...: @:@::
-@@@...:p@ @@@@::...@...p@ @:: @@@@@og @:@@: @5...o@:...O @::0@:o 
@:@::@u@...Q:È@ @...o...::@@:@ ::...@
@@@:...p@...@ @@:@::@...@ @@@ @: @@@@:@...@...p@ @:@@ @@:@@: @@... @:@@ 
@:...@:B @:n...:@ :: @@ @@@ : D

@@: @@ @::......@:Ë@ @:: :@@.........p:@ @> :O R@...@@ ::o...... .@@:@@@@@:Q 
@...:@...@@ @@... :::::@...@::
:@ @:@@...o...gx@ :@ ...: h...... ... @... ::o: G...û... @@... @:@@ 
:@...5@...@@ @u...@:...:o@ :o "......:@::@@...@@.8... @:...m

.».m.mm.@m H @... fi@...QS:@@...@ @@ .iâà V : W EUR: @5@ ...@...... :@...@:@

n...Ê @:@.........n...

@:...@...::fi... @@ â ...... @:@@:o ::o: @@ : @@ m @:p:@ @æ:@... @:@@ :@ 
@...:Q::O@ @:@...::@:Q @@Ë::o:
@@@ ...@@:@@@...o:@ @:@::@@@...Ë@V @@...:@ @... âr: à:$: @@ ...:w: . .. S...: H 
:... @@ .........oe@fi@ ......

.: W @:@...@:@ @@... @:@@ @@ ::::::8 @...:...@...::: ...............@Q... 
@:...Q... @... fiZ ... :
::o: °.:@...:@...@@ @@ @:@Ë@:Ë@: @:Efi:ooe...@ :: :@@m...@:@fi@ @@ 
@.........:@Q @...E@@ @@ ......p@@....n...@......

Ë@QQ @@ ...:u...@u :D |...... @...Ë@ñ...

... u%m :@ @:@äofi @w@@...@@...@ @@ @......@@n...@@ @@ ...@ @@:@@@.EQ @@ @@@ËQ 
@@ Ë@...@E@Ë :: ::@
...5@...@@ @@ @.@Ë:@@..... @::...@ @:...@E :@ ...@......5@.@.: @... ...:@:ËE@: 
... @:@...:@ :: ......@...@@::@@...@æv :@n...

doc... H .: @@ hm o...:@o:: 808. :@...5@...@@ @@ @...Q@::o@...@: :8@.... @:: 
:@@ogo:m Q.O....
:: @@ @:@:@...... @@ @@ @.........@...... @... @:@@ 5@@...n...@...... :: 
@:@@.........Ë :o...Ë:o.... @:@@O .î:@@...n...@p @@@
@:@@ @...ä...::0@ @ @@...o...@...:@> @@ @:o...p@@@@ü@ @@ @:o...fi@@@ ?: 
...:VX@::VO :@ â. ......:@...:@...@@
:o...Ë:o.... @:: @:...:@@ fi@......:@@@@@Ë... :o...p@@:...@ @... @:@@ @@@ @... 
@@ @@@... @@@": @@ % GND...
.@. @@ @@>...@@@@@:@ @:@@...@> @@@ :@v...@@...@ Ë@Q @@@...@@... :: 
@:@@.........Ë :O

.@:o...fi@@@ ...:VO @:@@...@.... :@ @@. ......:@:ËSË

@@ ...: @@ @: @@:p:@ :@ @:@:@:Q & @>...p@:@p... :o...Ë:o.... @:: @:@:@@:...@:: 
@:...:@......... ...m.O....
.@......5@ @... @@ @@S:@... :@@@@...@@@: @@@ @:@@...@8@ @: :@

...@......@@:m... :@ @......@@:a... @@ @@S:@... @...:@:\@.Ë@ @@... 
...:@...:@...@@ ..........@:@...... @EE@:OE@Ë... :: @:.E@@ :O
..Ë. ......:@:Ëop@: @@ : @@.S:@ :@ @:@:@:Q moe :o...Ë:o....

@:: @:...:@OE .m H @: @@@ @... @:@@ @:@S@...s@@ :o......@@:...@ @Ë@@ Ë@Q 
@@@...Q @@ :O ...m.O....

.?@.........:@@: :@ @......@:Ëo.... @>5@.8... @:: @@@... @@:@::@@ @: :oV 
:o...@:@@x@fi@
@n...::@...... :@ ::@@:@:w @@ @:@Ë :: :@::oû .@. @:@@@...:OE@@ :o...u@...@: 
@... @:@::@...Q::...@ @:@5...@
-......Q:@ :@ @@. Ë@:Ë©Ë: @@ fi: @@ @: @@:u:@ :@ @:@:@:@... & :o...Ë:o.... @:: 
@:...:@......... .......D....

.Ê|S+Ë @@ â. @@:ÆËo: x:@@ @@@ @::::o@ @... @@ È+:3 Z ... : Ëo...... ::o:
:|S+â+ @@. H S+:@. ... @@:@Ë:@@: @@ :o...p@...@: @... ......:@OE...Ë> @@ "... H 
:|S@. H . . . H @. H 8.
@@ @ H @@. @@:Ë@p @:@...::@:Q @@ @. @p...:@ @... ...@M...... m A .: ::o: 
.........:@:3:...@:: @:@@...@:O@ :O

:o...@@@......@:@:@oe @:D - D....
........m.O.... :o...u@@:...@ @... @@ @@@:ÈË@R... @@ :@:@Q:ÈO 
.@...o......@...... @@...o: @@ ......B @... @:@>

......:o.... @@...o: @@ ......B :@ fi: @@ @:...@:...@... :o...p@@:@@@ä...@: 
@... @:@@: :@ ": :@...@:@ ::...@ ...... o...:@o::
@:@@: @... :@:...:Ë@p@@ @@ ......:@Ë@:Ë@Q @@@:ÈË@ :: :@@:@@@:Q@: @@ 
@:...::p@:oO G.O....

.@@:@@@@@:Q :o...u@@:...@ @... @@ u@u...:@@: @...
:@>5@:u@: @@ @5@...@0...:@Q-æ @@ ...fi :...... H 3... @: @...:OE@@ @... @@...:@ 
@... @:...@ :@>5@:L Ê.O....

....OE o...om...... @@ :5@...@> @... :@::O@ "@:@@@@@.8... @p@::o@:@fi... @@ 
@@...@...... < @.O.... ....fi :...... H ê3 @:...@ ...@...... ...... ......@......@ :: @:@@ ...DOÈ<ÊOEOKZ... @... && ....ZHHHOOO .oeËm5 -oä @@ ÊËo @Ëoeoewä oeËËEOOEËL ËoeÆ=Ë :oe @@ ËËoËo Ëoa oeËoeoeoeoeoæfl oeQË3 2 : Æo QOOEËO... :oe ËoeËoeË...oeoe0ä ËEOE>OE .: 2 @@ E 25 .OE>soä Ëoea :O - Ü.Ë

&... oeoeoæomOEoe oeEQ
oeoeSÆ...ËOOEË oeÆo =-Y3Æ...Ë .:05593% 383 :$ ÊoeËoeä...oeoe8æ .OEEOE>OE 
.....ÆËËQ pm@
.5...Ëoe :: ...oe ËEËËËÜ Æo ËËËËËQ oeäË:oefiwä oefififiooeË :: Hamon...on - m.:

QÊ 9@.Èl ...DOÈ<ÊOEOn=S

Extrait du corrigé obtenu par reconnaissance optique des caractères


Centrale Informatique MP 2007 -- Corrigé
Ce corrigé est proposé par Vincent Danjean (Enseignant-chercheur en école 
d'ingénieur) ; il a été relu par Sattisvar Tandabany (ENS Lyon) et Vincent 
Puyhaubert
(Professeur en CPGE).

Cette épreuve se compose de deux problèmes indépendants de longueurs inégales.
· En informatique, on est parfois amené à devoir évaluer des suites (complètes
ou seulement certaines valeurs) dont le calcul direct est hors de portée de nos
moyens de calcul actuels. Le premier problème explore de telles problématiques
à travers l'étude de suites récurrentes linéaires. La suite de Fibonacci, très
connue, en est un exemple typique. Ce problème est l'occasion de comparer
la complexité de plusieurs méthodes de calcul et de découvrir de nouvelles
techniques pour la réduire.
Les idées proposées pour la suite de Fibonacci dans les parties I.B et I.C 
seront
une sources d'inspiration pour résoudre les questions de la partie I.D, qui 
aborde
des problèmes plus généraux.
C'est en utilisant des méthodes semblables à celles présentées ici que l'on
parvient, par exemple, à calculer une décimale quelconque d'un nombre
transcendant comme , sans avoir besoin de calculer celles qui la précèdent.
· Le second problème expose un algorithme de calcul de ppcm utilisant une 
structure de donnée particulière : les tas. Il s'agit ici de comprendre 
l'algorithme
proposé afin de calculer sa complexité. La question II.C demande de dérouler
manuellement l'algorithme qui manipule un tas.

Indications
I.A.1 En binaire, la multiplication d'un nombre a par un bit a pour résultat a 
ou 0.
I.A.2 Soit a = a1 2m + a2 et b = b1 2m + b2 . Si l'on pose
X = a1 b 1

Y = a2 b 2

alors
et donc

et

Z = (a1 + b1 ) (a2 + b2 )

Z - X - Y = a1 b 2 + a2 b 1
ab = X22m + (Z - X - Y)2m + Y

I.B.1 Utiliser les résultats classiques sur les suites récurrentes linéaires 
d'ordre 2.
I.B.3 Poser F(n) le nombre d'appels récursifs. Exprimer une relation de 
récurrence
sur F(n) grâce au programme.
I.B.4 Penser à stocker quelques uns des résultats précédents pour pouvoir 
calculer
facilement fk .
I.B.5 L'algorithme d'exponentiation rapide marche aussi pour les matrices.
I.B.6 Constater que le modulo est compatible avec l'addition, la multiplication 
et
l'exponentiation par une constante.
I.C.1 Prouver la relation demandée par récurrence sur n.
2

I.C.2 Calculer A2n+1 = (An ) A et ne pas oublier que fn-1 = fn+1 - fn .
I.C.3 Utiliser les états pour stocker l'information (fn [2], fn+1 [2]).

I.C.5 Montrer que fn+3
- fn = 0.

I.C.6 Utiliser les états pour stocker le reste modulo 3 de l'entier en cours de 
lecture.
I.D.2 Il suffit de garder les 3 dernières valeurs calculées de la suite.
I.D.3 Il suffit de garder les m dernières valeurs calculées de la suite.
I.D.4 Le tableau est vu comme une mémoire circulaire des m dernières valeurs.
Utiliser le modulo m pour calculer l'indice du tableau en fonction de l'indice
de la suite g.
I.D.5 Généraliser la forme de la matrice A de la question I.B.5 et exprimer gn 
à l'aide
d'une puissance de A.
II.A Trouver la place du nouveau noeud dans l'arbre puis suivre le chemin entre 
la
racine et ce nouveau noeud pour insérer la nouvelle valeur à la bonne place.
II.B À partir de la racine, échanger récursivement la valeur du noeud courant 
avec
celle de son plus petit fils si nécessaire.
II.D Montrer que h = log2 (n) où x représente la partie entière de x.

II.E Montrer que le nombre de percolations dues au nombre premier p est majoré
par ln n/ ln p.

II.F Tester la divisibilité de n par tous les entiers impairs plus petits que n.

I. Autour de la suite de Fibonacci
Dans tout ce corrigé, la notation x désigne la partie entière (inférieure)
de x alors que x désigne sa partie entière supérieure.
I.A.1 Pour multiplier deux nombres binaires, on peut utiliser la méthode que 
l'on
apprend à l'école primaire : on multiplie le premier nombre par chacun des 
chiffres
du second et on additionne au fur et à mesure les résultats partiels (en 
n'oubliant
pas de « décaler » le résultat d'une place à chaque fois). La différence est 
que la
multiplication d'un nombre par un bit se fait en temps constant : le résultat 
est égal
au nombre si le bit est 1, ou bien il est égal à 0 si le bit est 0.
Si on note b = bn-1 bn-2 . . . b1 b0 l'écriture en base 2 de b, on a
a×b=

n-1
P
i=0

bi × (a × 2i )

La multiplication par bi (bit) se fait en temps constant (ie on prend 0 ou bien
le second opérande). Le calcul de a × 2i peut être fait en temps proportionnel 
à n :
il suffit de décaler les n chiffres de a de i places vers la gauche. Suivant la 
manière
de stocker a (par exemple dans un tableau), l'opération peut demander un nombre
d'opérations proportionnel au nombre de chiffres du résultat (ie n + i < 2n). Le coût total de ces décalages est donc en O (n × n). Il ne reste plus qu'à prendre aussi en compte le coût des additions. On doit additionner au plus n fois un nombre binaire de taille au plus 2n (avec les décalages). Une addition de nombres de taille 2n étant en O(n), le coût des additions est aussi en O (n × n). Le produit de deux nombres entiers de n bits s'effectue en O n2 opérations élémentaires. Si l'on choisit une représentation interne astucieuse pour stocker les entiers de taille quelconque, il est possible d'obtenir a × 2i en temps constant. Cela ne change pas la complexité finale puisqu'une addition est toujours en O(n). I.A.2 Pour effectuer une multiplication d'entiers plus efficace, utilisons une méthode diviser pour régner. Soient a et b deux nombres de n bits et posons m = n/2. On note a = a1 2m + a2 et b = b1 2m + b2 avec a2 < 2m et b2 < 2m . Autrement dit, a2 (resp. b2 ) est constitué des m derniers chiffres de a (resp. b) tandis que a1 (resp. b1 ) est constitué des n - m premiers chiffres de a (resp. b). On peut remarquer que : ab = (a1 2m + a2 ) (b1 2m + b2 ) = a1 b1 22m + (a1 b2 + a2 b1 ) 2m + a2 b2 Posons X = a1 b 1 et Y = a2 b 2 Alors Z - X - Y = a1 b2 + a2 b1 et Z = (a1 + b1 ) (a2 + b2 ) ab = X22m + (Z - X - Y)2m + Y On voit ici qu'il est possible de calculer la multiplication de a et b décomposés en deux parties à l'aide de 3 multiplications (et 6 additions). Les additions se faisant en O(n), on sera gagnant si l'on applique le même procédé récursivement pour calculer les 3 multiplications nécessaires. En effet, si l'on note T (n) la complexité d'une multiplication de deux nombres de taille n par cette méthode, on aura : j n k + O (n) T (n) 6 3T 2 ce qui nous permet d'obtenir une complexité globale en O nlog2 3 . Sans utiliser ces égalités, on aurait intuitivement calculé X = a1 b 1 Y = a2 b 2 Z 1 = a1 b 2 Z 2 = a2 b 1 ab = X22m + (Z1 + Z2 )2m + Y puis soit 4 multiplications (et 3 additions), ce qui ne permet aucun gain avec la méthode diviser pour régner. En effet, en notant T la complexité de cette méthode de calcul, on a alors j n k T (n) 6 4T + O (n) 2 et donc une complexité en O n2 . En résumé, pour multiplier deux nombres a et b, l'algorithme proposé consiste donc à 1. scinder ces deux nombres en deux parties ; 2. calculer X, Y, Z (définis ci-dessus) en appliquant cette méthode récursivement pour calculer les trois produits ; 3. sommer X22m + (Z - X - Y)2m + Y pour obtenir le résultat. Cette méthode, appelée méthode de Karatsuba, a une complexité en O nlog2 3 soit environ O n1,585 . Il existe une généralisation de la méthode de Karatsuba, dite de ToomCook ou encore Toom-3. Cette méthode découpe chaque nombre à multiplier en plusieurs parties (Karatsuba découpant les nombres en 2 parties). Ainsi, en découpant en 3 parties, on obtient un algorithme dont la complexité est O nlog3 (5) ) soit environ O n1,465 (on remplace 9 multiplications par 5). Il faut cependant noter que le coût de gestion des additions et des appels récursifs est important et augmente vite avec le nombre de parties de la découpe des nombres. C'est pourquoi la méthode de Toom-Cook (et donc de Karatsuba) n'est utilisée que lorsque les nombres sont suffisamment grands pour que le gain en complexité soit suffisamment important. I.A.3 Pour tout n  N, on a a(2n) = a2 n et a(2n+1) = a × a2 n En notant b = bn-1 bn-2 . . . b1 b0 l'écriture en base 2 de b, l'algorithme d'exponentiation rapide pour calculer ab est le suivant :