Centrale Informatique MP-PC-PSI 2017

Thme de l'preuve Mars Exploration Rovers: mission d'exploration martienne
Principaux outils utiliss algorithmique, recherche de minimum, listes, SQL
Mots clefs numpy, calcul de distances, minimisation, algorithme gntique, algorithme du plus proche voisin, jointure, robot, Mars

Corrig

(c'est payant, sauf le dbut): - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrig

(tlcharger le PDF)

nonc complet

(tlcharger le PDF)

Rapport du jury

(tlcharger le PDF)

nonc obtenu par reconnaissance optique des caractres


JS- S*- SaA- haA j ?2m`2b *H+mHi`B+2b miQ`Bb2b kyRd AM7Q`KiB[m2 J`b 1tTHQ`iBQM _Qp2`b JBbbBQM /2tTHQ`iBQM K`iB2MM2 J`b 1tTHQ`iBQM _Qp2`b UJ1_V 2bi mM2 KBbbBQM /2 H La [mB +?2`+?2  im/B2` H2 `H2 DQm T` H2m /Mb H?BbiQB`2 /2 H THMi2 J`bX .2mt `Q#Qib ;QHQ;m2b- aTB`Bi 2i PTTQ`imMBiv U};m`2 RV- b2 bQMi TQbb bm` +2ii2 THMi2- bm` /2mt bBi2b QTTQbb- 2M DMpB2` kyy9X G2m` KBbbBQM 2bi /2 `2+?2`+?2` 2i /MHvb2` /Bz`2Mib ivT2b /2 `Q+?2b 2i /2 bQHb [mB T2mp2Mi +QMi2MB` /2b BM/B+2b bm` H T`b2M+2 /2mX AHb bQMi [mBTb /2 bBt `Qm2b 2i /mM2 bmbT2MbBQM bT+BH2K2Mi +QMm2 TQm` H2m` T2`K2ii`2 /2 b2 /TH+2` [m2HH2 [m2 bQBi H Mim`2 /m i2``BM `2M+QMi`X G2m` +?B2` /2b +?`;2b T`pQvBi mM2 /m`2 /2 pB2 /2 Ny DQm`b K`iB2Mb UH2 DQm` K`iB2M 2bi 2MpB`QM 9y KBMmi2b THmb HQM; [m2 H2 DQm` i2``2bi`2VX aTB`Bi +2bb /K2ii`2 H2 kk K`b kyRy- bQBi kkRy DQm`b K`iB2Mb T`b bQM ``Bp2 bm` H THMi2X .#mi kyRd- PTTQ`imMBiv 2bi iQmDQm`b 2M +iBpBi 2i BH T`+Qm`m THmb /2 99 FK bm` J`bX 6B;m`2 R om2 /`iBbi2 /mM `Q#Qi ;QHQ;m2 /2 H KBbbBQM J`b 1tTHQ`iBQM _Qp2`b ULafCSG *H@ i2+?f*Q`M2HHV *?[m2 `Q#Qi 2bi [mBT /2 THmbB2m`b BMbi`mK2Mib /MHvb2 U+K`- KB+`Qb+QT2- bT2+i`QKi`2bV 2i /mM #`b [mB T2`K2i /K2M2` H2b BMbi`mK2Mib m THmb T`b /2b `Q+?2b 2i bQHb /B;M2b /BMi`iX  T`iB` /2 T?QiQ;`T?B2b /2 H bm`7+2 /2 H THMi2- T`Bb2b  THmbB2m`b HQM;m2m`b /QM/2b T` /Bz`2Mib bi2HHBi2b 2i T` H2 `Q#Qi HmB@KK2- H2b b+B2MiB}[m2b /2 H La /}MBbb2Mi mM2 HBbi2 /2KTH+2K2Mib UTQBMib /BMi`i Qm SAV Q 2z2+im2` /2b MHvb2bX *2ii2 HBbi2 2bi i`MbKBb2 m `Q#Qi [mB /QBi b2 `2M/`2  +?[m2 2KTH+2K2Mi BM/B[m 2i v 2z2+im2` H2b MHvb2b T`pm2bX *?[m2 `Q#Qi 2bi +T#H2 /2z2+im2` mM +2`iBM MQK#`2 /2 ivT2b /MHvb2b ;QHQ;B[m2b +Q``2bTQM/Mi mt /Bz`2Mib BMbi`mK2Mib /QMi BH /BbTQb2X lM2 7QBb iQmb H2b TQBMib /BMi`ib pBbBib 2i H2b `bmHiib /2b MHvb2b kyRd@yj@kd ky,Rj,98 S;2 Rf3 i`MbKBb  H h2``2- H2 `Q#Qi `2QBi mM2 MQmp2HH2 HBbi2 /2 TQBMib /BMi`ib 2i /K``2 mM2 MQmp2HH2 2tTHQ`iBQMX *QKTi2@i2Mm /2b +QMi`BMi2b /2 i`MbKBbbBQM 2Mi`2 H h2``2 2i H2b `Q#Qib UHi2M+2- T`BQ/2b /QK#`2- 7B#H2 /#Bi2i+XV BH 2bi T`pm [m2 H2b `Q#Qib i`pBHH2Mi 2M miQMQKB2 TQm` THMB}2` H2 T`+Qm`b /2 +?[m2 2tTHQ`iBQMX BMbBmM2 7QBb H HBbi2 /2b TQBMib /BMi`i `2m2- H2 `Q#Qi MHvb2 H2 i2``BM }M /2 /i2+i2` /p2Mim2Hb Q#bi+H2b 2i /i2`KBM2 H2 K2BHH2m` +?2KBM HmB T2`K2iiMi /2 pBbBi2` H2Mb2K#H2 /2 +2b TQBMib 2M /T2MbMi H2 KQBMb /M2`;B2 TQbbB#H2X T`b bi`2 BMi`2bb  H2M`2;Bbi`2K2Mi /2b 2tTHQ`iBQMb- /2b TQBMib /BMi`ib +Q``2bTQM/Mib 2i /2b MHvb2b  v K2M2`- +2 bmD2i #Q`/2 i`QBb H;Q`Bi?K2b [mB T2mp2Mi i`2 miBHBbb T` H2 `Q#Qi TQm` /i2`KBM2` H2 K2BHH2m` T`+Qm`b HmB T2`K2iiMi /2 pBbBi2` +?[m2 TQBMi /BMi`i mM2 2i mM2 b2mH2 7QBbX SQm` +2H MQmb 7BbQMb [m2H[m2b ?vTQi?b2b bBKTHB}+i`B+2bX G xQM2 /2tTHQ`iBQM 2bi /TQm`pm2 /Q#bi+H2 , H2 `Q#Qi T2mi `2DQBM/`2 /B`2+i2K2Mi 2M HB;M2 /`QBi2 MBKTQ`i2 [m2H TQBMi /BMi`iX G2 bQH 2bi ?Q`BxQMiH 2i /2 Mim`2 +QMbiMi2 , HM2`;B2 miBHBb TQm` b2 /TH+2` 2Mi`2 /2mt TQBMib M2 /T2M/ [m2 /2 H2m` /BbiM+2- mi`2K2Mi /Bi H2 K2BHH2m` +?2KBM 2bi H2 THmb +Qm`iX G +Qm`#m`2 /2 H THMi2 2bi M;HB;2 +QKTi2 i2Mm /2 H /BK2MbBQM `/mBi2 /2 H xQM2 /2tTHQ`iBQM , MQmb i`pBHH2`QMb 2M ;QKi`B2 2m+HB/B2MM2 2i H2b TQBMib /BMi`ib b2`QMi `2T`b T` H2m`b +QQ`/QMM2b +`ibB2MM2b  HBMi`B2m` /2 H xQM2 /2tTHQ`iBQMX G2b b2mHb HM;;2b /2 T`Q;`KKiBQM miQ`Bbb /Mb +2ii2 T`2mp2 bQMi Svi?QM 2i aZGX hQmi2b H2b [m2biBQMb bQMi BM/T2M/Mi2bX LMKQBMb- BH 2bi TQbbB#H2 /2 7B`2 TT2H  /2b 7QM+iBQMb Qm T`Q+/m`2b +`2b /Mb /mi`2b [m2biBQMbX .Mb iQmi H2 bmD2i QM bmTTQb2 [m2 H2b #B#HBQi?[m2b Ki?- MmKTv 2i `M/QK QMi i BKTQ`i2b ;`+2 mt BMbi`m+iBQMb BKTQ`i Ki? BKTQ`i MmKTv b MT BKTQ`i `M/QK aB H2b +M/B/ib 7QMi TT2H  /2b 7QM+iBQMb /mi`2b #B#HBQi?[m2b BHb /QBp2Mi T`+Bb2` H2b BMbi`m+iBQMb /BKTQ`i@ iBQM +Q``2bTQM/Mi2bX *2 bmD2i miBHBb2 H bvMit2 /2b MMQiiBQMb TQm` T`+Bb2` H2 ivT2b /2b `;mK2Mib 2i /m `bmHii /2b 7QM+iBQMb  +`B`2X BMbB /27 K6QM+iBQMUM,BMi- t,7HQi- /,bi`V @= MTXM/``v, bB;MB}2 [m2 H 7QM+iBQM K6QM+iBQM T`2M/ i`QBb `;mK2Mib- H2 T`2KB2` 2bi mM 2MiB2`- H2 /2mtBK2 mM MQK#`2  pB`;mH2 ~QiiMi2 2i H2 i`QBbBK2 mM2 +?BM2 /2 +`+i`2b 2i [m2HH2 `2MpQB2 mM i#H2m MmKTvX lM2 HBbi2 /2 7QM+iBQMb miBH2b 2bi /QMM2  H }M /m bmD2iX A *`iBQM /mM2 2tTHQ`iBQM 2i ;2biBQM /2b TQBMib /BMi`i lM2 2tTHQ`iBQM 2bi mM 2Mb2K#H2 /2 TQBMib /BMi`ib  HBMi`B2m` /mM2 xQM2 ;Q;`T?B[m2 HBKBi2- mM2 b`B2 /MHvb2b iMi bbQ+B2  +?[m2 TQBMi /BMi`iX *?[m2 ivT2 /MHvb2 [m2 H2 `Q#Qi T2mi 2z2+im2` 2bi +Q/B} 2i `7`2M+ T` mM MQK#`2 2MiB2`X lM TQBMi /BMi`i 2bi `2T` T` /2mt 2MiB2`b- TQbBiB7b Qm MmHb- +Q``2bTQM/Mi  b2b +QQ`/QMM2b +`ibB2MM2b 2M KBHHBKi`2b  HBMi`B2m` /2 H xQM2 /2tTHQ`iBQMX G2Mb2K#H2 /2b TQBMib /BMi`ib /mM2 2tTHQ`iBQM [mB 2M +QMiB2Mi 2bi `2T`b2Mi T` mM Q#D2i /2 ivT2 MmKTvXM/``v-  HK2Mib 2MiB2`b-  k +QHQMM2b 2i HB;M2b- HHK2Mi /BM/B+2 B-y +Q``2bTQM/Mi  H#b+Bbb2 /m TQBMi /BMi`i 2i HHK2Mi /BM/B+2 B-R  bQM Q`/QMM2X y j98 ej8 R Ryde 9R8 k j3 38N j RkR 83k 6B;m`2 k 1t2KTH2 /2tTHQ`iBQM p2+ [mi`2 TQBMib /BMi`i AX :M`iBQM /mM2 2tTHQ`iBQM /2bbB AXXRV *?QBt /2 TQBMib m ?b`/ V }M /2 /BbTQb2` /2 /QMM2b TQm` i2bi2` H2b /Bz`2Mib H;Q`Bi?K2b /2 +H+mH /2 +?2KBM [mB b2`QMi /p2HQTTb THmb i`/- +`B`2 mM2 7QM+iBQM [mB +QMbi`mBi mM2 2tTHQ`iBQM m ?b`/X *2ii2 7QM+iBQM /2Mii2 /27 ;M`2`nSAUM,BMi- +Kt,BMiV @= MTXM/``v, kyRd@yj@kd ky,Rj,98 S;2 kf3 T`2M/ 2M T`Ki`2b H2 MQK#`2 /2 TQBMib /BMi`ib  ;M`2` 2i H H`;2m` /2 H xQM2 /2tTHQ`iBQM UbmTTQb2 +``2V 2i `2MpQB2 mM Q#D2i /2 ivT2 MmKTvXM/``v +QMi2MMi H2b +QQ`/QMM2b /2 TQBMib /2mt  /2mt /BbiBM+ib +?QBbBb m ?b`/ /Mb H xQM2 /2tTHQ`iBQM U};m`2 kVX #V Zm2HH2b +QMi`BMi2b /QBp2Mi p`B}2` H2b `;mK2Mib /2 H 7QM+iBQM ;M`2`nSA \ AXXkV *H+mH /2b /BbiM+2b PM /BbTQb2 /2 H 7QM+iBQM /2Mii2 /27 TQbBiBQMn`Q#QiUV @= imTH2, [mB `2MpQB2 mM +QmTH2 /QMMMi H2b +QQ`/QMM2b +im2HH2b /m `Q#Qi /Mb H2 bvbiK2 /2 +QQ`/QMM2b /2 H2tTHQ`iBQM  THMB}2`X BMbB HBMbi`m+iBQM t- v 4 TQbBiBQMn`Q#QiUV T2`K2i /2 `+mT`2` H2b +QQ`/QMM2b +Qm`Mi2b /m `Q#QiX }M /2 7+BHBi2` HTTHB+iBQM /2b /Bz`2Mib H;Q`Bi?K2b /2 `2+?2`+?2 /2 +?2KBM- QM bQm?Bi2 +QMbi`mB`2 mM i#H2m /2b /BbiM+2b 2Mi`2 H2b /Bz`2Mib TQBMib /BMi`i /mM2 2tTHQ`iBQM 2i 2Mi`2 +2mt@+B 2i H TQbBiBQM +Qm`Mi2 /m `Q#Qi m KQK2Mi /m +H+mHX +`B`2 mM2 7QM+iBQM /2Mii2 /27 +H+mH2`n/BbiM+2bUSA,MTXM/``vV @= MTXM/``v, [mB T`2M/ 2M T`Ki`2 mM i#H2m /2 TQBMib /BMi`i i2H [m2 /+`Bi T`+/2KK2Mi 2i `2MpQB2 mM i#H2m /2 MQK#`2b ~QiiMib- /2 /BK2MbBQM - i2H [m2 HHK2Mi /BM/B+2 B-D 7Qm`MBi H /BbiM+2 2Mi`2 H2b TQBMib /BMi`i 2i - HBM/B+2 M /bB;MMi H2 TQBMi /2 /T`i /m `Q#QiX AX" h`Bi2K2Mi /BK;2 PM /BbTQb2 /2 T?QiQ;`T?B2b /mM2 xQM2 /2tTHQ`iBQM 2z2+im2b  /Bz`2Mi2b HQM;m2m` /QM/2X *?[m2 T?QiQ@ ;`T?B2 i KBb2b  H+?2HH2 /2 H xQM2 /2tTHQ`iBQM TmBb biQ+F2 /Mb mM i#H2m MmKTv UMTXM/``vV  /2mt /BK2MbBQMbX G2b /BK2MbBQMb +Q``2bTQM/2Mi mt +QQ`/QMM2b ;Q;`T?B[m2b /m TQBMi T?QiQ;`T?B- +?[m2 HK2Mi 2bi mM 2MiB2`- +QKT`Bb 2Mi`2 y 2i k88- /QMMMi HBMi2MbBi /m TQBMi +QMbB/` bm` HBK;2X BMbB HHK2Mi /BM/B+2 t-v +QMiB2Mi mM 2MiB2`- +QKT`Bb 2Mi`2 y 2i k88- +Q``2bTQM/Mi  HBMi2MbBi bm` H T?QiQ;`T?B2 +QMbB/`2 /m TQBMi /2 +QQ`/QMM2b X  T`iB` /2 +2b T?QiQ;`T?B2b- H2b ;QHQ;m2b /i2`KBM2Mi H2b 2M/`QBib  MHvb2` 2M }Hi`Mi +2mt [mB QMi mM T`Q}H /KBbbBQM +`+i`BbiB[m2 /2 +2`iBM2b `Q+?2b BMi`2bbMi2bX AX"XRV MHvb2 /mM2 BK;2 G 7QM+iBQM 6R +B@/2bbQmb T`2M/ 2M T`Ki`2 mM2 T?QiQ;`T?B2 `2T`b2Mi2 +QKK2 /+`Bi THmb ?miX 1tTHB[m2` +2 [m2 7Bi +2ii2 7QM+iBQM 2i /+`B`2 bQM `bmHiiX R k j 9 8 e d /27 6RUT?QiQ,MTXM/``vV @= MTXM/``v, M 4 T?QiQXKBMUV # 4 T?QiQXKtUV ? 4 MTXx2`QbU# @ M Y R- MTXBMie9V 7Q` T BM T?QiQX7Hi, ?(T @ M) Y4 R `2im`M ? AX"XkV aH2+iBQM /2 TQBMib /BMi`ib +`B`2 mM2 7QM+iBQM /2Mii2 /27 bH2+iBQMM2`nSAUT?QiQ,MTXM/``v- BKBM,BMi- BKt,BMiV @= MTXM/``v, Q T?QiQ 2bi mM i#H2m `2T`b2MiMi mM2 T?QiQ;`T?B2X G2 `bmHii /2 H 7QM+iBQM bH2+iBQMM2`nSA 2bi mM i#H2m  /2mt /BK2MbBQMb- /2 bi`m+im`2 bBKBHB`2  +2HmB /+`Bi };m`2 k- +QMi2MMi H2b +QQ`/QMM2b /2b TQBMib /QMi HBMi2MbBi bm` H T?QiQ;`T?B2 2bi +QKT`Bb2 2Mi`2 BKBM 2i BKtX AX* "b2 /2 /QMM2b }M /bbm`2` bQM miQMQKB2 QT`iBQMM2HH2- H2 `Q#Qi /BbTQb2 HQ+H2K2Mi /2b BM7Q`KiBQMb M+2bbB`2b  bQM 7QM+iBQMM2K2Mi [mQiB/B2MX BMbB- BH 2M`2;Bbi`2 H /m`2 /miBHBbiBQM /2 b2b /Bz`2Mib BMbi`mK2Mib 2K#`[mbX AH +QMMBi ;H2K2Mi H2b /Bz`2Mib ivT2b /MHvb2b [mBH T2mi 2z2+im2` 2i- TQm` +?+mM /2 +2b ivT2b- H2b BMbi`mK2Mib  miBHBb2`X AH 2M`2;Bbi`2 H T`Q+?BM2 2tTHQ`iBQM- +2bi@@/B`2 H2b /Bz`2Mib TQBMib /BMi`ib [mBH /QBi pBbBi2` 2i TQm` +?+mM H Qm H2b MHvb2b [mBH /QBi 2z2+im2`X .mi`2 T`i- BH +QMb2`p2 H2b `bmHiib /MHvb2b 2z2+im2b HQ`b /2 b2b 2tTHQ`iBQMb Tbb2bX *2b `bmHiib M2 bQMi 2z+b [mT`b +QM}`KiBQM /2 H2m` #QMM2 i`MbKBbbBQM bm` h2``2X *2b /Bz`2Mi2b BM7Q`KiBQMb bQMi biQ+F2b /Mb mM2 #b2 /2 /QMM2b `2HiBQMM2HH2 /QMi H2 KQ/H2 T?vbB[m2 2bi b+?KiBb };m`2 jX kyRd@yj@kd ky,Rj,98 S;2 jf3 1sSGP SA LGu 1snLlJ BMi2;2` 1snLlJ BMi2;2` 1snLlJ BMi2;2` 1sn*>: `2H SAnLlJ BMi2;2` SAnLlJ BMi2;2` 1sn.1" `2H SAns BMi2;2` hunLlJ BMi2;2` 1sn6AL `2H SAnu BMi2;2` Ln.h `2H 1snGh `2H SAn__ `2H Ln.h_ `2H 1snGPL `2H SAn.1S `2H Ln_1a #HQ# ALah_ ALhuS huL ALnLlJ BMi2;2` hunLlJ BMi2;2` hunLlJ BMi2;2` ALn6*h `2H ALnLlJ BMi2;2` hun.1a p`+?`U3yV ALn.1_ `2H Ahn.l_ `2H ALnLPJ p`+?`U3yV 6B;m`2 j ai`m+im`2 T?vbB[m2 /2 H #b2 /2 /QMM2b /mM `Q#Qi *2ii2 #b2 +QKTQ`i2 H2b bBt i#H2b bmBpMi2b , H i#H2 1sSGP /2b 2tTHQ`iBQMb- p2+ H2b +QHQMM2b r 1snLlJ MmK`Q U2MiB2`V /2 H2tTHQ`iBQM U+H27 T`BKB`2V r 1sn*>: /i2 /2 i`MbKBbbBQM /2b TQBMib /BMi`ib /2 +2ii2 2tTHQ`iBQM r 1sn.1" /i2 /2 /#mi /2 H2tTHQ`iBQM ULlGG bB H2tTHQ`iBQM M2bi Tb 2M+Q`2 +QKK2M+2V r 1sn6AL /i2 /2 }M /2 H2tTHQ`iBQM ULlGG bB H2tTHQ`iBQM M2bi Tb 2M+Q`2 i2`KBM2V r 1snGh HiBim/2 U2M /2;`b /+BKmtV /m TQBMi /2 +QQ`/QMM2b /2 H xQM2 /2tTHQ`iBQM r 1snGPL HQM;Bim/2 U2M /2;`b /+BKmtV /m TQBMi /2 +QQ`/QMM2b /2 H xQM2 /2tTHQ`iBQM H i#H2 SA /2b TQBMib /BMi`ib- /2 +H27 T`BKB`2 U1snLlJ- SAnLlJV- p2+ H2b +QHQMM2b r 1snLlJ MmK`Q /2 H2tTHQ`iBQM  H[m2HH2 TT`iB2Mi H2 TQBMi /BMi`i r SAnLlJ MmK`Q /m TQBMi /BMi`i /Mb H2tTHQ`iBQM Um b2BM /mM2 2tTHQ`iBQM H2b SA bQMi MmK`Qib 2M b[m2M+2 2M +QKK2MMi  y- +2 MmK`Q M Tb /2 `TTQ`i p2+ HQ`/`2 /Mb H2[m2H H2b SA bQMi 2tTHQ`b T` H2 `Q#QiV r SAns H#b+Bbb2 /m TQBMi /BMi`i /Mb H xQM2 /2tTHQ`iBQM U2MiB2` TQbBiB7 2M KBHHBKi`2bV r SAnu HQ`/QMM2 /m TQBMi /BMi`i /Mb H xQM2 /2tTHQ`iBQM U2MiB2` TQbBiB7 2M KBHHBKi`2bV r SAn__ /i2 /``Bp2 /m `Q#Qi m TQBMi /BMi`i ULlGG bB +2 TQBMi M Tb 2M+Q`2 i pBbBiV r SAn.1S /i2  H[m2HH2 H2 `Q#Qi [mBii H2 TQBMi /BMi`i ULlGG bB +2 TQBMi M Tb 2M+Q`2 i 2tTHQ` Qm bB H pBbBi2 2bi 2M +Qm`bV H i#H2 ALah_ /2b BMbi`mK2Mib 2K#`[mb- p2+ H2b +QHQMM2b r ALnLlJ H2 MmK`Q U2MiB2`V /2 HBMbi`mK2Mi U+H27 T`BKB`2V r ALn6*h H /m`2 T2M/Mi H2[m2H HBMbi`mK2Mi /D i miBHBb /2TmBb H``Bp2 bm` H THMi2 UMQK#`2 /+BKH , 7`+iBQM /2 DQm` K`iB2MV r ALn.1_ H /i2 /2 H /2`MB`2 miBHBbiBQM /2 HBMbi`mK2Mi r ALnLPJ MQK /2 HBMbi`mK2Mi H i#H2 huL /2b ivT2b /MHvb2b  2z2+im2`- p2+ H2b +QHQMM2b r hunLlJ H2 MmK`Q /2 `7`2M+2 U2MiB2`V /m ivT2 /MHvb2 U+H27 T`BKB`2V r hun.1a H2 MQK /m ivT2 /MHvb2 H i#H2 ALhuS /2b BMbi`mK2Mib miBHBbb TQm` mM ivT2 /MHvb2- /2 +H27 T`BKB`2 UhunLlJ- ALnLlJV- p2+ H2b +QHQMM2b r hunLlJ H2 MmK`Q /2 `7`2M+2 U2MiB2`V /m ivT2 /MHvb2 r ALnLlJ H2 MmK`Q U2MiB2`V /2 HBMbi`mK2Mi r Ahn.l_ H /m`2 biM/`/ /miBHBbiBQM /2 HBMbi`mK2Mi /Mb +2 ivT2 /MHvb2 UMQK#`2 /+BKH , 7`+iBQM /2 DQm` K`iB2MV H i#H2 LGu BM/B[mMi TQm` +?[m2 TQBMi /BMi`i H2b ivT2b /MHvb2b  2z2+im2` Qm 2z2+im2b- /2 +H27 T`BKB`2 U1snLlJ- SAnLlJ- hunLlJV 2i p2+ H2b +QHQMM2b r 1snLlJ MmK`Q /2 H2tTHQ`iBQM  H[m2HH2 TT`iB2Mi H2 TQBMi /BMi`i r SAnLlJ MmK`Q /m TQBMi /BMi`i /Mb H2tTHQ`iBQM r hunLlJ ivT2 /2 HMHvb2 kyRd@yj@kd ky,Rj,98 S;2 9f3 r Ln.h /i2 /2 HMHvb2 ULlGG bB HMHvb2 M Tb i 2z2+im2V r Ln.h_ /i2 /2 i`MbKBbbBQM bm` h2``2 /2b `bmHiib /2 HMHvb2 ULlGG bB HMHvb2 M Tb i i`MbKBb2V r Ln_1a `bmHii /2 HMHvb2 U/QMM2 QT[m2 /QMi H bB;MB}+iBQM /T2M/ /m ivT2 /MHvb2V hQmi2b H2b /i2b bQMi biQ+F2b bQmb 7Q`K2 /mM MQK#`2 /+BKH +Q``2bTQM/Mi m MQK#`2 /2 DQm`b K`iB2Mb /2TmBb H``Bp2 /m `Q#Qi bm` H THMi2X AX*XRV +`B`2 mM2 `2[mi2 aZG [mB /QMM2 H2 MmK`Q /2 H2tTHQ`iBQM 2M +Qm`b- bBH v 2M mM2X AX*XkV +`B`2 mM2 `2[mi2 aZG [mB /QMM2- TQm` mM2 2tTHQ`iBQM /QMi QM +QMMBi H2 MmK`Q- H HBbi2 /2b TQBMib /BMi`ib /2 +2ii2 2tTHQ`iBQM p2+ H2m`b +QQ`/QMM2bX AX*XjV +`B`2 mM2 `2[mi2 aZG [mB /QMM2 H bm`7+2- 2M Ki`2b +``b- /2 +?[m2 xQM2 /D 2tTHQ`2 T` H2 `Q#QiX G xQM2 /2tTHQ`iBQM 2bi /}MB2 +QKK2 H2 THmb T2iBi `2+iM;H2 [mB 2M;HQ#2 H2Mb2K#H2 /2b TQBMib /BMi`ib /2 H2tTHQ`iBQM 2i /QMi H2b #Q`/b bQMi T`HHH2b mt t2b /2 `7`2M+2 Ut2b /2b #b+Bbb2 2i /2b Q`/QMM2bVX AX*X9V Zm2HH2 2bi H bm`7+2 KtBKH2 /mM2 xQM2 /2tTHQ`iBQM [m2 T2mi biQ+F2` +2ii2 #b2 /2 /QMM2b \ AX*X8V +`B`2 mM2 `2[mi2 aZG [mB /QMM2- TQm` H2tTHQ`iBQM 2M +Qm`b- H2 MQK#`2 /2 7QBb Q +?[m2 BMbi`mK2Mi /QBi i`2 miBHBb 2i b /m`2 /miBHBbiBQM i?Q`B[m2 U2M DQm`b K`iB2MbV TQm` H iQiHBi /2 H2tTHQ`iBQMX AA SHMB}+iBQM /mM2 2tTHQ`iBQM , T`2KB`2 TT`Q+?2 pMi /2 /K``2` mM2 MQmp2HH2 2tTHQ`iBQM- H2 `Q#Qi /QBi /i2`KBM2` mM +?2KBM [mB HmB T2`K2i /2 Tbb2` T` iQmb H2b TQBMib /BMi`ib mM2 2i mM2 b2mH2 7QBbX G2MD2m /2 HQT`iBQM 2bi /2 i`Qmp2` H2 +?2KBM H2 THmb +Qm`i TQbbB#H2 }M /2 HBKBi2` H /T2Mb2 /M2`;B2 2i /2 HBKBi2` Hmbm`2 /m `Q#QiX *?[m2 TQBMi /BMi`i b2` `2T` T` mM 2MiB2` TQbBiB7 Qm MmH +Q``2bTQM/Mi  bQM BM/B+2 /Mb H2 i#H2m /2b TQBMib /BMi`iX lM +?2KBM /2tTHQ`iBQM b2` `2T`b2Mi T` mM Q#D2i /2 ivT2 HBbi /QMMMi H2b BM/B+2b /2b TQBMib /BMi`i /Mb HQ`/`2 /2 H2m` T`+Qm`bX AAX Zm2H[m2b 7QM+iBQMb miBHBiB`2b AAXXRV GQM;m2m` /mM +?2KBM +`B`2 mM2 7QM+iBQM /2Mii2 /27 HQM;m2m`n+?2KBMU+?2KBM,HBbi- /,MTXM/``vV @= 7HQi, [mB T`2M/ 2M T`Ki`2 mM +?2KBM  T`+Qm`B` 2i H Ki`B+2 /2b /BbiM+2b 2Mi`2 TQBMib /BMi`i Ui2HH2 [m2 `2MpQv2 T` H 7QM+iBQM +H+mH2`n/BbiM+2bV 2i `2MpQB2 H /BbiM+2 [m2 /QBi 2z2+im2` H2 `Q#Qi TQm` bmBp`2 +2 +?2KBM 2M T`iMi /2 b TQbBiBQM +Qm`Mi2 U+Q``2bTQM/Mi  H /2`MB`2 HB;M2f+QHQMM2 /m i#H2m /V 2i 2M pBbBiMi iQmb H2b TQBMib /BMi`i /Mb HQ`/`2 BM/B[mX AAXXkV LQ`KHBbiBQM /mM +?2KBM +`B`2 mM2 7QM+iBQM /2Mii2 /27 MQ`KHBb2`n+?2KBMU+?2KBM,HBbi- M,BMiV @= HBbi, [mB T`2M/ 2M T`Ki`2 mM2 HBbi2 /2MiB2`b 2i `2MpQB2 mM2 HBbi2 +Q``2bTQM/Mi  mM +?2KBM pHB/2- +2bi@@/B`2 +QMi2MMi mM2 b2mH2 7QBb iQmb H2b 2MiB2`b 2Mi`2 y 2i M U2t+HmVX SQm` +2H +2ii2 7QM+iBQM +QKK2M+2 T` bmTT`BK2` H2b p2Mim2Hb /Qm#HQMb U2M M2 +QMb2`pMi [m2 H T`2KB`2 Q++m``2M+2V 2i H2b pH2m`b bmT`B2m`2b Qm ;H2b  MbMb KQ/B}2` HQ`/`2 `2HiB7 /2b HK2Mib +QMb2`pb- TmBb DQmi2  H }M H2b p2Mim2Hb HK2Mib KM[mMib 2M Q`/`2 +`QBbbMi /2 MmK`QbX AAX" 6Q`+2 #`mi2 SQm` `2+?2`+?2` H2 THmb +Qm`i +?2KBM- QM T2mi BK;BM2` /2 +QMbB/`2` iQmb H2b +?2KBMb TQbbB#H2b 2i /2 +H+mH2` H2m` HQM;m2m`X PM Q#iB2M/` BMbB  +QmT b` H2 +?2KBM H2 THmb +Qm`iX AAX"XRV .i2`KBM2` 2M 7QM+iBQM /2 - MQK#`2 /2 TQBMib  pBbBi2`- H2 MQK#`2 /2 +?2KBMb TQbbB#H2b TbbMi 2t+i2K2Mi mM2 7QBb T` +?+mM /2b TQBMibX AAX"XkV *2i H;Q`Bi?K2 2bi@BH miBHBb#H2 TQm` mM2 xQM2 /2tTHQ`iBQM +QMi2MMi ky TQBMib /BMi`ib \ CmbiB}2`X AAX* H;Q`Bi?K2 /m THmb T`Q+?2 pQBbBM lM2 B/2 bBKTH2 TQm` Q#i2MB` mM H;Q`Bi?K2 miBHBb#H2 2bi /2 +QMbi`mB`2 mM +?2KBM 2M +?QBbBbbMi bvbiKiB[m2@ K2Mi H2 TQBMi- MQM 2M+Q`2 pBbBi- H2 THmb T`Q+?2 /2 H TQbBiBQM +Qm`Mi2X AAX*XRV +`B`2 mM2 7QM+iBQM /2Mii2 /27 THmbnT`Q+?2npQBbBMU/,MTXM/``vV @= HBbi, [mB T`2M/ 2M T`Ki`2 H2 i#H2m /2b /BbiM+2b `bmHii /2 H 7QM+iBQM +H+mH2`n/BbiM+2b U[m2biBQM AXXkV 2i 7Qm`MBi mM +?2KBM /2tTHQ`iBQM 2M TTHB[mMi HH;Q`Bi?K2 /m THmb T`Q+?2 pQBbBMX kyRd@yj@kd ky,Rj,98 S;2 8f3 AAX*XkV Zm2HH2 2bi H +QKTH2tBi i2KTQ`2HH2 /2 HH;Q`Bi?K2 /m THmb T`Q+?2 pQBbBM 2M +QMbB/`Mi [m2 +2i H;Q`Bi?K2 2bi +QMbiBim /2b /2mt 7QM+iBQMb +H+mH2`n/BbiM+2b 2i THmbnT`Q+?2npQBbBM \ AAX*XjV 1M +QMbB/`Mi H2b i`QBb TQBMib /2 +QQ`/QMM2b - - 2i 2M +?QBbBbbMi mM TQBMi /2 /T`i /[mi TQm` H2 `Q#Qi- KQMi`2` [m2 HH;Q`Bi?K2 /m THmb T`Q+?2 pQBbBM M2 7Qm`MBi Tb M+2bbB`2K2Mi H2 THmb +Qm`i +?2KBMX .Mb H T`iB[m2- QM +QMbii2 [m2- /b [m2 H2 MQK#`2 /2 TQBMib /BMi`i /2pB2Mi BKTQ`iMi- HH;Q`Bi?K2 /m THmb T`Q+?2 pQBbBM 7Qm`MBi mM +?2KBM [mB T2mi i`2 8yW THmb HQM; [m2 H2 THmb +Qm`i +?2KBMX AAA .2mtBK2 TT`Q+?2 , H;Q`Bi?K2 ;MiB[m2 G2b H;Q`Bi?K2b ;MiB[m2b bBMbTB`2Mi /2 H i?Q`B2 /2 HpQHmiBQM 2M bBKmHMi HpQHmiBQM /mM2 TQTmHiBQMX AHb 7QMi BMi2`p2MB` +BM[ i`Bi2K2MibX RX AMBiBHBbiBQM AH b;Bi /2 +`2` mM2 TQTmHiBQM /Q`B;BM2 +QKTQb2 /2 BM/BpB/mb UB+B /2b +?2KBMb TQm` H2tTHQ`iBQM  THMB}2`VX :M`H2K2Mi H TQTmHiBQM /2 /T`i 2bi T`Q/mBi2 HiQB`2K2MiX kX pHmiBQM *2ii2 iT2 +QMbBbi2  ii`B#m2`  +?[m2 BM/BpB/m /2 H TQTmHiBQM +Qm`Mi2 mM2 MQi2 +Q``2bTQM/Mi  b +T+Bi  `TQM/`2 m T`Q#HK2 TQbX A+B H MQi2 b2` bBKTH2K2Mi H HQM;m2m` /m +?2KBMX jX aH2+iBQM lM2 7QBb iQmb H2b BM/BpB/mb pHmb- HH;Q`Bi?K2 M2 +QMb2`p2 [m2 H2b K2BHH2m`b BM/BpB/mbX SHmbB2m`b K@ i?Q/2b /2 bH2+iBQM bQMi TQbbB#H2b , +?QBt HiQB`2- +2mt [mB QMi Q#i2Mm H K2BHH2m`2 MQi2- HBKBMiBQM T` iQm`MQB- 2i+X 9X *`QBb2K2Mi G2b BM/BpB/mb bH2+iBQMMb bQMi +`QBbb /2mt  /2mt TQm` T`Q/mB`2 /2 MQmp2mt BM/BpB/mb 2i /QM+ mM2 MQmp2HH2 TQTmHiBQMX G 7QM+iBQM /2 +`QBb2K2Mi UQm `2T`Q/m+iBQMV /T2M/ /2 H Mim`2 /2b BM/BpB/mbX 8X JmiiBQM lM2 T`QTQ`iBQM /BM/BpB/mb 2bi +?QBbB2 U;M`H2K2Mi HiQB`2K2MiV TQm` bm#B` mM2 KmiiBQM- +2bi@@/B`2 mM2 i`Mb7Q`KiBQM HiQB`2X *2ii2 iT2 T2`K2i /pBi2`  HH;Q`Bi?K2 /2 `2bi2` #HQ[m bm` mM QTiBKmK HQ+HX 1M `TiMi H2b iT2b /2 bH2+iBQM- +`QBb2K2Mi 2i KmiiBQM- HH;Q`Bi?K2 7Bi BMbB pQHm2` H TQTmHiBQM- Dmb@ [m i`Qmp2` mM BM/BpB/m [mB `TQM/2 m T`Q#HK2 BMBiBHX *2T2M/Mi /Mb H2b +b T`iB[m2b /miBHBbiBQM /2b H;Q`Bi?K2b ;MiB[m2b- BH M2bi Tb TQbbB#H2 /2 bpQB` bBKTH2K2Mi bB H2 T`Q#HK2 2bi `bQHm UH2 THmb +Qm`i +?2@ KBM };m`2@i@BH /Mb K TQTmHiBQM \VX PM miBHBb2 /QM+ /2b +QM/BiBQMb /``i ?2m`BbiB[m2b #b2b bm` mM +`Bi`2 `#Bi`B`2X G2 #mi /2 +2ii2 T`iB2 2bi /2 +QMbi`mB`2 mM H;Q`Bi?K2 ;MiB[m2 TQm` `2+?2`+?2` mM K2BHH2m` +?2KBM /2tTHQ`iBQM [m2 +2HmB Q#i2Mm T` HH;Q`Bi?K2 /m THmb T`Q+?2 pQBbBMX AAAX AMBiBHBbiBQM 2i pHmiBQM lM2 TQTmHiBQM 2bi `2T`b2Mi2 T` mM2 HBbi2 /BM/BpB/mb- +?[m2 BM/BpB/m iMi `2T`b2Mi T` mM +QmTH2 UHQM@ ;m2m`- +?2KBMV /Mb H2[m2H +?2KBM /bB;M2 mM +?2KBM `2T`b2Mi +QKK2 T`+/2KK2Mi T` mM2 HBbi2 /2MiB2`b +Q``2bTQM/Mi mt BM/B+2b /2b TQBMib /BMi`i /Mb H2 i#H2m /2b /BbiM+2b T`Q/mBi T` H 7QM+iBQM +H+mH2`n/BbiM+2b c HQM;m2m` 2bi mM 2MiB2` +Q``2bTQM/Mi  H HQM;m2m` /m +?2KBM- 2M i2MMi +QKTi2 /2 H TQbBiBQM /2 /T`i /m `Q#QiX +`B`2 mM2 7QM+iBQM /2Mii2 /27 +`2`nTQTmHiBQMUK,BMi- /,MTXM/``vV @= HBbi, [mB +`2 mM2 TQTmHiBQM /2 BM/BpB/mb HiQB`2bX *2ii2 7QM+iBQM T`2M/ 2M T`Ki`2 H2 MQK#`2 /BM/BpB/mb  2M;2M/`2` 2i H2 i#H2m /2b /BbiM+2b 2Mi`2 TQBMib /BMi`i U2i H TQbBiBQM +Qm`Mi2 /m `Q#QiV i2H [m2 T`Q/mBi T` H 7QM+iBQM +H+mH2`n/BbiM+2bX 1HH2 `2MpQB2 mM2 HBbi2 /BM/BpB/mb- +2bi@@/B`2 /2 +QmTH2b UHQM;m2m`- +?2KBMVX AAAX" aH2+iBQM +`B`2 mM2 7QM+iBQM /2Mii2 /27 `/mB`2UT,HBbiV @= LQM2, [mB `/mBi mM2 TQTmHiBQM /2 KQBiB 2M M2 +QMb2`pMi [m2 H2b BM/BpB/mb +Q``2bTQM/Mi mt +?2KBMb H2b THmb +Qm`ibX PM `TT2HH2 [m2 T 2bi mM2 HBbi2 /2 +QmTH2b UHQM;m2m`- +?2KBMVX G 7QM+iBQM `/mB`2 M2 `2MpQB2 Tb /2 `bmHii KBb KQ/B}2 H HBbi2 Tbb2 2M T`Ki`2X kyRd@yj@kd ky,Rj,98 S;2 ef3 AAAX* JmiiBQM AAAX*XRV +`B`2 mM2 7QM+iBQM /2Mii2 /27 Kmi2`n+?2KBMU+,HBbiV @= LQM2, [mB T`2M/ 2M T`Ki`2 mM +?2KBM 2i H2 i`Mb7Q`K2 2M BMp2`bMi HiQB`2K2Mi /2mt /2 b2b HK2MibX AAAX*XkV +`B`2 mM2 7QM+iBQM /2Mii2 /27 Kmi2`nTQTmHiBQMUT,HBbi- T`Q#,7HQi- /,MTXM/``vV @= LQM2, [mB T`2M/ 2M T`Ki`2 mM2 TQTmHiBQM /QMi 2HH2 7Bi Kmi2` mM +2`iBM MQK#`2 /BM/BpB/mbX G2 T`Ki`2 T`Q# U+QKT`Bb 2Mi`2 y 2i RV /bB;M2 H T`Q / 2bi H Ki`B+2 /2b /BbiM+2b 2Mi`2 TQBMib /BMi`iX AAAX. *`QBb2K2Mi AAAX.XRV +`B`2 mM2 7QM+iBQM /2Mii2 /27 +`QBb2`U+R,HBbi- +k,HBbiV @= HBbi, [mB +`2 mM MQmp2m +?2KBM  T`iB` /2 /2mt +?2KBMb Tbbb 2M T`Ki`2X *2 MQmp2m +?2KBM b2` T`Q/mBi 2M T`2MMi H T`2KB`2 KQBiB /m T`2KB2` +?2KBM bmBpB /2 H /2mtBK2 KQBiB /m /2mtBK2 TmBb 2M MQ`KHBbMi H2 +?2KBM BMbB Q#i2MmX AAAX.XkV +`B`2 mM2 7QM+iBQM /2Mii2 /27 MQmp2HH2n;M`iBQMUT,HBbi- /,MTXM/``vV @= LQM2, [mB 7Bi ;`QbbB` mM2 TQTmHiBQM 2M +`QBbMi b2b K2K#`2b TQm` 2M /Qm#H2` H2z2+iB7X SQm` +2H- H 7QM+iBQM 7Bi b2 `2T`Q/mB`2 iQmb H2b +QmTH2b /BM/BpB/mb [mB b2 bmBp2Mi /Mb H TQTmHiBQM UT(B)- T(BYR)V 2i UT(K@R)- T(y)V /2 7QM  T`Q/mB`2 MQmp2mt BM/BpB/mb [mB bDQmi2Mi mt BM/BpB/mb /2 H TQTmHiBQM /2 /T`iX AAAX1 H;Q`Bi?K2 +QKTH2i AAAX1XRV +`B`2 mM2 7QM+iBQM /2Mii2 /27 H;Qn;MiB[m2USA,MTXM/``v- K,BMi- T`Q#,7HQi- ;,BMiV @= 7HQi- HBbi, [mB T`2M/ 2M T`Ki`2 mM i#H2m /2 TQBMib /BMi`ib U};m`2 kV- H iBHH2 K /2 H TQTmHiBQM- H T`Q /2 KmiiBQM T`Q# 2i H2 MQK#`2 /2 ;M`iBQMb ;X *2ii2 7QM+iBQM BKTHMi2 mM H;Q`Bi?K2 ;MiB[m2  HB/2 /2b /Bz`2Mi2b 7QM+iBQMb +`Bi2b Dmb[m T`b2Mi 2i `2MpQB2 H HQM;m2m` /m THmb +Qm`i +?2KBM /2tTHQ`iBQM 2i H2 +?2KBM HmB@KK2 Q#i2Mmb m #Qmi /2 ; ;M`iBQMbX AAAX1XkV 1bi@BH TQbbB#H2 p2+ HBKTHMiiBQM `HBb2- [mmM2 Bi`iBQM /2 HH;Q`Bi?K2 /;`/2 H2 `bmHii , H2 K2BHH2m` +?2KBM Q#i2Mm  H ;M`iBQM 2bi THmb HQM; [m2 +2HmB /2 H ;M`iBQM \ .Mb H{`KiBp2- +QKK2Mi KQ/B}2` H2 T`Q;`KK2 TQm` [m2 +2ii2 bBimiBQM M2 TmBbb2 THmb ``Bp2` \ AAAX1XjV Zm2HH2b mi`2b +QM/BiBQMb /``i T2mi@QM BK;BM2` \ i#HB` mM +QKT`iB7 T`b2MiMi H2b pMi;2b 2i BM+QMpMB2Mib /2 +?[m2 +QM/BiBQM /``i 2MpBb;2X PT`iBQMb 2i 7QM+iBQMb Svi?QM /BbTQMB#H2b 6QM+iBQMb `M;2UMV `2MpQB2 H b[m2M+2 /2b M T`2KB2`b 2MiB2`b U V HBbiU`M;2UMVV `2MpQB2 mM2 HBbi2 +QMi2MMi H2b M T`2KB2`b 2MiB2`b /Mb HQ`/`2 +`QBbbMi , HBbiU`M;2U8VV (y- R- k- j- 9) `M/QKX`M/`M;2U- #V `2MpQB2 mM 2MiB2` HiQB`2 +QKT`Bb 2Mi`2 2i #@R BM+Hmb U 2i # 2MiB2`bV `M/QKX`M/QKUV `2MpQB2 mM MQK#`2 ~QiiMi iB` HiQB`2K2Mi /Mb < < bmBpMi mM2 /Bbi`B#miBQM mMB7Q`K2 `M/QKXb?m77H2UmV T2`Kmi2 HiQB`2K2Mi H2b HK2Mib /2 H HBbi2 m UKQ/B}2 mV `M/QKXbKTH2Um- MV `2MpQB2 mM2 HBbi2 /2 M HK2Mib /BbiBM+ib /2 H HBbi2 m +?QBbBb HiQB`2K2Mi- bB M = H2MUmV- /+H2M+?2 H2t+2TiBQM oHm21``Q` Ki?Xb[`iUtV +H+mH2 H `+BM2 +``2 /m MQK#`2 Ki?X+2BHUtV `2MpQB2 H2 THmb T2iBi 2MiB2` bmT`B2m` Qm ;H  t kyRd@yj@kd ky,Rj,98 S;2 df3 Ki?X7HQQ`UtV `2MpQB2 H2 THmb ;`M/ 2MiB2` BM7`B2m` Qm ;H  t bQ`i2/UmV `2MpQB2 mM2 MQmp2HH2 HBbi2 +QMi2MMi H2b HK2Mib /2 H HBbi2 m i`Bb /Mb HQ`/`2 Mim`2H /2 b2b HK2Mib UbB H2b HK2Mib /2 m bQMi /2b HBbi2b Qm /2b imTH2b- HQ`/`2 miBHBb 2bi HQ`/`2 H2tB+Q;`T?B[m2V PT`iBQMb bm` H2b HBbi2b H2MUmV /QMM2 H2 MQK#`2 /HK2Mib /2 H HBbi2 m , H2MU(R- k- j)V j c H2MU((R-k)- (j-9))V k m Y p +QMbi`mBi mM2 HBbi2 +QMbiBim2 /2 H +QM+iMiBQM /2b HBbi2b m 2i p , (R- k) Y (j- 9- 8) (R- k- j- 9- 8) M m +QMbi`mBi mM2 HBbi2 +QMbiBim /2 H HBbi2 m +QM+iM2 M 7QBb p2+ 2HH2@KK2 , j (R- k) (R- k- R- k- R- k) 2 BM m 2i 2 MQi BM m /i2`KBM2Mi bB HQ#D2i 2 };m`2 /Mb H HBbi2 m- +2ii2 QT`iBQM mM2 +QKTH2tBi i2KTQ`2HH2 2M k BM (R- k- j) h`m2 c k MQi BM (R- k- j) 6Hb2 mXTT2M/U2V DQmi2 HHK2Mi 2  H }M /2 H HBbi2 m UbBKBHB`2  m 4 m Y (2)V /2H m(B) bmTT`BK2 /2 H HBbi2 m bQM HK2Mi /BM/B+2 B /2H m(B,D) bmTT`BK2 /2 H HBbi2 m iQmb b2b HK2Mib /QMi H2b BM/B+2b bQMi +QKT`Bb /Mb HBMi2`pHH2 < < mX`2KQp2U2V bmTT`BK2 /2 H HBbi2 m H2 T`2KB2` HK2Mi [mB TQm` pH2m` 2- /+H2M+?2 H2t+2TiBQM oHm21``Q` bB 2 M2 };m`2 Tb /Mb m- +2ii2 QT`iBQM mM2 +QKTH2tBi i2KTQ`2HH2 2M mXBMb2`iUB- 2V BMb`2 HHK2Mi 2  H TQbBiBQM /BM/B+2 B /Mb H HBbi2 m U2M /+HMi H2b HK2Mib bmBpMibV c bB B =4 H2MUmV- 2 2bi DQmi 2M }M /2 HBbi2 m(B)- m(D) 4 m(D)- m(B) T2`Kmi2 H2b HK2Mib /BM/B+2 B 2i D /Mb H HBbi2 m mXbQ`iUV i`B2 H HBbi2 m 2M TH+2- /Mb HQ`/`2 Mim`2H /2 b2b HK2Mib UbB H2b HK2Mib /2 m bQMi /2b HBbi2b Qm /2b imTH2b- HQ`/`2 miBHBb 2bi HQ`/`2 H2tB+Q;`T?B[m2V PT`iBQMb bm` H2b i#H2mt UMTXM/``vV MTX``vUmV +`2 mM MQmp2m i#H2m +QMi2MMi H2b HK2Mib /2 H HBbi2 mX G iBHH2 2i H2 ivT2 /2b HK2Mib /2 +2 i#H2m bQMi //mBib /m +QMi2Mm /2 m MTX2KTivUM- /ivT2V- MTX2KTivUUM- KV- /ivT2V +`2 `2bT2+iBp2K2Mi mM p2+i2m`  M HK2Mib Qm mM2 K@ i`B+2  M HB;M2b 2i K +QHQMM2b /QMi H2b HK2Mib- /2 pH2m`b BM/i2`KBM2b- bQMi /2 ivT2 /ivT2 [mB T2mi i`2 mM ivT2 biM/`/ U#QQH- BMi- 7HQi- wV Qm mM ivT2 bT+B}[m2 MmKTv UMTXBMiRe- MTX7HQijk- wVX aB H2 T`Ki`2b /ivT2 M2bi Tb T`+Bb- BH T`2M/ H pH2m` 7HQi T` /7mi MTXx2`QbUM- /ivT2V- MTXx2`QbUUM- KV- /ivT2V 7QM+iBQMM2 +QKK2 MTX2KTiv 2M BMBiBHBbMi +?[m2 H@ K2Mi  H pH2m` x`Q TQm` H2b ivT2b MmK`B[m2b Qm 6Hb2 TQm` H2b ivT2b #QQH2Mb XM/BK MQK#`2 /2 /BK2MbBQMb /m i#H2m UR TQm` mM p2+i2m`- k TQm` mM2 Ki`B+2- 2i+XV Xb?T2 imTH2 /QMMMi H iBHH2 /m i#H2m TQm` +?+mM2 /2 b2b /BK2MbBQMb H2MUV iBHH2 /m i#H2m /Mb b T`2KB`2 /BK2MbBQM UMQK#`2 /HK2Mib /mM p2+i2m`- MQK#`2 /2 HB;M2b /mM2 Ki`B+2- 2i+XV [mBpH2Mi  Xb?T2(y) XbBx2 MQK#`2 iQiH /HK2Mib /m i#H2m X7Hi Bi`i2m` bm` iQmb H2b HK2Mib /m i#H2m XKBMUV- XKtUV `2MpQB2 H pH2m` /m THmb T2iBi U`2bT2+iBp2K2Mi THmb ;`M/V HK2Mi /m i#H2m c +2b QT`iBQMb QMi mM2 +QKTH2tBi i2KTQ`2HH2 2M # BM /i2`KBM2 bB # 2bi mM HK2Mi /m i#H2m c bB # 2bi mM b+HB`2- p`B}2 bB # 2bi mM HK2Mi /2 c bB # 2bi mM p2+i2m` Qm mM2 HBbi2 2i mM2 Ki`B+2- /i2`KBM2 bB # 2bi mM2 HB;M2 /2 MTX+QM+i2Mi2UUR- kVV +QMbi`mBi mM MQmp2m i#H2m 2M +QM+iMMi /2mt i#H2mt c R 2i k /QBp2Mi pQB` H2 KK2 MQK#`2 /2 /BK2MbBQMb 2i H KK2 iBHH2  H2t+2TiBQM /2 H2m` iBHH2 /Mb H T`2KB`2 /BK2MbBQM U/2mt Ki`B+2b /QBp2Mi pQB` H2 KK2 MQK#`2 /2 +QHQMM2b TQm` TQmpQB` i`2 +QM+iM2bV r r r 6AL r r r kyRd@yj@kd ky,Rj,98 S;2 3f3

Extrait du corrig obtenu par reconnaissance optique des caractres


 Centrale Informatique PC 2017 -- Corrig Ce corrig est propos par Cyril Ravat (professeur en CPGE) ; il a t relu par Julien Dumont (professeur en CPGE) et Jean-Julien Fleck (professeur en CPGE). Ce sujet d'informatique a pour contexte la mission martienne Mars Exploration Rovers. Celle-ci conduit  une tude en trois parties des aspects robotiques de l'exploration, principalement le dplacement du systme sur une carte : calculs de distances parcourues et optimisation du chemin reliant tous les points suivant deux approches. De nombreuses questions font intervenir des tableaux numpy, donc l'utilisation des fonctions associes, alors que des listes de listes suffiraient la plupart du temps. Un catalogue de ces fonctions est fourni en fin de sujet, avec des explications claires et des exemples.  La premire partie est compose de trois sous-parties indpendantes et de difficults ingales : la premire permet de raliser deux fonctions lmentaires de gnration de carte et de calcul de distance ; la deuxime traite trs brivement de traitement d'image ; la troisime tudie le fonctionnement de la base de donnes des analyses  effectuer. On regrette la difficult importante de la premire question, qui a d dcourager nombre de candidats, du moins ceux qui ont correctement lu le sujet. Comparativement, les deux questions sur le traitement d'image sont d'une simplicit dconcertante. Enfin, on note que les requtes SQL demandent l'utilisation d'une syntaxe (IS NULL) conceptuellement complexe et certainement peu enseigne.  La deuxime partie aborde le problme trs classique dit  du voyageur de commerce  : il faut optimiser le passage du robot par tous les points d'une liste une seule et unique fois. On met en place ici quelques fonctions lmentaires puis on ralise l'algorithme glouton du plus proche voisin. L'ensemble est quilibr et suffisamment progressif en termes de difficult.  La dernire partie continue le travail prcdent en proposant pour le mme problme l'tude d'un autre type de solution, lui aussi classique : un algorithme gntique. Les questions sont bien dtailles et se suivent parfaitement ; y rpondre donne le plaisir de construire petit  petit un algorithme complexe et utilisable sur un cas concret. Ce sujet laisse au final deux impressions : celle d'un dbut mal matris et peu progressif, suivie dans les deux dernires parties d'un sujet classique permettant aux candidats de s'exprimer correctement. Il contient quelques questions de langage SQL mais n'aborde pas la partie ingnierie numrique du programme et ne demande aucune dmonstration thorique. Indications Partie I I.A.1.a Le plus simple est de continuer  gnrer des couples tant que le rsultat n'en contient pas n et d'enregistrer ces couples uniquement s'ils ne sont pas dj prsents dans le rsultat,  l'aide de l'oprateur not in. I.A.2 Ce genre de matrices est symtrique, on vite de doubler les calculs. La distance entre deux points se calcule  l'aide du thorme de Pythagore. I.B Il existe une fonction permettant d'obtenir les dimensions d'un tableau numpy. I.C.1 Pour tester si un champ est gal  NULL, ce n'est pas l'oprateur = mais l'oprateur IS qui est ncessaire : champ IS NULL ou champ IS NOT NULL. I.C.3 Un seul rsultat par exploration, pour plusieurs explorations, car il s'agit d'une requte d'agrgation. Les champs  calculer et la slection des explorations termines se font sur deux tables, une jointure est donc ncessaire. I.C.4 L'nonc est incomplet, il ne dit pas comment sont stocks les entiers dans la base. On peut imaginer qu'ils sont positifs et enregistrs sur 64 bits. I.C.5 Il faut raliser une jointure. Toutes les tables dcrites dans l'nonc ne sont pas utiles. Les champs EX_NUM et TY_NUM sont prsents et quivalents dans trois tables. Partie II II.A.2 Gnrer une liste de n valeurs boolennes permet de savoir rapidement si un point a dj t visit, sans utiliser la syntaxe in. II.C.1 Il s'agit d'une recherche classique de minimum, mais uniquement sur les points encore disponibles  la ie itration. Comme en II.A.2, une liste de valeurs boolennes peut aider. Faire attention  l'initialisation du critre minimal recherch. II.C.3 Les points donns sont aligns, faire un dessin au brouillon. Partie III III.A Pour gnrer une liste alatoire d'entiers, le plus simple est d'utiliser la fonction de permutation donne en fin d'nonc, sur la liste complte. III.B Pour trier les chemins, la mthode sort fonctionne immdiatement et il n'est pas utile de la coder  la main. Attention, il faut supprimer directement des lments de la liste p, il est interdit d'crire p = p[0 :len(p)//2] par exemple. III.C.1 La fonction random.sample permet d'obtenir plusieurs valeurs distinctes prises alatoirement au sein d'une liste. III.C.2 Penser  utiliser les fonctions muter_chemin et longueur_chemin ralises aux questions prcdentes. III.D.1 On peut concatner deux listes avec l'oprateur +. III.E.1 Attention  la syntaxe des fonctions prcdentes, notamment de celles qui ne renvoient pas de valeur. III.E.2 O est le meilleur chemin dans une gnration ? Est-il modifi ? III.E.3 Classiquement, une srie converge si sa valeur n'volue plus beaucoup. I. Cration d'une exploration et gestion des points d'intrt La syntaxe des dfinitions de fonctions choisie pour cet nonc est une possibilit offerte par Python pour rendre le code plus explicite (les  annotations ). Bien que peu d'lves l'aient dj vu, son emploi n'a pas d tre un problme. I.A.1.a Dans la fonction gnrer_PI, on peut choisir de manipuler une liste et d'utiliser la mthode append pour ajouter chaque point avant une transformation finale en tableau numpy, puisque celle-ci est impose par l'nonc : def gnrer_PI(n:int, cmax:int) -> np.ndarray: PI = [] while len(PI) < n: x = random.randrange(0,cmax+1) y = random.randrange(0,cmax+1) if [x,y] not in PI: PI.append([x,y]) return np.array(PI) La difficult de cette question rside en grande partie dans le besoin de ne garder que des points distincts. La rflexion pour obtenir une liste de n points alatoire est trs courte, mais celle pour liminer les doublons l'est beaucoup moins, notamment parce qu'un grand nombre de possibilits existent. Si l'on ajoute  cela le retour sous forme de tableau numpy exig, difficult supplmentaire pour beaucoup de candidats, alors que la liste de listes est suffisante, cette question est plutt difficile pour un dbut d'preuve. Il est aussi possible d'utiliser un tableau numpy depuis le dbut de l'algorithme, en l'initialisant  un tableau de n zros puis en le remplissant ligne par ligne, en vrifiant que chaque couple tir au sort n'est pas dj prsent : def gnrer_PI(n:int, cmax:int) -> np.ndarray: PI = np.zeros((n,2),int) # n lignes, 2 colonnes i = 0 while i < n: x = random.randrange(0,cmax+1) y = random.randrange(0,cmax+1) if [x,y] not in PI[0:i]: PI[i] = [x,y]; i = i+1 return PI Malheureusement, malgr ce qu'indique l'annexe de l'nonc, la construction en [x,y] in PI[0:i] ne donne pas le rsultat prvu avec un tableau numpy : >>> PI = np.array([[1,2],[3,4]]) >>> [1,2] in PI # Normal True >>> [1,5] in PI # Pas normal ! True ce qui n'est pas vraiment le rsultat escompt...  n'en pas douter, la fonction propose plus haut devrait tre accepte par les correcteurs, mais ce code ne fonctionne pas en pratique. Une des possibilits pour rsoudre ce problme, trs au-del de ce que l'on peut attendre d'un candidat, est any(np.equal([x,y],PI[0 :i]).all(1)) qui rpond correctement sur notre exemple : >>> any(np.equal([1,2],PI).all(1)) True >>> any(np.equal([1,5],PI).all(1)) False I.A.1.b Les deux nombres doivent tre positifs et aussi permettre d'obtenir n points distincts sur les cmax+1, c'est--dire n 6 (cmax+1)2 Les coordonnes ainsi que cmax tant notes en millimtres, il est peu probable que n s'approche de cette valeur limite. On peut nanmoins noter dans ce cas que l'algorithme donn  la question prcdente devient trs inefficace. Il convient alors de le remplacer par un algorithme procdant par limination d'un nombre complmentaire de points, choisis alatoirement. I.A.2 La fonction demande doit calculer pour chaque couple de points (i,j) la distance,  l'aide du thorme de Pythagore. Le rsultat est donc symtrique et il faut recopier chaque valeur du triangle infrieur gauche vers le triangle suprieur droit. On n'oublie pas d'ajouter la position actuelle en fin de ligne et de colonne. def calculer_distances(PI:np.ndarray) -> np.ndarray: n = len(PI) pos = position_robot() distances = np.zeros((n+1,n+1)) for i in range(n): for j in range(i): distances[i,j] = math.sqrt((PI[i,0]-PI[j,0])**2 \ + (PI[i,1]-PI[j,1])**2) distances[j,i] = distances[i,j] distances[i,n] = math.sqrt((PI[i,0]-pos[0])**2 \ + (PI[i,1]-pos[1])**2) distances[n,i] = distances[i,n] return distances On peut viter une des racines en ajoutant la position actuelle directement  la liste des points d'intrt avant calcul, mais il faut pour cela tre un peu familier de la fonction np.concatenate, qui ncessite des listes ou des tableaux numpy en argument. Les crochets ici sont essentiels, ce qui n'est pas du tout vident... def calculer_distances(PI:np.ndarray) -> np.ndarray: points = np.concatenate((PI,[position_robot()])) n = len(points) distances = np.zeros((n,n)) for i in range(n): for j in range(i): distances[i,j] = math.sqrt( \ (points[i,0]-points[j,0])**2 \ + (points[i,1]-points[j,1])**2) distances[j,i] = distances[i,j] return distances