CCINP 2016 MP Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2016, filière MP, en 4 heures. Thème : Logique trivaluée et flot maximal dans un réseau de transport.
Ce que traite le sujet, partie par partie
- Partie I : logique et calcul des propositions. Logique à trois valeurs (vrai, faux, indéterminé) : tables de vérité, recherche de tautologies, comparaison de deux définitions de l'implication, puis représentation des formules et fonction récursive CaML d'évaluation.
- Partie II : algorithmique et programmation. Réseaux de transport et flots, coupes, algorithme de Ford et Fulkerson par chemins améliorants avec terminaison et complexité, graphe des résidus et théorème flot maximal égal à coupe minimale, puis couplage maximum dans un graphe biparti, le tout programmé en CaML.
Chapitres à revoir avant de traiter ce sujet
- Logique, ensembles et applications
- Langage OCaml : expressions, types, filtrage, récursivité
- Complexité des algorithmes itératifs et récursifs
- 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.