[PDF] Algorithmique et Complexité 1 Introduction à la Complexité des

View - Download Algorithmique et Complexité

Previous PDF

Next PDF

Algorithmique et Complexité

Emmanuel Hebrard et Mohamed SialaPlan

1Introduction à la Complexité des Algorithmes

2Analyse Asymptotique

3Algorithmes Récursifs

4Programmation Dynamique

5Algorithmes gloutons

6Représentation des Données

7Classes de Complexité

8Les Classes NP et coNP

2 / 169

Supports de cours

Transparents sur la page du cours (ils seront

distribués!)Support de cours d"Olivier Bournezpour l"Ecole Polytechnique (lien sur la page du cours)"Introduction to Algorithms"

Thomas H. Cormen, Charles E. Leiserson, Ronald L.

Rivest and Clifford Stein

MIT Press."Computational Complexity"

Christos H. Papadimitriou

Addison-Wesley."Computational Complexity : A Modern Approach"

Sanjeev Arora and Boaz Barak

Princeton University.3 / 169Question d"un entretien d"embauche chez Google 479
5 22
14 34
Soit un histogramme avecnbarressur lequel on a versé un volume d"eau infini.I Donnez un algorithme pour calculer le volume d"eau résiduel (16).I Donnez un algorithme pour calculer le volume d"eau résiduel en temps linéaire .4 / 169

Vaincre la Combinatoire : Algo. ou Matériel?

Problème du Voyageur de Commerce

donnée: ensemble de villesquestion: quel est le plus court chemin passant une fois par chaque ville?Méthode "Brute-force" : trois instructions par nano seconde

Un ordinateur plus rapide : une instruction partemps de Planck(5:391044s)Un ordinateur plus parallèle : remplissons l"univers de processeurs d"un mm

3donnéeprocesseur 3 GHzprocesseur de Planckmassivement parallèle

10 villes1/100s

15 villes1 heure

19 villes1 an

27 villes8âge de l"univers35 villes5e+23âge de l"univ. 5/1000s40 villes4e+31âge de l"univ. 12 heures50 villes1;5e+48âge de l"univ. 4000âge de l"universtemps de planck

95 villes5e+131âge de l"univ. 1;3e+87âge de l"univ. 3âge de l"univers5 / 169Complexité des algorithmes

Savoir développer des algorithmesefficacesSavoir analyser l"efficacitéd"un algorithmeComprendre la notion decomplexitéd"un problème

6 / 169

Introduction à la Complexité

des Algorithmes Introduction à la Complexité des Algorithmes7 / 169Problème & Donnée

Définition : Problème'fonction sur les entiersUne questionQqui associe unedonnée xà unesolution Q(x)

I "Quel est le plus court chemin dex1versx2par le réseauR?"

I"Quel est la valeur du carré dex?"Qest une relation, pas toujours une fonction : plus court(s) chemin(s)On peut se restreindre aux fonctions0

B

BBBB@11

2 4 3 9 4 16 5 25
: : : 1 C CCCCAProblème :"Étant donné un ensemble de villes, quel est le plus court chemin passant

une fois par chaque ville?"Instance :"Les préfectures d"Occitanie"Solution :"Auch!Montauban!Cahors!Rodez!Mende!Nimes!

Montpellier!Albi!Toulouse!Carcassonne!Perpignan!Foix!Tarbes"Introduction à la Complexité des Algorithmes8 / 169

Algorithme

Un algorithme est une méthode pourcalculerla solutionQ(x)d"un problème, pour toute

valeur de la donnée xAlgorithme pour le problèmeQComposée d"instructions primitives : exécutable par une machine

Déterministe : une seule exécution possible pour chaque donnée

Correct : termine et retourne la bonne solutionQ(x)pour toute valeur de la donnéexQu"est-ce qu"une "instruction primitive" ?

Pas de définition formelle dans ce cours : langages de programmations classiques

(boucles,conditions,assignements,opérations arithmétiques, etc.)Introduction à la Complexité des Algorithmes9 / 169Preuve de correction

Pour prouver qu"un algorithme est correct (terminaison + résultat attendu) on va souvent utiliser la notion d"invariant de boucleInvariant de boucle

Initialisation : L"invariantest vrai avant la première itération de la boucle.Conservation : Si l"invariantest vrai avant une itération de la boucle, il le reste avant

