Algorithmique et Analyse d'Algorithmes - L3 Info Cours 1 : notion de

Algorithmique et Analyse d’Algorithmes

Algorithmique et Analyse d’AlgorithmesL3 Info

Cours 1 : notion de coût d’un algorithme

Benjamin Wack

2017- 2018

1 / 41


Objectifs du cours

Savoir proposer une solution algorithmique à un problème posé,savoir implanter la solution et savoir analyser celle-ci.

Objectifs détaillés

I Savoir reconnaître et mettre en œuvre des schémas génériquesd’algorithmes (séquence, arbre, graphe...),

I Savoir construire une solution selon une démarche allant du plussimple (algorithme naïf) au plus efficace (diviser pour régner, etc.)

I Savoir démontrer la correction des algorithmesI Savoir comment évaluer la complexité d’une solution

algorithmique :- analyser la complexité au pire, en moyenne avec des hypothèsesprobabilistes,

- analyser la complexité en utilisant des mesures sur des simulations oudes jeux de test.

2 / 41


Plan

Présentation du cours

Problématique

Coût d’un algorithme

ComplexitéMéthodologieOrdres de grandeur

Algorithme de Horner

3 / 41

Algorithmique et Analyse d’AlgorithmesPrésentation du cours

Structure du cours

Cours (Benjamin Wack)Une partie synthétique sur les concepts et schémas algorithmiquesUn algorithme classique afin de se constituer une culture de référence

TD1 (Florence Perronnin, Anne Rasse, Jean-Marc Vincent)Exercices permettent de renforcer la compréhension des concepts.

TD2 (Vincent Danjean, David Monniaux, Benjamin Wack)Mise en œuvre des concepts et préparation aux activités pratiques

APNEES (VD, DM, BW) : Activités Personnelles Non EncadréesÉvaluéesValidation des concepts par la pratique et évaluation de la compréhension

+ au moins autant de travail personnel ! (exercices, petits programmes)Adresse Mail enseignant : Pré[email protected]

5 / 41

[email protected]


Ressources

Bibliographie

I Algorithmique, T. Cormen, R. Rivest & C. Leiserson, DunodI Algorithmes, R. Sedgewick, Pearson Education

Page WebPlanning, documents, annales

http://www-verimag.imag.fr/~wack/ALGO5/

Moodle de l’UFRSujets et rendus d’Apnées

https://im2ag-moodle.e.ujf-grenoble.fr/course/view.php?id=229

6 / 41

http://www-verimag.imag.fr/~wack/ALGO5/

https://im2ag-moodle.e.ujf-grenoble.fr/course/view.php?id=229


Évaluations

Note finale = 67 % Examen + 33 % CC

Les contrôles continus

I 2 quicks (début octobre et fin novembre) : 50 % du CCI 3 comptes-rendus d’APNEEs dont 2 notés : 50 % du CC

Examen terminal

I 2h30 sans documents ni calculatriceI Session 2 en juin...

Challenge de programmation

I Semaine du 13 au 17 novembreI En équipes

7 / 41


Programme (indicatif) du coursI Complexité des algorithmes

1. Coût d’un algorithme (itérations, ordres de grandeur) Horner2. Analyse en moyenne Quicksort

I Preuves d’algorithmes3. Invariant, correction, terminaison Drapeau hollandais4. Logique de Hoare Dichotomie

I Types abstraits élémentaires et implantation5. Structures séquentielles Algorithme de parenthésage6. Structures arborescentes Partition Binaire de l’Espace

I Arbres7. Arbres binaires de recherche Arbres B8. Arbres ordonnés, structure de tas Algorithmes gloutons9. Arbres et codage Algorithme de Huffman

I Graphes et algorithmes10. Algorithmique de graphes Prim et Kruskal11. Prétraitement Algorithme de Knuth-Morris-Pratt

8 / 41

Algorithmique et Analyse d’AlgorithmesProblématique

Notion de problème données

I Effectuer une recherche dans un inventaire stockI Résoudre une équation coefficientsI Trouver le plus court chemin sur un plan de ville planI Corriger des fautes d’orthographe texte + dictionnaireI Multiplier des matrices coefficientsI . . .

