GRAPHES ET COMPLEXITE

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 efﬁcace 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 difﬁculté

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 Conﬁgurations 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

GRAPHESETCOMPLEXITE

JohanneCohen

LRI-CNRS,

Charg´eedeRechercheauCN RS.

1R´ef´erencesducours

1.ComputersandIntractabili ty:AGuide tothe

TheoryofNP-Complete nes s,M.R .Ga rey,D. S.

Johnson,1976.

2.AlgorithmDesign,Jon Klein berg,EvaTardos,

Addison-Wesley,2006.

3.TheAlgorit hmDesignManual,StevenSkiena,

Springer2014.

2D´eroulementducours

5s´ eancesdecours:

1.Introduction`alacomplexit´e

2.Lacompl exit´e:lesclassesPetNP.

3.LaNP-c ompl´etudeetlesentiers

4.Algorithmesd'approximation

5.Audel `adelaclasseNP.

Chaques´eanceestd ivis´eeendeuxdedur´e e1H30chacun e: uneparti ecoursetunepartied' exercices.

Evaluationducours:

Ilaura lieule19d´ece mbre(10h`a12h)

Lesdocum entssontautoris´es.

3Introduction`alacompl exit´e:

algorithmesgloutons

JohanneCohen

LRI-CNRS,

Charg´eedeRechercheauCN RS.

Pluspr´eci s´ement

Rappelsurlath´eori edesgraph es

Lesgraphe s

Lesarbres

6Ungrap he

Ungraphe

1 donn´eparuncoupl eG=(V,E),o` u

Vestunensemb le.

E!V"Vestunens emble depaires{u,v}avecu,v#V.

Les´el´ ementsdeVsontappel´ esdessommets(ounoeuds). Les´el´e mentsdeEsontappel´ esdesarˆetes. Lapaire {u,v}peutˆetre repr´esent´eepa r(u,v)ou( v,u). Autrementdit,(u,v)et(v,u)d´ enotentlamˆemearˆete.

Exemple:

V={0,1,...,6}

E={(0,1),(3,4),(5,1),(6,3),(6,4)}.

0 1 2 3 4 5 6

1.Lorsq u'onnepr´ecisepas,pard´efa ut,ung rapheestnon-orient´e.

7Vocabulaire

0 1 2 3 4 5 6 uetvsontditsvoisinss'ilyaun ear ˆeteen treuetv.

Ledegr´edeuestlenombr edevoi sinsdeu.

Remarque:(saufautreconve nti onexplicite)

Lesboucles nesontpasautoris´e es.

8Vocabulaire:cheminsetcycles

0 1 2 3 4 5 6

Unchemindusommetsverslesomm ettestunesui te

e 0 ,e 1 ,···,e n desomme tstelleque e 0 =s,e n =t,(e i!1 ,e i )#E,pou rtout1$i$n. nestappel´ elalongueurduchem in, ondi tquetestjoignable `apartirde s.

Lechem inestditsimplesiles e

i sontdisti nctsdeux-`a-deux.

Uncycleestunchem indelon gueurnon-nulleavece

0 =e n sestdit `adist ancendets'ilexisteu nchemindelongueurn entresett,ma isaucunchem indelongueurinf´e rieure. 9

Vocabulaire:composant esconne xes

Larela tion"ˆetrejoignable"estunerelationd'´equiv alence. Lesclasse sd'´equivalencesontap pel´eeslescomposantes connexes. 0 1 2 3 4 5 6 Ungraph eestditconnexes'iln'y aqu'uneseu leclass e d'´equivalence. Autrementdit,toutsommetestjoi gnable`apart irdetout sommet.

10Lesgraphes sontpa rtout!

Beaucoupdeprobl`emesse mod´el isentpardesobjetsetdes relationsentreobjets.

Exemples:

Legraph eroutier.

Lesr´es eauxinformatiques.

Legraph eduweb.

Beaucoupdeprobl`emesse ram`en ent`adesprobl`emessurles graphes.

Th´eoriedesgraphes:

Euler,Hamilton,Kirc hho!,K¨onig,Edmonds ,Berge,Lov´asz,

Seymour,...

Lesgraphes sontomnipr´esentsen informati que.

11Typedegra phes

Ungraph eestditplanaires'ilpeut serepr´esenters urun plan sansqu'aucun earˆeten'encroiseuneautre. Ungraph eestditbipartisil'en sembleVdessommet sest partitionn´eendeuxsous-ensemblesAetBtelleque chaque arˆeteaitunee xtr´emit´ edansAetl' autredansB. K 3,3

12Exemple:Co lori agedegraphe.

Allouerdesfr´equenc esGSMcor respond`acolorierlessommets d'ungraphe(pl anaire). sommets:des´emetteu rs radio. arˆeteentreuetv:le signal deuperturbevou r´eciproquement. couleur:fr´equencer adi o. Leprobl `emedecoloriaged'ungraphe:col orierlessommets d'ungraphedet ellesortequ'il n'yait aucunearˆeteen tredeux sommetsd'unemˆemec ouleur.

Uncolor iageavec4couleurs

Pluspr´eci s´ement

Rappelsurlath´eori edesgraph es

Lesgraphe s

Lesarbres

14Lesa rbressontparto ut!

Ungraph econnexesanscycl eestappel´eunarbre.

Ungraph esans-cycleest appel´euneforˆet:

chacunedesescomposante sconnex esestuna rbre. D`esqu'onades objets,desre lat ionsentreob jets,etpasde cycle,onadoncunarbr eouu nef orˆet. 0 1 2 3 4 5 6

Lesarbres sontomnipr´esentsen informati que.

15Quelquespropri´ et´es

SoitG=(V,E)un graphe .

Lespropri ´et´essuivantessont´equivalentes:

Gestunar bre;

Gestconnex e,maisnel'estplussione nl`even'imp orte laquelledesesar ˆetes;

Gestconnex eet|E|=|V|%1;

Gestsanscyc leet|E|=|V|%1;

0 1 2 3 4 5 6

16Pluspr´ec is´ement

Repr´esentationdesgraphes

Matriced'adjacence s

Listedesucc esseur s

SoitG=(V,E)avecV={1,2,...,n},

Gpeutˆetre repr´esent´epar unematriceMn"n. M i,j

1si( i,j)#E

0si non

0 1 2 3 4 5 6

0100000

1000010

0000000

0000101

0001001

0100000

0001100

19Pluspr´ec is´ement

Repr´esentationdesgraphes

Matriced'adjacence s

Listedesuc cess eurs

Onasso cie`achaquesommeti,la liste dessommetsjtelsque (i,j)#E. 0 1 2 3 4 5 6

L[0]=(1)

L[1]=(0,5)

L[2]=()

L[3]=(4,6)

L[4]=(3,6)

L[5]=(1)

L[6]=(3,4)

21Meilleurerepr´esentat ion?

Matrice:m´emoireO(n

Listes:m´emoireO(n+m)

o`unnombredesommets, mnombred'arˆetes .

Quelleestlameilleu rerepr´e sentat ion?

Celad´epend ducontexte.

Lam´ ethodepluse"caceest

Testersi(u,v)es tdanslegr aphe.matriced'adjacences Testersicalculerl edegr´e devlistede successe urs

Stockerdesgraphesdens esmatriced'adjacences

Stockerdesgraphescreu xlistede successe urs

Ins´ererousupprimerdesar ˆet esmatriced'adjacences 22

Unpre mierexemple:probl`e medustockage.

Consid´eronsnprogrammesP

1 ,P 2 ,...,P n quipeuven tˆetrestoquer surundisq uedur decapacit´eDgigabytes.

ChaqueprogrammeP

i abe soins i gigabytespourˆetrestock ´e. Touslesprogr ammesnepe uventpasˆetrestock´essu rle disque:( n i=1 s i >D)

Objectif:

Concevoirunalgorithmequ iperme tdemaximiserlenombre deprogra mmesstock´essurledisque .

25Probl`emed'optimisation

Donn´ees:

Xunense mblefini,

vunevalua tiondes´el´ementsdeX:X&R

Funense mbledepartiesdeX(ensembledessolutions

faisables)

Objectif:TrouverS#Fquimaximise laquantit´e

e"S v(e)

Remarque:SiFestl'en sembledespartiesdeX,alors

|X| )op´ erations.

