Algorithme et structures de données

Références bibliographiques • "Algorithms in Java"; Robert Sedgewick & Michael Shildlowsky; Third edition, Parts 1-4 : Fundamentals, data structures, sorting & searching; Addison-Wesley. • "Algorithms in Java"; Third edition, Part 5 : Graph algorithm; Robert Sedgewick & Michael Shildlowsky; Addison-Wesley. • "Data Structure and Algorithm"; Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman; Addison-Wesley. • "Algorithmique du texte"; Maxime Crochemore, Christophe Hancart, Thierry Lecroq; Vuibert.

Implémentation d'un algorithme (2)

•  2 cas typiques qui nécessitent des algorithmes efficaces :

–   taille du problème énorme

–   code exécuter un grand nombre de fois

•  Recherche d'algorithme plus efficace et si possible simple

Analyse empirique d'un algorithme ?

Analyse mathématique d'un algorithme ?

Implémentation d'un algorithme

•  Ecriture en Java : mais peut-être implémenté dans n'importe quel autre langage

•  Un algorithme fait parti d'un gros programme

–   utilisation de structure de données abstraites

–   peuvent être substituées

•  Dès le début : connaître les performances d'un algorithme

•  Tout le système en dépend (recherche, tri, …)

Analyse empirique

•  Soit 2 algorithmes réalisant la même tâche– compare temps d'exécution sur des entrées typiques

–   3 s ou 30 s d'attente pour l'utilisateur feront une grande différence

–   permet aussi de valider une analyse mathématique

•  Si le temps d'exécution devient trop long, l'analyse mathématique s'impose

–   attente pouvant être de l'ordre de l'heure ou du jour

Temps d'exécution 10-6 s pour une instruction int i, j, k, count=0; for (i=0; i < N; i++) for (j=0; j < N; j++) for (k=0; k < N; k++) count++;     Temps pour N= 10,     100,    1000,       100000 ou   1 million                             10-3s 1s      1000s         1 an         10 siècles

Analyse empirique (3)

•  Nécessite l'implémentation d'une première version d'un algorithme !!!

•  Nature des données à tester

–   données typiques

–   données aléatoires

–   données extrêmes

•  Attention à la comparaison– soin accordé à l'implémentation

–   différences entre ordinateurs, compilateurs, systèmes

d'exploitation, ….

Choix de l'algorithme (2)

•  Algorithme rapide souvent plus compliqué qu'un algorithme "brute force"

–   problèmes de grande taille -> algorithme rapide

•  Rien ne sert de multiplié par 10 la performance de l'algorithme si celui-ci – ne prend que quelques millisecondes

–   et est très peu utilisé

•  Le temps de développement peut-être prohibitif

•  un programme non écrit ne peut-être testé!

Outil mathématique •    Mesure générale des performances d'un algorithme •    Comparer 2 algorithmes pour la même tâche •    Prédire la performance dans un nouvel environnement

Analyse mathématique

•  L'analyse mathématique d'un algorithme peut-être complexe

•  Une spécialité en informatique

•  Paramètres hors de portée du programmeur Java :

–   temps d'exécution d'une instruction (MV/compilateur)

–   ressources partagées

–   dépendance des données en entrée

–   certains algorithmes sont tout simplement complexes et il n'y a pas de résultat mathématique pour les décrire

Analyse mathématique (2)

•    Néanmoins il est possible de prédire

–   la performance d'un algorithme

–   si un algorithme est meilleur qu'unautre

•    Premières étapes:

–   identifier les opérations abstraites de l'algorithmes

–   exemple de la triple boucle, le nombre d'exécutions de l'instruction : count++

–   sans tenir compte du temps en milliseconde

–   cette séparation permet de comparer des algorithmes

Les entrés testées par l'algorithme •  Plusieurs cas sont envisagés: –   le cas moyen : fiction mathématique –   le pire des cas : construction qui se produit que rarement –   donnent néanmoins des informations clés •  Exemple : –   recherche séquentiel d'un nombre dans un tableaustatic int search(int a[], int v, int l, int r) { int i; for (i = l; i <= r; i++) if (v == a[i]) return i; return -1; }

