Centrale Option Informatique MP 2020

Le seul langage de programmation autorisé dans cette épreuve est Caml.
Toutes les fonctions des modules Array et List, ainsi que les fonctions de la librairie standard (celles qui s'écrivent sans nom de module, comme max ou incr ainsi que les opérateurs comme ©) peuvent être librement utilisées. Les candidats ne devront faire appel à aucun autre module.
En Caml, les matrices d'entiers sont représentées par des tableaux de tableaux, c'est-à-dire par le type int array array. L'expression . (i). (j) permet d'accéder au coefficient de la i-ème ligne et de la j-ième colonne de la matrice . Dans le texte, en dehors du code Caml, ce coefficient sera noté . On rappelle les définitions suivantes:

Dans ce problème, les graphes ont un ensemble de sommets de la forme et sont orientés complets et pondérés par des entiers : pour tout couple de sommets distincts, il existe un arc de à de poids . Le graphe est représenté par sa matrice d'adjacence , avec la convention que pour tout sommet (il n'y a pas d'arc d'un sommet vers lui-même).

Nous considérons une élection, à laquelle se présentent candidats. Chaque électeur inscrit sur son bulletin l'ensemble des candidats (tous les candidats sont classés), par ordre de préférence. L'ensemble des bulletins est rassemblé dans une urne. Le nombre de votants est noté , l'urne contient donc bulletins.
Les trois types de données suivants sont utilisés pour représenter un vote:

Par exemple, s'il y a trois candidats et qu'un électeur préfère le candidat 2 , puis le candidat 0 et enfin considère que le candidat 1 est le moins souhaitable, son bulletin de vote sera .
Une fois le vote effectué, on compare les résultats de deux candidats particuliers et en comptant le nombre de bulletins qui classent le candidat avant le candidat . On exprime le résultat de la comparaison entre les candidats et en calculant la différence entre le nombre de bulletins de vote qui placent avant et le nombre de ceux qui placent avant .

On considère une élection avec trois candidat et trois votants : . Les bulletins sont [2; ], et . La comparaison entre le candidat numéro 0 et le candidat numéro 1 donne -1 car le candidat 0 est placé une fois avant le candidat 1 et deux fois après.
Q 1. Écrire une fonction duel : candidat candidat urne int, telle que duel i j u renvoie la comparaison entre le candidat et le candidat à partir des bulletins contenus dans l'urne .
On peut alors synthétiser le contenu d'une urne u en construisant le graphe de préférence des votants : ses sommets correspondent aux candidats et l'arc du sommet i vers le sommet j est pondéré par la comparaison entre le candidat i et le candidat j, c'est-à-dire la valeur de duel i j u.
La figure 1 donne le graphe de préférence obtenu à partir du vote de l'exemple 1 ainsi que sa matrice d'adjacence . Afin d'alléger le schéma, seuls les arcs avec un poids strictement positif sont représentés.

On considère une élection avec trois candidats et 4 votants : . À l'issue du vote, le contenu de l'urne est .
Q 2. Tracer le graphe de préférence de l'urne (en ne dessinant que les arcs ayant un poids strictement positif) et donner sa matrice d'adjacence.

Q 3. Expliquer pourquoi la matrice d'adjacence d'un graphe de préférence est antisymétrique et pourquoi tous ses coefficients non-diagonaux ont la même parité.
Étant donné une urne , on note la matrice du graphe de préférence associée à cette urne.
Q 4. Écrire une fonction depouillement : int urne int array array qui prend en paramètres le nombre de candidats et une urne et renvoie la matrice .

