Cours algorithmique avancée structures de données élémentaires , tutoriel & guide de travaux pratiques en pdf.

Complexité

Définition 2 (Complexité). La complexité d’un algorithme est la mesure du nombre d’opérations fondamentales qu’il effectue sur un jeu de données. La complexité est exprimée comme une fonction de la taille du jeu de données.
Nous notons Dn l’ensemble des données de taillen et T (d) le coût de l’algorithme sur la donnéed.
Complexité au meilleur : Tmin(n) = mind2Dn C(d). C’est le plus petit nombre d’opérations qu’aura à exécuter l’algo-rithme sur un jeu de données de taille fixée, ici à n. C’est une borne inférieure de la complexité de l’algorithme sur un jeu de données de taillen.
Complexité au pire : Tmax(n) = maxd2Dn C(d). C’est le plus grand nombre d’opérations qu’aura à exécuter l’algo-rithme sur un jeu de données de taille fixée, ici à n.
Avantage : il s’agit d’un maximum, et l’algorithme finira donc toujours avant d’avoir effectué Tmax(n) opérations.
Inconvénient : cette complexité peut ne pas refléter le comportement « usuel » de l’algorithme, le pire cas pouvant ne se produire que très rarement, mais il n’est pas rare que le cas moyen soit aussi mauvais que le pire cas.
Complexité en moyenne : Tmoy(n) = åd2Dn C(d) . C’est la moyenne des complexités de l’algorithme sur des jeux de jDn j données de taillen (en toute rigueur, il faut bien évidemment tenir compte de la probabilité d’apparition de chacun des jeux de données).
Avantage : reflète le comportement « général » de l’algorithme si les cas extrêmes sont rares ou si la complexité varie peu en fonction des données.
Inconvénient : la complexité en pratique sur un jeu de données particulier peut être nettement plus importante que la complexité en moyenne, dans ce cas la complexité en moyenne ne donnera pas une bonne indication du comportement de l’algorithme.
En pratique, nous ne nous intéresserons qu’à la complexité au pire et à la complexité en moyenne.
Définition 3 (Optimalité). Un algorithme est dit optimal si sa complexité est la complexité minimale parmi les algorithmes de sa classe.
Nous nous intéresserons quasi exclusivement à la complexité en tempsdes algorithmes. Il est parfois intéressant de s’intéresser à d’autres de leurs caractéristiques, comme lacomplexité en espace(taille de l’espace mémoire utilisé), la largeur de bande passante requise, etc.

Modèle de machine

Pour que le résultat de l’analyse d’un algorithme soit pertinent, il faut avoir un modèle de la machine sur laquelle l’algorithme sera implémenté (sous forme de programme). On prendra comme référence un modèle demachine à accès aléatoire (RAM)et à processeur unique, où les instructions sont exécutées l’une après l’autre, sans opérations simultanées.

Illustration : cas du tri par insertion

Problématique du tri

Entrée : une séquence den nombres, a1, …, an.
Sortie : une permutation, a01, …, a0n, de la séquence d’entrée, telle quea01 a02 ::: a0n.

Principe du tri par insertion

De manière répétée, on retire un nombre de la séquence d’entrée et on l’insère à la bonne place dans la séquence des nombres déjà triés (ce principe est le même que celui utilisé pour trier une poignée de cartes).
Complexité en moyenne : supposons que l’on applique l’algorithme de tri par insertion à n nombres choisis au ha-sard. Quelle sera la valeur de t j ? C’est-à-dire, où devra-t-on insérer A[j] dans le sous-tableau A[1.. j 1] ? En moyenne, pour moitié les éléments de A[1j.. 1] sont inférieurs à A[j], et pour moitié supérieurs. Donc t j = j=2. Si l’on reporte cette valeur dans l’équation définissantT (n), on obtient, comme dans le pire cas, une fonction quadratique en n.
Caveat : ce raisonnement est partiellement faux ; un raisonnement précis doit bien évidemment tenir compte des valeurs des éléments déjà triés. Pour un calcul précis, voirNUTHK [4, p. 82]. CORI et LÉVY [1, p. 26] font un autre raisonnement et trouve un autre résultat (de même ordre de grandeur). Les deux sont justes : tout dépend de l’hypothèse que l’on prend sur les jeux de données. Ainsi [1] suppose que les permutations sont équiprobables, et [4] que les valeurs à trier sont équiprobables…

Ordre de grandeur

