-
Cours :
- Arbres binaires de recherche
- cours 1
transparents : pdf, html - planche de TD/TP 1 (pdf)
- cours 1
- Tas
- cours 2
transparents : pdf, html - planche de TD/TP 2 (pdf)
- cours 2
- Parcours de graphe
- cours 3
transparents : pdf, html - planche de TD/TP 3 (pdf)
- cours 3
- Plus courts chemins et coloration de graphe
- cours 4
transparents : pdf, html - planche de TD/TP 4 (pdf)
- cours 4
- Programmation dynamique 1
- cours 5
transparents : pdf, html - planche de TD/TP 5 (pdf)
- cours 5
- Programmation dynamique 2
- Recherche textuelle
- cours 7
transparents : pdf, html - planche de TD/TP 7 (pdf)
- cours 7
- Algorithmes randomisés
- cours 8
transparents : pdf, html - planche de TD/TP 8 (pdf)
- cours 8
- Calculabilité
- transparents : pdf
- planche de TD/TP 9 (pdf)
- Complexité
- transparents : pdf
- planche de TD/TP 10 (pdf)
Programmation dynamique
Rappel : Définition de suites récurrentes
Exemple de la factorielle:
u0 = 1 et ∀n ≥ 1 un = n × un − 1
Correction et complexité s’étudient par des preuves par récurrence (a, b ∈ N)
C0 = a et ∀n ≥ 1 Cn = b + Cn − 1
Cn = O(n)
Fonctions récursives : attention aux écueils
Suite de Fibonacci:
F0 = F1 = 1 et ∀n ≥ 2 Fn = Fn − 1 + Fn − 2
Graphe d’appels
Graphe d’appels et nombre total d’appels nécessaires
Pour faire mieux : calcul ascendant
- Calculer l’ensemble S des sommets accessibles depuis le sommet v dont on cherche à calculer la valeur
- Ordonner S selon un tri topologique < (c’est-à-dire tel que si (u, v) est un arc du graphe d’appels alors v < u) : cf séance sur les parcours de graphes
- Par ordre croissant, calculer et stocker l’image de chaque sommet de S
Calcul ascendant pour Fibonacci
- Si on veut calculer Fn, l’ordre topologique nous dit de calculer tous les Fi pour i de 0 à n…
- On les stocke dans une liste !
def fibonacci(n):
resultats = [1, 1] # on connait les valeurs de F0 et F1
for i in range(2, n + 1):
resultats.append(resultats[-1] + resultats[-2])
return resultats[n]
Programmation dynamique
Une méthodologie pour aborder certains problèmes…
Lorsque les sous-problèmes ont des sous-sous-problèmes en commun, il faut les résoudre une seule fois et mettre le résultat dans une table !
Méthodologie
Problèmes d’optimisation
- des problèmes qui admettent un ensemble de solutions 𝒮
- c: 𝒮 → R fonction objectif
- on cherche une solution s* telle que c(s*) = min {c(s) ∣ s ∈ 𝒮}
Conception d’un algorithme de programmation dynamique
- Caractérisation de la structure des solutions optimales
- Définition récursive de la valeur optimale
- Calcul ascendant de la valeur optimale
- Construction d’une solution optimale à partir des informations obtenues en 3 (facultatif)
Exemple : ordonnancement de chaînes de montage
- Un constructeur automobile possède un atelier avec deux chaînes de montage (1 et 2) comportant chacune n postes.
- Chaque véhicule doit passer par les n postes dans l’ordre.
Exemple : ordonnancement de chaînes de montage
Données du problème
- Si, j le j-ième poste de la chaîne i
- ei le temps d’entrée d’un véhicule sur la chaîne i
- ai, j le temps de montage pour le poste j sur la chaîne i (on peut avoir a1, j ≠ a2, j)
- ti, j le temps de transfert d’un véhicule de la chaîne i vers l’autre chaîne après le poste Si, j
- xi le temps de sortie d’un véhicule de la chaîne i
Problème
Déterminer quels sont les postes à sélectionner sur la chaîne 1 et sur la chaîne 2 pour minimiser le délai de transit d’une auto à travers l’atelier
Exemple
Espace des solutions
- Chaque solution est définie par le sous-ensemble de postes de la chaîne 1 utilisés (les postes restants sont choisis dans la chaîne 2)
Combien de solutions possibles ?
- 2n solutions possibles : l’approche naïve consistant à parcourir tous les chemins possibles est inefficace
Étape 1 : sous-structures optimales
Les sous-problèmes à considérer consistent à calculer un itinéraire optimal jusqu’au poste Si, j pour i = 1, 2 et j = 1, …, n
Par exemple, considérons un itinéraire optimal jusqu’au poste S1, j:
- Si j = 1, il n’y a qu’un seul chemin possible
- Pour j = 2, …, n, il y a deux possibilités:
- ou bien l’itinéraire optimal jusqu’à S1, j − 1 suivi du poste S1, j
- ou bien l’itinéraire optimal jusqu’à S2, j − 1 suivi d’un changement de chaîne et du poste S1, j
Étape 2 : solution récursive
fi[j] : délai optimal jusqu’à Si, j
f* : délai optimal pour traverser l’atelier
f* = min (f1[n] + x1, f2[n] + x2)
Pour le poste 1 de chaque chaîne, pas de choix:
f1[1] = e1 + a1, 1 f2[1] = e2 + a2, 1
Pour le poste j = 2, …, n de la chaîne 1, deux possibilités:
f1[j] = min (f1[j − 1] + a1, j, f2[j − 1] + t2, j − 1 + a1, j)
et idem pour la chaîne 2:
f2[j] = min (f2[j − 1] + a2, j, f1[j − 1] + t1, j − 1 + a2, j)
Exemple
Information pour la construction de la solution
Les fi[j] sont les valeurs des solutions optimales des sous-problèmes
Pour pouvoir reconstruire les solutions optimales elles-mêmes, on définit
li[j] le numéro de la chaîne (1 ou 2) dont le poste j − 1 est utilisé par un chemin optimal jusqu’au poste Si, j
l1[j] n’est pas défini car aucun poste ne vient avant le poste 1
Exemple
Étape 3 : calcul des temps optimaux de manière ascendante
Complexité : O(n)
Étape 4 : construction du chemin optimal
Affichage par ordre décroissant des numéros de poste :