Complexité des algorithmes – notes de cours –

Cours complexité des algorithmes, tutoriel & guide de travaux pratiques en pdf.

Graphes et arbres

Les graphes sont des structures tres courantes en algorithmique. Il sont formes d’entites elementaires que l’on appelle nuds ou sommets. On rajoute entre ces sommets des connexions qui lient deux sommets, soit de maniere non-orientee (on parle alors d’ar^ete, et le graphe est dit non-oriente, voir Fig. 5), soit speciquement d’un sommet vers un autre (dans ce cas la connexion est appelee arc, et le graphe est un graphe oriente, encore appele digraphe, voir Fig. 6).
Un graphe est dit connexe s’il existe toujours un chemin d’un sommet a un autre (on s’autorise, dans le cas des digraphes, a prendre des arcs a rebrousse-poil). Un digraphe est fortement connexe si il existe toujours un chemin d’un sommet vers un autre en respectant le sens des arcs. Un cycle est un chemin qui, partant d’un certain sommet, parcours un certain nombre d’autres sommets et revient au point de depart.
Un arbre est un graphe connexe sans cycle. On peut distiguer dans un graphe une racine qui est un sommet unique. L’existence d’une racine permet d’orienter toutes les ar^etes du graphes de maniere naturelle: on oriente l’ar^ete depuis la racine vers les extr^emites de l’arbre.

Tri