Dans chacun de ces exemples on s’intéresse en fait à une classe deproblèmes similaires, dont chaque instance est définie par des données.

Il faut également préciser le résultat attendu.(par exemple pour l’inventaire : oui/non ? quantité ? localisation ?)

10 / 41


Qu’est-ce qu’un algorithme ?Procédure de résolution de n’importe quelle instance d’un problèmesuffisamment élémentaire pour être exécutée de façon automatique.

Problème concret

Problème formalisé

// AlgorithmeProgrammation

Programme

Exécution

Données

tt ))Instance Solution

Exemple : résolution d’équation

11 / 41


Un algorithme traite donc des données pour produire un résultat ; maisavec quelles primitives et quelles ressources ?

12 / 41


Nécessité d’un modèle

Alan M. Turing Machine « de papier »1912-1954 1936

La machine est dotée :I d’un ruban infini (' mémoire)I d’une tête de lecture/écritureI d’un automate (' processeur)

Un modèle donc tourné vers les opérations de lecture/écriture(' affectation, calculs)

13 / 41


Les questions “résolues” par Turing

I Qu’est-ce qu’un calcul effectué automatiquement ?I Peut-on tout calculer ?I Peut-on décider automatiquement si une formule logique est vraie ?

10 ans avant les premiers ordinateurs !

Cf. Modèles de calcul au semestre 6

14 / 41


Les questions traitées en Algo5

Est-ce que je peux construire un programme qui résout mon problème(sur une machine conforme à mon modèle) ?Spécification du problème et construction d’un algorithme

Est-ce que l’exécution de mon programme sur la machine donne bien lerésultat souhaité ?Vérification de propriétés qualitatives par test et preuve

Est-ce que mon programme me fournit le résultat en un tempsacceptable ?Validation de propriétés quantitatives par mesure et analyse

15 / 41


Les questions traitées en Algo5

Problème concretspécification

Correction Efficacité

Problème formalisé

construction // AlgorithmeProgrammation

preuveOO

analyse decomplexité

66

Programme

Exécution

^^ mesure

Données

tt ))

55

Instance Solution

test@@

Exemple : résolution d’équation

15 / 41

Algorithmique et Analyse d’AlgorithmesCoût d’un algorithme

Notre modèle de machine

Une machine est constituée d’un processeur, d’une mémoire et d’unensemble d’opérations.

I Mémoire- infinie (mais un calcul donné utilise un espace fini),- types élémentaires (finis) int, float,...- puis on ajoutera des structures de données

I Opérations- nombre fini d’opérations (arithmétiques, booléennes...) ;- chaque opération a un nombre fini de paramètres(nombre fini de variables lues et écrites)

I Processeur- processeur unique ;- effectue les opérations en temps constant (1 top = 1 opération)

17 / 41


Efficacité d’un algorithme

I Est-ce que mon programme consomme une quantité acceptable deressources pour fournir un résultat ?

I Étant donnés deux programmes résolvant le même problème, lequelest le “meilleur” ?

CalculUn calcul est une séquence d’opérations qui, à partir d’une configurationinitiale de la mémoire, produit, en un temps fini, une configurationterminale.

I coût en temps à partir d’une configuration initiale d= nombre d’opérations dans la séquence

I coût en mémoire= nombre maximal de variables utilisées simultanément

18 / 41


Exemple (1)

Moyenne de 2 flottantsMOY(a,b)Données : Deux flottants : a et bRésultat : La moyenne de a et de bs := a + bm := s/2Return (m)

Coût de l’algorithmeCoût temps ? 2 opérationsCoût en espace mémoire ? 2 variables

Coût constant, indépendant des données

19 / 41


Exemple (2)

Puissance : calcul de xn

PUISSANCE(x ,n)Données : Un flottant x et un entier nRésultat : La valeur de xn

p := 1k := 0while k 6= n

p := p × xk := k + 1

Return (p)

I Coût en temps : 2 + 2n opérationsI Coût variable, dépend de la valeur des données

20 / 41


Exemple (3)

Maximum d’un tableauMAXIMUM(T ,n)Données : T tableau de n entiersRésultat : L’indice d’un élément maximax := T [1]for i := 1 to n