Les fonctions d'accroissement

•  La plupart des algorithmes ont un paramètre N qui les caractérise :

–   le nombre d'assurés sociaux

–   le nombre de fichiers

–   le nombre de caractères

•  Une mesure abstraite du problème •  Plusieurs paramètres peuvent exister :

–   par exemple M et N (producteurs et consommateurs, usine de productions et sites de vente)

–   garder un paramètre fixe en faisant varier l'autre paramètre

•  But : exprimer les besoins en fonction de N ( ou M et N)

par des formules mathématiques

Type de fonctions

•  1         instructions exécutées un nombre limité de fois; exécution constante

•  log N  division du problème pour le résoudre; exécution logarithmique

•  N        exécution linéaire

•  N*log Nrésolution de pbs plus petits, puis recombinaison des solutions

•  N²           utilisable sur de petits pbs; exécution quadratique

•  N³           triple boucle sur les données

•  2^N           exécution exponentielle; N=20 alors 2^N=1 million

Une mesure générale des performances d'un algorithme

La notation O :

Soit deux fonctions f(x) et g(x) avec x ? 0 On dit que f(x)=O( g(x) ) si

?    N₀ ? 0, ? c ? 0, ? N ? N₀ f (N) ? c . g (N)

A partir d'un certain rang, la fonction « g » majore la fonction « f » à un coefficient multiplicatif près.

^{On peut encore écrire :}                          lim?? f (n) = c

n            g(n)

La notation grand-O

•    ?        N₀ ? 0, ? c ? 0, ? N ? N₀ g (N) ? c . f (N)

•    Cette notation permet de :

–   limiter l'erreur quand on ignore les termes plus petits dans uneformule mathématique

–   limiter l'erreur quand on ignore certaines parties du programme qui prennent peut de temps

–   classer les algorithmes en fonction de leur comportement asymptotique (avec N grand)

•    Les constantes N₀ et c₀ cachent des détails d'implémentation

•    si N < N₀ on ne connaît pas le comportement de l'algorithme

•    On ne s’intéresse qu'aux termes les plus grands : comparer N² nanosecondes et logN siècles

Propriétés de la notation O (1) •    Les constantes peuvent être ignorées : ?  k > 0,  k*f  est O( f) •    Les puissances supérieures croissent plus rapidement : si  f  est un polynôme de degré d alors  f  est O(nd) •    Les termes croissant rapidement dominent la somme si  f  est O(g),  alors  f + g est O(g)  ex:   an4 +  bn4 est   O(n4 ) •    Une croissance polynomiale est dictée par la puissance la plus élevée       nr     est O( ns)  si   0 ? r ? s

Propriétés de la notation O (2)

•  f est O(g)  est  transitif : si  f  est O(g) et g  est O(h) alors  f  est O(h)

•  Le produit des bornes supérieures est la borne supérieure du produit : si  f  est O(g)  et  h  est O(r)  alors  f*h  est O(g*r)

•  Les fonctions exponentielles croissent plus vite que les puissances : n^k                 est  O(  bⁿ ) ? b > 1 et k ? 0 ex : n²⁰        est O( 1.05ⁿ)

•  Les logarithmes croissent plus lentement que les puissances :

log_bn est  O( n^k)  ? b > 1 et k > 0 ex: log₂n   est  O( n^0.5)

Algorithmes polynomiaux et difficiles

•  Algorithme polynomiale

–   s'il est O(n^d) pour un entier "d" donnée

•  Ils peuvent être résolus en un temps raisonnable

•  Algorithmes difficiles

– algorithmes pour lesquels il n'y a pas d'algorithme avec un temps polynomiale

