Deug MASS - Cours d'Algorithmique: Comment abstraire un problème

Exemple du carrefour:

Tableau des itinéraires incompatibles:

	AB	AC	AD	BA	BC	BD	DA	DB	DC	EA	EB	EC	ED
AB					1	1	1			1
AC						1	1	1		1	1
AD										1	1	1
BA
BC	1							1			1
BD	1	1					1				1	1
DA	1	1				1					1	1
DB		1			1							1
DC
EA	1	1	1
EB		1	1		1	1	1
EC			1			1	1	1
ED

Coloration de graphe:

Ce tableau définit un graphe, qu'il s'agite de colorier, c'est à dire attribuer à chaque sommet une couleur de façon que deux sommets liés par une arête (c'est à dire dans ntre cas deux itinéraires incompatibles) soient de couleur différente. Nous utiliserons pour cela une heuristique gloutonne, qui consiste à colorier avec une couleur tant qu'on peut avant d'utiliser une autre couleur. On obtient dans ce cas une coloration en 4 couleurs.

étape

AB

AC

AD

BA

BC

BD

DA

DB

DC

EA

EB

EC

ED

1

*

*

*

*

*

*

2

*

*

*

3

*

*

4

*

*

Retour sur le problème:

En revenant maintenant au problème, il est possible d'affiner notre solution en la complétant sans la remettre en question. Noter les itinéraires qui peuvent être dans plusieurs classes: ils pourront circuler pendant plusieurs cycles de nos feux de trafic. Ainsi BA, DC et ED peuvent circuler tout le temps, EA est compatible avec les classes 3 et 4 et AD est compatible avec la classe 3. Est ce que la coloration trouvée est minimale? On peut essayer de répondre à cette question en remarquant qu'une k-clique (graphe à k sommets 2 à 2 connectés) nécessite k couleurs. Donc si notre graphe contient une 4-clique, il faut 4 couleurs pour le colorier et notre solution est minimale.

Explicitation de l'algorithme:

1. NC := {};
2. Pour chaque sommet s non colorié de V faire:
3. si v est compatible avec tous les éléments de NC alors:
4. NC := NC U {v};
5. classer v parmi les sommets coloriés;

Puis on va chercher à expliciter, en choisissant une représentation de nos données, c'est à dire en définissant un type de données abstrait, la ligne 3, puis les lignes 2 et 5 de notre algorithme.

Exercices

Le tournoi de foot

On désire organiser un tournoi entre 6 équipess de football: Castelnau, Jacou, Lunel, Montpellier, Nimes, Pézenas. Chaque équipe ne peut faire qu'un match par semaine, et 2 équipes ont déjà joué des matches: Castelnau contre Montpellier et Pézenas, et Montpellier contre Lunel et Nimes.

En s'inspirant de l'exemple du carrefour, trouver un algorithme pour résoudre ce problème. Le tournoi doit durer le moins de semaines possible. On commencera par abstraire le problème sous forme d'un graphe où chaque sommet représente un match à jouer: que doivent représenter les arêtes pour que le problème se ramène à une coloration de graphe? Examiner le cas de tournoi symétrique ou non.

Trouver la fausse pièce

Les algorithmes ne sont pas faits que pour les ordinateurs, mais peuvent être appliqués à des instruments aussi étranges que la balance Roberval, par exemple.

On dispose d'une balance Roberval et d'un tas de N=1000 pièces de monnaie, dont une est fausse et pèse plus lourd que les autres. Il est demandé de la trouver en faisant le moins d'opérations possibles. Donner une estimation du nombre d'opérations nécessaires en fonction de la taille N du tas. Une balance Roberval possède 2 plateaux, et indique si ce que l'on a mis sur les plateaux a le même poids ou non. Comment adapter l'algorithme si l'on ne sait pas si la fausse pièce est plus lourde ou plus légère?