Un algorithme de base pour le calcul de la complexite est le tri. Supposins qu’une liste a trier
se trouve sous la forme d’une liste doublement cha^nee, comme explique au paragraphe1.1.1.
Une premiere methode consiste a parcourir toute la liste, selectionner lelement maximal, le supprimer de la liste courante, puis de l’inserer en t^ete d’une liste a trier. Cette methode demande n operations de recherche sur la liste courante de taille n, puis une operation de suppression, et enn une operation d’insertion. Soit n + 2 operations pour passer d’une liste de taille na une liste de taille n ? 1. Le temps total de calcul est alors, en nombre d’operations, de:
(n + 2) + (n + 1) + (n) + (n ? 1) + :: + 3 = Xi=n
i=1
i + 2 = n2 + 5n
Une methode alternative consiste a utiliser un tas. Le tas se forme sur une structure d’arbre particuliere appelee arbre binaire quasi-complet.
Soit G un arbre non-oriente et muni d’une racine. Appelons pere le voisin d’un sommet qui se trouve du cote de la racine, et ls ses autres voisins. Designons par feuille un sommet qui n’a pas de ls. Appelons niveau d’un sommet la distance, en termes de longueur de chemin, qui le separe de la racine.
Un arbre binaire complet est un arbre dote d’une racine, dont toutes les feuilles sont au m^eme niveau, et dont tous les autres sommets ont exactement deux ls. Un arbre binaire quasi-complet est un arbre complet auquel on a eventuellement supprime un certain nombre de feuilles, mais uniquement \en bas a droite » (voir la Fig. 7). Alors qu’un arbre binaire complet possede 2h+1 ? 1 sommets, ou h represente le niveau des feuilles, un arbre binaire quasi-complet peut avoir un nombre quelconque de feuilles. On ajoute un sommet en placant une feuille a la position inoccupee la plus a gauche sur le dernier niveau incomplet (et eventuellement en commacant un nouveau niveau si necessaire. On retire un sommet en supprimant le sommet le plus a droite du dernier niveau. La Fig. 8 donne toutes les topologies d’arbres binaires quasi-complets de 1 a 16 sommets.
Munissons maintenant chaque sommet de l’arbre d’une valeur numerique. On dira que l’arbre est bien ordonne si la valeur d’un pere est toujours inferieure a celle de ses ls. Un tas est un arbre binaire quasi-complet bien ordonne (voir Fig. 9). Le tas est une structure qui permet pour un ensemble de n elements
(1) d’ajouter un nouvel element en O(log(n) operations,
(2) d’extraire le minimum du tas en O(log(n) operations.
Pour inserer un nouvel element dans un tas, on s’autorise dans un premier temps a violer la regle de bien-ordonnancement pour obtenir un un arbre binaire quasi-complet ayant le bon nombre de sommets. Par exemple, si on introduit un nouveau sommet ayant la valeur 7 a l’arbre de la Fig. 9, on obtient dans un premier temps l’arbre de la Fig. 10, qui est quasi-complet. Ensuite, on retablit le bon-ordonnancement en partant du sommet introduit et en l’echangeant avec son pere si la valeur du pere est superieure. Cette operation retablit le bon-ordre sur le lien pere/ls mais peut eventuellement introduire une violation de la regle de bien-ordonnancement sur le lien grand-pere/pere. On echange dans ce cas les sommets pere/grand-pere, et ainsi de suite eventuellement jusqu’a la racine. Dans le cas le pire, on remonte le chemin jusqu’a la racine, soit O(log(n)) operations. Dans notre exemple, les sommets des valeurs 7 et 14 sont d’abord echanges, puis les sommets des valeurs 8 et 7, pour donner le tas de la Fig. 11.
L’autre operation majeure est l’extraction de la valeur minimale. La valeur minimale se trouve a la racine. Dans un premier temps, comme le montre la Fig. 12, on maintient simplement la structure d’arbre binaire quasi-complet en deplacant le contenu de la derniere feuille (en bas a droite) sur la racine. Cette derniere feuille est donc supprimee. On retablit ensuite le bon ordonnancement de la maniere suivante: le contenu du sommet a mettre a jour est compare a ses deux ls, et est echange avec son ls de valeur minimale. On deplace alors le probleme d’ordonnancement au ls choisi pour l’echange et sa descendance. On continue a echanger les valeur de ce sommet avec le plus petit de ses ls jusqu’a ce que l’arbre soit ordonne, comme le montre la Fig. 13. L’operation se fait en O(log(n)).
Au nal, le tri par tas sur une liste de n element commence par n insertions, suivies de n extractions de la valeur minimale, pour un total de O(n log(n)) operations.

Chemins Euleriens et Hamiltoniens

Le probleme du chemin dit Eulerien est apparu en rapport avec la ville de Konigsberg (aujourd’hui Kaliningrad), dont une carte sommaire est donne en Fig. 14. La question etait de savoir s’il existait une promenade passant une et une seule fois par tous les ponts(representes en brun).
Leonhard Euler a resolu cette question en 1735 en demontrant qu’une telle promenade d’existait pas. Sa demonstration repose sur une representation en graphe du probleme (Fig. 15). Il s’agit alors de trouver un chemin ou un cycle qui passe une et une seule fois par toutes les ar^etes, moyennant un passage eventuel plusieurs fois par le m^eme sommet.
La demonstration d’Euler repose sur la constatation que (1) si un tel chemin ou cycle existe, alors tous les sommets sauf eventuellement les sommets de depart et d’arrivee ont un nombre pair d’ar^etes adjacentes. De plus, (2) tous les sommets non-isoles sont alors dans la m^eme composante connexe du graphe. Euler a demontre que les conditions (1) et (2) etaient egalement susantes pour s’existence d’un tel chemin. Ainsi, la Fig.15 n’a pas de chemin eulerien puisque quatre sommets ont un nombre impair d’ar^etes adjacentes.
Une variante de ce probleme concerne l’existence d’un chemin ou d’un cycle hamiltonien: il s’agit d’un cycle ou chemin sur le graphe qui passe une et une seule fois par tous les sommets. Nous montrons sur un graphe legerement modie (Fig. 16) un chemin eulerien (Fig. 17) et un chemin hamiltonien (Fig. 18). Nous allons voir dans la suite qu’en depit des apparences, le probleme qui consiste a trouver un chemin eulerien est considerablement plus simple que celui du chemin hamiltonien.

Modélisation de la complexité

Cette partie du cours s’inspire essentiellement de [4].

Machines de Turing

Une machine de Turing est un modele simplie d’ordinateur qui permet d’evaluer ce qui est faisable en matiere de calcul. Bien que tres elementaire, elle represente une premiere approche fondamentale pour la theorie de la complexite.
La machine, comme indique sur la Fig. 19, est un ordinateur qui lit et ecrit des symboles sur une bande enregistreuse de longueur innie, et le fait a la position du curseur ou elle se trouve. La machine lit et ecrit un seul symbole a la fois en suivant des regles precises. Ces regles dependent d’un \etat » dans lequel se trouve la machine, ainsi que du symbole qui est lu. La machine possede un nombre ni d’etats.
Formellement, on se donne donc, pour denir la machine de Turing:
un ensemble Q d’etats,
un ensemble de symbole,
un etat initial ,
un symbole distingue t 2 (appele le symbole \blanc »),
un ensemble d’etats naux A Q,
une fonction de transition , de Q dans Qf?1; +1g. Son sens est le suivant:
si la machine est dans l’etat q0 et qu’elle lit le symbole 0 a la position courante du curseur, et en ecrivant (q0; 0) = (q1; 1; « 1), alors la machine va ecrire a l’emplacement du curseur le symbole 1, passe a l’etat q1. Par ailleurs, elle avance le curseur sur la bande d’une case si « 0 = +1 et le recule d’une case si « 0 = ?1.
Dans le cas d’une machine de Turing deterministe, le fonctionnement est le suivant.
On fournit a la machine le probleme initial, par exemple le graphe sur lequel un chemin eulerien ou hamiltonien doit ^etre calcule, ce qui est exprime avec un certain encodage sur les cases 0 a n de la bande de la machine de Turing, et la machine eectue son calcul, et on se demande si on peut garantir que la machine va au bout d’un certain temps repondre par VRAI ou FAUX sur la nature de probleme, par exemple a la question existe t-il un chemin eulerien ou hamiltonien, va t-elle repondre VRAI ou FAUX dans un temps determine.
Si par contre on s’interesse a une machine de Turing non-deterministe, alors on s’autorise, une fois que le probleme a ete ecrit, a rajouter des cases magiques par exemple avant la case 0, qui encode une solution devinee du probleme. Dans le cas d’une question sur l’existence d’un chemin, on pourra fournir l’encodage complet d’un chemin donnant la solution du probleme. La machine verie que les cases magiques fournissent bien une solution au probleme, et repond par VRAI ou FAUX. La question est de savoir si, etant donne un probleme ayant une solution, il existe au moins une aectation des cases magiques qui atteste de l’existence de cette solution en un temps determine. Par exemple, si un chemin eulerien
ou hamiltonien existe dans le graphe, si on fournit a la machine sur sa bande l’encodage du graphe et d’un chemin valide, la machine peut-elle en un temps determine attester la validite de ce chemin?

1 Quelques notions d’algorithmique et complexite elementaire 
1.1 Strutures de calcul
1.1.1 La liste
1.1.2 La pile
1.1.3 La le
1.1.4 Graphes et arbres
1.2 Tri
1.3 Chemins Euleriens et Hamiltoniens
2 Modelisation de la complexite 
2.1 Machines de Turing
2.2 Les classes P et NP
2.3 Le probleme SAT et le theoreme de Levin-Cook
2.4 Autres problemes NP-Complets
2.4.1 3-SAT
2.4.2 VERTEX COVER
2.4.3 CYCLE HAMILTONIEN
3 Un algorithme polynomial pour la programmation lineaire 
3.1 La methode de Khachiyan
4 Le probleme de separation 22
5 Approximation des problemes 
5.1 Classification des algorithmes d’approximation
5.2 La programmation dynamique
5.3 Approximation de multi-flot