[PDF] Algorithmes gloutons Question 1.2 Donner un





Previous PDF Next PDF



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)?Correction

N(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=bRv

icpieces, 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 de

1.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 : 1

Figure1 { 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 2

Montrer 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.2

CommejS0j=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.Correction

Voici 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'une

seancevsoit 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;jAjLes elementsde Fsont appelesindependants. Question 3.1Montrer que les for^ets d'un graphe correspondent a un matrode.(indication : une for^et qui contientxarbres possedentnxar^etes.)Correction

SoitG= (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

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

si ce n'etait pas le cas, on pourrait les etendre par la propriete d'echange.2Considerons lesmatrodes ponderes

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

|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

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;jAjRemarque Minimiser les p enalitesdes t^ achesen retard = Maximaliser les p enalitesdes t^ aches qui ne sont pas en retard.

Th eoreme: ( X;F), ouXest l'ensemble des t^aches,Fla famille des sous-ensemblesde t^aches independantes est un matrode.

Preuve

H eredite: triviale.

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

Question 4.3Determiner un algorithme glouton qui fournit un ensemble independantA optimal.Correction On peut constater que les caracteristiques utiles a l'algorithme sont celles-la m^emes de

matrode. Cet algorithme peut donc ^etre utilise de maniere generique sur tout problemequi presente ces caracteristiques.

1.

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

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

X i2Fnb(F)3fChaque ar^ete est une frontiere de deux faces et donc on peut en deduire que X

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

SiGpossede des sommets de degre 1, alors il existe bien un sommet de degre au plus7

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

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 :

1.

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.

2 Remarque :En fait, tout graphe planaire peut ^etre colorer avec 4 couleurs. Ce resultat est connu sous le nom de theoreme des quatre couleurs. Il a ete demontre en 1976 par Appel et

Haken.

8quotesdbs_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