Le but de cette sous-partie est de démontrer le théorème de McGarvey : «Pour toute matrice antisymétrique à coefficients pairs , il existe une urne telle que .»
Soient et trois entiers naturels tels que et . On note la matrice carrée de taille dont tous les coefficients sont nuls sauf les coefficients d'indices et qui valent respectivement 2 et -2 .
Q 5. Soit un nombre de candidats et et deux entiers naturels strictement inférieurs à . Montrer qu'il existe une urne contenant deux votes telle que .
Q 6. On considère deux urnes et . Exprimez en fonction de et de .
Q 7. Démontrer le théorème de McGarvey.
Q 8. Écrire une fonction mcgarvey : int array array urne prenant en paramètre une matrice antisymétrique de coefficients tous pairs et renvoyant une urne telle que .
Q 9. Estimer la complexité de la fonction mcgarvey en fonction de , la taille de la matrice (c'est-à-dire le nombre de candidats), et de , le maximum des coefficients de la matrice.

L'objectif de cette partie est de déterminer le vainqueur, ou les vainqueurs ex aequo, d'un vote par préférence.

On appelle vainqueur de Condorcet tout sommet tel que, dans le graphe de préférence, les arcs sortant de ce sommet ont tous un poids positif ou nul. Ainsi, dans le premier exemple de la partie I, le candidat 2 est un vainqueur de Condorcet.
Q 10. Expliquer pourquoi un vainqueur de Condorcet peut être qualifié de «vainqueur» de l'élection.
Q 11. Écrire une fonction condorcet : int array array candidat list prenant en paramètre la matrice d'adjacence d'un graphe de préférence et renvoyant la liste des vainqueurs de Condorcet.
Q 12. En se plaçant dans le cas et , construire une urne pour laquelle il n'existe pas de vainqueur de Condorcet. Tracer le graphe de préférence correspondant.

À la fin du siècle, Markus Schulze imagina une méthode permettant de déterminer un vainqueur à l'issue de n'importe quel vote par préférence.
On appelle poids d'un chemin du graphe de préférence, le minimum des poids des arcs constituant ce chemin. Ainsi, dans le premier exemple de la partie I, le poids du chemin est -1 .
Le graphe intermédiaire de Schulze est un graphe orienté pondéré complet dont les sommets sont les candidats et dont l'arc du sommet vers le sommet (distinct de ) est pondéré par le maximum des poids de tous les chemins allant de à dans le graphe de préférence. Sa matrice d'adjacence est notée .

Q 13. Pour et , candidats distincts, démontrer que est aussi le maximum des poids des chemins sans boucle de à , c'est-à-dire des chemins avec deux à deux distincts.
Q 14. Démontrer que pour tout triplet de sommets distincts.
Q 15. En adaptant l'algorithme de Floyd-Warshall, programmer une fonction intermediaire : int array array int array array prenant en paramètre la matrice d'adjacence d'un graphe de préférence et renvoyant la matrice d'adjacence du graphe intermédiaire de Schulze correspondant.
Q 16. Estimez la complexité de la fonction intermediaire en fonction de , le nombre de candidats.
Q 17. Serait-il pertinent d'utiliser l'algorithme de Dijkstra au lieu de l'algorithme de Floyd-Warshall ? Argumenter la réponse.

Le graphe de préférence de Schulze est défini à partir du graphe intermédiaire de Schulze. Si I est la matrice d'adjacence du graphe intermédiaire de Schulze, alors la matrice d'adjacence du graphe de préférence de Schulze est définie par pour tous entiers naturels et strictement inférieurs à .
Q 18. Montrer que la matrice d'adjacence d'un graphe de préférence de Schulze est antisymétrique et que tous ses coefficients sont pairs.
Q 19. Écrire une fonction graphe_schulze : int array array int array array qui prend en paramètre un graphe intermédiaire de Schulze et qui renvoie le graphe de préférence de Schulze correspondant.

Un vainqueur de Schulze est un vainqueur de Condorcet dans le graphe de préférence de Schulze.
Q 20. Écrire une fonction schulze : int urne candidat list qui prend en paramètres le nombre de candidats et un ensemble de bulletins de vote et renvoie la liste des vainqueurs de Schulze.
Q 21. Estimer la complexité de la fonction schulze en fonction du nombre de candidats et du nombre de votants .
À partir d'un graphe de préférence de Schulze représenté par la matrice , on définit la relation entre les candidats comme suit : si et seulement est strictement positif.
Q 22. Montrer que la relation est transitive, c'est-à-dire que pour tous candidats et , si et alors .

Si désigne la matrice d'adjacence du graphe intermédiaire, on pourra distinguer les cas et .
Q 23. Montrer que quelle que soit l'urne non vide considérée, il existe toujours au moins un vainqueur de Schulze.

Étant donné une variable propositionnelle , on appelle littéral, les formules et est la négation de . On appelle clause une disjonction de littéraux, par exemple est une clause ( signifie «ou»).
On appelle conjonction de clauses, une formule qui est la conjonction entre plusieurs clauses. Par exemple est une conjonction de clauses ( signifie « et »).
On appelle interprétation une fonction qui à chaque variable propositionnelle associe une valeur de vérité (vrai ou faux).
On dit qu'une conjonction de clauses est satisfiable s'il existe une interprétation qui la rend vraie, c'est-à-dire qui rend vrai toutes ses clauses, autrement dit qui rend vrai au moins un littéral de chacune de ses clauses.
Le problème SAT consiste à déterminer si une conjonction de clauses est satisfiable :
Entrées : Une conjonction de clauses .
Sortie : Un booléen. Vrai si est satisfiable. Faux sinon.
Q 24. Montrer qu'il est possible de résoudre le problème SAT avec une complexité en où est le nombres de variables distinctes et le nombre de littéraux de l'entrée (comptés avec leurs répétitions).

On considère un vote par préférence pour lequel on a réparti les candidats en trois groupes :

Le problème appelé CONTROL-ADD-ALT consiste à déterminer s'il est possible d'éliminer un certain nombre de candidats optionnels de façon à ce que soit un vainqueur de Schulze de l'élection :

Entrées : Le candidat . L'ensemble . L'ensemble . Le graphe de préférence du vote sur l'ensemble des candidats . Un budget .
Sortie: Un booléen. Vrai, s'il est possible de choisir candidats distincts dans tels que est un vainqueur de Schulze de l'élection en considérant uniquement l'ensemble de candidats . Faux sinon.

Pour obtenir le graphe de préférence de l'élection avec l'ensemble de candidats , on prend le graphe de préférence sur l'ensemble des candidats et on supprime les candidats de qui n'ont pas été choisis (ainsi que les arrêtes entrantes et sortantes de ces candidats).
On appelle instance de CONTROL-ADD-ALT une entrée du problème CONTROL-ADD-ALT et instance de SAT une entrée du problème SAT.
On considère l'algorithme «Transformation d'une formule en élection» qui, étant donné une instance de SAT (c'est-à-dire une conjonction de clauses), construit une instance de CONTROL-ADD-ALT :

Entrées : Une conjonction de clauses
Sortie : Un candidat (le champion), un ensemble de candidats automatiques , un ensemble de candidats optionnels , un budget , un graphe de préférence sur l'ensemble de candidats

pour tout variable propositionnelle apparaissant dans faire

fin pour
Créer un nouveau candidat
Créer un graphe avec un seul sommet

pour tout clause de faire
Créer un nouveau candidat associé à et l'ajouter à et à
Ajouter à un arc de poids +4 de vers et un arc de poids -4 en sens inverse.
fin pour
pour tout variable propositionnelle apparaissant dans faire
Créer un nouveau candidat associé au littéral et l'ajouter à et à
Créer un nouveau candidat associé au littéral et l'ajouter à et à
Ajouter à deux arcs de poids +6 de vers et vers puis ajouter deux arcs de poids -6 en sens inverse.
fin pour
pour tout couple avec un littéral de et une clause de contenant le littéral faire
Ajouter à un arc de poids +6 de vers et un arc de poids -6 en sens inverse.
fin pour
Compléter le graphe avec des arrêtes de poids nul pour le rendre complet.
le nombre de variables propositionelles qui apparaissent dans .
renvoyer .
Q 25. Donner le graphe de préférence créé à partir de la formule . Est-il possible de choisir candidat parmi et de sorte que gagne?
Q 26. Montrer que si on peut choisir candidats optionnels de sorte à faire gagner le champion, alors, pour toute variable propositionnelle , on a choisi ou mais on n'a pas choisit et .
Q 27. Justifier que est satisfiable si et seulement si l'instance de CONTROL-ADD-ALT créée par cet algorithme à partir de donne une réponse positive.
On dit qu'un algorithme est en temps polynomial en un paramètre , si la complexité de cet algorithme est majorée par un polynôme en .
Conjecture. Il n'existe pas d'algorithme en temps polynomial en nombre de littéraux de l'entrée qui résout SAT.
Q 28. Montrer que, si la conjecture précédente est vraie, alors il n'existe pas d'algorithme en temps polynomial en nombre de candidats qui résout CONTROL-ADD-ALT.