Ce qui nous intéresse vraiment, c’est l’ordre de grandeur du temps d’exécution. Seul le terme dominant de la formule exprimant la complexité nous importe, les termes d’ordres inférieurs n’étant pas significatifs quandn devient grand. On ignore également le coefficient multiplicateur constant du terme dominant. On écrira donc, à propos de la complexité du tri par insertion :
meilleur cas : (n).
pire cas : (n2).
en moyenne : (n2).
En général, on considère qu’un algorithme est plus efficace qu’un autre si sa complexité dans le pire cas a un ordre de grandeur inférieur.

Classes de complexité

Les algorithmes usuels peuvent être classés en un certain nombre de grandes classes de complexité :
– Les algorithmes sub-linéaires dont la complexité est en général enO(log n).
– Les algorithmes linéaires en complexitéO(n) et ceux en complexité enO(n log n) sont considérés comme ra-pides.
– Les algorithmes polynomiaux en O(nk ) pour k > 3 sont considérés comme lents, sans parler des algorithmes exponentiels (dont la complexité est supérieure à tout polynôme en n) que l’on s’accorde à dire impraticables dès que la taille des données est supérieure à quelques dizaines d’unités.

La récursivité et le paradigme « diviser pour régner »

Récursivité

De l’art d’écrire des programmes qui résolvent des problèmes que l’on ne sait pas résoudre soi-même !
Définition
Définition 4 (Définition récursive, algorithme récursif).Une définition récursive est une définition dans laquelle intervient ce que l’on veut définir. Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même.
Dans le cadre de ce cours, nous ne nous intéresserons qu’aux programmes et algorithmes récursifs. Mais la notion de définition récursive est beaucoup plus générale :
en mathématiques : définition de l’exponentielle : 8x 2 R; f 0(x) = f (x) et f (0) = 1.
en programmation : définition en Ocaml d’une liste infinie dont tous les éléments valent 1 :
let rec z = 1::z ; ;

Principe et dangers de la récursivité

Principe et intérêt ce: sont les mêmes que ceux de la démonstration par récurrence en mathématiques. On doit avoir :
– un certain nombre de cas dont la résolution est connue, ces « cas simples » formeront les cas d’arrêt de la récursion ;
– un moyen de se ramener d’un cas « compliqué » à un cas « plus simple ».
La récursivité permet d’écrire des algorithmes concis et élégants.
Difficultés :
– la définition peut être dénuée de sens : Algorithme A(n) renvoyer A(n)
– il faut être sûrs que l’on retombera toujours sur un cas connu, c’est-à-dire sur un cas d’arrêt ; il nous faut nous assurer que la fonction est complètement définie, c’est-à-dire, qu’elle est définie sur tout son domaine d’applications.
Moyen : existence d’un ordre strict tel que la suite des valeurs successives des arguments invoqués par la définition soit strictement monotone et finit toujours par atteindre une valeur pour laquelle la solution est explicitement définie.
L’algorithme ci-dessous teste si a est un diviseur de b.
La suite des valeurs b, b a, b 2 a, etc. est strictement décroissante, cara est strictement positif, et on finit toujours pas aboutir à un couple d’arguments (a;b) tel que b a est négatif, cas défini explicitement.
Cette méthode ne permet pas de traiter tous les cas :
SYRACUSE(n)
Si n = 0 ou n = 1 alors 1
sinon si n mod 2 = 0 alors SYRACUSE (n=2)
sinon SYRACUSE (3 n + 1)
Problème ouvert : l’algorithme est bien défini et vaut 1 sur N.
Question : N’y a-t-il vraiment aucun moyen de déterminer automatiquement si un algorithme récursif quelconque va terminer ? Réponse à la section suivante…

Non décidabilité de la terminaison

Question : peut-on écrire un programme qui vérifie automatiquement si un programme donnéP termine quand il est exécuté sur un jeu de donnéesD?
Entrée Un programme P et un jeu de donnéesD.
Sortie vrai si le programme P termine sur le jeu de donnéesD, et faux sinon.
Démonstration de la non décidabilité
Supposons qu’il existe un tel programme, nommé termine, de vérification de la terminaison. À partir de ce programme on conçoit le programme Q suivant :
programme Q résultat =termine(Q,) tant que résultat =vrai faire attendre une seconde fin tant que renvoyer résultat
Supposons que le programme Q —qui ne prend pas d’arguments— termine. Donc termine(Q,) renvoie vrai, la deuxième instruction de Q boucle indéfiniment et Q ne termine pas. Il y a donc contradiction et le programme Q ne termine pas. Donc, termine(Q,) renvoie faux, la deuxième instruction deQ ne boucle pas, et le programme Q termine normalement. Il y a une nouvelle fois contradiction : par conséquent, il n’existe pas de programme tel quetermine, c’est-à-dire qui vérifie qu’un programme termine ou non sur un jeu de données…
Le problème de la terminaison est indécidable !
Petit historique : cf. [1, p. 48].

