ECOLE POLYTECHNIQUE - ECOLES NORMALES SUPERIEURES
CONCOURS D'ADMISSION 2020
!
MARDI 21 AVRIL 2020 - 14h00 18h00
FILIERE MP (Spécialité Informatique)
Epreuve n° 4
INFORMATIQUE A
(XULCR)
Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Cette composition ne concerne qu'une partie des candidats de la filière MP,
les autres candidats effectuant simultanément la composition de Physique et
Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.!
0
0
1
···
0
-1
×
{0, 1, . . . , × - 1}
·
( + 1)
0
< -1 · ( + ) 0 < ( - 1) × 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 0 >0
{0, 1, . . . , - 1}
{0, 1, . . . , - 1}
0
-1
0
-1
( , )
( , )
A
A
0 , · · · , r-1
A
O(f (0 , · · · , r-1 ))
0 , · · · , r-1
C > 0
0 , · · · , r-1
C f (0 , · · · , r-1 )
0
< = x 0 x Pr(x = ) = 1 . x 0 < < 0 < x = Pr(x = ) = 1 < 0 < {0, 1, . . . , - 1} = = = = = {0, 2, 5, 6} {1} 5 1 {3, 4} 3 {0, 1, . . . , - 1} 0 < = = {0, 2, 5, 6} {1} 0, 2, 4, 6 {0, 1, . . . , - 1} 0 , < 2k k k k 0 = {0, 1, . . . , - 1} =0 {3, 4} {0, 1, . . . , - 1} O(log ) {0, 1, . . . , - 1} X X X × {0, 1, . . . , × - 1} ( + 1) +1 1/2 +1 + + -1 + 0 < 0 -1- =7 =2 =4 =7 =5 =4 m -1 = -1 · (m, ) m · (m, ) (m, ) m (m1 , 1 ) < (m2 , 2 ) m1 < m2 (1, ) (1, ) (2, ) m1 = m2 (1, ) 1 < 2 (m, ) (-1, -1) · · (0, 0) · (1, 0) (m, ) = = (m, ) (m, + 1) (-1, -1) · (m, + 1) · (m + 1, + 1) =0 =8 0 1 2 3 4 5 0 (0, 0) 1 (0, 1) 3 (1, 1) 2 (0, 2) 4 (1, 2) 5 (1, 3) 6 7 6 (1, 2) 7 (2, 3) 8 (1, 4) 8 =0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 = 11
