Operations sur un ensemble

Le tableau suivant presente les principales operations de base sur un ensemble ainsi que leur complexité selon le type de repr´esentation m´emoire. Le choix d’une structure de donn´ees adaptee est un facteur `a prendre en compte lors de la conception d’un algorithme. Nous nous pla¸cons dans la configuration du pire cas o`u |S| = |E| = n.
L’initialisation consiste `a mettre en place en m´emoire la structure de donn´ees correspon-dante. Pour le TB, il faut initialiser toutes les cases a` z´ero ce qui impose une complexit´ en O(n). Pour la LC, il suffit d’´ecrire NULL dans un pointeur [O(1)].
La s´election permet de prendre un el´ement quelconque de l’ensemble ou de tester si l’en-semble est vide. Pour la LC il suffit de s´electionner le premier el´ement de la liste, par contre pour le TB il faut parcourir les cases jusqu’`a trouver ´eventuellement un el´ement non nul [O(n)].
La recherche permet de savoir si un el´ement donn´e est pr´esent dans l’ensemble. Dans un TB il suffit de lire la case correspondante [O(1)], pour une LC il faut parcourir l’ensemble des el´ements pr´esents [O(n)].
La suppresion s’effectue en O(1) pour la LC et le TB. Cependant l’insertion qui technique-ment s’effectue aussi en O(1) pour ces deux structures, pose un probl`eme pour la LC. En effet, si nous voulons maintenir une liste d’´el´ements sans multiplicit´e : {1} ∪ {1} = {1}, il faut avant l’insertion tester la pr´esence de cet el´ement [O(n)]. N´eanmoins, par exemple, si l’on sait que les el´ements sont ins´er´es une seule fois dans la liste, l’insertion peut s’effectuer en O(1).
Le parcours est proportionnel au nombre d’´el´ements presents dans la LC [O(n)] et au nombre de cases allou´ees dans le TB [O(n)].

Representation d’un graphe (E, )

Double tableau – DT
Cette repr´esentation consiste en deux tableaux I et T de taille | |, tels que I (j) est le sommet initial de l’arc num´ero j et T (j) est le sommet terminal de l’arc num´ero j.

Representation d’un graphe (E, )

Tableau de listes chaˆın´ees – TLC
Cela consiste `a prendre un tableau de taille |E| contenant des pointeurs sur des listes chaˆın´ees tel que la i-`eme liste chaˆın´ee corresponde a` (i).
Matrice de bool´eens – MB
Il s’agit de la version bidimensionnelle des tableaux de bool´eens monodimensionnels (1.2.1). La matrice M est telle que Mij = 1 si et seulement si (i, j) est un arc de G. La ligne Mi correspond au tableau de bool´eens monodimensionnel qui repr´esente (i).
Le choix des structures de donn´ees utilis´ees influe sur la complexit´ des programmes et donc sur leur efficacit´.
Exercice 1
D´ecrivez par des diagrammes, comme dans les illustrations qui pr´ec`edent, les repr´esen-tations possibles en m´emoire des graphes de l’exemple 7 (section 1.3.1).

Evaluation de la complexité d’un algorithme

