[PDF] Algorithmique et Complexité Algorithmes gloutons



Previous PDF Next PDF







Algorithmique et Complexité Algorithmes gloutons

Algorithmique et Complexité Partie II EmmanuelHebrardetMohamedSiala Algorithmes gloutons Algorithmes gloutons 2 / 83 Rappel Algorithme : Glouton (n, distance)



Complexité Algorithmique: Algorithme Glouton et Programmation

Algorithme Glouton Cadre générale d’un algorithme glouton Pour mettre au point un algorithme glouton, il faut donc: Trouver un critère objectif Trouver un critère de sélection qui parait optimal: souvent facile L’implémenter: en général facile et efficace 10 Chiheb-Eddine Ben N’Cir (ESEN) Complexité Algorithmique: 2016 10 / 1



Algorithmique Avancée et Complexité: Algorithmes Gloutons

Algorithmique Avancee et Complexit´ e:´ Algorithmes Gloutons (greedy algorithms) AAC Sophie Tison-USTL-Master1 Informatique



Algorithmique avancée et complexité Algorithmes gloutons

Ecrire un algorithme glouton résolvant le problème, cad renvoyant la liste des pompes a essence ou l’on doit s’arrêter Pour un réservoir de 250 Km, tester avec la liste [120, 142, 90, 70, 130, 150, 84, 25, 110]



GRAPHES ET COMPLEXITE

Un algorithme glouton : principe g´en´eral Pour un probl`eme d’optimisation, on construit la solution de fac¸on s´equentielle, en faisant `a chaque ´etape le meilleur choix local Pas de retour en arri`ere : on va directement vers une solution Progression descendante = choix puis r´esolution d’un probl`eme plus petit 32



Algorithmes gloutons - Education

D’autres systèmes ne sont pas canoniques L’algorithme glouton ne répond alors pas de manière optimale Par exemple, avec le système {1,3,6,12,24,30}, l’algorithme glouton répond en proposant le rendu 49 = 30+12+6+1, soit 4 pièces alors que la solution optimale est 49 = 2×24+1, soit 3 pièces La réponse à cette difficulté



Exercice 1 : Complexité des algorithmes (8 points)

Exercice 2 : Algorithme glouton – Problème du sac à dos (6 points) On dispose d'un ensemble S de n objets Chaque objet i possède une valeur b i et un poids w i On souhaiterait prendre une partie T de ces objets dans notre sac à dos, malheureusement, ce dernier dispose d'une capacité limitée (en poids) W



Algorithmes gloutons - IRIF

Algorithme de Prim “on fait pousser un arbre” A chaque étape de l’algorithme, (S,A’) correspond à un arbre et un ensemble de sommets isolés (on part de ∅) L’algorithme choisit une arête de poids minimal reliant un sommet isolé à l’arbre Exemple q0 q1 q2 q3 q4 q5 q6 q7 q8 2 2 2 4 1 3 2 2 1 8 5 3 4 2 2 Utilisation d’une



Algorithmes gloutons - ressourceelecfreefr

Algorithme glouton – NSI - L R - Lycée R Doisneau Page 2 Analysez la démarche que vous avez utilisée et demandez-vous si elle donne une solution optimale 1ere méthode : on essaie toutes les possibilités et on voit celle qui est optimale



Complexité des algorithmes - diluniv-mrsfr

Complexité des algorithmes Evaluation du nombre d’opérations élémentaires en fonction de la taille des données, de la nature des données Notations : n : taille des données, T(n) : nombre d’opérations élémentaires Configurations caractéristiques meilleur cas, pire des cas, cas moyen Cours complexité – Stéphane Grandcolas

[PDF] algorithme glouton explication

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

[PDF] corrige bac pro gestion administration 2016

[PDF] corrigé tonea factory

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

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