if T [i ] ≥ maximax := imax := T [i ]Traiter (max)

Return (imax )

Coût de l’algorithmeModèle de coût ?Supposons Traiter coûteux

I pour T=[1,2,...,n] ?I pour T=[14,28,...,14n] ?I pour T=[n,1,2,...,n-1] ?

Dépend de la taille des donnéesBorné par une fonction linéaire

Expression du coût : en fonction de quoi ?

I Pour ce tableau n est la taille des donnéesI Pour un entier n est la valeur de la donnée : on préférera log2(n)

21 / 41

Algorithmique et Analyse d’AlgorithmesComplexité

Généralisation

Taille de la donnée

Entier Entier

Cout du calcul

Espace des données

Machine

Espace des résultatsAlgorithme

Caractériser l’efficacité générale de l’algorithme =trouver la relation entre la taille des données et le coût de l’algorithmesur un (modèle de) machine donnée

23 / 41


Coût d’un algorithme

Coût (au pire)Le coût d’un algorithme A est fonction de la taille des données :

CA(n) = max(coût(d)) pour toutes les données d de taille n

I Suppose d’avoir fixé la notion de tailleI Maximum = garantie quelles que soient les conditions d’utilisationI Exhiber un cas défavorable « suffit »

Coût au mieux

CminA (n) = min(coût(d)) pour toutes les données d de taille n

I Correspond au cas le plus favorable

Quel comportement privilégie-t-on ? 24 / 41


Méthodologie

Coûts des structures de base

Instructions en séquenceLe coût de

Faire TrucFaire Machin

est la somme des coûts de Truc et de Machin

Composition des coûts

Le coût d’une boucle est donc la sommedes coûts de chaque itération

Instructions FOR, WHILE, REPEAT,...

26 / 41


Méthodologie

Coûts des structures de base (2)

Instructions conditionnellesif condition

Faire Trucelse

Faire MachinCoût de l’une des branches plus le coût d’évaluation de la condition

Majoration du coûtLe coût au pire sera donc majoré par le maximum des coûts au pire dechaque branche.

Cout(si Condition alors A sinon B) ≤ Cout(evaluation(Condition))+maxCout(A),Cout(B)

Instructions IF, SWITCH,... 27 / 41


Méthodologie

Coûts des structures de base (3)

Appel de procédureLe coût de l’appel d’une procédure est :

I le coût du corps de la procédure pour ses paramètres d’appelI plus le coût de l’évaluation de ses paramètres.

Méthode de calcul de coûtLe calcul du coût d’un algorithme s’obtient donc en composant les coûtsdes différentes opérations composant l’algorithme.

I assemblage et reconstructionI méthode par compositionI se fait à la conception de l’algorithme

28 / 41


Méthodologie

Exemple

Calcul de la somme des entiers de 1 à ni := 1somme := 0Tantque (i ≤ n) :

somme := somme + ii := i + 1

I Coût d’une itération = 2 (additions) + 1 testI Nombre d’itérations = nI Coût de la boucle = 3nI Coût de l’algorithme = 3n + 1

Niveau de détail judicieux ?

29 / 41


Ordres de grandeur

Ordres de grandeur

I La complexité est une prédiction du temps d’exécution duprogramme codant l’algorithme.

I Mais dépend de l’architecture de la machine, donc c’est uneabstraction (approximation)

I Passage à l’échelle des algorithmes

Ce qui est important c’est :

1. l’ordre de grandeur ;2. de pouvoir comparer les algorithmes

Complexité d’un algorithmeOn appelle complexité d’un algorithme une fonction de référence(logarithme, polynome, exponentielle...) comparable à son coût.

31 / 41


Ordres de grandeur

Exemples n = 106n = 109

I moyenne des éléments d’un tableau de taille n⇒ complexité en n opérations

1/1000e s1 sI tri par insertion des éléments d’un tableau de taille n⇒ complexité en n2 opérations

1/4 h30 ansI énumération des vecteurs de bits de taille n⇒ complexité en 2n opérations

10300 000 années...

Définir des ordres de grandeur comparables

Pour se donner une représentation concrète : sur un PC récent, environ 1milliard d’opérations / seconde

32 / 41


Ordres de grandeur

Borne supérieure asymptotique