Coût des instructions • Instructions simples : a=b; a+=b; … s1; s2; …. ; sk O(1) si k est une constante O(1) • boucle simple : for(i=1; i <N; i++) inst; avec inst O(1) donc N*O(1)=O(N) O(N) • double boucle imbriquée : for(i=1; i <N; i++) for(j=1; j <N; j++) inst; complexité N*O(N) donc O(N2) O(N2) • triple boucle imbriquée : O(N3) Copyright " 'Algorithms in Java'; Robert Sedgewick & Michael Shildlowsky; Third edition, Parts 1-4; Addison-Wesley " Reproduction ULP Strasbourg. Autorisation CFC - Paris

Exemple avec O(N)

•    T(0)=1

•    T(1)=4

•    T(N)=(N+1)²

•    T(N) est O(N²) avec N₀=1 et c=4

•    T(N) ? 4*N² pour N ? N₀=1

•    N₀=0 n'est pas possible car T(0)=1 or c*0²=0 pour toutes constantes c

Exercice avec O(N) (1)

•  montrer que O(1) est la même chose que O(2) ?

    ?    N₀ ? 0, ? c ? 0, ? N ? N₀ g(N) ? c . f (N)

•  Cela revient à trouver 2 entiers N₀ et c avec : f(N)=1 et la fonction g(N)=2

•  N₀ = 0 et c = 2 on a bien 2 ? c*1=2 pour tout ? ? N₀ = 0

Exercice avec                   HN =1+ 1 + 1 + + 1

2              3              N 12N

O(N) (4.2)                       _{?ln N}+_?+ 1

•  Avec la notation O(N) que devient cette estimation ?

a₁ + 2a₂N*H_N + a₃*N ns

•  2a₂N*H_N + O(N)

•  Une forme plus simple qui indique que ce n'est pas la peine de chercher a₁ et a₃

•  Temps d'exécution exprimé en notation « grand-O » ?

•  H_N=ln(N) + O(1) on obtient ainsi 2a₂N*Ln(N)+ O(N)

•  l'expression asymptotique du temps total d'exécution : temps proche de 2a₂N*Ln(N) pour des N grands

Exercice avec O(N) (3) •  Supposons qu'il existe 2 constantes c et N0 tel que N ? N0 pour lesquelles l'inégalité suivante est vérifiée : 3N ? c*2N •  alors c ? (3/2)N , c peut devenir arbitrairement grand pour N grand,  donc il n'existe pas de constante supérieure (3/2)N quelque soit N

Exercice avec  O(N) (4.3)

•  l'expression asymptotique du temps total d'exécution :

temps proche de 2a₂N*Ln(N) pour des N grands

•  que se passe-t-il si N double : taille 2N?

2a₂(2N)ln(2N)+O(2N) ₌ 2ln(2N)+O(1)

                  2a₂N ln N+O(N)             ln N+O(1)

= 2+O( ¹ ) 2a₂N en facteur  ln N

•  sans connaître a₂ on peut prédire que le temps doublera pour le traitement des données de taille 2N

Accélération de la recherche

•    Comment?

Application : Recherche du maximum • Recherche séquentielle : •       l                                                            r static int search(int a[], int v, int l, int r) { int i; Analyse de l'algorithme? for (i = 1; i <= r; i++) if (v == v[i]) return i; paramètre clé? return -1; }

Recherche séquentielle : coût? • static int search(int a[], int v, int l, int r) { int i; for (i = 1; i <= r; i++) if (v == v[i]) return i; return -1; } • Coût moyen (1 + 2 + 3 + 4 +…+ N) / N = N (N + 1) / 2N = (N + 1)/2 • Coût extrême N car on parcourt tout le tableau

•    Trier les nombres (N nombres) : O(NlogN) Coût faible comparé au nombre de comparaisons si on fait une recherche très souvent (M : nombre de recherche; M >>N)

•    La recherche séquentielle : M*N

•    La recherche binaire : NLogN + M*?

Recherche binaire (3)

static int search(int a[], int v, int l, int r)

^{  2 situations : while(r>=l) {

if (v < a[m]) r=m-1; else l=m+1;

}

return -1;

^}                               T_N ? T_?N/2? + 1, pour N ?2 avec T₁ = 1

N=2ⁿ; T_N ? n +1= ?lgN? + 1

N=10⁹ recherche en au plus 30 comparaisons