Importance de l’ordre des appels récursifs

Fonction qui affiche les entiers par ordre décroissant, de n jusqu’à 1 :
DÉCROISSANT (n)
Si n = 0 alors ne rien faire
sinon afficher n
DÉCROISSANT (n 1)
Exécution pourn = 2 :
Appel de DÉCROISSANT (2)
Affichage de 2.
Appel de DÉCROISSANT (1)
Affichage de 1.
Appel de DÉCROISSANT (0)
L’algorithme ne fait rien.
Résultat affichage d’abord de 2 puis de 1 : l’affichage a lieu dans l’ordre décroissant.
Intervertissons maintenant l’ordre de l’affichage et de l’appel récursif :
CROISSANT(n)
Si n = 0 alors ne rien faire
sinon CROISSANT(n 1)
afficher n
Exécution pourn = 2 :
Appel de CROISSANT(2)
Appel de CROISSANT(1)
Appel de CROISSANT(0)
L’algorithme ne fait rien.
Affichage de 1.
Affichage de 2.
Résultat affichage d’abord de 1 puis de 2 : l’affichage a lieu dans l’ordre croissant.

Exemple d’algorithme récursif : les tours de Hanoï

Le problème
Le jeu est constitué d’une plaquette de bois où sont plantées trois tiges. Sur ces tiges sont enfilés des disques de diamètres tous différents. Les seules règles du jeu sont que l’on ne peut déplacer qu’un seul disque à la fois, et qu’il est interdit de poser un disque sur un disque plus petit.
Au début tous les disques sont sur la tige de gauche, et à la fin sur celle de droite.
Résolution
Hypothèse: on suppose que l’on sait résoudre le problème pour (n 1) disques.
Principe : pour déplacern disques de la tige A vers la tige C, on déplace les(n 1) plus petits disques de la tige A vers la tige B, puis on déplace le plus gros disque de la tigeA vers la tige C, puis on déplace les(n 1) plus petits disques de la tige B vers la tige C.
Validité: il n’y a pas de viol des règles possible puisque le plus gros disque est toujours en « bas » d’une tige et que l’hypothèse (de récurrence) nous assure que nous savons déplacer le « bloc » de (n 1) disques en respectant les règles.
Algorithme
HANOÏ(n, départ, intermédiaire, destination)
Si n = 1 alors sinon déplacer le disque supérieur de la tigedépart vers la tige destination HANOÏ(n 1, départ, destination, intermédiaire) déplacer le disque supérieur de la tigedépart vers la tige destination HANOÏ(n 1, intermédiaire, départ, destination)
Exécution avec trois disques
1. Déplace un disque de la tigedépart vers la tige destination
2. Déplace un disque de la tigedépart vers la tige intermédiaire
3. Déplace un disque de la tigedestination vers la tige intermédiaire
4. Déplace un disque de la tigedépart vers la tige destination
5. Déplace un disque de la tigeintermédiaire vers la tige départ
6. Déplace un disque de la tigeintermédiaire vers la tige destination
7. Déplace un disque de la tigedépart vers la tige destination
Il ne faut pas chercher à comprendre comment ça marche, mais pourquoi ça marche…

Complexité

On compte le nombre de déplacements de disques effectués par l’algorithme HANOÏ invoqué surn disques.
C(n) =C(n 1)+1 +C(n 1) sinon = 1 + 2 C(n 1) sinon
1 si n = 1 1 si n = 1 d’où l’on en déduit queC(n) = 2n 1. On a donc ici un algorithme de complexité exponentielle.

Dérécursivation

Dérécursiver, c’est transformer un algorithme récursif en un algorithme équivalent ne contenant pas d’appels ré-cursifs.

Récursivité terminale

Définition 5 (Récursivité terminale).Un algorithme est dit récursif terminal s’il ne contient aucun traitement après un appel récursif.
Exemple :
ALGORITHME P(U)
si C alors D; P((U ))
sinon T où :
– U est la liste des paramètres ;
– C est une condition portant sur U ;
– D est le traitement de base de l’algorithme (dépendant deU ) ;
– (U ) représente la transformation des paramètres ;
– T est le traitement de terminaison (dépendant deU ).
Avec ces notations, l’algorithme P équivaut à l’algorithme suivant :
Récursivité non terminale
Ici, pour pouvoir dérécursiver, il va falloir sauvegarder le contexte de l’appel récursif, typiquement les paramètres de l’appel engendrant l’appel récursif. Originellement, l’algorithme est :
ALGORITHME Q(U)
si C(U ) alors D(U ); Q((U )); F (U )
sinon T (U )
Les piles sont des structures de stockage (via les primitives empiler et dépiler) qui fonctionnent sur le principe « le dernier entré est le premier sorti » (cf. chapitre 5). Les compilateurs utilisent des piles pour stocker les paramètres des appels de fonctions, et en particulier lors de la transcription des fonctions récursives. Nous mimons ici l’utilisation des piles pour dérécursiver l’algorithme.

