X/ENS Informatique A MP 2020

Thème de l'épreuve Constructions et explorations de labyrinthes
Principaux outils utilisés preuve d'algorithmes, algorithmes de graphes, parcours de graphes, probabilités, programmation OCaml, file, plus court chemin
Mots clefs labyrinthe, graphe, parcours, parfait, mélange de Knuth, profondeur, largeur, aléatoire, classes disjointes, algorithme d'Eller, Eller, monstre, distance

Corrigé

 :
👈 gratuite pour tous les corrigés si tu crées un compte
👈 l'accès aux indications de tous les corrigés ne coûte que 1 € ⬅ clique ici
👈 gratuite pour tous les corrigés si tu crées un compte
- - - - -
👈 gratuite pour ce corrigé si tu crées un compte
- - - - - - - - - - - - -

Énoncé complet

(télécharger le PDF)
                                            

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


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