e3a-Polytech 2018 MP Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours e3a-Polytech, France, session 2018, filière MP, en 3 heures. Thème : Terminaison et problème de l'arrêt, pgcd binaire, chemins dans un graphe, requêtes SQL et normalisation de formules logiques.
Ce que traite le sujet, partie par partie
- Exercice 1 (Python) : terminaison et problème de l'arrêt. Valeurs pour lesquelles des fonctions terminent, déroulé d'un appel, puis raisonnement par l'absurde montrant qu'une fonction qui déciderait la terminaison de tout calcul ne peut pas exister.
- Exercice 2 (Caml) : valuation, résidu et pgcd. Lecture de la valuation 2-adique en base deux, fonction résidu, pgcd par soustractions successives en itératif puis en récursif, méthode chinoise et sa complexité.
- Exercices 3 et 4 (Caml, SQL) : chemins dans un graphe et base de zoos. Matrice d'adjacence d'un graphe et fonction qui vérifie qu'une liste de sommets forme un chemin, puis requêtes SQL de sélection, de jointure et de regroupement sur une base de zoos et d'animaux.
- Exercice 5 (Caml) : formes normales conjonctives positives. Arbre et type d'une formule, fonctions qui reconnaissent les disjonctions de variables et les formes normales conjonctives, puis preuve de la terminaison et de la correction d'une fonction de normalisation par des mesures bien choisies.
Chapitres à revoir avant de traiter ce sujet
- Spécifier, tester, prouver : terminaison et correction
- Bases de Python : expressions, types, instructions, fonctions
- Langage OCaml : expressions, types, filtrage, récursivité
- Complexité des algorithmes itératifs et récursifs
- Architecture de l'ordinateur et représentation des nombres
- Graphes : représentations et parcours
- Logique, ensembles et applications
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.