26Ordred egrandeur

Pourunpro cesseu rcapabled'e!ectuerunmilliond'i nstruc tions

´el´ementairesparseconde:

taillennlog 2 nn 2 n 3 1.5 n 2 n n! n=10<1s<1s<1s<1s<1s<1s4s n=30<1s<1s<1s<1s<1s18 m10 25
a n=50<1s<1s<1s<1s11 m36a ' n=10 2 <1s<1s<1s1s12.9a10 17 a' n=10 3 <1s<1s1s 18m''' n=10 4 <1s<1s2 m12h ''' n=10 5 <1s2 s3h 32a''' n=10 6

1s20s12 j31710a '''

Notations:

s=se conde,m=minute,h=heure,a=an, '=le tempsd ´epasse10 25
ann´ees.

27Unalgo rithmer´esolvantleprobl `emedustockage.

Rappel:Trouverunsous-ensem blede{P

1 ,...,P n }decardi nal maximumquipeutˆetr estock´e ssurledisque decapacit´e D.

1.ClasserlesprogrammesP

1 ,P 2 ,...,P n enfonct iondelataille duprogra mmes i :O(nlogn)op´ erations s 1 $s 2 $···$s n

2.Initialiserlarecherchea vecS=(O(1)op´erations

3.Pouri=1`anfaire:laboucl eestex´ecut´ee nfois

