Centrale Informatique MP-PC-PSI 2017

Thème de l'épreuve Mars Exploration Rovers: mission d'exploration martienne
Principaux outils utilisés algorithmique, recherche de minimum, listes, SQL
Mots clefs numpy, calcul de distances, minimisation, algorithme génétique, algorithme du plus proche voisin, jointure, robot, Mars

Corrigé

(c'est payant) : - - - - - - - - - - - - - - - - - - - - - - - - - - -

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


JS- S*- SaA- haA
j ?2m`2b

*H+mHi`B+2b miQ`Bbû2b

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 TQbûb bm` +2ii2
THMi2- bm` /2mt bBi2b QTTQbûb- 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 
û[mBTûb /2 bBt `Qm2b 2i /mM2
bmbT2MbBQM bTû+BH2K2Mi +QMÏm2 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
``Bpû2 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 
pBbBiûb 2i H2b `ûbmHiib /2b MHvb2b

kyRd@yj@kd ky,Rj,98

S;2 Rf3

i`MbKBb ¨ H h2``2- H2 `Q#Qi `2ÏQBi 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 `2Ïm2- 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 miBHBbûb 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 , HûM2`;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 ;ûQKûi`B2 2m+HB/B2MM2 2i H2b TQBMib /BMiû`ib b2`QMi `2Tû`ûb T` 
H2m`b +QQ`/QMMû2b +`iûbB2MM2b
¨ HBMiû`B2m` /2 H xQM2 /2tTHQ`iBQMX
G2b b2mHb HM;;2b /2 T`Q;`KKiBQM miQ`Bbûb /Mb +2ii2 ûT`2mp2 bQMi Svi?QM 2i aZGX 
hQmi2b H2b [m2biBQMb
bQMi BM/ûT2M/Mi2bX LûMKQBMb- 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`iû2b ;`+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 /QMMû2 ¨ 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 HBKBiû2- mM2 bû`B2
/MHvb2b ûiMi bbQ+Bû2 ¨ +?[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`/QMMû2b +`iûbB2MM2b 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- ¨ ûHûK2Mib
2MiB2`b- ¨ k +QHQMM2b 2i  HB;M2b- HûHûK2Mi /BM/B+2 B-y +Q``2bTQM/Mi ¨ H#b+Bbb2 
/m TQBMi /BMiû`i  2i HûHûK2Mi
/BM/B+2 B-R ¨ bQM Q`/QMMû2X

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 /QMMû2b TQm` i2bi2` H2b /Bzû`2Mib H;Q`Bi?K2b /2 +H+mH /2 
+?2KBM [mB b2`QMi /ûp2HQTTûb
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 UbmTTQbû2
+``û2V 2i `2MpQB2 mM Q#D2i /2 ivT2 MmKTvXM/``v +QMi2MMi H2b +QQ`/QMMû2b /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`/QMMû2b +im2HH2b /m `Q#Qi /Mb H2 bvbiK2 /2 
+QQ`/QMMû2b /2 H2tTHQ`iBQM
¨ THMB}2`X BMbB HBMbi`m+iBQM t- v 4 TQbBiBQMn`Q#QiUV T2`K2i /2 `û+mTû`2` H2b 
+QQ`/QMMû2b +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 HûHûK2Mi /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+imû2b ¨ /Bzû`2Mi2b 
HQM;m2m` /QM/2X *?[m2 T?QiQ@
;`T?B2  ûiû KBb2b ¨ Hû+?2HH2 /2 H xQM2 /2tTHQ`iBQM TmBb biQ+Fû2 /Mb mM i#H2m 
MmKTv UMTXM/``vV ¨
/2mt /BK2MbBQMbX G2b /BK2MbBQMb +Q``2bTQM/2Mi mt +QQ`/QMMû2b ;ûQ;`T?B[m2b /m 
TQBMi T?QiQ;`T?Bû- +?[m2
ûHûK2Mi 2bi mM 2MiB2`- +QKT`Bb 2Mi`2 y 2i k88- /QMMMi HBMi2MbBiû /m TQBMi 
+QMbB/û`û bm` HBK;2X BMbB HûHûK2Mi
/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`/QMMû2b   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`ûb2Miû2 +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

aûH2+iBQM /2 TQBMib /BMiû`ib

ú+`B`2 mM2 7QM+iBQM /2Mii2
/27 böH2+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 
böH2+iBQMM2`nSA 2bi mM
i#H2m ¨ /2mt /BK2MbBQMb- /2 bi`m+im`2 bBKBHB`2 ¨ +2HmB /û+`Bi };m`2 k- +QMi2MMi 
H2b +QQ`/QMMû2b /2b TQBMib
/QMi HBMi2MbBiû bm` H T?QiQ;`T?B2 2bi +QKT`Bb2 2Mi`2 BKBM 2i BKtX
AX* 
"b2 /2 /QMMû2b
}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#`[mûbX 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+imû2b
HQ`b /2 b2b 2tTHQ`iBQMb Tbbû2bX *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+Fû2b /Mb mM2 #b2 /2 /QMMû2b `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 /QMMû2b /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`KBMû2V
r 1snGh HiBim/2 U2M /2;`ûb /û+BKmtV /m TQBMi /2 +QQ`/QMMû2b   /2 H xQM2 
/2tTHQ`iBQM
r 1snGPL HQM;Bim/2 U2M /2;`ûb /û+BKmtV /m TQBMi /2 +QQ`/QMMû2b   /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û`Qiûb 2M
bû[m2M+2 2M +QKK2MÏMi ¨ 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`/QMMû2 /m TQBMi /BMiû`i /Mb H xQM2 /2tTHQ`iBQM U2MiB2` TQbBiB7 2M 
KBHHBKi`2bV
r SAn__ /i2 /``Bpû2 /m `Q#Qi m TQBMi /BMiû`i ULlGG bB +2 TQBMi M Tb 2M+Q`2 ûiû 
pBbBiûV
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#`[mûb- 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``Bpû2 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 miBHBbûb 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+imû2b- /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+imû2V
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/QMMû2 QT[m2 /QMi H bB;MB}+iBQM /ûT2M/ /m ivT2 
/MHvb2V
hQmi2b H2b /i2b bQMi biQ+Fû2b bQmb 7Q`K2 /mM MQK#`2 /û+BKH +Q``2bTQM/Mi m 
MQK#`2 /2 DQm`b K`iB2Mb
/2TmBb H``Bpû2 /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`/QMMû2bX
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`/QMMû2bVX
AX*X9V Zm2HH2 2bi H bm`7+2 KtBKH2 /mM2 xQM2 /2tTHQ`iBQM [m2 T2mi biQ+F2` +2ii2 
#b2 /2 /QMMû2b \
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
`2MpQvû2 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[mûX
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 ûHûK2Mib +QMb2`pûb- TmBb 
DQmi2 ¨ H }M H2b ûp2Mim2Hb ûHûK2Mib 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 bvbiûKiB[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`/QMMû2b   -   -   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 ;ûMûiB[m2
G2b H;Q`Bi?K2b ;ûMûiB[m2b bBMbTB`2Mi /2 H i?ûQ`B2 /2 HûpQHmiBQM 2M bBKmHMi 
HûpQHmiBQM /mM2 TQTmHiBQMX AHb
7QMi BMi2`p2MB` +BM[ i`Bi2K2MibX
RX AMBiBHBbiBQM
AH b;Bi /2 +`û2` mM2 TQTmHiBQM /Q`B;BM2 +QKTQbû2 /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 HûiQB`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 TQbûX A+B H MQi2 b2` bBKTH2K2Mi H HQM;m2m` /m 
+?2KBMX
jX aûH2+iBQM
lM2 7QBb iQmb H2b BM/BpB/mb ûpHmûb- HH;Q`Bi?K2 M2 +QMb2`p2 [m2 H2b  K2BHH2m`b  
BM/BpB/mbX SHmbB2m`b Kû@
i?Q/2b /2 bûH2+iBQM bQMi TQbbB#H2b , +?QBt HûiQB`2- +2mt [mB QMi Q#i2Mm H 
K2BHH2m`2 MQi2- ûHBKBMiBQM T`
iQm`MQB- 2i+X
9X *`QBb2K2Mi
G2b BM/BpB/mb bûH2+iBQMMûb bQMi +`QBbûb /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 HûiQB`2K2MiV TQm` bm#B` mM2 
KmiiBQM- +2bi@¨@/B`2
mM2 i`Mb7Q`KiBQM HûiQB`2X *2ii2 ûiT2 T2`K2i /ûpBi2` ¨ HH;Q`Bi?K2 /2 `2bi2` 
#HQ[mû bm` mM QTiBKmK
HQ+HX
1M `ûTûiMi H2b ûiT2b /2 bûH2+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 ;ûMûiB[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 #bû2b bm` mM +`Bi`2
`#Bi`B`2X
G2 #mi /2 +2ii2 T`iB2 2bi /2 +QMbi`mB`2 mM H;Q`Bi?K2 ;ûMûiB[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`ûb2Miû2 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 HûiQB`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"  aûH2+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 Tbbû2 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 HûiQB`2K2Mi /2mt /2 
b2b ûHûK2MibX
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 Tbbûb 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 7ÏQM ¨ 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;öMöiB[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 ;ûMûiB[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 `ûHBbû2- [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+QMpûMB2Mib /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` HûiQB`2 +QKT`Bb 2Mi`2  2i #@R BM+Hmb U 2i 
# 2MiB2`bV
 `M/QKX`M/QKUV `2MpQB2 mM MQK#`2 ~QiiMi iB`û HûiQB`2K2Mi /Mb < < bmBpMi mM2 /Bbi`B#miBQM mMB7Q`K2 `M/QKXb?m77H2UmV T2`Kmi2 HûiQB`2K2Mi H2b ûHûK2Mib /2 H HBbi2 m UKQ/B}2 mV `M/QKXbKTH2Um- MV `2MpQB2 mM2 HBbi2 /2 M ûHûK2Mib /BbiBM+ib /2 H HBbi2 m +?QBbBb HûiQB`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 ûHûK2Mib /2 H HBbi2 m i`Bûb /Mb HQ`/`2  Mim`2H  /2 b2b ûHûK2Mib UbB H2b ûHûK2Mib /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 /ûHûK2Mib /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 +QMbiBimû2 /2 H +QM+iûMiBQM /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+iûMû2 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 HûHûK2Mi 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 ûHûK2Mi /BM/B+2 B /2H m(B,D) bmTT`BK2 /2 H HBbi2 m iQmb b2b ûHûK2Mib /QMi H2b BM/B+2b bQMi +QKT`Bb /Mb HBMi2`pHH2 < < mX`2KQp2U2V bmTT`BK2 /2 H HBbi2 m H2 T`2KB2` ûHûK2Mi [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 HûHûK2Mi 2 ¨ H TQbBiBQM /BM/B+2 B /Mb H HBbi2 m U2M /û+HMi H2b ûHûK2Mib 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 ûHûK2Mib /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 ûHûK2Mib UbB H2b ûHûK2Mib /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 ûHûK2Mib /2 H HBbi2 mX G iBHH2 2i H2 ivT2 /2b ûHûK2Mib /2 +2 i#H2m bQMi /û/mBib /m +QMi2Mm /2 m MTX2KTivUM- /ivT2V- MTX2KTivUUM- KV- /ivT2V +`û2 `2bT2+iBp2K2Mi mM p2+i2m` ¨ M ûHûK2Mib Qm mM2 K@ i`B+2 ¨ M HB;M2b 2i K +QHQMM2b /QMi H2b ûHûK2Mib- /2 pH2m`b BM/ûi2`KBMû2b- 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 #QQHû2Mb 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 /ûHûK2Mib /mM p2+i2m`- MQK#`2 /2 HB;M2b /mM2 Ki`B+2- 2i+XV û[mBpH2Mi ¨ Xb?T2(y) XbBx2 MQK#`2 iQiH /ûHûK2Mib /m i#H2m X7Hi Biû`i2m` bm` iQmb H2b ûHûK2Mib /m i#H2m XKBMUV- XKtUV `2MpQB2 H pH2m` /m THmb T2iBi U`2bT2+iBp2K2Mi THmb ;`M/V ûHûK2Mi /m i#H2m  c +2b QTû`iBQMb QMi mM2 +QKTH2tBiû i2KTQ`2HH2 2M # BM  /ûi2`KBM2 bB # 2bi mM ûHûK2Mi /m i#H2m  c bB # 2bi mM b+HB`2- pû`B}2 bB # 2bi mM ûHûK2Mi /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+iûMMi /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+iûMû2bV r r r 6AL r r r kyRd@yj@kd ky,Rj,98 S;2 3f3

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


© Éditions H&K

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 déplacement du système 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 associées, 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 première partie est composée de trois sous-parties indépendantes et de 
difficultés inégales : la première permet de réaliser deux fonctions 
élémentaires de
génération de carte et de calcul de distance ; la deuxième traite très 
brièvement de traitement d'image ; la troisième étudie le fonctionnement de la 
base
de données des analyses à effectuer. On regrette la difficulté importante de la
première question, qui a dû décourager 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é déconcertante. Enfin, on note que les
requêtes SQL demandent l'utilisation d'une syntaxe (IS NULL) conceptuellement 
complexe et certainement peu enseignée.
· La deuxième partie aborde le problème très 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 élémentaires 
puis
on réalise l'algorithme glouton du plus proche voisin. L'ensemble est équilibré
et suffisamment progressif en termes de difficulté.
· La dernière partie continue le travail précédent en proposant pour le même
problème l'étude d'un autre type de solution, lui aussi classique : un 
algorithme
génétique. Les questions sont bien détaillées et se suivent parfaitement ; y 
répondre 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 début mal maîtrisé et peu
progressif, suivie dans les deux dernières 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 ingénierie numérique du programme et ne demande
aucune démonstration théorique.

© Éditions H&K

Indications
Partie I
I.A.1.a Le plus simple est de continuer à générer des couples tant que le 
résultat n'en
contient pas n et d'enregistrer ces couples uniquement s'ils ne sont pas déjà
présents dans le résultat, à l'aide de l'opérateur not in.
I.A.2 Ce genre de matrices est symétrique, on évite de doubler les calculs. La 
distance entre deux points se calcule à l'aide du théorème 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'opérateur = mais
l'opérateur IS qui est nécessaire : champ IS NULL ou champ IS NOT NULL.
I.C.3 Un seul résultat par exploration, pour plusieurs explorations, car il 
s'agit
d'une requête d'agrégation. Les champs à calculer et la sélection des 
explorations terminées se font sur deux tables, une jointure est donc 
nécessaire.
I.C.4 L'énoncé est incomplet, il ne dit pas comment sont stockés les entiers 
dans
la base. On peut imaginer qu'ils sont positifs et enregistrés sur 64 bits.
I.C.5 Il faut réaliser une jointure. Toutes les tables décrites dans l'énoncé 
ne sont
pas utiles. Les champs EX_NUM et TY_NUM sont présents et équivalents dans
trois tables.
Partie II
II.A.2 Générer une liste de n valeurs booléennes permet de savoir rapidement si 
un
point a déjà é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 itération. Comme en II.A.2, une liste de
valeurs booléennes peut aider. Faire attention à l'initialisation du critère 
minimal recherché.
II.C.3 Les points donnés sont alignés, faire un dessin au brouillon.
Partie III
III.A Pour générer une liste aléatoire d'entiers, le plus simple est d'utiliser 
la fonction de permutation donnée en fin d'énoncé, sur la liste complète.
III.B Pour trier les chemins, la méthode sort fonctionne immédiatement et il 
n'est
pas utile de la coder à la main. Attention, il faut supprimer directement
des éléments 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 aléatoirement au sein d'une liste.
III.C.2 Penser à utiliser les fonctions muter_chemin et longueur_chemin 
réalisées
aux questions précédentes.
III.D.1 On peut concaténer deux listes avec l'opérateur +.
III.E.1 Attention à la syntaxe des fonctions précédentes, notamment de celles 
qui ne
renvoient pas de valeur.
III.E.2 Où est le meilleur chemin dans une génération ? Est-il modifié ?
III.E.3 Classiquement, une série converge si sa valeur n'évolue plus beaucoup.

© Éditions H&K

I. Création d'une exploration et
gestion des points d'intérêt
La syntaxe des définitions de fonctions choisie pour cet énoncé est une 
possibilité offerte par Python pour rendre le code plus explicite (les « 
annotations »).
Bien que peu d'élèves l'aient déjà vu, son emploi n'a pas dû être un problème.
I.A.1.a Dans la fonction générer_PI, on peut choisir de manipuler une liste et
d'utiliser la méthode append pour ajouter chaque point avant une transformation
finale en tableau numpy, puisque celle-ci est imposée par l'énoncé :
def générer_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 réside en grande partie dans le besoin de ne garder que des points distincts. La réflexion pour obtenir une liste de n points aléatoire est très courte, mais celle pour éliminer les doublons l'est beaucoup moins, notamment parce qu'un grand nombre de possibilités existent. Si l'on ajoute à cela le retour sous forme de tableau numpy exigé, difficulté supplémentaire pour beaucoup de candidats, alors que la liste de listes est suffisante, cette question est plutôt difficile pour un début d'épreuve. Il est aussi possible d'utiliser un tableau numpy depuis le début de l'algorithme, en l'initialisant à un tableau de n zéros puis en le remplissant ligne par ligne, en vérifiant que chaque couple tiré au sort n'est pas déjà présent : def générer_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 résultat prévu 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 résultat escompté... À n'en pas douter, la fonction
proposée plus haut devrait être acceptée par les correcteurs, mais ce code ne
fonctionne pas en pratique. Une des possibilités pour résoudre ce problème,
très au-delà de ce que l'on peut attendre d'un candidat, est
any(np.equal([x,y],PI[0 :i]).all(1))

© Éditions H&K

qui répond 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 coordonnées ainsi que cmax étant notées en millimètres, il est peu probable 
que n s'approche de cette valeur limite. On peut néanmoins noter dans
ce cas que l'algorithme donné à la question précédente devient très inefficace.
Il convient alors de le remplacer par un algorithme procédant par élimination
d'un nombre complémentaire de points, choisis aléatoirement.
I.A.2 La fonction demandée doit calculer pour chaque couple de points (i,j) la
distance, à l'aide du théorème de Pythagore. Le résultat est donc symétrique et 
il
faut recopier chaque valeur du triangle inférieur gauche vers le triangle 
supérieur
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'intérêt avant calcul, mais il faut pour cela être un
peu familier de la fonction np.concatenate, qui nécessite 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