Complexité Algorithmique: Algorithme Glouton et Programmation
Complexité Algorithmique: Algorithme Glouton et. Programmation Dynamique. Dr.Chiheb-Eddine Ben N'Cir chiheb.benncir@gmail.com chiheb.benncir@isg.rnu.tn.
Algorithmique et Complexité - Partie II
La recherche exhaustive est inefficace ! ! Algorithmes gloutons. 9 / 83. Algorithme Glouton. Idée gloutonne : ? Construction
GRAPHES ET COMPLEXITE
The Algorithm Design Manual Steven Skiena
Cours complexité – algorithmique Outline
Algorithme de Glouton: Approche gloutonne: Trier les valeurs de pièces de monnaie par ordre décroissant. Pour chaque valeur de pièce maximiser le
Algorithmique et Complexité
1 Introduction à la Complexité des Algorithmes. 2 Analyse Asymptotique. 3 Algorithmes Récursifs. 4 Programmation Dynamique. 5 Algorithmes gloutons.
Cours complexité – algorithmique Outline
Cours complexité – algorithmique (DSSD) cours 6: Algorithmes de Gloutons ?Un algorithme de Glouton est un algorithme qui résout des problèmes.
L3 Info Cours 10 : Algorithmes gloutons Coloration de graphe
Algorithmes gloutons. Exemple : le problème de choix des activités. Graphes. Définitions notations. Manipulation algorithmique. Complexité des algorithmes
Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale
Notons enfin qu'il existe des algorithmes de complexité meilleure que celle en O(n ? S) alors que l'algorithme glouton avait une complexité en O(nlog ...
Algorithmes gloutons
Question 1.2 Donner un algorithme qui calcule N(x) et sa complexité en terme d'opérations. Correction. Algorithme Glouton :.
Coloriage de sommets
Algorithm 1: Algorithme glouton L'algorithme glouton centralisé est correct et termine en n ... Pour cette algorithme la complexité temporelle est.
[PDF] Algorithmique et Complexité
Résoudre des problèmes d'optimisation avec des algorithmes gloutons Pourquoi calculer la complexité en fonction de la taille de la donnée ?
[PDF] LES ALGORITHMES GLOUTONS - NPA
ALGORITHME GLOUTON les algorithmes gloutons ne conduisent pas toujours à la solution optimale Lélia Blin Université d'Evry
[PDF] Algorithmes gloutons [gl] Algorithmique - Unisciel
Complexité Cet algorithme est glouton parce qu'il consid`ere les éléments de E par ordre de poids décroissant et qu'il ajoute immédiatement un élément x `a F
[PDF] Algorithme Glouton et Programmation Dynamique - Esentn
Ecrire un algorithme qui permet de résoudre le problème en utilisant le principe Glouton 7 Chiheb-Eddine Ben N'Cir (ESEN) Complexité Algorithmique: 2016 7 /
[PDF] Chapitre 3 Algorithmes gloutons
HLIN401 : Algorithmique et complexité L2 Informatique I On voit dans ce cours des algorithmes gloutons simples et dont on peut prouver l'optimalité
[PDF] Les algorithmes gloutons
Les algorithmes gloutons constituent une méthode possible de résolution de ce graphes et théorie de la complexité une heuristique est un algorithme qui
[PDF] Algorithmes gloutons
Question 1 2 Donner un algorithme qui calcule N(x) et sa complexité en terme d'opérations Correction Algorithme Glouton : — Trier les types de pi`eces par
[PDF] Algorithmes gloutons
Complexité et Graphe 2014-2015 ENSTA Algorithmes gloutons Exercice 1 Comment rendre la monnaie Nous considérons des pi`eces de monnaie de 1 2
[PDF] Algorithmique Avancée et Complexité - Département Informatique
Algorithmique Avanc´ee et Complexit´e: Algorithmes Gloutons (greedy algorithms) AAC Sophie Tison-USTL-Master1 Informatique
[PDF] Algorithmes gloutons
Algorithmique Avancée et Complexité 2010–2011 Master 1 d'Informatique S Tison Fiche TD : Algorithmes gloutons Exercice 1 : Les gardiens de musée
Complexite et Graphe 2014-2015
ENSTA Algorithmes gloutonsExercice 1Comment rendre la monnaie. Nous considerons des pieces de monnaie de 1, 2, et 5 centimes. NotonsN(x) le nombre minimun de pieces pour obtenirxcentimes. Question 1.1Quelle est la valeur deN(0),N(1),N(2),N(3),N(4),N(5)?CorrectionN(0) = 0,N(1) = 1,N(2) = 2,N(3) = 2,N(4) = 2,N(5) = 12Question 1.2Donner un algorithme qui calculeN(x) et sa complexite en terme d'operations.Correction
Algorithme Glouton:|T rierles t ypesde pi ecespar v aleurd ecroissante. P ourc haquev aleurde pi ece,maximise rle nom brede pi ecesc hoisies. Plus formellement, soitRla somme restante, initialisee aS. Pour chaque valeurvi,prendreci=bRvicpieces, et poserR Rcivi.Pour prouver l'optimalite de l'algorithme glouton avec les valeurs 5;2 et 1 :|Au plus une pi ecede 1 (sinon une d e2)
Au plus deux pi ecesde 2 (sinon une d e5 et un ede 1)Le nom brede pi ecesde 5 est donc bx5
c|Conclure a vecce qui pr ecede 2 Question 1.3Appliquer cet algorithme qui calculeN(14) en considerant maintenant qu'on dispose des pieces de monaies de 1, 7 et 10 centimes. Que constatez-vous?Correction Si on utilise l'algorithme precedent, alors on utilise une piece de 10 et quatre pieces de1.2Exercice 2Comment gerer un cinema
Un cinema possedessalles de cinema. Chaque semaine, le cinema propose une liste de lms a voir. Chaque lm correspond a un nombre ni de seances. Chaque seance se deroule selon un horaire (intervalle de temps) precis. Les lms n'ont pas tous la m^eme duree. On precise qu'il est impossible de changer les horaires des seances. Question 2.1Un etudiant qui a une journee de libre veut voir le maximum de lms pendant cette journee (il peut voir un m^eme lm plusieurs fois). Ce probleme peut ^etre resolu par un algorithme glouton : 1Figure1 { Planning des seances de cinema
Entree :
Un ensem bleIdes seances : chaque seanceiest caracterisee par l'intervalle (di;fi).Sortie
Un ensem bleSdes seances.
1. Classer les in tervallespar v aluationsvcroissantes :v(i1)v(i2) v(in) 2.Initialiser la rec herchea vecS=;;
3.T antque In'est pas vide faire
(a)Choisir i2 Iqui a la plus petite valuation.
(b)Ajouter idansS
(c) Supprimer toutes les s eancesde Iqui ne sont pas compatible aveci 4.Retourner S
Maintenant il reste a determiner la valuation. Donner un exemple ou l'algorithme ne retourne pas la solution optimale : 1. si la v aluationvd'un intervalle est sa date de debut (di).Correction 2 2. si la v aluationvd'un intervalle est sa duree (fidi).Correction 2Montrer que l'algorithme est optimal si la valuationvd'un intervalle est sa date de n (fi).Correction
SoitSla solution retournee par le glouton. SoitSune solution optimale.Notonsjle premier element deSinsere par l'algorithme glouton. Nous allons prouverqu'il existe une solution optimale qui contient elementj. SiScontient elementj, alors iln'y a rien a prouver.
Sinon, notonsil' element deStel queiest l'element deSayant la valeurfila pluspetite.Considerons l'ensembleS0=S fig [ fjg. Tout d'abord, nous pouvons remarquerquefjfi:jse termine avanti. Si ce n'etait pas le cas, l'algorithme glouton aura choisitla seancei. De plus, cela signie aussi que la seancejn'intersecte pas avec les seances deS
figcar toutes les autres seances deS figcommence apres la datefi.2CommejS0j=jSj,S0est une solution optimale qui contientj. Pour prouver queSestune solution optimale, on se restreint aux solutions optimales contenantjet on raisonnepar recurrence.
Les ensemblesSetSont leskpremiers elements identiques (mais ils dierent auxk+ 1 element).Soitilek+ 1 element deS( il n'est pas dansS)i
Soitjlek+ 1 element deS( il n'est pas dansS)j
Nous allons prouver queipeut ^etre remplace par le premier elementjdeSqui n'estpas dansS.En eet il sut de remarquer quefjfi:jse termine avanti. Si ce n'etait pas le cas,l'algorithme glouton aura choisit la seancej.On obtient une autre solutionS0=Sfig[fjgtelle quejS0j=jSjet donc toujoursoptimale.
2 Question 2.2La personne qui gere l'aectation des salles doit aecter a chaque seance une salle. Son probleme est de comprendre si le nombre de salles est susant. Proposer un algorithme polynomial. Justier.Indication : on pourra considerer les seances dans l'ordre de leur date de debut.CorrectionVoici en eet un algorithme :
1. on trie les s eancesp ardate de d ebut; 2. on aecte les salles selon l'ordre obten upar ce tr i(bien en tendu,une salle es tlib eree des qu'une seance est terminee); 3. on calcule le nom bred esalles utilis eespar cette aec tation; 4.si ce nom brede salles est inf erieur as, alors on retourne vrai, sinon on retourne faux.Cet algorithme est correct. En eet, la remarque cle est la suivante : l'algorithme
considere bien une aectation optimale en nombre de salles. En eet, supposons qu'uneseancevsoit aectee dans une sallek. Puisque cette seancevn'a pas ete aectee avant parl'algorithme c'est que la date de debutade cette seance tombe sur un moment ou les salles1 ak1 sont utilisees. Les seances a ce moment la ont toute la dateaen commun dans leurintervalle (par denition de la facon dont fonctionne l'algorithme). Il faut donc au moins
ksalles a ce moment la, et quoi que l'on fasse, dans toute aectation a ce moment la, lenombre de salles est au moinsk. L'algorithme produit donc une solution necessairementoptimale.
L'algorithme est bien polynomial.2Exercice 3La theorie des matrodes permet de comprendre si un algorithme glouton est
optimal pour un probleme. Voici la denition d'un matrode. ( X;F) est un matrode siXest un ensemble denelements,Fest une famille de parties deX(F P(X)) veriant 3 1.Heredite:X2 Fimplique8YX,Y F
2. Echange: (A;B2 F;jAjSoitG= (V;E) un graphe ,jVj=n, on denit alorsX=EetF=fAE=A sans cyclesg, c.a.d. qu'un ensemble d'ar^etes est un independant ssi c'est une for^et.L'heredite est evidente, car un sous-ensemble d'une for^et est une for^et (en enlevant des
ar^etes a une for^et on ne cree pas de cycles).L'echange : SoientAetBdes for^ets deGtqjAj si ce n'etait pas le cas, on pourrait les etendre par la propriete d'echange.2Considerons lesmatrodes ponderes |Soit skle premier element independant deX(= le premier indiceide l'algorithmeprecedent tel quefsig 2 F.|Lemme : Il existe une solution optimale qui con tientsk.|Soit Bun independant de poids maximal, etAla solution retournee par l'algorithme.On ask2A.|Supp osonssk62B(sinon, rien a prouver) : on appliquejBj 1 fois la proprieted'echange pour completerfskgpar des elements deB: on obtient un independantA Th eoreme: ( X;F), ouXest l'ensemble des t^aches,Fla famille des sous-ensemblesde t^aches independantes est un matrode. echange: Soit A;Bindependants avecjAj t(A)Nt(B),Nt+1(A)< Nt+1(B), ...,Nn(A)< Nn(B).DansBil y a plus de t^aches de date limitet+ 1 que dansA: on en prend unexqui n'est pas deja dansA:A[ fxgest independant.2 matrode. Cet algorithme peut donc ^etre utilise de maniere generique sur tout problemequi presente ces caracteristiques. On procede par recurrence sur le nombrefde faces. Sif= 1, le graphe possedeuniquement une unique face. Par consequent, le graphe connexe ne possede aucun cycle et est un arbre. Ainsi,na+f=n(n1) + 1 = 2 et la formule est veriee.Supposons que la formule d'Euler satisfaite pour les valeurs inferieur af.Soiteune ar^ete d'un cycle du graphe. Par denition, l'ar^ete appartient separe deuxfacesAetB. En supprimant cette ar^ete, le nouveau graphe obtenu possede le m^eme nombrede sommets (n),a1 ar^etes. De plus ce graphe af1 faces puisqueAetBforment uneseule face de ce nouveau graphe. En appliquant l' hypothese de recurrence, on a n(a1) +f1 = 2En simpliant on obtientna+f= 2 et le graphe respecte bien la formule d'Euler.Donc tout graphe planaire satisfait la formule d'Euler.2Question 5.2On supposen>3. Montrer que 3f2a.Correction SoitFl'ensemble de faces. Notonsnb(F) le nombre d'ar^etes qui delimitent la faceFChaque faceFest delimitee par au moins 3 ar^etes.nb(F)3Donc i2Fnb(F) = 2aDonc en combinant les deux equations, on obtient 3f2a.2Question 5.3Montrer qu'il existe un sommet de degre au plus 5 dans le graphe planaireG.Correction NotonsD(G) l'ensemble des sommets deGtel que leur degres sont inferieurs ou egalea 5. Nous allons contruire une suite de graphesG1;:::;Gnde la facon suivante1.G1 G2.p ouriallant de 2 anfaire(a)calculer D(Gi);(b)extraire un som metvitel quevi2 D(Gi);(c)construire Gi+1= (Vi+1;Ei+1) tel queV i+1=Vinfvig, etEi+1=Einfe:eest adjacent avidansGig.Tout d'abord remarquons que ces graphes sont des graphes planaires (puisqu'on enleve simplement un sommet entre deux graphesGietGi1.)A partir de cette suite, nous pouvons construire une colorationc:V! f1;:::;6gdela facon suivante : p ouriallant dena 1 faire(a)colorier viavec la plus petite couleur qui n'appartient aux couleurs de son voi-sinnage dansGi;Nous construisons une coloration utilisant 6 couleurs : a chaque iterationi, le sommet aau plus 5 voisins et donc il peut ^etre voisin de sommets ayant au plus 5 couleurs dierentes.Un independant est dit
maximals'il est maximal au sens de l'inclusion. Question 3.2Montrer que tous les independants maximaux ont le m^eme cardinal.Correction On a jouteune fonction de p oidsw:x2 X 7!w(x)2R0.
On p ose
w(X) =X x2Xw(x): Question 3.3Etant donne un matrode pondere, considerons l'algorithme glouton qui construit un independant de poids maximal (vu en cours) 1. T rierles elementsde Xpar poids decroissants :w(s1)w(s2) w(sn): 2.A:=;.
3. P ouri=1 anfaire
(a) Si A[ fsig 2 FalorsA:=A[ fsig
4. retourner A Prouver la validite de votre algorithme.Correction Cet algorithme retourne une solution optimale.
|;est un independant, par heredite.4 0qui contient tous les elements deBsauf un seul que l'on peut appelerbi.|On a w(A0) =w(B)w(bi)+w(sk), orw(sk)w(bi), carfbig 2 F(heredite) etbia ete considere apresskpar ordre decroissant.|Donc w(A0)w(B), doncw(A0) =w(B), etA0est une solution optimale quicontientsk.|Puis par r ecurrence,on obtien tque glouton d onnela solution optimale : on se
restreint a une solution contenantfskg, et on recommence avec X 0=X fskget
F 0=fX X0jX[ fskg 2 Fg:2
Exercice 4Ordonnancement de t^aches
Le probleme de l'ordonnancement de t^aches sur un seul processeur se compose d'un ensem blede t^ achesX=f1;:::;ngde duree 1, a vecd esdates limites d1;:::;dn: la t^acheidoit nir avant la datedi, sinon on doit payer la penalitewi. L'objectif est de trouver un ordonnancement des t^aches pour minimiser la somme des penalites. An de resoudre ce probleme, on utilise les denitions suivantes : Un ensem bleAde t^aches est ditindependants'il est possible de les ordonnancer de sorte que personne ne soit en retard. On note Nt(A) le nombre de t^aches de l'ensembleAdont la date limite estt. Question 4.1Montrer que les 3 proprietes suivantes sont equivalentes 1.Aest independant;
2. P ourt= 1;:::;n, on aNt(A)t;
3. Si les t^ achesde Asont ordonnancees dans l'ordre croissant de leur dates limites, alors aucune t^ache n'est en retard.Correction Preuve :
1 !2 : supposonsNt(A)> t, alors il y a au moins une t^ache qui se deroulera apresle tempst, et doncAne peut pas ^etre independant.|2 !3 : trivial.|3 !1 : par denition.2
Question 4.2Montrer que (X;F), ouXest l'ensemble des t^aches etFla famille des sous- ensembles de t^aches independantes, verie les proprietes suivantes : 5 1.Heredite:X2 Fimplique8YX,Y F
2. Echange: (A;B2 F;jAjPreuve
H eredite: triviale.
T rierles elementsde Xpar poids decroissants
w(s1)w(s2) w(sn):2.A:=;.3.P ouri:= 1 an=jXjfaire(a)Si A[ fsig 2 FalorsA:=A[ fsig4.retourner A2 Question 4.4Appliquer cet algoritme a l'exemple suivant compose de 7 t^aches :i1 2 3 4 5 6 7 d i4 2 4 3 1 4 6 w i7 6 5 4 3 2 1 Correction
Iterations :
|A=f1g;|A=f2;1g;|A=f2;1;3g6 |A=f2;4;1;3g;|A=f2;4;1;3;7g.|R esultat: f2;4;1;3;7get la penalite maximale est 5.2 Exercice 5Coloriage des graphes planaires
Un graphe estplanairesi on peut le dessiner dans le plan sans que les ar^etes ne se croisent. SoitG= (V;E) un graphe planaire non videconnexe. Notonsn=jVj,a=jEj. Considerons un dessin deGdans le plan (sans que les ar^etes ne se croisent). Soitfle nombre de regions du plan delimitees par les ar^etes deG. Question 5.1Montrer que les graphes planaires respectent la relation d'Eulerna+f= 2. (Indication : raisonner par recurrence sur le nombre de faces)Correction 5 dansG.Supposons queGne possede pas des sommets de degre 1. Raisonnons par l'absurde etsupposons que pour tout sommetvdeG,d(v)6. On a 6n2acar la somme de tous lessommets est egale a 2 fois le nombre de ar^etes.
En appliquant la formule d'Euler (na+f= 2), on af= 2 +an.3f2a 3(2 +an)2a
a3n6 2a6n12Ce qui est en contradiction avec 6n2a. Donc il existe un sommet dedegre au plus 5 dansG.2Question 5.4Concevoir un algorithme de 6-coloration des graphes planaires en temps po-
lynomial.Correction Haken.
8quotesdbs_dbs43.pdfusesText_43
[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