| 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 |
...: &&
@>...Ë@ @@ 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 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 :