l"itération suivante a.Terminaison : Une fois la boucle terminée, l"invariantimplique que la solution est

correcte.a.A vantune itération veut dire avant de faire le test de la b oucle'preuve par récurrenceIntroduction à la Complexité des Algorithmes10 / 169

Exemple : TriSélection

L"algorithme suivant trie un tableuaLdenéléments.Algorithme :TriSélection

Données :tableauLdenéléments comparables

Résultat :le tableau trié

1pouriallant de1ànfaire2m i;

3pourjallant dei+1ànfaire4siL[j] i=2030 17 9 29 24 i=309 17 30 29 24 i=40 917 30 29 24 i=50 9 1724 29 30

Introduction à la Complexité des Algorithmes11 / 169Exemple : Prouver queTriSélectionest correctTriSélectiontermine?Oui car :

I En dehors de la boucle principale, il y a un nombre fini d"instructions (0) I

2ème boucle :nest constant,jest strictement croissant et la boucle se termine pourj>n

I

1ère boucle :nest constant,iest strictement croissant, la boucle se termine pouri>n,

et la 2ème boucle termineTriSélectionretourne un résultat correct?Invariant de boucle Inv(i):Au début de laième itération de la 1ère boucle "pour",

(a)trie(i): Lesi1 premiers éléments sont triés

(b)mins(i): Lesi1 premiers éléments sont les plus petitsIntroduction à la Complexité des Algorithmes12 / 169

Invariants pour TriSélection

L"algorithme suivant trie un tableauTdenéléments.Algorithme :TriSélection

Données :tableauLdenéléments

comparables

Résultat :le tableau trié

1pouriallant de1ànfaire2m i;

3pourjallant dei+1ànfaire4siL[j]

Au début de l"itérationi:

(a)i1 1ers éléments triés (b)i1 1ers éléments minimumsi=129 30 17 9 0 24 i=20 |{z} trié30 17 929 24 i=309 |{z} trié1730 29 24 i=40 917 |{z} trié30 29 24i=50 9 1724 |{z}

trié2930 Introduction à la Complexité des Algorithmes13 / 169Démonstration deTriSélectionpar invariant

Au début de laième itération de la 1ère boucle "pour", 2 invariants : (a)trie(i): Lesi1 premiers éléments sont triés (b)mins(i): Lesi1 premiers éléments sont les plus petitsPreuve Initialisation :trie(i)etmins(i)sont vrais lors de la première itération de la boucle

car pouri=1 la liste desi1 premiers éléments est videConservation : Supposons que les invariants soient vrais à l"itérationi. On montre

qu"ils sont vrais à l"itérationi+1 : I Lesi1 premiers éléments du tableauLne changent pas (le seul changement est à la ligne 6 etmi). Donctrie(i)etmins(i)impliquenttrie(i+1).

IA la ligne 6,L[m]est le plus petit élément parmiL[i];:::;L[n]a, et il et échangé avecL[i].

Doncmins(i)impliquemins(i+1).Terminaison : La fin de la boucle correspond au début d"une itérationi=n+1, Mais

trie(n+1)implique queLest totalement trié et donc l"algorithme est correct.a.Il f audraitfaire une aut rep reuvepa rinva riantp ourmontrer ça !!Introduction à la Complexité des Algorithmes14 / 169

Complexité Algorithmique : pourquoi?

Pour développer des algorithmesefficaces, il faut pouvoir :Évaluer la complexité d"un algorithme;

Comparer deux algorithmes entre eux;

XKCDhttps://xkcd.com/Qu"est ce qu"un algorithme efficace?

Critère : utilisation d"uneressource, e.g., letemps(d"exécution) ou l"espace (mémoire)Introduction à la Complexité des Algorithmes15 / 169Le temps d"exécution

Le temps d"exécution

Le temps d"exécution est la durée (en secondes, minutes, etc.) nécessaire au programme pour s"éxecuter.Maisle temps d"éxecution dépend :de la machine; du système d"exploitation; du langage; de la donnée;

On veut une méthodeindépendante de l"environnement.Introduction à la Complexité des Algorithmes16 / 169

Nombre d"opérations élémentaires (I)

Opération élémentaire

Une opération élementaire est une opération qui prend un temps constant Même temps d"exécution quelque soit la donnée

Exemples d"opérations en temps constant

Instructions assembleur

