Résumé de cours Algorithmique et complexité

ViaRézo
24 janvier 2019

1 Graphes Le parcours en profondeur

C'est quoi ? Principe : on prend toujours le premier noeud non exploré parmi
les voisins. En clair, on ne revient en arrière que quand on est obligé,
Un graphe, c'est un ensemble de points (des sommets), reliés entre quand on est au bout d'une série de noeuds.
eux ou pas. Les liaisons (les arêtes) peuvent aussi n'être que dans un Complexité : La complexité est en O(|E| + |V |), ce qui vaut souvent
sens : on dit alors que le graphe est orienté. Elles peuvent aussi être O(|E|).
pondérées (à chacune on aecte une valeur). On note souvent l'ensemble Implémentation : L'implémentation utilise une pile, ou de la récursivité.
des sommets V, celui des arêtes E et leurs cardinaux respectifs |V| et
|E|. Un peu de vocabulaire :
Non-orienté Orienté Description Le parcours en largeur
Chaîne Chemin Une suite de sommets reliés entre eux
Cycle Circuit
Principe : on explore tous les voisins, puis on continue. En clair, on
Une suite de sommets qui boucle
Connexe Fortement connexe
revient en arrière autant que possible.
Se dit d'une partie du graphe,
ou du graphe lui même.
Complexité : La complexité est en O(|E| + |V |), ce qui vaut souvent
Cela signie qu'il y a un chemin
O(|E|).
de chaque sommet vers chaque autre.

Un graphe qui est à la fois non-orienté, connexe et sans cycle est Implémentation : L'implémentation utilise une le.
appelé un arbre.
Un graphe est dit complet si tous les sommets sont reliés entre eux :
|V |(|V |−1)
|E| = 2 Utilisations des parcours

Existence d'un plus court chemin Voici quelques utilisations des parcours :
 Pour construire une chaîne ou un chemin entre deux sommets
On se place dans le cadre d'un graphe, orienté ou pas, dont les arêtes (décision + construction)
sont pondérées par des nombres, réels par exemple. La longueur d'un  Pour détecter les composantes connexes (un parcours permet
chemin est la somme des poids des arêtes. On peut prouver qu'il existe d'explorer une composante connexe).
un plus court chemin ssi il n'y a pas de cycle/circuit de longueur néga-  Pour détecter les cycles (ssi on visite deux fois un même sommet,
tive. Un tel cycle/circuit est dit absorbant. il y a un cycle).
1
Algorithme de Dijkstra Algorithme de Prim
Principe : on prend le sommet le plus proche non encore visité, Culture : Cet algorithme repose sur la notion de cocycle. Un cocycle

