Algorithmique avancée éléments de programmation dynamique

Support de cours algorithmique avancée éléments de programmation dynamique, tutoriel & guide de travaux pratiques algorithmes en pdf.

Complexité et optimalité ; premier algorithme de tri

Définition de la complexité
Notations de Landau
Quand nous calculerons la complexité d’un algorithme, nous ne calculerons généralement pas sa complexité exacte, mais son ordre de grandeur. Pour ce faire, nous avons besoin de notations asymptotiques.
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é
Nous passons en revue les différentes étapes de notre algorithme afin d’évaluer son temps d’exécution. Pour ce faire, nous attribuons un coût en temps à chaque instruction, et nous comptons le nombre d’exécutions de chacune des instructions. Pour chaque valeur de j 2 [2;n], nous notons t j le nombre d’exécutions de la boucletant que pour cette valeur de j. Il est à noter que la valeur de t j dépend des données…
Complexité au meilleur : le cas le plus favorable pour l’algorithme TRI-INSERTION est quand le tableau est déjà trié, comme le montre le cas j = 4 de la figure 2.1. Dans ce cas t j = 1 pour tout j.
T (n)
= c1n + c2(n
1) + c3(n
1) + c4(n 1) + c7(n
1)
= (c1 + c2 + c3 + c4 + c7)n
(c2 + c3 + c4
+ c7):
T (n) peut ici être écrit sous la forme T (n) = an + b, a et b étant des constantes indépendantes des entrées, et T (n) est donc une fonction linéaire de n.
Le plus souvent, comme c’est le cas ici, le temps d’exécution d’un algorithme est fixé pour une entrée donnée ; mais il existe des algorithmes « aléatoires » intéressants dont le comportement peut varier même pour une entrée fixée. Nous verrons un algorithme de ce style au chapitre 4 : une version « aléatoire » dutri rapide
Complexité au pire : le cas le plus défavorable pour l’algorithme TRI-INSERTION est quand le tableau est déjà trié dans l’ordre inverse, comme le montre le cas j = 5 de la figure 2.1. Dans ce cas t j = j pour tout j.
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 ; ;
Récursivité simple
Revenons à la fonction puissance x 7!xn. Cette fonction peut être définie récursivement :
xn = xxn 1 si n 1:
1 si n = 0;
L’algorithme correspondant s’écrit :
PUISSANCE (x, n)
Si n = 0 alors renvoyer 1
sinon renvoyer x PUISSANCE(x, n 1)
Récursivité multiple
Une définition récursive peut contenir plus d’un appel récursif. Nous voulons calculer ici les combinaisonsCnp en se servant de la relation de Pasca
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.

1 Introduction 
1.1 Qu’est-ce que l’algorithmique ?
1.2 Motivation : calcul de xn
1.3 Conclusion
2 Complexité et optimalité ; premier algorithme de tri 
2.1 Définition de la complexité
2.2 Illustration : cas du tri par insertion
3 La récursivité et le paradigme « diviser pour régner » 
3.1 Récursivité
3.2 Dérécursivation
3.3 Diviser pour régner
4 Algorithmes de tri 
4.1 Tri par fusion
4.2 Tri par tas
4.3 Tri rapide (Quicksort)
5 Structures de données élémentaires 
5.1 Introduction
5.2 Piles et files
5.3 Listes chaînées
6 Programmation dynamique 
6.1 Multiplication d’une suite de matrices
6.2 Éléments de programmation dynamique
7 Algorithmes gloutons 
7.1 Location d’une voiture
7.2 Éléments de la stratégie gloutonne
7.3 Fondements théoriques des méthodes gloutonnes
8 Graphes et arbres 
8.1 Graphes
8.2 Arbres
8.3 Parcours
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.2 Plus courts chemins pour tout couple de sommets
11 NP-complétude 
11.1 La classe P
11.2 La classe NP
11.3 NP-complétude
12 Heuristiques 
12.1 Le problème de la couverture de sommet
12.2 Le problème du voyageur de commerce
12.2.1 Exemple d’utilisation
12.2.2 Garantie de performances

……..