Le sujet comporte 18 pages, numérotées de 1 à 18 .
Début de l'épreuve.
Complexité. Par la complexité d'un algorithme, on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc.) nécessaires à l'exécution de celui-ci dans le pire cas. Lorsque la complexité dépend d'un ou plusieurs paramètres , on dit que l'algorithme a une complexité en s'il existe une constante telle que, pour toutes les valeurs de suffisamment grandes (c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres la complexité est au plus .
Fonctions utiles en OCaml. Dans les questions de programmation en OCaml, il est interdit d'utiliser des fonctions de la bibliothèque qui ne sont pas incluses dans la liste suivante.
Option.get: 'a option -> 'a renvoie v si l'argument de type 'a option est égal à Some v , et lève une exception sinon. La complexité est en .
List.length: 'a list -> int renvoie la taille de la liste donnée en argument. La complexité est en , où est la longueur de la liste donnée en argument.
List.hd: 'a list -> 'a renvoie le premier élément de la liste donnée en argument si celle-ci n'est pas vide, et lève une exception sinon. La complexité est en .
List.tl: 'a list -> 'a list renvoie la liste donnée en argument privée de son premier élément si la liste donnée en argument n'est pas vide, et lève une exception sinon. La complexité est en .
List.rev: 'a list -> 'a list renvoie la liste donnée en argument dans l'ordre inverse. La complexité est en , où est la longueur de la liste donnée en argument.
List.map: ('a -> 'b) -> 'a list -> 'b list renvoie la liste de type 'b list obtenue en appliquant la fonction de type ' a -> ' b donnée en premier argument à chaque élément de la liste de type 'a list donnée en second argument. Si la complexité de f est en , alors la complexité de List.map f lst est en , où est la longueur de lst.
List.mem: 'a -> 'a list -> bool renvoie true si la valeur donnée en premier argument est un élément de la liste donnée en second argument, et renvoie false sinon. La complexité est en , où est la longueur de la liste donnée en second argument.
List.assoc: 'a -> ('a * 'b) list -> 'b: cette fonction spécifique aux listes d'association est décrite en page 4.
Fonctions utiles en C. Dans les questions de programmation en C, on pourra supposer que les en-têtes <stdbool.h>, <stdio.h>, <stdlib.h>, et <math.h> ont été inclus. En particulier, on pourra utiliser la fonction double (double x ) définie par l'entête <math.h>, qui calcule le logarithme en base 2.
Présentation du sujet. Ce sujet concerne les couplages dans les graphes non orientés. La partie I, à composer dans le langage OCaml, concerne la recherche d'un couplage maximal dans un graphe. On étudiera et implémentera un algorithme dû à Edmonds. Les parties II et III, à composer dans le langage C, concernent le problème de l'existence d'un couplage parfait dans un graphe. On y implémente des méthodes algébriques et probabilistes basées sur des calculs de déterminants. La partie II concerne l'implémentation d'un algorithme pour calculer le déterminant d'une matrice carrée dû à Mahajan et Vinay. La partie III exploite cet algorithme pour implémenter un algorithme probabiliste testant l'existence d'un couplage parfait dans un graphe non orienté.
Les parties I et II sont indépendantes. La partie III dépend de la partie II et de notions introduites en partie I.
Graphes non orientés. On travaillera dans les parties I et III sur des graphes non orientés et sans boucles. Un tel graphe est défini par une paire d'ensembles finis ( ), où est l'ensemble des sommets du graphe et l'ensemble de ses arêtes. Une arête est une paire non-ordonnée d'exactement deux sommets . Ainsi, les arêtes sont non orientées et il n'y a pas de boucles ( n'est jamais une arête de ). Une arête est dite incidente aux sommets et . On supposera toujours que est non vide.
Étant donné un graphe :
Un chemin est une suite finie de sommets avec et telle que pour tout , on a . La longueur du chemin est .
Un chemin est élémentaire si ses sommets sont deux-à-deux distincts.
Un cycle est un chemin de longueur , avec et tel que le chemin est élémentaire. Autrement dit, le seul sommet autorisé à apparaître plusieurs fois dans un cylce est le sommet , qui apparaît exactement deux fois (une fois au début et une fois à la fin).
Partie I : Algorithme d'Edmonds
Cette partie concerne l'algorithme d'Edmonds pour la recherche de couplage maximal.
Question 1. Écrire une fonction del: 'a list 'a list 'a list qui prend en entrée deux listes 1st1 et 1st2 et renvoie la liste des éléments de 1st1 n'apparaissant pas dans 1st2. On attend une complexité en où est la longueur de 1st1 et est la longueur de 1st2, sans la justifier.
On suppose définie une fonction join: 'a list -> 'a list -> 'a list telle que join lst1 lst2 est une liste sans répétitions contenant l'ensemble de tous les éléments apparaissant dans lst1 et de tous les éléments apparaissant dans lst2.
Nous utilisons des listes d'association pour représenter les graphes. Les listes d'association implémentent une structure de dictionnaire; il s'agit de listes de paires (a,b), dont le premier élément représente la clef et le second élément représente la valeur associée à cette clef.
Il existe des fonctions OCaml permettant de travailler avec les listes d'association. Dans la suite, nous utiliserons seulement la fonction List.assoc: 'a -> ('a * 'b) list -> 'b qui prend en arguments une clef x et une liste d'association lst, et renvoie la valeur b associée à cette clef, c'est-à-dire l'élément du premier couple ( ) appartenant à lst, s'il en existe. La fonction lève une exception si x n'est pas une clef de la liste lst. La complexité est en , où est la longueur de lst.
Question 2. Écrire une fonction keys: ('a * 'b) list 'a list qui prend en entrée une liste d'association 1st et qui renvoie la liste de ses clefs. On attend une complexité en où est la longueur de 1st, sans la justifier.
Nous représentons les graphes en utilisant le type OCaml suivant :
type graphe int int list list
Un graphe est représenté par une liste de paires (a,lst) où a est un sommet du graphe et lst est la liste d'adjacence de ce sommet. Dans la suite, on suppose toujours que :
les sommets du graphe sont exactement les clefs de la liste d'association;
chaque clé de la liste d'association est unique.
Par exemple, le graphe
peut être représenté par la liste d'association .
Couplages
Un couplage dans un graphe est un ensemble (possiblement vide) d'arêtes de sans intersections : un sommet de ne peut appartenir à plus d'une arête dans .
Considérons par exemple le graphe :
Les ensembles d'arêtes suivants sont des couplages dans ce graphe :
Les arêtes d'un couplage sont représentées par des traits plus épais. Par exemple, les trois couplages ci-dessus sont représentés comme suit :
Question 3. On considère le graphe suivant :
Indiquer lesquels des ensembles suivants sont des couplages dans le graphe ci-dessus :
(1) ,
(2) ,
(3) .
Un couplage est représenté par une liste de paires de sommets :
type couplage (int * int) list
Dans toute la suite, une arête sera représentée par la paire (min .
Étant donné un couplage dans un graphe , on dit qu'un sommet de est couvert par s'il existe une arête dans le couplage qui est incidente à .
Question 4. Écrire une fonction couverts: couplage -> int list qui prend en entrée un couplage cpl et qui renvoie la liste des sommets couverts par cpl .
On attend une complexité en où est la longueur de la liste cpl , sans la justifier.
Couplages maximaux
Nous allons maintenant nous intéresser aux couplages maximaux, c'est-à-dire aux couplages ayant un nombre maximal d'arêtes. On remarque qu'un couplage dans un graphe à sommets ne peut contenir plus de arêtes.
Considérons le graphe suivant :
Le couplage est maximal. Mais le couplage n'est pas maximal bien qu'il ne soit pas possible de lui adjoindre d'arête supplémentaire.
Question 5. Donner un autre couplage maximal dans le graphe ci-dessus.
Chemins d'augmentation
L'algorithme d'Edmonds est basé sur la recherche de chemins d'augmentation. Étant donné un couplage dans un graphe , un chemin d'augmentation pour (dans ) est un chemin élémentaire dans le graphe tel que et :
et ne sont pas couverts par ;
c'est un chemin alternant : pour tout , on a si et seulement si .
Un chemin d'augmentation pour permet de construire un nouveau couplage constitué des arêtes de qui ne sont pas dans et des arêtes de qui ne sont pas dans .
Par exemple, dans le graphe
le chemin suivant est un chemin d'augmentation :
Le nouveau couplage obtenu à partir de ce chemin d'augmentation est le suivant :
Question 6. Considérons le graphe en (1) ci-dessus. Donner un chemin d'augmentation
pour le couplage de manière à ce que le couplage soit maximal.
Question 7. On considère le graphe et le couplage suivants :
Donner un chemin d'augmentation et le couplage augmenté correspondant.
Question 8. Soit un chemin d'augmentation pour un couplage dans un graphe . Montrer que est bien un couplage, et qu'il contient strictement plus d'arêtes que .
En OCaml, un chemin est représenté par une liste de sommets, c'est-à-dire par une valeur de type int list.
Question 9. Écrire une fonction
separer : int list -> ((int * int) list) * ((int * int) list)
qui prend en entrée un chemin d'augmentation chm et renvoie deux listes lstin et lstout où lstin contient les arêtes composant le chemin chm qui appartiennent au couplage, et où lstout contient les arêtes composant le chemin chm qui n'appartiennent pas au couplage.
On attend une complexité en , où est la longueur de la liste chm, sans la justifier.
Question 10. Écrire une fonction augmente: couplage -> int list -> couplage qui prend en entrée un couplage cpl et un chemin d'augmentation chm, et qui renvoie le couplage cpl(chm).
L'algorithme d'Edmonds, que nous allons voir ci-dessous, repose essentiellement sur le lemme de Berge. Ce résultat, que nous admettrons, énonce qu'un couplage dans un graphe est maximal si et seulement s'il n'existe pas de chemin d'augmentation pour dans .
Bourgeons
L'algorithme d'Edmonds va de plus effectuer des opérations de contraction de bourgeons. Soit un couplage dans un graphe . Un bourgeon est un cycle dans de longueur impaire dont exactement arêtes sont dans . La base d'un bourgeon est le seul sommet
de dont les deux arêtes adjacentes dans ne sont pas dans :
La contraction d'un bourgeon consiste à identifier tous les sommets de celui-ci. On représente un bourgeon par une valeur de type int list qui contient exactement les sommets de , dans un ordre quelconque, mais sans répétition. Par exemple, le bourgeon illustré ci-dessus peut être représenté par la liste .
Étant donné un graphe et une liste de sommets , le graphe contracté est défini comme suit :
L'ensemble des sommets du graphe est où , le nouveau sommet de , est un entier qui n'est pas un sommet de .
Les arêtes de sont les arêtes de entre sommets n'étant pas dans , ainsi que les arêtes de la forme où n'appartient pas à mais est adjacent dans à un sommet de . L'ensemble des arêtes de est donc défini comme et et adjacent dans à un sommet de
On suppose donnée une fonction renomme: int list -> int list -> int -> int list telle que renomme lst rnm w renvoie une liste obtenue en remplaçant dans lst tous les éléments de rnm par , et en supprimant tous les doublons.
Question 11. Écrire une fonction contracteG: graphe int list int graphe qui prend en entrée un graphe grph, une liste de sommets lst, et le nom w du nouveau sommet, et qui renvoie le graphe contracté grph/lst.
Soit un couplage dans un graphe , et soit un bourgeon. On définit un couplage dans le graphe contracté . En notant le nouveau sommet de , l'ensemble a pour éléments :
les arêtes telles que et
les arêtes telles que et telles qu'il existe un avec .
On remarquera que ne dépend que de , et du nom du nouveau sommet.
Question 12. Montrer que est un couplage dans .
Question 13. Écrire une fonction
contracteC : couplage -> int list -> int -> couplage
qui prend en entrée un couplage cpl, un bourgeon brg, et le nom w du nouveau sommet, et qui renvoie le couplage .
On admettra dans la suite qu'il existe un chemin d'augmentation pour le couplage dans si et seulement s'il existe un chemin d'augmentation pour le couplage dans .
Recherche de chemins d'augmentation
La recherche de chemins d'augmentation va utiliser des forêts, c'est-à-dire des listes d'arbres. Les types ci-dessous représentent des arbres et des forêts dont les nœuds sont étiquetés par des entiers. Ces entiers seront par la suite des sommets d'un graphe.
type arbre = N of int * foret
and foret = arbre list
Question 14. Écrire une fonction find: foret int (int list) option telle que find foret v renvoie None si l'entier v n'étiquette aucun des nœuds de foret, et telle que find foret v renvoie Some c sinon, où c est la liste des étiquettes le long d'un chemin allant d'une racine à un nœud d'étiquette v dans foret.
On attend une complexité en , où est le nombre de nœuds de foret, sans la justifier.
Question 15. Écrire une fonction extend: foret int int foret, qui prend en arguments une forêt foret et deux entiers u et v, et qui renvoie une copie de foret dans laquelle pour chaque nœud étiqueté par u, on a créé un nouvel enfant étiqueté par v. On attend une complexité en , où est le nombre de nœuds de foret, sans la justifier.
La profondeur d'un nœud dans un arbre est définie inductivement comme suit : la racine est à profondeur 0 , et pour , les nœuds à profondeur sont les enfants des nœuds à profondeur .
L'algorithme de recherche de chemins d'augmentation prend en entrée un graphe et un couplage dans . Il manipule un ensemble de sommets et peut être décrit comme suit.
(1) On construit une forêt dont les nœuds consistent exactement en une racine pour chaque sommet de non couvert par .
(2) On fixe .
(3) Tant qu'il existe un sommet tel que apparaît à profondeur paire dans :
On ajoute à l'ensemble .
Pour chaque voisin de dans tel que :
(a) Si n'est pas dans la forêt , il est couvert par une arête de , et on ajoute les arêtes et à .
(b) Si est dans la forêt :
(i) Si apparaissent à profondeurs paires dans des arbres distincts de racines respectives , alors on renvoie la suite des sommets de vus dans en allant de à ( et inclus), puis en allant de à ( et inclus).
(ii) Si et apparaissent dans le même arbre à profondeurs paires, alors on construit le bourgeon correspondant, et on cherche un chemin d'augmentation pour le couplage dans le graphe . Si on en trouve un, alors on renvoie un chemin d'augmentation pour dans .
Question 16. Montrer que la suite de sommets renvoyée par l'algorithme dans le cas (3)(b)(i) est un chemin d'augmentation pour dans .
On admet dans toute la suite que l'algorithme ci-dessus renvoie un chemin d'augmentation pour si et seulement s'il en existe un.
Nous allons étudier une implémentation OCaml de cet algorithme. On suppose données les fonctions suivantes.
La fonction frais: int list -> int renvoie un entier n'appartenant pas à la liste donnée en argument.
La fonction prochain: foret -> int list -> int option prend en arguments une forêt et une liste de sommets lst. Un appel prochain lst renvoie Some où d est un entier apparaissant dans à profondeur paire et n'appartenant pas à lst si un tel entier d existe. Sinon, prochain f lst revoie None.
La fonction apparie: couplage -> int -> int prend en arguments un couplage cpl et un sommet u couvert par le couplage, et renvoie le sommet apparié, c'est-à-dire l'unique v tel que (min ) appartient à cpl .
La fonction gonfle: graphe -> int list -> int list -> int -> int list prend en arguments un graphe grph, un bourgeon brg, un chemin d'augmentation dans le graphe contracté grph/brg, et le nom du nouveau sommet nv, et renvoie le chemin d'augmentation correspondant dans grph.
La figure 1 page 11 représente une implémentation incomplète d'une fonction
recherche : graphe -> couplage -> (int list) option
Les questions ci-dessous demandent de donner le code de la ligne 15, des lignes 17-18 et des lignes 24-26, ainsi que d'implémenter la fonction extrait (ligne 20).
La fonction recherche prend en arguments un graphe et un couplage. Elle doit renvoyer Some p s'il existe un chemin d'augmentation p, et renvoyer None sinon. Certaines fonctions appelées dans le code de recherche peuvent lever des exceptions, mais on admettra que ces exceptions ne sont jamais levées si les données d'entrée sont bien formées.
Question 17. Donner le code devant apparaître à la ligne 15 de la figure 1.
Question 18. Donner le code devant apparaître dans le bloc aux lignes 17-18 de la figure 1.
Question 19. Écrire une fonction extrait: int list int list int list telle que l'appel extrait cu cv ligne 20 renvoie le bourgeon associé aux chemins cu et cv.
Question 20. Donner le code devant apparaître dans le bloc aux lignes 24-26 de la figure 1.
Question 21. Écrire une fonction edmonds: graphe -> couplage qui prend en entrée un graphe et qui renvoie un couplage maximal.
let rec recherche graphe couplage =
let nc = del (keys graphe) (couverts couplage) in
let foret = ref (List.map (fun x -> N(x,[])) nc) in
let rec aux_voisins u liste_voisins =
let cu = Option.get (find !foret u) in
match liste_voisins with
| [] -> None
| v :: tl ->
match find !foret v with
| None -> let z = apparie couplage v in
foret := extend (extend !foret u v) v z;
aux_voisins u tl
| Some cv when (List.length cv) mod 2 = 0
(* nombre de sommets pair = profondeur impaire *)
-> ...
| Some cv when (List.hd cu) <> (List.hd cv)
-> ...
...
| Some cv
-> let bourgeon = extrait cu cv in
let nv = frais (keys graphe) in
let ng = contracteG graphe bourgeon nv in
let nc = contracteC couplage bourgeon nv in
...
...
...
in
let rec aux_sommets traites =
match prochain !foret traites with
| None -> None
| Some u -> let liste_voisins = del (List.assoc u graphe) traites in
match aux_voisins u liste_voisins with
| None -> aux_sommets (u::traites)
| Some ch -> Some ch
in
aux_sommets
Figure 1 - Fonction recherche.
Partie II : Calculs de déterminants
Cette partie concerne l'algorithme de Mahajan-Vinay pour le calcul de déterminants de matrices carrées. Elle est à composer dans le langage C .
Préliminaires : matrices linéarisées
On travaille avec des matrices carrées de taille arbitraire indexées à partir de 0 . On utilise une représentation linéarisée de ces matrices. Une matrice de dimension (c'est-à-dire avec n lignes et n colonnes) est représentée par un tableau A avec éléments de manière à ce que le coefficient de la matrice (indice de ligne et indice de colonne ) corresponde à l'élément du tableau.
On suppose dans la suite que les opérations arithmétiques ont une complexité en .
Question 22. Écrire des fonctions
int read_sqmatrix (int n, int *A, int i, int j)
void write_sqmatrix (int n, int *A, int i, int j, int val)
telles que
read_sqmatrix ( ) renvoie la valeur du coefficient où est la matrice représentée par A ;
write_sqmatrix( modifie la valeur du coefficient pour qu'il soit égal à val.
On supposera que A est un tableau avec éléments et que .
On attend une complexité en pour ces fonctions, sans la justifier.
Algorithme de Mahajan-Vinay
L'algorithme de Mahajan-Vinay est basé sur une formulation du déterminant d'une matrice en termes de suites de marches fermées dans un graphe associé à .
Soit une matrice carrée de dimension . On associe à son graphe d'adjacence . Le graphe est orienté et pondéré. Il est défini comme suit :
les sommets de sont les entiers de 0 à ,
les arcs sont les paires ordonnées telles que ,
le poids d'un arc est égal à .
Les sommets de sont donc des entiers. L'ordre usuel sur ces entiers est utilisé dans la suite de cette partie.
Question 23. Dessiner le graphe d'adjacence de la matrice suivante :
Une marche fermée dans le graphe est une suite de sommets avec et qui satisfait les conditions suivantes :
pour tout , il existe un arc ( ) dans ;
le sommet est le plus petit entier de la suite, appelé la tête de , notée ;
le sommet n'apparaît qu'au début et à la fin de la suite : pour tout , on a .
La longueur de la marche fermée est le nombre d'arcs qui la composent. La longueur de est donc égale à . Le poids d'une marche fermée est le produit des poids des arcs (avec multiplicités) qui la composent :
Exemple. Considérons le graphe suivant, dont les arcs ont tous poids 1 :
Dans ce graphe, les suites de sommets suivantes sont des marches fermées :
On remarque qu'il est possible de passer plusieurs fois par le même sommet. Cependant la suite
n'est pas une marche fermée car la tête ne doit apparaître qu'au début et à la fin. La suite
n'est pas non plus une marche fermée car la tête n'est pas le plus petit sommet.
Question 24. Donner une marche fermée de longueur 3 et de tête 1 dans le graphe ci-dessus.
Une suite de marches fermées est une suite de marches fermées telle que :
les têtes sont croissantes : ;
le nombre total d'arcs (en comptant les multiplicités) est égal au nombre de sommets de .
Le poids d'une suite de marches fermées est le produit des poids des marches fermées qui la composent : . La tête de , notée , est la tête de la première marche fermée de .
Question 25. On considère le graphe suivant :
(1) Donner les marches fermées de longueur au plus 3 et leurs poids.
(2) Donner les suites de marches fermées et leurs poids.
On définit aussi le signe d'une suite de marches fermées. Si , alors on pose :
On dit que est une suite de marches fermées positive lorsque , et que est une suite de marches fermées négative lorsque .
Le résultat fondamental de Mahajan et Vinay est que le déterminant d'une matrice carrée peut être exprimé comme suit :
Soit une matrice avec lignes et colonnes. Pour implémenter le calcul du déterminant de selon la formule ci-dessus, Mahajan et Vinay introduisent un nouveau graphe orienté et pondéré , que nous allons maintenant décrire.
Le graphe possède trois sommets distingués : , et . La construction de permet d'assurer que les chemins de à (respectivement ) dans correspondent aux suites de marches fermées positives (respectivement négatives) dans . Les autres sommets sont des quadruplets avec , et . Ceux-ci représentent des étapes de tentatives de construction de suites de marches fermées. Le sommet représente le cas où des marches fermées ont été construites, et où on cherche à construire une marche fermée commençant par , où
le signe de la suite de marches fermées est ;
est la tête de la marche fermée en cours de construction, c'est-à-dire ;
est le sommet courant, c'est-à-dire ;
est le nombre d'arcs parcourus jusque là, c'est-à-dire .
Le graphe a les arcs suivants.
(1) Un arc de poids 1 de vers chaque sommet de la forme . Ces arcs permettent d'initialiser les suites de marches fermées.
(2) Pour chaque coefficient , chaque et chaque , un arc de poids de vers . Ces arcs correspondent à l'extension de la marche fermée en cours de construction (la marche dans l'explication ci-dessus).
(3) Pour chaque coefficient , chaque , et chaque , un arc de poids de vers . Ces arcs correspondent à la fermeture de la marche fermée en cours de construction, et à l'initialisation d'une nouvelle marche fermée de tête .
(4) Pour chaque coefficient et chaque , un arc de poids de vers . Ces arcs correspondent à la fermeture de la dernière marche fermée de la suite.
Question 26. On considère la matrice suivante :
La figure ci-dessous représente certains sommets du graphe correspondant, ainsi que certains arcs. Indiquer les arcs manquants entre les sommets représentés, ainsi que leurs poids.
Question 27. Soit une matrice carrée avec lignes et colonnes. Montrer que si est une marche fermée dans , alors
est un chemin dans pour tout et tout .
En déduire qu'à chaque suite de marches fermées positive dans correspond un chemin de à dans .
On peut démontrer que les chemins de à dans sont en fait en bijection avec les suites de marches fermées positives dans . Dans toute la suite, on admet ce résultat ainsi que le résultat analogue pour les chemins de à dans et les suites de marches fermées négatives dans .
Nous ne construirons pas le graphe mais travaillerons de manière implicite avec celui-ci. Afin de calculer le déterminant de la matrice en utilisant la formule de Mahajan-Vinay, nous allons calculer la somme des poids des chemins de vers et dans . Soit la fonction qui à chaque sommet de associe la somme des poids des chemins de à dans .
Nous allons commencer par calculer la valeur de pour l'ensemble des sommets de la forme . On remarque que les sommets du graphe peuvent être organisés en couches selon la valeur du dernier entier. Formellement, la couche de est l'ensemble des sommets de de la forme .
Question 28. Exprimer la valeur de en fonction des valeurs de la couche , c'est-à-dire des .
Implémentation
On veut représenter pour chaque de la forme . Pour cela, on suppose donnés les types et fonctions C suivants.
Un type Fourtable.
Une fonction Fourtable *create (int n). Un appel create(n) alloue dans le tas une valeur de type Fourtable et renvoie un pointeur t vers celle-ci. La valeur ainsi créée a la taille nécessaire pour enregistrer les valeurs de lorsque est une matrice . Les valeurs contenues dans *t sont toutes initialisées à 0 . On supposera que free( t ) a une complexité en .
Une fonction void write(Fourtable *t, int val, int , int , int , int i) qui enregistre dans *t l'entier val comme valeur correspondant au sommet .
Une fonction int read (Fourtable *t, int , int , int , int i) qui renvoie la valeur correspondant au sommet dans .
On suppose de plus que les fonctions read et write ont une complexité en , et que la fonction create a une complexité en , où n est la valeur donnée en argument.
Notons que ne dépend que de et de la dimension de la matrice .
Question 29. Écrire une fonction Fourtable *initialise (int n) telle que initialise(n) renvoie un pointeur vers un Fourtable contenant les valeurs de pour tous les sommets de la couche 0 de , où A est une matrice .
On attend une complexité en pour cette fonction, sans la justifier.
Question 30. Écrire une fonction Fourtable *remplit (int n , int ) qui prend en entrée la représentation linéarisée A d'une matrice de dimension , et renvoie un pointeur vers un Fourtable contenant les valeurs de pour tous les sommets de la forme avec , et .
On attend une complexité pour cette fonction, qu'il faudra justifier.
Question 31. Écrire une fonction int determinant (int n , int ) qui prend en entrée la représentation linéarisée A d'une matrice de dimension et renvoie son déterminant. On veillera à libérer correctement la mémoire allouée dans le tas.
On attend une complexité en pour cette fonction, qu'il faudra justifier.
Partie III : Méthode algébrique et probabiliste pour les couplages parfaits
Cette partie concerne un algorithme qui teste si un graphe possède un couplage parfait, c'est-à-dire un couplage qui couvre tous ses sommets. Elle est à composer dans le langage C . On pourra réutiliser le matériel de la partie précédente.
On ne considère que des graphes non orientés (voir page 3 ). Un tel graphe d'ensemble de sommets est représenté par sa matrice d'adjacence , de dimension , et dont les coefficients sont donnés par
Nous allons utiliser des méthodes algébriques, basées sur le déterminant de la matrice de Tutte. La matrice de Tutte d'un graphe est une matrice symbolique, et son déterminant est un polynôme réel à plusieurs variables. Un polynôme réel à variables est une somme finie de monômes, c'est-à-dire de termes de la forme avec et . Lorsque , la variable est omise dans . Par exemple, le monôme est noté .
Considérons un graphe non orienté dont l'ensemble de sommets est . La matrice de Tutte de est une matrice dont les éléments sont des monômes sur l'ensemble de variables . Les coefficients de sont donnés par
Un théorème de Tutte énonce que possède un couplage parfait si, et seulement si, le déterminant de est différent du polynôme nul (c'est-à-dire du polynôme dont toutes les valeurs sont 0.
Une partie du problème consiste donc à décider si un polynôme est nul ou non. Nous allons implémenter un algorithme probabiliste qui teste si un polynôme s'annule en un certain nombre de points choisis aléatoirement.
Dans la suite, on suppose donnée une fonction int rand_range(int n) qui prend en entrée un entier et renvoie un entier tiré aléatoirement entre 0 et (inclus) selon la distribution uniforme. On suppose que cette fonction s'exécute en temps constant.
On suppose que l'instruction suivante, qui crée un tableau d'entiers t de longueur m , s'exécute en temps :
int t [m];
Question 32. Écrire une fonction int tirage_tutte(int n , int ) qui prend en entrée la représentation linéarisée A d'une matrice d'adjacence de dimension , et renvoie le
déterminant d'une instantiation de la matrice de Tutte du graphe représenté par obtenue en tirant aléatoirement les valeurs des variables dans l'ensemble . On attend une complexité en pour cette fonction, sans la justifier.
On va utiliser la fonction définie ci-dessus pour décider si un polynôme réel à plusieurs variables est nul ou non. On se propose d'appliquer le lemme de Schwartz-Zippel. Ce résultat permet, pour un polynôme non nul , de borner le nombre de zéros de (dans un ensemble fini donné) en fonction du degré total de (et de la taille de cet ensemble). Le degré total d'un monôme est la somme . Le degré total d'un polynôme est le degré total maximal des monômes qui le composent.
Soit un polynôme réel non nul à variables et de degré total , et soit un sous-ensemble fini non vide de . On note la probabilité pour que s'annule en , où sont des réels tirés aléatoirement dans , de manière uniforme et indépendante. Le lemme de Schwartz-Zippel énonce que
On souhaite obtenir un algorithme probabiliste décidant si un graphe possède un couplage parfait. En s'aidant du lemme de Schwartz-Zippel, on pourra assurer la correction de cet algorithme et en borner l'erreur. On pourra utiliser la fonction définie lorsque l'entête <math.h> est incluse.
Question 33. Écrire une fonction
bool parfait (int n , int , int p )
qui prend en entrée la matrice d'adjacence linéarisée A d'un graphe ayant n sommets, et décide si possède un couplage parfait avec une probabilité d'erreur inférieure à , faudra justifier.
On attend une complexité en , qu'il faudra justifier.
Fin du sujet.
X ENS Informatique C MPI 2025 - Version Web LaTeX | WikiPrépa | WikiPrépa