Opérations arithmétiques (+;;), affectation, comparaisonssur lestypes primitifs (entiers, flottants, etc.)Introduction à la Complexité des Algorithmes17 / 169Exemple L"algorithme suivant calculen! =n(n1)(n2)21 (avec 0! =1).Algorithme :Factorielle

Données :un entiern

Résultat :un entier valantn!

1fact 1;

2pouriallant de2ànfaire3fact facti;4retournerfact;nombre coût

initialisation :11 op.itérations :n1 op.mult. + affect. :(n1)2 op.retour fonction :11 op.Nombre total d"opérations :

1+n+ (n1)2+1=3nIntroduction à la Complexité des Algorithmes18 / 169

Exemple : TriSélection

Algorithme :TriSélection

Données :tableauLdenéléments

comparables

Résultat :le tableau trié

1pouriallant de1ànfaire2m i;

3pourjallant dei+1ànfaire4siL[j] itérations :n1 op. affectation :n1 op.itérations :P n i=1(ni1)1 op. comparaison :Pn i=1(ni1)1 op.affectation :n?1 op.

échange :n3 op.Nombre total d"opérations :

n(n+4)n+n+2nX

i=1(ni1) +? + 3nn(2n+5)Introduction à la Complexité des Algorithmes19 / 169Nombre d"opérations élémentaires (II)

Le nombre d"opérations dépend en général de la donnée du problème;

(a)trier 10 entiers est plus facile que trier 1000000 entiers?(b)trier une liste très désordonnée est plus difficile?Le nombre d"opérations est calculé en fonction de la donnée, mais comment tenir

compte de toutes les valeurs possibles? I

Plusieurs types de complexités!pire/meilleur cas ou en moyenne.Quel paramètre choisir? Est-il possible de comparer des algorithmes pour des

problèmes distincts? I On calcule la complexité en fonction de lataille de la donnée:jxjest le nombre de

bits de la représentation en mémoire de la donnéexComment connait-on la taillejxjde la donnéex? (cf. "Représentation des Données")Introduction à la Complexité des Algorithmes20 / 169

Complexité en fonction de la taille de la donnée

SoitCoûtA(x)la complexité de l"algorithmeAsur la donnéexde taillejxj.Complexité dans le meilleur des cas

Inf A(jxj) =minfCoûtA(x)jxde taillejxjgComplexité dans le pire des cas Sup A(jxj) =maxfCoûtA(x)jxde taillejxjgComplexité en moyenne Besoin d"une probabilitéP()pour toutes les données de taillesn Moy

A(jxj) =X

xde taillejxjP(x)CoûtA(x)Introduction à la Complexité des Algorithmes21 / 169Exemple (Recherche dans un tableau)

L"algo. suivant recherche l"élémentedans un tableau.Algorithme :RechercheElmt

Données :un entiereet un tableauL

contenante

Résultat :l"indiceit.q.L[i] =e

i 0 ; tant queL[i]6=efairei i+1;retourneri;Le nombre de comparaisons dépend de la donnéeL:eest dans la case 1!1 comp.eest dans la casej!jcomp.eest dans la casen!ncomp. (n=jLj: taille deL)meilleur :1 comp.pire :ncomp.moyenne : n+12 (voir slide suivant)Introduction à la Complexité des Algorithmes22 / 169

Complexité en moyenne (Recherche)

L"algo. suivant recherche l"élémentedans un tableau.Algorithme :RechercheElmt

Données :un entiereet un tableauL

contenante

Résultat :l"indiceit.q.L[i] =e

i: entier; débuti 0 ; tant queL[i]6=efairei i+1;retourneri;moyenne : n+12Hyp. : distribution uniforme nbOcc(e) =1)P(L[i] =e) =1=n.On applique la formule : Moy

A(n) =X

xde taillenP(x)CoûtA(x) Moy

A(n) =1n

n(n+1)2 Introduction à la Complexité des Algorithmes23 / 169Complexité en moyenne (TriSélection) Inf

TriSélection(n) =n(n+4),SupTriSélection(n) =n(2n+5)Le temps de calculT(n)deTriSélectionpournélément est tel que :

c

1(n2+4n)T(n)c2(2n2+5n)Les valeurs des constantesc1etc2dépendent de :

I Le coût exact des opérations (comparaisons, affectations, etc.)

ILe matériel (processeur, RAM, etc.)