Si P j !S s j +s i $D

O(1)op´erations

alorsS)S*{P i

O(1)op´erations

4.RetournerS

Complexit´e(aupire):O(nlogn)

Exemple:Consid´eronsqu'ondispose4programmes detailles3,5,

7,10,e tun disqu edurde capacit´eD=17.

L'algorithmeretourneS={P

1 ,P 2 ,P 3 28

NotationO

(imagescann´eed anslelivreIntroductiontoAlgorithmsdeThoma sH. CormenCharlesE.Lei sersonRonaldL.RivestCl i!ordSte in)

29Th´eor`eme

Th´eor`eme

L'algorithmeretourneunesolutionoptima le.

Preuve:

Ilsu "tde prouve rparr´ecurrencequ' unesoluti onoptimaleS contientles|S|premiersprogrammesayantle spluspetites tailles.

SoitSunesoluti onoptimale

siScontientleprogrammeP 1 ,al orsc'estbon. siSneconti entpasleprogrammeP 1 ,alors PPPP 83715
enrem placantun´el´ementdeSparP 1 PPPP 83115
lasolut ionobtenueresteoptim ale. etains idesuiteenconsid ´eran tlesprogrammes P 2 ,P 3 ...,P |S|

30Unalgo rithmeglouton:principe g´en´eral

Pourunprobl `emed' optimisation,

oncon struitlasolutiondefa¸cons´ equent ielle,enfaisant`a chaque´etapelemei lleurchoixlocal. Pasderetou renarr i`ere:onvadirec tement versunesolution. Progressiondescendante=choi xpuisr´esolutiond'un probl`emepluspetit.

32Unalgo rithmegloutong´en´er ique

1.Classerles´el´em entsdeXparvaluat ionsd´ecroissantes:

v(e 1 )+v(e 2 )+···+v(e n

O(nlogn)op´ erations

2.Initialiserlarecherchea vecS=(;O(1)op´erations

3.Pouri=1`anfaire:laboucl eestex´ecut´ee nfois

SiS*{e

i }#F

O(T)op´erations

alorsS)S*{e i

O(1)op´erations

4.RetournerS

Complexit´e:O(nlogn+nT)

o`uTcorrespondaucoˆutdutest(S*{e i }#F) 33

Graphespond´er´es

Ungraph epond´er´eestungrap heo`uc haquearˆeteeaun poidsw(e). A BC DE F 2 3 1 21
1 3 1 2 5 5 Parabusd enotation,nous´ etendr onslad´efinitiondepoids auxensembles Ad'arˆetes: w(A)= e"A w(e)

35Arbrescouvrants depoidsmaximum

Leprobl `emedel'arbrecouvrantdepoidsmaxi mun:

construireunarbrecouvrantdont lasomme despoidsdes arˆetesestmaximu n.

Donn´ees:

Ungraph eG=(V,E);

Unefonction depoidsw:E&R

Objectif:Trouverunarbrecouvr antTquimaximisela

quantit´ew(T)= e!T w(e). 0 1234
5678
9 15 12quotesdbs_dbs43.pdfusesText_43

[PDF] GRAPHES ET COMPLEXITE

GRAPHESETCOMPLEXITE

JohanneCohen

LRI-CNRS,

Charg´eedeRechercheauCN RS.

1R´ef´erencesducours

1.ComputersandIntractabili ty:AGuide tothe

TheoryofNP-Complete nes s,M.R .Ga rey,D. S.

Johnson,1976.

2.AlgorithmDesign,Jon Klein berg,EvaTardos,

Addison-Wesley,2006.

3.TheAlgorit hmDesignManual,StevenSkiena,

Springer2014.

2D´eroulementducours

5s´ eancesdecours:

1.Introduction`alacomplexit´e

2.Lacompl exit´e:lesclassesPetNP.

3.LaNP-c ompl´etudeetlesentiers

4.Algorithmesd'approximation

5.Audel `adelaclasseNP.

Evaluationducours:

Ilaura lieule19d´ece mbre(10h`a12h)

Lesdocum entssontautoris´es.

3Introduction`alacompl exit´e:

JohanneCohen

LRI-CNRS,

Charg´eedeRechercheauCN RS.

Pluspr´eci s´ement

Rappelsurlath´eori edesgraph es

Lesgraphe s

Lesarbres

6Ungrap he

Ungraphe

Vestunensemb le.

E!V"Vestunens emble depaires{u,v}avecu,v#V.

Exemple:

V={0,1,...,6}

E={(0,1),(3,4),(5,1),(6,3),(6,4)}.

1.Lorsq u'onnepr´ecisepas,pard´efa ut,ung rapheestnon-orient´e.

7Vocabulaire

Ledegr´edeuestlenombr edevoi sinsdeu.

Remarque:(saufautreconve nti onexplicite)

Lesboucles nesontpasautoris´e es.

8Vocabulaire:cheminsetcycles

Unchemindusommetsverslesomm ettestunesui te

Lechem inestditsimplesiles e

Uncycleestunchem indelon gueurnon-nulleavece

Vocabulaire:composant esconne xes

10Lesgraphes sontpa rtout!

Exemples:

Legraph eroutier.

Lesr´es eauxinformatiques.

Legraph eduweb.

Th´eoriedesgraphes:

Seymour,...

Lesgraphes sontomnipr´esentsen informati que.

11Typedegra phes

12Exemple:Co lori agedegraphe.

Uncolor iageavec4couleurs

Pluspr´eci s´ement

Rappelsurlath´eori edesgraph es

Lesgraphe s

Lesarbres

14Lesa rbressontparto ut!

Ungraph econnexesanscycl eestappel´eunarbre.

Ungraph esans-cycleest appel´euneforˆet:

Lesarbres sontomnipr´esentsen informati que.

15Quelquespropri´ et´es

SoitG=(V,E)un graphe .

Gestunar bre;

Gestconnex eet|E|=|V|%1;

Gestsanscyc leet|E|=|V|%1;

16Pluspr´ec is´ement

Repr´esentationdesgraphes

Matriced'adjacence s

Listedesucc esseur s

SoitG=(V,E)avecV={1,2,...,n},

1si( i,j)#E

0si non

0100000