Prepa HelpMines-Ponts 2024 MPI Informatique 2 : sujet en PDF
Sujet de l'épreuve de Informatique 2 du Concours commun Mines-Ponts, France, session 2024, filière MPI, en 4 heures. Thème : Flots de données en OCaml : estimation de cardinal, chiffrement par flot et énumération combinatoire.
Ce que traite le sujet, partie par partie
- Section 1 : flots de données. Listes cycliques et dépassement de pile, type des flots paresseux, fonctions de base (range, map, zip, entrelacement), produit cartésien correct, problème de l'arrêt et impossibilité d'un filtre général.
- Section 2 : estimation du cardinal d'un flot de données. Premier bit activé, algorithme naïf par table de hachage, algorithmes de Flajolet-Martin et HyperLogLog, moyenne harmonique et courses critiques entre fils d'exécution.
- Section 3 : chiffrement par flot de booléens. Preuves en déduction naturelle sur le ou exclusif, registres à décalage à rétroaction linéaire, évaluation de formules sur des flots et déchiffrement par le destinataire.
- Section 4 : énumération d'objets combinatoires. Grammaire des mots de Dyck et non-ambiguïté, algorithme de Heap : nombre d'affichages, preuve par récurrence de son effet et flot des permutations d'un tableau.
Chapitres à revoir avant de traiter ce sujet
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Spécifier, tester, prouver : terminaison et correction
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.