ILe logiciel (langage, compilateur, système d"exploitation, etc.)Impossible à quantifier! Les variations dec1etc2sont plus importantes que le facteur (inférieur à 2) entre n

2+4net 2n2+5nInf

TriSélection(n)'MoyTriSélection(n)'SupTriSélection(n)'cn2Introduction à la Complexité des Algorithmes24 / 169

Exemple : TriRapide

Algorithme :TriRapide

Données :tableauLd"elts comparables, entierss;e Résultat :le tableau trié entre les indicessete

1ProcedureTriRapide(L;s;e)2sis

4TriRapide(L;s;p1);

5TriRapide(L;p+1;e);6ProcedurePartition(L;s;e)7pivot L[e];

8i s;

9pourjallant desàe1faire10siL[j]

12i i+1;13échangerL[i]avecL[e];

14retourneri;Invariants

I

L[0];:::;L[i1]

IL[i];:::;L[j1]pivot17 9 0

9 17

929 30

29173029924pivot

02424pivot30

i;jijjjijiji Introduction à la Complexité des Algorithmes25 / 169Complexité de TriRapide

Algorithme :TriRapide

ProcedureTriRapide(L;s;e)sisTriRapide(L;s;p1);

TriRapide(L;p+1;e);ProcedurePartition(L;s;e)pivot L[e]; i s; pourjallant desàe1fairesiL[j]Ici on compte lenombre de

comparaisons, égal au nombre total d"opérations,à une constante près.TriRapide fait un nombre constant (disonsc1) d"opérations pour chaque comparaison I

Au plus un échange et entre 1 et 2

incrémentation(s)Introduction à la Complexité des Algorithmes26 / 169

Complexité dans le pire des cas (TriRapide)

Algorithme :TriRapide

ProcedureTriRapide(L;s;e)sisTriRapide(L;s;p1);

TriRapide(L;p+1;e);ProcedurePartition(L;s;e)pivot L[e]; i s; pourjallant desàe1fairesiL[j]Le pivot est comparé auxn1 éléments et

reste en dernière positionPartitionretourne toujourse I Partition(L;1;n),Partition(L;1;n1),:::Nombre total de comparaisons : n X i=1(ni)=n2nX

i=1i=n(n1)=2Introduction à la Complexité des Algorithmes27 / 169Complexité en moyenne (TriRapide)

Algorithme :TriRapide

ProcedureTriRapide(L;s;e)sisTriRapide(L;s;p1);

TriRapide(L;p+1;e);ProcedurePartition(L;s;e)pivot L[e]; i s; pourjallant desàe1fairesiL[j]Complexité en moyenne (TriRapide)

z 1z 2z 3z 4z 5z 6z 7z 8z

9Soit la liste triée des éléments deT:z1 nombre de comparaisons est donc : n1X i=1n X j=i+1p(zi;zj)z ietzjsont comparés ssi un des deux est le premier pivot parmizi;zi+1;:::;zj I

sinon, le pivotzkséparezizk!Doncp(zi;zj) =2=(ji+1)(les choix de pivot sont équiprobables)

n1X i=1n X j=i+12ji+1= n1X i=1niX j=12j+12n1X i=1n X j=11j'2nlnnIntroduction à la Complexité des Algorithmes29 / 169Résumons

TriSélection TriRapide

Sup(n)c

1n2c2n2Moy(n)c

3n2c4nlnnSoient :

ITs(n)le temps effectif de calcul pourTriSélectiondenéléments,'Moys(n) =c3n2 I

Tr(n)le temps effectif de calcul pourTriRapidedenéléments,'Moyr(n) =c4nlnnExpérience : essayons pourn=100000 et estimonsn=300000

cquotesdbs_dbs43.pdfusesText_43

[PDF] algorithme glouton explication

[PDF] corrige bac pro gestion administration 2016

[PDF] epreuve e2 gestion administrative des relations avec le personnel 2017

[PDF] der krieg otto dix histoire des arts

[PDF] otto dix der krieg gravures

[PDF] gestion admission bac pro

[PDF] der krieg otto dix description

[PDF] gestion admission post bac 2017

[PDF] gestion admission post bac identifiant

[PDF] otto dix der krieg analyse du tableau

[PDF] la monnaie évaluation ce2

[PDF] apb gestion oullins

[PDF] gestion admission post bac enseignant

[PDF] gestion scei

[PDF] gestion admission post bac mot de passe perdu