1 Introduction 
1.1 Qu’est-ce que l’algorithmique ?
1.2 Motivation : calcul de xn
1.2.1 Problème
1.2.2 Algorithme trivial
1.2.3 Méthode binaire
1.2.4 Algorithme des facteurs
1.2.5 Algorithme de l’arbre
1.2.6 Et après ?
1.3 Conclusion
2 Complexité et optimalité ; premier algorithme de tri 
2.1 Définition de la complexité
2.1.1 Notations de Landau
2.1.2 Complexité
2.1.3 Modèle de machine
2.2 Illustration : cas du tri par insertion
2.2.1 Problématique du tri
2.2.2 Principe du tri par insertion
2.2.3 Algorithme
2.2.4 Exemple
2.2.5 Complexité
3 La récursivité et le paradigme « diviser pour régner » 
3.1 Récursivité
3.1.1 Définition
3.1.2 Récursivité simple
3.1.3 Récursivité multiple
3.1.4 Récursivité mutuelle
3.1.5 Récursivité imbriquée
3.1.6 Principe et dangers de la récursivité
3.1.7 Non décidabilité de la terminaison
3.1.8 Importance de l’ordre des appels récursifs
3.1.9 Exemple d’algorithme récursif : les tours de Hanoï
3.2 Dérécursivation
3.2.1 Récursivité terminale
3.2.2 Récursivité non terminale
3.2.3 Remarques
3.3 Diviser pour régner
3.3.1 Principe
3.3.2 Premier exemple : multiplication naïve de matrices
3.3.3 Analyse des algorithmes « diviser pour régner »
3.3.4 Résolution des récurrences
3.3.5 Deuxième exemple : algorithme de Strassen pour la multiplication de matrices
4 Algorithmes de tri 
4.1 Tri par fusion
4.1.1 Principe
4.1.2 Algorithme
4.1.3 Complexité
4.2 Tri par tas
4.2.1 Définition d’un tas
4.2.2 Conservation de la structure de tas
4.2.3 Construction d’un tas
4.2.4 Algorithme du tri par tas
4.3 Tri rapide (Quicksort)
4.3.1 Principe
4.3.2 Algorithme
4.3.3 Complexité
5 Structures de données élémentaires 
5.1 Introduction
5.2 Piles et files
5.2.1 Piles
5.2.2 Files
5.3 Listes chaînées
5.3.1 Définitions
5.3.2 Algorithmes de manipulation des listes chaînées
5.3.3 Comparaison entre tableaux et listes chaînées
6 Programmation dynamique 
6.1 Multiplication d’une suite de matrices
6.2 Éléments de programmation dynamique
6.2.1 Sous-structure optimale
6.2.2 Sous-problèmes superposés
6.2.3 Recensement
7 Algorithmes gloutons 
7.1 Location d’une voiture
7.2 Éléments de la stratégie gloutonne
7.2.1 Propriété du choix glouton
7.2.2 Sous-structure optimale
7.3 Fondements théoriques des méthodes gloutonnes
7.3.1 Matroïdes
7.3.2 Algorithmes gloutons sur un matroïde pondéré
8 Graphes et arbres 
8.1 Graphes
8.2 Arbres
8.3 Parcours
8.3.1 Parcours des arbres
8.3.2 Parcours des graphes
9 Arbres de recherche et arbres de recherche équilibrés 
9.1 Arbres binaires de recherche
9.2 Arbres rouge et noir
10 Plus courts chemins 
10.1 Plus courts chemins à origine unique
10.1.1 Algorithme de Dijkstra
10.1.2 Algorithme de Bellman-Ford
10.2 Plus courts chemins pour tout couple de sommets
10.2.1 Programmation dynamique naïve
10.2.2 Algorithme de Floyd-Warshall
11 NP-complétude 
11.1 La classe P
11.2 La classe NP
11.3 NP-complétude
12 Heuristique
12.1 Le problème de la couverture de sommet
12.1.1 Heuristique
12.1.2 Exemple d’utilisation
12.1.3 Garantie de performances
12.2 Le problème du voyageur de commerce
12.2.1 Exemple d’utilisation
12.2.2 Garantie de performances