Centrale-Supélec 2020 MP Option informatique : sujet en PDF

Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2020, filière MP, en 4 heures. Thème : Un système de vote : graphes orientés pondérés, adaptation de Floyd-Warshall et réduction depuis le problème SAT.

Ce que traite le sujet, partie par partie

• Partie I : vote par préférence. En Caml, bulletins représentés par des listes, comparaison de deux candidats et calcul de la matrice d'adjacence du graphe de préférence, antisymétrie et parité de ses coefficients. Démonstration du théorème de McGarvey par réunion d'urnes, fonction qui construit une urne à partir d'une matrice antisymétrique à coefficients pairs, et sa complexité.
• Partie II : recherche du vainqueur. Sommets dont tous les arcs sortants ont un poids positif ou nul (vainqueurs de Condorcet). Poids d'un chemin défini comme le minimum de ses arcs, maximum sur les chemins et chemins sans boucle, adaptation de l'algorithme de Floyd-Warshall en Caml, complexité et discussion de l'algorithme de Dijkstra, graphe de préférence de Schulze, fonctions en Caml et complexité en fonction de n et p, transitivité de la relation associée et existence d'un vainqueur de Schulze.
• Partie III : satisfiabilité d'une formule de logique propositionnelle. Résolution du problème SAT en O(2^n m), puis transformation d'une conjonction de clauses en instance du problème CONTROL-ADD-ALT sur un graphe pondéré : exemple sur une formule, contraintes sur le choix des k candidats optionnels, équivalence avec la satisfiabilité et conséquence sur l'existence d'un algorithme polynomial, sous la conjecture admise sur SAT.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Complexité des algorithmes itératifs et récursifs
• 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.