puis on vérie si on peut utiliser le parcours actuel pour améliorer le est un ensemble d'arêtes séparant deux composantes d'un graphe (rien

meilleur parcours connu jusqu'à présent. à voir avec un cycle !). Pour créer un arbre couvrant minimal, il faut

Complexité : La complexité est en O(|E|×C +|V |×C _ ), relier une partie connexe au reste des points non encore reliés : on peut

O(|V | ) avec une liste d'adjacence, et O(|E| + |V | × log |V |) en utilisant

update extract min
2 démontrer qu'une arête de poids minimal entre ces deux parties sera

un tas de Fibonacci.
Principe : On crée un ensemble de sommets reliés entre eux par des
nécessairement dedans. D'où :

Implémentation : on utilise une liste de parents pour se souvenir depuis

quel sommet on a accédé à un sommet donné, et une liste de distances. arêtes, qui va former un arbre A. Au départ, il ne contient qu'un som-
Il faut penser à donner une convention pour les sommets qui sont à met et aucune arête. Puis, on ajoute le sommet voisin le plus proche
une distance innie! de notre arbre : on l'ajoute, ainsi que l'arête qui le relie à l'arbre, à
Inconvénients : Ne fonctionne pas avec des coecients négatifs, et ne l'arbre. On s'arête quand il n'y a plus de sommets à ajouter. En fait,
permet pas de détecter les cycles/circuits. c'est quasiment la même chose qu'un Dijsktra, du point de vue com-
plexité!
Complexité : Même chose que pour Dijkstra : O(|V | ) avec une liste
2

d'adjacence, et O(|E| + |V | × log |V |) en utilisant un tas de Fibonacci.

Algorithme de Ford-Bellman .
Principe : on calcule le chemin le plus court depuis n'importe quel Implémentation : Même chose que Dijsktra, à nouveau :p
sommet jusqu'à l'arrivée utilisant au plus i arcs, pour i entre 0 et |V |−1.
Pour i = 0, le calcul est simple, et après on se sert des résultats stockés Algorithme de Kruskal
au préalable. Pour rappel, la formule de récurrence : Culture : Cet algorithme repose sur la notion de cycle. Pour créer un
  arbre couvrant minimal, il faut casser les cycles : on peut démontrer
M [i, v] = min M [i − 1, v], min (M [i − 1, u] + ω((v, u))) qu'une arête de poids maximal au sein d'un cycle sera nécessairement
u∈V

Principe : On ajoute l'arête de poids minimal ,

exclue. D'où :

Complexité : O(|V | ), car on remplit un tableau de taille |V | , et chaque

3 2
puis on recommence jusqu'à ce que ça ne soit plus possible.
qui ne crée pas de cycle

case demande de l'ordre de |V | opérations. Implémentation : c'est de Complexité : O(|E| × log |E|), soit dans le cas où |E| ≈ |V | , ce qui est
la programmation dynamique! On préférera une matrice d'adjacence
2

pour implémenter le graphe, qui permet d'accéder facilement au poids souvent réalisé : O(|V | × log |V |).
2

des arêtes. Avantage : marche y compris avec poids négatifs, et détecte Implémentation : penser à enregistrer, et mettre à jour la composante
les circuits absorbants (distance de t à t négative). Inconvénient : com- connexe de chaque sommet pour éviter de créer des cycles! ça a un
plexité plus grande que pour Dijkstra, même si elle reste polynomiale. petit nom : c'est la structure union-nd.
Clustering
Problèmes d'arbre couvrant de poids minimal
L'algorithme de Kruskal considère des arêtes de plus en plus lourdes,
Le problème est donné ainsi : Pour un graphe pondéré donné, trouver donc les dernières arêtes qu'on prend sont chères, mais peu intéres-
un sous-graphe en enlevant des arêtes tel que le sous graphe soit un santes. Et si on ne les prenait juste pas? Cela permet de créer des
arbre, et la somme des pondérations des arêtes, son poids, soit minimal. catégories éloignées les unes des autres. On appelle ça du clustering.
2
De manière plus propre, on partitionne notre ensemble de sommets, et 2 Structures et mémoire
pour deux ensembles on cherche à maximiser le poids de l'arête entre
ces deux parties avec un poids minimal. Kruskal permet de trouver une Tas binaire
solution exacte à ce problème. Un tas binaire est un arbre, où la racine n'a que deux successeurs,
les successeurs en question n'ont que deux successeurs autres que la
racine, etc...
Problème de ot Ce qui nous intéresse, c'est la propriété suivante : sur chaque noeud la
Le problème de ot se dénit sur un graphe orienté et pondéré avec valeur aectée est plus petite que celle de ses enfants.
deux sommets particuliers : la , et le . La source n'a pas On l'implémente avec un tableau qui représente l'arbre parcouru étage
d'arête entrante, et le puits n'a pas d'arête sortante. Les arêtes sont
source puits
par étage : le premier élément est la racine, les deux suivants l'étage
pondérées par deux valeurs : une capacité, et un ot (qui ne peut pas de profondeur 1, et ainsi de suite... Ainsi le noeud i a pour enfants les
excéder la capacité). noeuds 2i + 1 et 2i + 2.
Le problème est de trouver la bonne pondération en ot telle que tout Ajouter ou retirer un élément n'est pas trivial : à chaque fois, on fait
le ot entrant d'un sommet soit égal au ot sortant du même sommet. une opération qui consiste à échanger un parent avec le plus petit de
ses enfants, et on recommence au niveau de l'enfant qui a été échangé.
Résolution mathématique Table de hachage
On peut démontrer que la valeur du ot maximal est égale à la valeur Une table de hachage est une petite astuce pour stocker de manière
de la coupe de capacité minimale. Une coupe est une partition des particulièrement ecace des couples (clé, valeur). Le principe est le
sommets du graphe en deux parties, l'une contenant s et l'autre t. suivant : on fait un tableau de taille xe N . Chaque case contient des
La capacité d'une coupe est la somme des capacités des arêtes qui tableaux de taille variable, pour stocker les couples.
relient des sommets qui vont de la partie contenant la source à la partie Comment fait-on pour déterminer dans où on range nos éléments?
contenant le puits. On utilise une fonction dite de hachage, à valeurs entières entre 0 et
N − 1. On range chaque valeur dans le tableau de taille variable à la
case correspondant à la valeur de la fonction de hachage sur la clé du
Algorithme de Ford-Fulkerson couple à ranger. En paramétrant ça bien, on atteint en moyenne des
complexités assez intéressantes!
Principe : On trouve une chaîne augmentante (le ot des arêtes dans
le bon sens peut être augmenté, et celui de celles dans le mauvais sens
peut-être diminué, et on applique l'amélioration. Cela marche... pour Implémentation de Graphe
des capacités dans N.
Complexité : Dans N, O((|V | + |E|) × Φ ) Φ est le ot maximal. Ici, on considère que les sommets du graphe sont numérotés de 0 à
Implémentation : pour rechercher les chaînes augmentantes, on adapte . Première méthode : liste d'adjacence, on stocke dans chaque case
max
n−1
le parcours en profondeur. d'une liste la liste des voisins d'un sommet donné. Au besoin, on stocke
Inconvénients : Ne marche pas pour des coecients dans R. La un couple (voisin, pondération de l'arête).
complexité dépend du ot maximal. Voici les diverses complexités :
 Encombrement mémoire : O(|E| + |V |)
3
  Parcours des voisins d'un sommet u : O(deg(u)) Tas binaire
 Vérier existence d'un arc : O(deg(u)) Extract_min : O(log n) Update : O(log n) Add : O(log n) Del : O(log n)
 Accès au poids : O(deg(u))
 Ajout d'un arc : O(1) Table de hachage
 Suppression d'un arc en O(deg(u))
Deuxième méthode : on fait une matrice de booléens, l'indice (i, j) Get : O(h) Set : O(h) Add : O(h) Del : O(h)
indiquant l'existence d'un arc de i à j. On peut stocker les pondérations Complexités en moyenne, où h est le temps de calcul de la fonction
dans la matrice, mais il faut convenir d'une valeur pour indiquer la non- de hachage.
existence d'un arc.
Voici les diverses complexités :
 Encombrement mémoire : O(|V | ) 2 Problème du rendu de monnaie
 Parcours des voisins d'un sommet u : O(|V |) On dispose d'un ensemble de valeurs de pièces, et on veut rendre
 Vérier existence d'un arc : O(1) une certaine somme avec le moins de pièces possible. Ce problème est
 Accès au poids : O(1) intéressant car pas si simple : l'algorithme glouton (on rend la plus
 Ajout d'un arc : O(1) grosse pièce possible puis on s'occupe du reste) ne donne pas toujours
 Suppression d'un arc en O(1) le nombre de pièces optimale et va même jusqu'à bloquer sur certains
Conclusion : la matrice d'adjacence prend beaucoup de place en mé- systèmes de monnaie. Un système sur lequel l'algorithme glouton est
moire, mais marche très bien si il faut modier des graphes. Pour des optimal est appelé canonique. Notre système l'est.
algorithmes de parcours, la liste d'adjacence peut quand même être Exemple de système non canonique : (4, 3, 2)
plus intéressante.
Programmation dynamique
Complexités des structures de stockage de données
Pour terminer, un petit rappel sur les complexités des opérations de Principe
base des diverses structures : Qu'est ce que la programmation dynamique? En gros, c'est utiliser
de la mémoire (complexité spatiale) pour stocker des résultats intermé-
Liste (pas forcément triée) diaires, ce qui évite des calculs redondants, et améliore la complexité
Get : O(n) Set : O(n) Add : O(1) en amorti Del : O(n) temporelle. L'algorithmique montre souvent des compromis entre ces
deux complexités.
Dans le cas du problème de rendu de monnaie, on peut calculer le
Liste triée nombre de pièces optimal pour rendre de 1 à n − 1 euros, juste pour
Get : O(log n) Set : O(log n) Add : O(n) Del : O(n) récursif. avoir le résultat pour n euros. Et pour n − 1, on fait pareil : c'est
C'est une méthode assez ecace!
Liste chaînée
Get : O(n) Set : O(n) Add : O(1) Del : O(n) Utilisation, exemples
Liste chaînée triée Comment détecter les problèmes où ce principe s'applique? En
général ce sont les problèmes où une la solution optimale peut être
Get : O(n) Set : O(n) Add : O(n) Del : O(n) calculée à partir de solutions optimales de sous problèmes. Le problème
4
du plus court chemin dans un graphe en est un exemple, le calcul de Cependant, tout n'est pas calculable par une MT! Il existe des pro-
la distance d'édition en est un autre (c'est le truc qu'on a vu avec blèmes dits indécidables : le problème de l'arrêt par exemple.
les séquences d'ADN). Il faut que les sous-problèmes On dénit alors la classe des problèmes qui peuvent être résolus sur
. Mathématiquement, ça se traduit par l'existence d'une une machine de Turing en temps polynomial, la fameuse classe P. En
ne soient pas

formule de récurrence, ou d'induction (généralisation du principe de particulier, cette classe ne change pas lorsqu'on ajoute des rubans/têtes
indépendants

récurrence), mais ce n'est pas susant! Par exemple, il n'y aucun de lecture, ou un alphabet ni plus complexe que {0, 1} à la machine
intérêt à programmer dynamiquement le calcul de la factorielle. Par de Turing.
contre, avec Fibonacci, on passe de O(φ ) à O(n).
n

Attention! Ces algorithmes ne permettent pas souvent de trouver la Classe NP

solution! Il faut remonter dans à la solution en étudiant les variations
de coût entre les diérents sous-problèmes. Parfois vérier qu'une proposition est bien solution est facile, beau-
coup plus que trouver la dite proposition. Ce sont les problèmes NP.
Pro tip vu en TD : pour des problèmes intrinsèquement multiplicatifs La dénition exacte est : l'algorithme de vérication s'exécute en temps
(problème du banquier), on peut passer au log. Le souci, c'est que ça polynomial.
peut créer des poids négatifs : on ne peut plus utiliser Dijkstra... Dans le cas du problème de décision, l'algorithme de résolution est un
algorithme de vérication : il produit une solution et répond oui au
problème de décision.
3 Théorie de la complexité Mais la question qui se pose aujourd'hui est :
Dénitions P = NP?

En théorie de la complexité on parle de problèmes et d'instances : C'est une question à un million de dollars. Littéralement. Et ce n'est
le problème est le prototype, le moule : un ensemble d'objets (Graphe pas le plus impressionnant : tout le système de cryptographie bancaire
avec un sommet départ et un sommet arrivée par exemple), et une actuel repose sur la conjecture non prouvée P 6= N P . Cette conviction,
question peut qu'on se poser sur chacun d'eux. L'instance comprend heureusement, est la plus répandue dans le monde de la recherche in-
les objets concrets sur lesquels on va se poser la question du problème. formatique.
On distingue trois types de problèmes : décision, construction, et Attention cependant : ce n'est pas parce qu'un algorithme est P qu'il
optimisation. est forcément rapide! Quand on parle d'algorithme polynomial, non
seulement on néglige les constantes multiplicatives, mais en plus on a
aucune condition sur la puissance. En pratique, on préférera largement
Machine de Turing du O (1.01 ) à du O n
.
n 4

