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] 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 gloutonsAlgorithmes gloutons2 / 83Rappel
Nous avons traité deux types de problèmes :
ILes 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). Lecoû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)IProgrammation 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"optimisationIdée de base :
I Résoudre le problème en une séquence d"étapes/choixIPour 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 7153
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 7153
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 1046solutions à 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 7153
42
Chemin initial : a
Coût initial :0
Algorithmes gloutons11 / 83Figure -Construction de la solution gloutonne étape par étapec b ad 7153
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 à trouverAlgorithmes gloutons15 / 83
Algorithme Glouton pour le voyageur de
commerceAlgorithme :Glouton(n,distance)
Données :n2N: nombre de villes,distance[i][j]2R+: la distance entre villeiet villejRésultat :Permutation de 1; : : : ;n
débutEnsemble f1; : : :ng; element 1 ;Permutation element;
Ensemble Ensemblen felementg;
tant quejPermutationjAlgorithmes 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 :IEest 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)FSiF2 I,H2 IetjFj SoitM= (E;I)un matroïdeMest pondéré s"il existe une fonction de poids pour les éléments deE. Pour chaque 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 n=jEj(car le tri peut se faire enO(nlog(n))).Algorithmes gloutons21 / 83L"importance des matroïdes 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 : Lecoûtd"une solution est la valeur correspondante à la fonction objectifPour exploiterGlouton(M(E;I),w) pour un problème d"optimisationP: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 Pourquoi calculer la complexité en fonction de lataille de la donnée?Sinon quel paramètre choisir? Multiplication dexpary: en fonction dex? dey? dex+y? dexy?Sinon comment comparer des algorithmes avec des données différentes? triSélection:(n2)opérations,jTj=n, donc(jLj2)opérationsComment connaitre la taille de la donnée? Typelisted"int:(n)(pour une liste de longueurn)Borne supérieure (O)Trouver un encodageBorne inférieure ( Sicest de type "char" alorsjcj 2 O(1), et doncjcj 2(1)Représentation des Données28 / 83Encodage d"un entiern2N00000001001011 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 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 Les choixmutuellement exclusifsse combinent par addition.Ex : combien de choix possibles de plats principal si on a 3 types de viande, 2 poisson 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 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 kmots binaires de longueurk(Principe multiplicatif)Il faut au moins autant de mots binaires que de valeurs possibles pour la donnée 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 Entier naturel inférieur ou égal àn:n+1, soit(n)Pourxun entier naturel inférieur ou égal àn:jxj 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 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 d"un algorithmeChoisir la structure pour laquelle les opérationsutilessont les plusefficacesUntype abstraitest défini par les opérations qui sontefficacessur ce type 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)? Une tableTavecT[x]contenant les informations pour l"étudiantxUtiliser le numéro de sécurité sociale? 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é,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é
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 ;
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 ;
Représentation des Données
Représentation des Données24 / 83Complexité en fonction de la taille de la donnée Typeschar,int,float, etc. :O(1)I
TypeN:(logn)(pour un entiern)I
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)
32
42
52
62
7|{z} N 32valeursReprésentation des Données31 / 83
Principes des tiroirs
Principe des tiroirs
Simobjets sont rangés dansntiroirs, alors un tiroir en contient au moinsdmn 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 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 Algorithme :Carré(x)
Données :un entierx
Résultat :un entier valantx2
r: entier; débutr 0; Structure de données
Le choix de la structure de données est très important dans la conception 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