e3a-Polytech 2019 MP Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours e3a-Polytech, France, session 2019, filière MP, en 3 heures. Thème : Recherche dichotomique et trichotomique, langages de mots binaires, diamètre d'un graphe et d'un arbre.
Ce que traite le sujet, partie par partie
- Exercice 1 : autour de la recherche par dichotomie. Principe et intérêt de la dichotomie, invariant d'une fonction qui ne termine pas et sa correction, preuve de terminaison et de correction, recherche par trichotomie et sa complexité, puis recherche de complexité logarithmique dans une matrice triée par colonnes.
- Exercice 2 : automates et langages de mots binaires. Écriture binaire des entiers, automate local standard, langage local et automate déterministe, automate du reste modulo 3 avec preuve par récurrence, intersection des langages et fonctions OCaml de reconnaissance.
- Exercice 3 : diamètre d'un graphe. Graphes de diamètre maximal et minimal construits en OCaml, calcul du diamètre par Dijkstra ou par parcours en largeur, puis diamètre d'un arbre binaire en le transformant en graphe ou par une méthode diviser pour régner de complexité linéaire.
Chapitres à revoir avant de traiter ce sujet
- Listes et algorithmes de recherche (séquentielle, dichotomique)
- Spécifier, tester, prouver : terminaison et correction
- Récursivité
- Complexité des algorithmes itératifs et récursifs
- Langage OCaml : expressions, types, filtrage, récursivité
- Architecture de l'ordinateur et représentation des nombres
- Graphes : représentations et parcours
- Plus courts chemins et applications : Dijkstra, A*, Floyd-Warshall, coloration
- Arbres binaires, arbres binaires de recherche et tas
Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.