[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

Algorithmique et Complexité

Partie II

Emmanuel Hebrard et Mohamed SialaAlgorithmes gloutons

Algorithmes gloutons2 / 83Rappel

Nous avons traité deux types de problèmes :

I

Les problèmes de décision : Trouver une solution qui satisfait des critères (i.e., problème

de tri, problème de recherche d"élément, PGCD, etc)I Les problèmes d"optimisation : Trouver une solution qui satisfait des critères et qui minimise ou maximise un coût (e.g., parenthèsage pour la multiplication de matrices). Le

coût dans ce cas s"associe à une "fonction objectif".Nous avons étudié différentes approches de résolutions :

I L"approche force brute (recherche exhaustive, énumération)I Paradigme diviser pour régner (et les algorithmes récursifs)I

Programmation dynamiqueOn découvre aujourd"hui une nouvelle approche de résolution (l"approche gloutonne)

et une jolie structure de représentation de problèmes qui s"appelle "les matroïdes"Algorithmes gloutons3 / 83Algorithmes gloutons (Greedy algorithms)

Contexte : typiquement pour les problèmes d"optimisation

Idée de base :

I Résoudre le problème en une séquence d"étapes/choix

IPour chaque étape, faire un choix qui semble optimal à l"étape couranteAvantage : Rapide en temps de calcul

Inconvénient : Pas de garantie sur l"optimalité

Algorithmes gloutons4 / 83

Exemple : Problème du Voyageur de commerce

Voyageur de commerce (optimisation)

donnée: ensemble de villesquestion: quel est leplus courtcycle passant par toutes les villes une seule fois?Algorithmes gloutons5 / 83Figure -Instance du problème du voyageur de commerce sous forme de graphec

b ad 71
53
42
Algorithmes gloutons6 / 83Figure -Une solution non optimalec b ad 71
53
42

Cycle : a,b,c,d,a

Coût de la solution :7+3+2+5=17

Algorithmes gloutons7 / 83Figure -Une solution optimalec b ad 71
53
42

Cycle : a,c,b,d,a

Coût de la solution :1+3+4+5=13

Algorithmes gloutons8 / 83

Énumération exhaustive?

2 Villes-> 1

3 Villes-> 1

4 Villes-> 3

5 Villes-> 12

n Villes-> (n1)!2 (la moitié du nombre de permutations possible de taillen1)40 villes-> à peu près 10

46solutions à tester!Avec une machine moderne : 31029années (plus queAgeUnivers3)!La recherche exhaustive est inefficace!!

Algorithmes gloutons9 / 83Algorithme Glouton

Idée gloutonne :

I Construction de la solution ville par ville selon l"ordre de visiteI

À partir de la dernière ville visitée, choisir la ville la plus proche qui est non visitée.I

Arrêter quand on visite toutes les villesI

Ajouter la première ville pour construire un cycle.Algorithmes gloutons10 / 83Figure -Construction de la solution gloutonne étape par étape : Initialisation à

partir de "a"c b ad 71
53
42

Chemin initial : a

Coût initial :0

Algorithmes gloutons11 / 83Figure -Construction de la solution gloutonne étape par étapec b ad 71
53
42

Cycle : a,c,d, b, a

Coût courant :1+2+4+7=14C"est la solution retournée par l"algorithme glouton Ce n"est pas une solution optimale mais c"est assez rapide à trouver

Algorithmes gloutons15 / 83

Algorithme Glouton pour le voyageur de

commerce

Algorithme :Glouton(n,distance)

Données :n2N: nombre de villes,distance[i][j]2R+: la distance entre villeiet villej

Résultat :Permutation de 1; : : : ;n

débutEnsemble f1; : : :ng; element 1 ;

Permutation element;

Ensemble Ensemblen felementg;

tant quejPermutationjEnsemble Ensemblen fvilleg; element ville;retournerPermutation;Complexité :O(n2)

Algorithmes gloutons16 / 83Matroïdes

Résoudre des problèmes d"optimisation avec des algorithmes gloutons Unmatroïdereprésente une structure particulière utilisée pour concevoir un algorithme glouton optimalAlgorithmes gloutons17 / 83Définition Un matroïde est un coupleM= (E;I)qui satisfait les conditions suivantes :I

Eest un ensemble fini non videI

Iest un ensemble de sous ensembles deEtel que :F

SiH2 I, etFH, alorsF2 I(on dit queIest héréditaire)F

SiF2 I,H2 IetjFj indépendant"Algorithmes gloutons18 / 83Exemple (simple) de Matroïde I

Eest un ensemble fini non vide (évident)I

Iest héréditaire car :F

Pourf2;4g:fg 2I;f2g 2I;f4g 2I

FPourf1;4g:fg 2I;f1g 2I;f4g 2I

FPourf1g:fg 2I;f1g 2I

FPourf2g:fg 2I;f2g 2I

FPourf3g:fg 2I;f4g 2I

FPourfg:fg 2II

Propriété d"échange :F

PourH=f1;4getF=f2g:F[ f4g 2I

FPourH=f2;4getF=f1g:F[ f2g 2I

FPourH=f4getF=fg:F[ f4g 2I

F...Algorithmes gloutons19 / 83

Matroïde pondéré

SoitM= (E;I)un matroïdeMest pondéré s"il existe une fonction de poids pour les éléments deE. Pour chaque

x2 E,w(x)2R+est le poids dex.SiFest un sous ensemble deE, alors le poids deFse définit avec w(F) =P x2Fw(x)Problème de sous ensemble indépendant de poids maximal : I Donnée :M= (E;I): matroïde etw: fonction de poidsI Question : TrouverF2 Ide poids maximalAlgorithmes gloutons20 / 83Algorithme glouton

Algorithme :Glouton(M(E;I),w)

Données :M(E;I): matroïde,w: fonction de poids Résultat :Sous ensemble indépendant deE(probablement de poids maximal) débutF fg; n jEj;

L Trier(E)par poids décroissant ;

pouri2[1::n]fairesiF[ fL[i]g 2 IalorsF F[ fL[i]g;retournerF;Complexité :Si le test d"appartenance (ligne 7) se fait enO(f(n)), alors

la complexité deGlouton(M(E;I),w) estO(nlog(n) +nf(n))avec

n=jEj(car le tri peut se faire enO(nlog(n))).Algorithmes gloutons21 / 83L"importance des matroïdes

Theorem

Glouton(M(E;I),w) retourne un sous ensemble indépendant optimalAlgorithme :Glouton(M(E;I),w) Données :M(E;I): matroïde,w: fonction de poids Résultat :Sous ensemble indépendant deEde poids maximal débutF fg; n jEj;

L Trier(E)par poids décroissant ;

pouri2[1::n]fairesiF[ fL[i]g 2 IalorsF F[ fL[i]g;retournerF;Algorithmes gloutons22 / 83Glouton(M(E;I),w), alors?Rappel pour un problème d"optimisation :

I Une solutionest une sortie qui respecte les exigences du problèmeI Une solution optimaleest une solution qui (minimise ou maximise) une fonction (objectif).I

Lecoûtd"une solution est la valeur correspondante à la fonction objectifPour exploiterGlouton(M(E;I),w) pour un problème d"optimisationP:I

Il faut trouver un matroïdeM(E;I)pondéré tel qu"une solution optimale deP correspond à un sous ensemble indépendant (i.e., élément deI) de poids maximal qu"on peut calculer à partir deGlouton(M(E;I),w).I

Dans ce cas, l"algorithme glouton est garanti de retourner une solution optimaleCette approche ne marche pas pour tous les problèmes. En particulier, il y a souvent

deux limites :1Difficulté à définir l"ensembleIdes sous ensembles indépendants2Même si on trouveI, le test d"appartenance (F2I?) est coûteux en temps (par exemple

quandf(n) =O(2n).Algorithmes gloutons23 / 83

Représentation des Données

Représentation des Données24 / 83Complexité en fonction de la taille de la donnée

Pourquoi calculer la complexité en fonction de lataille de la donnée?Sinon quel paramètre choisir?

I

Multiplication dexpary: en fonction dex? dey? dex+y? dexy?Sinon comment comparer des algorithmes avec des données différentes?

I Est-ce queFactorielleest plus efficace quetriSélection?I Factorielle:(x)opérations,jxj=log2x, donc(2jxj)opérations I

triSélection:(n2)opérations,jTj=n, donc(jLj2)opérationsComment connaitre la taille de la donnée?

Représentation des Données25 / 83Calculer la taille de la donnée On compte le nombre debitsmémoire, en ordre de grandeur ()Exemples : I

Typeschar,int,float, etc. :O(1)I

TypeN:(logn)(pour un entiern)I

Typelisted"int:(n)(pour une liste de longueurn)Borne supérieure (O)Trouver un encodageBorne inférieure (

)Principe des tiroirs

Représentation des Données26 / 83Encodage

Encodage

Un encodage pour un type de donnéeTest une fonctioninjective: f:T 7! f0;1gkToutx2 Ta un seul codef(x)(fonction) I Sinon on ne peut pas toujours encoderPourx;y2 Tdistincts,f(x)6=f(y)(injective) I Sinon on ne peut pas toujours decoderExemples : ASCII, Morse,...

Représentation des Données27 / 83

Encodage d"unchar01001011

012345672

02 12 22
32
42
52
62

7Représenter les entiers entre 0 et 255 (char)Chaque bit repésente un terme de la sommex=7P

i=0b i2iPourx=75 : 126+123+121+120Borne supérieure (et inféreieure)

Sicest de type "char" alorsjcj 2 O(1), et doncjcj 2(1)Représentation des Données28 / 83Encodage d"un entiern2N00000001001011

2 02 12 22
32
42
52
62
7|{z} N

de 0=Nde bits=7Code en base 2 :O(log2n)pour coder tout entier naturelnProblème : combien de bits allouer pour codern"importe quelentier?1?Donner le nombre de bits "utiles" en préfixe, en code unaire (autant de 0 que de bits

significatifs)Code enO(log2(n))pour le préfixe +O(log2(n))pour le suffixeBorne supérieure

Sin2Nalorsjnj 2 O(logn)Représentation des Données29 / 83Encodage d"un tableau denint813031829114sizeL[0]L[1]L[2]L[3]L[4]L[5]L[6]L[7]Chaqueintrequiert 4 octets :n O(1)Même astuce que pour les entiers, le nombre d"éléments en préfixe :O(logn)n O(1) +O(logn) =O(n)Borne supérieure

SiLest un tableau contenantnint, alorsjLj 2 O(n)Représentation des Données30 / 83Borne inférieure sur la taille de la donnée

Quelques principes de base dedénombrementPrincipe additif

Les choixmutuellement exclusifsse combinent par addition.Ex : combien de choix possibles de plats principal si on a 3 types de viande, 2 poisson

et 3 plats végétariens?3+2+3=8 platsPrincipe multiplicatif

Les choixindépendentsse combinent par multiplication.Combien de menus s"il y a 3 entrées, 4 plats, et 4 desserts?344=48 menusCombien de valeurs possibles pour unintsur 32 bits?2

32valeursReprésentation des Données31 / 83

Principes des tiroirs

Principe des tiroirs

Simobjets sont rangés dansntiroirs, alors un tiroir en contient au moinsdmn

e.Sim>nobjets sont rangés dansntiroirs, alors un tiroir en contient au moins 2Il y a deux londoniens avec exactement le même nombre de cheveux

I Il n"y a pas plus d"un million de cheveux sur un crâne, donc pas plus d"un million de nombres de cheveux distinctsI

Il y a plus d"un million de londoniensI

mlondoniens à répartir parminchevelures possibles)au moins deux londoniens avec la même chevelureReprésentation des Données32 / 83Minorant pour l"espace mémoire un encodage est unefonction injectived"un type de donnée vers les mots binaires : f:T 7! f0;1gkavecf(x)2 f0;1gjxjIl y a 2

kmots binaires de longueurk(Principe multiplicatif)Il faut au moins autant de mots binaires que de valeurs possibles pour la donnée

I

Principe des tiroirs : sinon, des données distinctes ont le même code, etfest non-injectiveMinorant pour la taillejxjd"une donnéexde typeTSoit#(T)le nombre de valeurs possibles du type de donnéeT, la mémoire

jxjnécessaire pour stocker une donnéx2 Test telle que 2jxj#(T),) jxj 2 (log#(T))Représentation des Données33 / 83Bornes inférieures Calculons#(T), le nombre de valeurs possibles pour la donnéexde typeT:I

Entier naturel inférieur ou égal àn:n+1, soit(n)Pourxun entier naturel inférieur ou égal àn:jxj 2

(logn)et puisqu"il existe un encodage tel quejxj 2 O(logn), alorsjxj 2(logn)I

Tableau d"intde longueurn:(232)n, soit(232n)I

Tableau d"intde longueurn:n

P i=0232i, soit(232n)I log2(232n) =32nlog2(2) =32nPourLun tableau d"intde longueurn:jLj 2

(n)et puisqu"il existe un encodage tel quejLj 2 O(n), alorsjLj 2(n)Représentation des Données34 / 83Complexité en fonction de la taille de la donnée

L"algorithmeAest en(f(x))pour une donnéexLa taillejxjde la donnée est en(g(x))Alors la complexité deAest en(f(g1(x)))Exemple

Algorithme :Carré(x)

Données :un entierx

Résultat :un entier valantx2

r: entier; débutr 0;

pouriallant de1àxfairepourjallant de1àxfairer r+1;retournerr;Complexité :(x2)Taille de la donnéejxj= (logx)Autrement dit,x= (2jxj)Donc complexité en(22jxj)(exponentielle!)Représentation des Données35 / 83

Structure de données

Le choix de la structure de données est très important dans la conception

d"un algorithmeChoisir la structure pour laquelle les opérationsutilessont les plusefficacesUntype abstraitest défini par les opérations qui sontefficacessur ce type

I

Insertion(I) : ajouter un nouvel élément

Itest d"Appartenance(A) : vérifier si l"élémentxest présent

ISuppression(S) : supprimer un élémentx

ISuppression du Dernier(SD) : supprimer le dernier élément inséré ISuppression du Premier(SP) : supprimer le premier élément inséré ISuppression du Minimum(SM) : supprimer l"élément minimum Représentation des Données36 / 83Structure de données

Untype abstraitest défini par les opérations qui sontefficacessur ce typeUneréalisationcorrespond à du code (des algorithmes)Type AbstraitRéalisationIASSPSDSM

PileListe chainéeO(1)(n)(n)(n)O(1)(n)Liste chainée avecFilepointeursdébutetfinO(1)(n)(n)O(1)(n)(n)Index statiqueVecteur trié(n)O(logn)(n)N/AN/A(n)File de prioritéTas binaireO(logn)(n)(n)N/AN/AO(logn)EnsembleTable de hâchageO(1)O(1)O(1)(n)(n)N/AN/A(n)Ensemble triéABR, AVL

Arbre rouge-noirO(logn)O(logn)O(logn)N/AN/AO(logn)Représentation des Données37 / 83Exemple : Table de Hâchage

Fichier des étudiants de l"INSA, il faut uneclé uniquepour identificationTatouer chaque étudiant avec son numéro d"inscrit (1;:::;n)?

I

Une tableTavecT[x]contenant les informations pour l"étudiantxUtiliser le numéro de sécurité sociale?

I

Beaucoup trop de clés possibles!Table de Hâchage :nenregistrements / table de taillem2(n)SoitUl"ensemble des clés possibles, avecjUj=M;mMSoith:U7! f1;:::;mgun fonction de hâchage : renvoie un index pour chaque clé,

par ex.h(x) = ((ax+b)modp)modm)avecmpMpremier et 0 qu"il y a unecollisionReprésentation des Données38 / 83Exemple : Table de Hâchage

T[i]T[i1]T[i+1]enregistrement(x)enregistrement(y)h(x) =h(y) =iAnalyse de la complexité du test d"appartenance (A)

I Pire des casTmax(n) = (n)(tous les enregistrements ont la même valeur de hâchage)I PourTmoy(n)on suppose une distribution uniforme des valeurs deh(x)dansf1;:::;mg I SoitLila longueur de la listeT[i], etE(Li)l"espérance deLi:mP i=1E(Li) =nI MaisE(Li)ne dépend pas dei, doncTmoy(n) =E(Li) =n=m2 O(1)Représentation des Données39 / 83

Exemple : Tas Binaire

Invariants : arbre binaire complet; sommet parentfils2 5 8

1295676

50382
5 8

129567

36
50382
5 8 12953
676
50382
3 8 12955
676
50382
3 8 12955
676
50382
3 8 12955
676

503867

3 8

129556

50383
67
8

129556

50383
5 8

1295676

50381
23
4567
89
réalisation : 1 2 3 4 5 6 7 8 9

10 226735336756867356750381295.367

parent dei:bi=2c fils gauche dei: 2i fils droit dei: 2i+1Insertion : la position libre la plus à gauche possible sur le dernier niveau I

Percolationéchange avec le parent jusqu"à ce que l"invariant soit rétabliO(logn)Suppression du minimum : la racine, qu"on remplace par le "dernier" sommet

I

Percolationéchange avec le fils minimum jusqu"à ce que l"invariant soit rétabliO(logn)Représentation des Données40 / 83Tri par tas

Donnée : une listeLd"éléments comparablesPour chaquex2L:Insérerxdans le tas binaireH

Tant queHn"est pas vide:Extraire le minimum deHet l"afficherninsertions enO(logn)nsuppressions enO(logn)Complexité du tri par tas :O(nlogn)Tri par tas est optimal!

O(nlogn)dans le pire des casReprésentation des Données41 / 83Classes de Complexité Classes de Complexité42 / 83Borne inférieure pour les algorithmes de tri

Tri par comparaison

donnée: une liste d"éléments comparablesquestion: quelle est la liste triée de ces éléments?Considérons les algorithmes de tri qui ne peuvent pas "lire" ces éléments, seulement

les comparer (e.g. un tableau de pointeurs vers une classe d"objets comparables).Lors de son execution, cet algorithme va comparerkpaires d"éléments (x;y), le

résultat peut être 0 (x résultats des comparaisons : x= [0;0;1;0;1;1;1;1;0;1;1;0;1;0;0;0;0;1]|{z} kClasses de Complexité43 / 83

Borne inférieure pour les algorithmes de tri

Un algorithme est deterministe, donc deux tables de comparaisons identiques donnent

la même exécution, et donc la même liste triée[0;0;1;0;1;1;1;1;:::][0;0;1;0;1;1;1;1;:::][0;1;0;0;1;0;0;1;:::][1;0;0;0;0;1;1;1;:::][0;1;1;0;1;1;0;0;:::][1;0;1;0;0;1;1;0;:::][0;0;1;0;1;1;1;1;:::].

..2

..n!Au pluskcomparaisons, donc au plus 2kdonnées/exécutions distinctesChacune desn!permutations de la donnée doit correspondre à une exécution distincteprincipe des tiroirs

2 kn!Classes de Complexité44 / 83Borne inférieure pour les algorithmes de tri 2 kn! =)klog(n!)=log(n(n1)(n2):::2)=logn+log(n1) +log(n2) +:::+log(2)= nX i=2logi= n=21X i=2logi+nX i=n=2logi nX i=n=2logn2 n2 logn2 (nlogn)Classes de Complexité45 / 83Borne inférieure pour les algorithmes de tri

Théorème

Tout algorithme de tripar comparaisonest en

(nlogn)Attention, il existe des algorithmes de tri enO(n) I

Mais ces algorithmes font des hypothèses sur les éléments à trierDans le cas général d"éléments comparables sans propriété particulière : impossible de

les trier avec une complexité dans le pire des cas inférieure à (nlogn)Classes de Complexité46 / 83La complexité d"un problème, à quoi ça sert?

Pour pouvoir objectivement analyser un algorithme

I OptimalitéParce que la difficulté du problème détermine le type de méthode I

solution approchée pour un problème difficile?Parce que la difficulté du problème est parfois une garantie

I Cryptographie, Block ChainClasses de Complexité47 / 83

Problème

Définition : Problème'fonction sur les entiersUne questionQqui associe unedonnée xà unerép onsey

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

I"Quel est la valeur du carré dex?"Q

pcc:Réseau :R;Villes :x1;x27!Route :x1;u1;u2;:::;uk;x2Q carr:Entier :x7!Entier :x2Classes de Complexité48 / 83Types de Problèmes

Problèmes généraux (fonctions)

Problèmes d"optimisation : la solution est leminimumd"un ensembleProblèmes de décision : la réponse est dansfoui, nong

Classes de Complexité49 / 83Problème de décision

Problème de décisionQFonctionQ:x7! foui;nongPour un problème d"optimisation, on peut généralement définir un problème

polynomialementéquivalent dont la réponse est dansfoui;nong, :Voyageur de commerce (optimisation)

donnée: ensemble de villesquestion: quel est leplus courtchemin passant par toutes les villes?Voyageur de commerce (décision)

donnée: ensemble de villes, entierkquestion: est-ce qu"il existe un chemin de longueur inférieure àkpassant par toutes

les villes?Classes de Complexité50 / 83Instance Instance : problème avec la donnée ("Combien vaut 567

2?", "Quel est le plus court

chemin entre Toulouse et Paris?")Ne pas confondreproblèmeetinstanceEn particulier, se poser la question de la difficulté d"une instance n"a pas

(beaucoup?) de sensI L"algorithme qui renvoie systématiquement, et sans calcul, la solution de cette instance (correct et enO(1))Classes de Complexité51 / 83

Classes d"Algorithmes

Un algorithme est dit :en tempsconstantsi sa complexité dans le pire des cas est bornée par une constantelinéairesi sa complexité dans le pire des cas est en(n)quadratiquesi sa complexité dans le pire des cas est en(n2)polynomialsi sa complexité dans le pire des cas est enO(nc)avecc>0exponentielsi elle est en(2nc)pour un certainc>1

Classes de Complexité52 / 83Classes de problèmes Comment évaluer la complexité d"un problème?

La complexité d"un problème :

La complexité du meilleur algorithme pour le résoudre

f(n)-TIMEEnsemble des problèmes pour lesquels il existe un algorithme enO(f(n))Tri2(nlogn)-TIMERecherche dans un tableau trié2(logn)-TIMERecherche du maximum dans un tableau2(n)-TIMEClasses de Complexité53 / 83Relation d"Inclusion

Inclusion

Sif(n)2 O(g(n))alorsf(n)-TIMEg(n)-TIME(nlogn)-TIMEn-TIME(logn)-TIMEn

2-TIMEClasses de Complexité54 / 83Problème de Tri

Tri donnée:Une listeLd"objet comparables question:La séquence triée des objets deL(nlogn)-TIME(logn)-TIMEn-TIMETri Max?

Tri2(nlogn)-TIMETout algorithme de tri est en

(nlogn) =)Tri62n-TIMELa recherche du maximum est dansn-TIME, dans(logn)-TIME?Classes de Complexité55 / 83

(Non-)Appartenance à une Classe

f(n)-TIMEEnsemble des problèmes pour lesquels il existe un algorithme enO(f(n))Pour prouver qu"un problème appartient à la classef(n)-TIME

I

il suffit d"un algorithme enO(f(n))Pour prouver qu"un problème n"appartient pas à une classe inférieure

I il faut montrer quetoutalgorithme est en (f(n))Classes de Complexité56 / 83Classe "Temps Polynômial"

Rappel :

f(n)-TIMEEnsemble des problèmes pour lesquels il existe un algorithme enO(f(n))Classe des problèmes pour lesquels il existe un algorithme polynômial :

P-TIMEou simplement :PEnsemble des problèmes pour lesquels il existe un algorithme enO(nc) pour une constantec. P=[quotesdbs_dbs43.pdfusesText_43