Notation OPour une fonction donnée g on note O(g) l’ensemble de fonctions :

O(g) = f telles que ∃c ≥ 0,∃n0 ≥ 0,∀n ≥ n0, f (n) ≤ c.g(n)

On écrit f = O(g) pour f ∈ O(g).On dit que g est une borne supérieure asymptotique pour f .

Vite dit : g dépasse f à partir d’un certain rang (taille de données)

Pause courbesExemples

n = O(n3) 1250n3 = O(2n)

n +√n = O(n) n

√n + n log n = O(n

√n)

33 / 41


Ordres de grandeur

Échelles de comparaison (à connaître)

Échelle polynomiale

I Si k ≤ l alors nk = O(nl )

Échelle logarithmique

I log(n) = O(n)I log(log(n)) = O(log(n))

Échelle exponentielle

I Si 0 < a < b alors an = O(bn)I Pour tous a > 1 et k ≥ 0 on a nk = O(an)

Deux propriétés utilesSi f = O(g) alors f + g = O(g) et k × f = O(g) 34 / 41


Ordres de grandeur

Autres encadrements

f = O(g) si ∃c ≥ 0,∃n0 ≥ 0,∀n ≥ n0, f (n) ≤ c.g(n)

Borne inférieure asymptotique (notation Ω)

f = Ω(g) si ∃c ≥ 0,∃n0 ≥ 0,∀n ≥ n0, c.g(n) ≤ f (n)

Borne asymptotique approchée : (notation Θ)

f = Θ(g) si ∃c1, c2 ≥ 0,∃n0 ≥ 0,∀n ≥ n0, c1.g(n) ≤ f (n) ≤ c2.g(n)

35 / 41

Algorithmique et Analyse d’AlgorithmesAlgorithme de Horner

Évaluation d’un polynôme

Un polynôme P à une seule variable X s’écrit de façon unique

P = anX n + an−1X n−1 + . . . + a1X + a0

Résultat : La valeur P(x0)

Données : Les coefficients an, . . . , a0 suffisent à donner le polynômeRangés dans un tableau A de taille n + 1Une valeur x0 en laquelle on veut évaluer le polynôme

Types de données :I les coefficients an, . . . , a0 sont des flottantsI x0 peut être un flottant mais aussi une matrice, un polynôme...

I Incidence sur le modèle de coût

37 / 41


Algorithme (très) naïf

Évaluation de P en x0EVAL(P,x0)Données : Un tableau de coefficients A et un flottant x0Résultat : La valeur de P(x0)r = 0i = nwhile i ≥ 0

p = 1k = 0while k 6= i

p = p × x0k = k + 1

(calcul de x0i dans p)

r = r + A[i ]× pi = i − 1

Return (r)

Complexité en O(n2)38 / 41


Évaluation droite-gaucheIdée : ne pas recalculer les puissances de x0 pour rien

Évaluation de P en x0 par la droiteEVAL_DROITE(P,x0)Données : Un tableau de coefficients A et un flottant x0Résultat : La valeur de P(x0)r = 0i = 0p = 1while i ≤ n

r = r + A[i ]× pp = p × x0i = i + 1

Return (r)

Complexité en O(n)

39 / 41


Évaluation gauche-droite efficaceOn se base sur la pseudo-factorisationP = ((. . . (an × X + an−1) . . .)× X + a1)× X + a0

Évaluation de P en x0 par la méthode de HornerHORNER(P,x0)Données : Un tableau de coefficients A et un flottant x0Résultat : La valeur de P(x0)r = 0i = nwhile i ≥ 0

r = r × x0 + A[i ]i = i − 1

Return (r)

Même complexité mais :I En place et meilleure constanteI Autres applications : dérivation, division, calcul de racines...

40 / 41


Conclusion

I Un même problème peut être résolu par des algorithmes trèsdifférents

I On peut (parfois) passer de l’un à l’autre par raffinementI L’analyse de complexité est un critère fiable pour les comparerI ... mais pas le seul

La prochaine fois

I schémas récursifsI analyse du coût en moyenneI tri rapide

41 / 41

Documents

Algorithmique et Analyse d'Algorithmes - L3 Info Cours 1 : notion de