Admin CliCours
Notes de cours algorithmique, graphes et programmation dynamique, tutoriel & guide de travaux pratiques algorithmes en pdf.
Problemes de recherches
Le probleme que nous nous posons est de rechercher un element (nombre, caractere ou autre) dans un tableau homogene d’elements. La particularite de ce tableau est qu’il est deja trie dans l’ordre croissant (ce qui impose d’avoir une relation d’ordre entre les elements).
Remarques sur l’evaluation de complexit d’un programme
Dans ce paragraphe et ceux qui suivront, nous allons evaluer le temps d’exe-cution des programmes en fonction de la taille n du probleme. Comparer 2 pro-grammes, c’est comparer les temps d’execution dans les pires des cas respectifs. Les constantes dependent de la machine qui executera l’algorithme.
De nition : Le programme P est de complexit O(f(n)) s’il existe et n0 tels que :
8n n0 Tp(n) f(n)
Ou Tp(n) represente le temps d’execution du programme P dans le pire des cas. Remarque : Si le programme P est en O(n), alors il est aussi en O(2n), O(n ) ou 2
Recherche dichotomique
Supposons que l’on cherche un element note e dans un tableau T . Le pro-gramme de recherche dichotomique que nous allons mettre au point repond a l’enonc suivant :
(T [0] e T [n 1]) RD (T [k] e T [k + 1])
Invariant : I(i; j) T [i] e T [j 1]
Condition d’arr^et : j = i + 2
Initialisation : (i = 0) ^ (j = n) ]))I( ; i) ) i+j
I(i; j) ^ ((j i) > 2) ^ (e T [i 2 2
^ +^j i+j
Implications : I(i; j) ((j i) > 2) e < T [ i+j ] I(i; )
Ce programme se base sur le fait que le tableau est deja trie. On compare l’element a rechercher avec l’element du milieu du tableau. Si l’element que l’on recherche est inferieur, alors il se trouve dans le sous-tableau de gauche, sinon dans celui de droite.
On continue a appliquer le m^eme raisonnement de maniere iterative jusqu’a ce que l’on a pu assez encadrer l’element.
Code Source
i=0;
j=n;
5 while( j-i > 2)
{
if (e < T[(i+j)/2]) // I(i,(i+j)/2)
8 j = (j+i)/2; // I(i,j)
9 else // I((i+j)/2,j)
10 i = (j+i)/2; // I(i,j)
}
// Ici on a I(i,j)&&(j-i = 2)
On peut eventuellement faire une veri cation prealable sur les donnees (pour voir si e 2 T [0 n 1])
Complexit
On rappelle l’invariant :
I(i; j) T [i] e T [j 1]
Precondition : T [0] e T [n 1]
Postcondition : T [i] e T [i + 1]
L’initialisation se fait en temps constant (on suppose a). L’evaluation de la condition de la boucle est elle aussi en temps constant, note b. Le corps de la boucle est egalement en temps constant c.
A chaque execution du corps de boucle, la taille du probleme restant a traiter est divisee par 2. On a la suite valeurs n; n2 ; n4 ; :::; 1.
Hypothese : La taille du probleme n est supposee ^etre un multiple de 2.
n = 2p. Avec n = 2p le corps de boucle est execut p fois.
Trd = a + (p + 1)b + pc
Trd = (a + b) + p(b + c)
Trd = log2(n) +
Pour un probleme de taille n = 2p, la complexit de la recherche dichotomique est de forme logarithmique, mais supposons que la taille du probleme ne soit pas un multiple de 2.
Pour 2p n 2p+1
log2(n) + Trd a + b(p + 2) + (p + 1)c
log2(n) + Trd 0log2(n) + 0
On peut en deduire que le facteur dominant du temps de calcul est en log2(n), la recherche dichotomique est (log2(n))
Remarque : Le logarithme base 2 et le logarithme neperien (base e) ne di erent que d’une constante, par consequent la recherche dichotomique est O(log(n)).
Recherche sequentielle
La recherche sequentielle est une methode plus traditionnelle : on regarde tous les elements du tableau sequentiellement jusqu’a ce que l’on tombe sur e, l’element que l’on cherchait.
L’avantage de la recherche sequentielle est qu’elle est possible sur des tableaux non-tries.
Invariant : I(k) e 2= T [0:::k 1]
Initialisation : k = 0
Condition d’arr^et : T [k] = e
Implications : I(k) ^ (T [k] 6= e) ) I(k + 1)
Code
k = 0;
3 while( T[k] != e)
{
k++
6 }
Complexit
La condition du while : T[k] != e est evaluee n + 2 fois dans le pire des cas.
Le corps de boucle k++ est executee n+1 fois dans le pire des cas.
Si on appelle a le temps d’execution de l’initialisation (k=0), b le temps d’execu-tion de la condition de boucle, et c le temps d’execution du corps de boucle. Dans le pire des cas ou T [n] = e, le temps d’execution de la recherche sequentielle est :
Trs = a + b(n + 2) + c(n + 1)
Dans le cas general :
Trs(n) = (b + c)n + a + 2b + c
Trs(n) = n +
On en deduit une complexit en (n).
Recherche arriere
Le but de cette algorithme est de rechercher un element e dans un tableau a 2 dimensions T [0:::m 1][0:::n 1] dont les lignes ET les colonnes sont tries par ordre croissant.
Complexit
Le corps de boucle est en temps constants (structure if, incrementations). La condition du while est elle aussi en O(1), le corps de boucle est evalue au plus m + n fois, donc la complexit de la recherche arriere est en (m + n)
I IN202 – Algorithmique
1 Systeme formel de preuve de programme de O’Hare
1.1 Regles et axiomes
1.2 Construction de programmes sur invariant
2 Problemes de recherches
2.1 Remarques sur l’evaluation de complexite d’un programme
2.2 Recherche dichotomique
2.3 Recherche sequentielle
2.4 Recherche arriere
3 Problemes de tris
3.1 Slowsort
3.2 Quicksort
3.3 Complexite minimum d’un algorithme de tri
4 Approche diviser pour regner
4.1 Diviser pour regner
4.2 Limites de l’approche diviser pour regner
5 Complexite des algorithmes
5.1 Expression du temps de calcul
5.2 Notations
5.3 Calculs courants dans le calcul des complexites
5.4 Un peu de theorie de la complexite
6 Programmation Dynamique
6.1 Cas concret : bonnaci
6.2 Exemple : Multiplication de matrices
6.3 Exemple : Recherche du plus long sous-mot commun a 2 chaines
7 Applications de la programmation dynamique
7.1 Un probleme d’assortiment
7.2 Compression d’image
7.3 Justication de Parapgraphes
III IN302 – Graphes et algorithmes
8 Notions de base
8.1 Premiere denition
8.2 Representation en memoire
8.3 Denitions complementaires
8.4 Chemins, connexite
8.5 Representation matricielle
8.6 Graphe biparti
9 Arbre et arborescences
9.1 Denitions
9.2 Exemples et applications
9.3 Arbre de poids minimum
9.4 Algorithmes de Kruskal
10 Plus courts chemins
10.1 Denition
10.2 Problematique du plus court chemin
10.3 Algorithme de Floyd
10.4 Algorithme de Bellman
10.5 Algorithme de Dikstra
10.6 Plus courts chemins (Exploration largeur)
10.7 Graphes sans circuits : GSC
11 Cycles euleriens et hamiltoniens
11.1 Cycle eulerien
11.2 Cycle hamiltonien
12 Flots et reseaux de transport
12.1 Modelisation d’un reseau de transport
12.2 Proprietes d’un reseau de transport
12.3 Algorithme de Ford et Fulkerson
13 Resolutions de problemes en Intelligence artificielle et optimisation
13.1 Exemple : le probleme des 8 dames
13.2 Strategies de recherche
13.3 Algorithme A et A
IV Annexes
………
Télécharger le cours complet