Une machine de Turing est un modèle théorique de calculabilité. Réductions de problèmes

Celle-ci est composée d'un ruban sur lequel on inscrit des 0 et des 1,
une tête de lecture/écriture, ainsi qu'une table d'états, qui indique à la La réduction de problème traduit l'idée qu'un problème est plus dur
tête que faire suivant l'état dans lequel elle se trouve. qu'un autre. On dit que P se réduit à P si on est capable de trouver
La thèse de Church-Turing, aujourd'hui largement acceptée dans le un algorithme qui résout P à partir de celui qui résout P .
1 2

monde scientique, stipule que tout système de calcul physique peut Un problème est dit NP-dicile si tout problème NP se réduit à lui.
polynomial 1 2

être simulé par une machine de Turing. Ce type de considérations a Un problème est dit NP-complet s'il est NP-dicile et NP.
mené à la notion de Turing-complétude. Remarque : si un problème est NP-dicile et P, alors automatiquement
5
P=NP. Inutile de préciser que je suis incapable de vous donner un à devenir plus coûteuse qu'une solution déjà essayée, et on continue sur
exemple! de nouvelles bases. Cela se représente bien sous la forme d'un arbre.
En 1971, Cook prouve que le problème SAT (pour satisabilité d'une Complexité : Dépend du problème, et surtout de la méthode choisie
formule booléenne) est NP-complet. Il sut alors de montrer que SAT pour séparer les solutions. Dans certains cas, pas beaucoup mieux que
se réduit à un problème donné, et que le dit problème est NP pour la force brute, dans d'autres, c'est beaucoup plus ecace. Intérêt :
prouver que ce dernier est NP-complet. S'applique à beaucoup de problèmes (Stable, Recherche de chemin...),
En particulier, c'est ce que l'on fait pour prouver que Stable et D-HAM solution optimale.
sont NP-complets.
Stable : trouver un ensemble de sommets non reliés entre eux dans un Branch & Bound
graphe.
D-HAM : dans un graphe orienté donné, trouver un chemin qui passe Principe : On fait deux choses : Branch c'est explorer l'arbre des
une et une seule fois par chaque sommet. solutions, Bound c'est borner la solution recherchée, pour jeter les
Tout cela permet de créer une hiérarchie des problèmes. branches non prometteuses. Là où ça devient intéressant, c'est que les
bornes peuvent être dynamiques : voir exemple de TSP où on dénit
Le problème du voyageur de commerce une borne inf en considérant les arêtes de poids minimal.
Complexité : Meilleure que celle du Backtracking, mais ça demande
Le problème s'énonce ainsi : étant donné un graphe, quel est le plus plus de réexion! Et ça dépend encore du problème et de comment on
court cycle qui passe par tous les sommets une et une seule fois? On le traite.
s'intéresse ici à la question de savoir s'il existe un chemin d'une lon- Intérêt : Idem que précédemment.
gueur plus petite qu'une borne B donnée.
Ce problème est NP : vérier qu'un cycle ne passe bien qu'une seule
fois par chaque sommet et que sa longueur est inférieure à la borne B Méthodes de résolution approchées pour NP-
s'eectue en temps polynomial.
Pour démontrer qu'il est NP-dicile (donc NP-complet), on peut dé- diciles
montrer que le problème du cycle Hamiltonien se réduit à celui-ci. Heuristiques
Principe : On approxime la solution en utilisant un algorithme en
Méthodes de résolution exactes pour NP-diciles temps polynomial.
Force Brute Complexité : Bah polynomiale...
Intérêt : Ce genre d'algorithme permet de trouver un compromis entre
Principe : Tester toutes les possibilités rapidité et précision.
Complexité : Délirante
Intérêt : Généralement simple à implémenter et étudier. Sert parfois
dans les démonstrations théoriques. Exemple d'heuristique
L'exemple est donné pour le problème TSP (Voyageur de commerce)
Backtracking sur un graphe complet et où les distances respectent l'inégalité trian-
gulaire, en pratique c'est souvent le cas. L'algorithme heuristique est
Principe : On construit petit à petit les solutions. On peut proposer le suivant : on recherche un arbre couvrant polynomial par Prim ou
une amélioration, qui consiste à jeter la solution dès qu'elle commence Kruskal, puis on numérote ses sommets avec un cycle eulérien, i.e. qui
6
passe une et une seule fois par chaque arête et on les visite dans l'ordre. Exemple de métaheuristique 2 : Recuit simulé
L'existence d'un cycle eulérien est équivalente à ce que tous les som- Pour cet algorithme le parcours choisit UNE solution aléatoire dans
mets aient un degré pair. Ici, on garantit l'existence du cycle eulérien le voisinage, et s'y déplace si elle est meilleure. Mais si elle est moins
en dédoublant les arêtes. bonne, il y a aussi une probabilité décroissante avec le temps que l'on
La solution donnée par cet algorithme est au pire deux fois pire qu'une s'y déplace. Cette probabilité s'exprime en terme de température :
solution optimale. La démonstration utilise le fait que si on enlève une au départ la température est élevée, puis elle baisse et avec elle la
arête à une solution optimale, on obtient un arbre couvrant. On dit que probabilité d'accepter une solution moins bonne. L'algorithme s'arête
notre algorithme est une 2-approximation. quand le système se ge (la température est en dessous d'un certain
seuil).
Métaheuristiques De manière contre-intuitive, cet algorithme est plus ecace que le
précédent. La raison est simple : il permet de sortir de minima locaux,
Principe : On munit l'espace des solutions d'éléments de topologie, de temps en temps.
puis on l'explore, à l'aide d'algorithmes polynomiaux (de parcours par Cependant, son ecacité est aussi soumise au choix de la fonction qui
exemple), pour essayer de minimiser une certaine fonction d'évaluation. assure la décroissance de la température (en général une exponentielle
Complexité : polynomiale. Attention! Il faut que nos fonctions liées à décroissante), et on a aucune garantie sur le résultat, puisque c'est un
la topologie ne soient pas trop lourdes, sinon cela ne sert à rien. Le algorithme probabiliste!
principe est justement qu'à partir d'une solution il est facile de passer
à une solution proche, mais légèrement meilleure.
Intérêt : C'est une puissante variante des algorithmes heuristiques, qui 4 Conclusion
est très générale.
Inconvénients : Pas toujours facile d'expliciter la fonction de voisinage. On oublie pas de faire la diérence entre complexité d'un problème,
et complexité d'un algorithme! L'un est purement théorique, alors
Exemple de métaheuristique 1 : Hill climbing que l'autre est pratique (dépend de l'implémentation des structures de
données).
Pour cet algorithme on parcourt l'espace des solutions à partir d'un
point donné, puis "selon la pente" jusqu'à ce que l'évolution de la qua- écrit par Alexandre Blanchon pour ViaRézo.
lité de la solution soit négligeable. En termes mathématiques, on suit remplacer ledecours
Ce résumé cours est un outil qui n'a en aucun cas vocation à
le gradient de la fonction d'évaluation. En pratique, une manière pas venir râler si vous d'Algorithmique
avez fait une
& Complexité. Merci de ne PAS
erreur au partiel ou autre car vous
très propre mais simple de faire cela est de calculer tout le voisinage avez recopié quelque-chose de faux provenant de ce document.
du point de départ, dans ce voisinage de choisir le point qui réalise le
minimum de la fonction d'évaluation, puis de recommencer.
L'inconvénient majeur de cette méthode est qu'elle va souvent rester N'hésitez
Mail :
pas à me contacter si vous constatez une coquille!
coincée dans un minimum local. Il est donc important de bien dénir Telegram : [Link]@[Link]

la notion de voisinage! Un voisinage trop grand entraîne de grandes @SeaSalt_VR

pertes en temps, et trop petit il va faire que l'algorithme reste plus

facilement coincé...
En pratique, les problèmes sont très irréguliers et cet algorithme a des
performances limitées.
7