L’algorithme suivant a pour but de rechercher les successeurs d’une partie X d’un en-semble E.
Soit G = (E, ), soit X ⊂ E. On d´efinit l’ensemble des successeurs de la partie X ainsi :
succ(X ) = { y ∈ E | ∃x ∈ X , (x, y) ∈ } = (x) x∈X
De la premi`ere forme de la d´efinition, on d´eduit l’algorithme suivant :
Algorithme 1 : SuccPartie 1
Donn´ees : X ⊂ E,
R´esultat : Y ⊂ E
1 Y ←∅;
2 pour chaque (x, y) ∈ faire
3 si x ∈ X alors Y ← Y ∪ {y};
Selon le choix du type de donn´ees pour X et Y , la complexit´ de l’algorithme pr´ec´edent peut varier. Prenons par exemple Y sous forme d’un tableau de bool´eens et X sous forme de liste chaˆın´ee.
On note n = |E| et m = | |.
L’instruction d’initialisation de Y `a la ligne 1 est en O(n). La boucle de la ligne 2 a` 6 est execut´ee m fois. Le test d’appartenance ligne 3 est en O(n) car X est sous forme d’une liste chaˆın´ee, de plus il est execut´ m fois. On comptera donc O(mn) pour la ligne 3. L’ajout d’un el´ement a` un tableau de bool´eens, ligne 4, est en temps constant. On comptera donc pour la ligne 4 : O(m × 1). On peut conclure que la forme de la complexit´ de cet algorithme est en O(n + m + mn + m) = O(mn).
Choisissons maintenant X sous forme d’un tableau de bool´eens. L’instruction de la ligne 3 devient en temps constant O(1) ; le corps de boucle de la ligne 2-6 est en temps constant et est execut´ m fois. L’algorithme est donc en O(m + n) ce qui est bien meilleur que la complexit´ pr´ec´edente.
Evaluez la complexit´ de l’algorithme suivant, inspir´e de la seconde forme de la d´efinition de succ(X ), en supposant que Y est repr´esent´ par un tableau de bool´eens.
Algorithme 2 : SuccPartie 2
Donn´ees : X ⊂ E,
R´esultat : Y ⊂ E
1 Y ←∅;
2 pour chaque x ∈ X faire
3 pour chaque y ∈ (x) faire
4Y ← Y ∪ {y} ;

Graphes orientes et non-orient´es

Le symetrique d’un graphe

Soit G = (E, ). On appelle sym´etrique de G le graphe G−1 = (E, −1) d´efini par :
∀x ∈ E , −1(x) = { y ∈ E | x ∈ (y)}
Il s’agit d’un graphe dont l’orientation des arcs a et´ invers´ee par rapport au graphe initial. Cette notation : −1 est aussi utilis´ee pour repr´esenter la “fonction pr´ed´cesseur”, c’est a` dire la fonction qui a` tout sommet du graphe fait correspondre l’ensemble de ses pr´edecesseurs.

Graphe non-orienté

D´efinition
On appelle graphe non-orient´ sur E un couple G = (E, ) tel que soit un sous-ensemble de { {x, y} | x ∈ E, y ∈ E }. Ainsi est de la forme : {{a, b}, {c, d}, {e, f }, …}. Tout el´ement de : {x, y} est appel´ arˆete du graphe. On dit que l’arˆete {x, y} est adjacente au sommet x et au sommet y. A on peut associer l’application n.o. de E −→ P(E) d´efinie par :
y ∈ n.o.(x) ⇔ {x, y} ∈
Dans tous les cas, (E, n.o.) est un graphe sym´etrique.
Ainsi la donn´ee d’un graphe sym´etrique est ´equivalente a` la donn´ee d’un graphe non-orient´.
Graphe non-orient´ associ´e `a un graphe orient´
Il se peut qu’`a partir d’un graphe orient´e, l’on cherche a` travailler dans un contexte non-orient´. Pour cela nous associons au graphe donn´e (E, ) sa version non-orient´ee (E, )

1 Notions de base 
1.1 Premi`ere d´efinition
1.2 Repr´esentation en m´emoire
1.3 Graphes orient´es et non-orient´es
1.4 Chemins, connexit´e
1.5 Repr´esentation matricielle
1.6 Graphe biparti
2 Arbres et arborescences 
2.1 D´efinitions
2.2 Exemples et applications
2.3 Arbre de poids extr´emum
3 Plus courts chemins 
3.1 D´efinition
3.2 Probl´ematique du plus court chemin
3.3 R´eseaux `a longueurs quelconques (Bellman)
3.4 R´eseaux `a longueurs positives (Dijkstra)
3.5 Graphes et r´eseaux sans circuits
4 Flots et reseaux de transport 
4.1 Mod´elisation du r´eseau de transport
4.2 Algorithme de Ford et Fulkerson
5 Resolution de problemes en intelligence artificielle et optimisation combinatoire 
5.1 Exemple 1 : le probl`eme des 8 reines
5.2 Graphe de r´esolution de probl`eme
5.3 Exemple 2 : jeu du taquin
5.4 Strat´egies de recherche
6 Compl´ements 
6.1 Exploration en profondeur
6.2 Exploration en largeur
Bibliographie