[PDF] Algorithmes gloutons 1 Égypte

View - Download Algorithmes gloutons 1 Égypte

Previous PDF

Next PDF

IREM DE LYON

Algorithmes gloutons

Le principe de l"algorithme glouton : faire toujours un choix localement optimal dans l"espoir que ce

choix mènera à une solution globalement optimale.

1 Égypte

On appelle fraction égyptienne une fraction de la forme 1n 1. S oientaetbdeux entiers (premiers entre eux) tels queaÇb. Donner l"expression de la fraction égyptienne la plus grande parmi les fractions égyptiennes strictement plus petites que ab et l"ex- pression de leur différence. 2.

O nc onsidèrel "algorithmes uivant: Xcas

egypte(a,b) :={ localc ,d; c:=a; a:=numer(c/b) ; b:=denom(c/b) ; sia==1alors returnb ; sinon c:=a¡irem(b,a) ; d:=iquo(b,a) +1; return(d, egypte(c ,b*d) ) ; fsi; } : ;dans lequel l"entrée (a;b) est un couple d"entiers avecaÇb. Écrire une version itérative de l"algorithme. 3.

Q uellee stla s ortiede l "algorithmeav ecl "entrée( a,b)AE(2,2nÅ1) oùnest un entier naturel non

nul? 4. Q uelest le rô lede cet algor ithme?Démont rer. 5.

L "algorithmeg loutonpr oposédonn e-t-ilu nedéc ompositionen somme d efr actionség yptiennes

avec le minimum de termes possibles?

Une résolution

1. ab AE1b ba cÅ1Åa¡irem(b,a)b£³ bba cÅ1´

Il n"y a pas d"entierntel queab

È1n

È1b

ba cÅ1puisque cela s"écrit aussiba

ÇnÇbba

cÅ1.1

IREM DE LYON

2.

U nev ersionit érative:

Xcas egypt(a,b) :={ localk,tmp; // k initialisé à sequence vide : k:=seq []; // on réduit la fraction a/b : tmp:=numer(a/b) ; b:=denom(a/b) ; a:=tmp; // boucle principale : tantquea<>1faire // ajout d"un élément à la séquence k : k:=k ,( iquo(b,a)+1) ; // fraction restante et simplification de cette fraction : tmp:=a¡irem(b,a) ; b:=b *(iquo(b,a)+1) ; a:=numer(tmp/b) ; b:=denom(tmp/b) ; ftantque; // ajout du dernier dénominateur à la séquence : k:=k ,(b) ; returnk; } : ;3.

22nÅ1AE1nÅ1Å1(nÅ1)(2nÅ1)

4.

L "algorithmeécr itle q uotient

ab sous la forme d"une somme de fractions égyptiennes à dénomina- teurs strictement croissants. (a)

L "algorithmese ter mine.

a,bdésignent ci-dessous le numérateur et le dénominateur après réduction de la fractionab

A chaque étape,

i. S oitaAE1 (c"est à dire irem(b,a)AE0) et l"algorithme se termine. ii. S oita6AE1. Dans ce cas, on a irem(b,a)6AE0 (puisque, la fraction étant irréductible, on ab non multiple dea). On a donc 0Çirem(b,a)Çaet 0Ça¡irem(b,a)Ça. Les fractions a¡irem(b,a)b£³ bba cÅ1´successives ont (après réduction) des numérateurs strictement décroissants compris entre 1 eta: l"algorithme se termine. (b) La l istedes dénomin ateursr envoyéepa rl "algorithmeest st rictementcr oissante.

On a 2

ba

È2bba

cpoura6AE1 puisqueab est réduite et 2bba cÊjba k

Å1 puisquebba

cÊ1. On a donc 2 ba

Èbba

cÅ1 lorsquea6AE1 (etaussi, defaçonclaire, lorsqueaAE1 puisquebÈ1 à toute étape).

On a donc :ab

¡1b

ba cÅ1Ç1b ba cÅ12

IREM DE LYON

En d"autres termes, la fraction

a¡irem(b,a)b£³ bba cÅ1´est strictement plus petite que la fraction égyp- tienne précédente. Les fractions égyptiennes obtenues dans la suite de la décomposition seront donc strictement plus petites que la fraction égyptienne 1b ba cÅ1et donc à dénomina- teurs strictement plus grands. 5.

Le nombr ede ter mesn "estpas m inimal.

L"algorithme renvoie par exemple la décomposition suivante : 1920
AE12

Å13

Å19

Å1180

alors que l"on a :1920

AE10Å5Å420

AE12

Å14

Å15

Ou encore :

5121
AE125

Å1757

Å1763309

Å1873960180913

Å11527612795642093418846225

alors que :5121 AE133

Å1121

Å1363

2 Les épreuves dans le gymnase

Dans un gymnase doivent se dérouler une série d"épreuves. Les épreuves ne sont pas seulement carac-

térisées par leurs durées : chaque épreuve est caractérisée par une date de débutdiet une date de fin

f i.

On souhaite "caser" le plus possible d"épreuves, deux épreuves ne pouvant avoir lieu en même temps

(leurs intervalles de temps doivent être disjoints).

Glouton 1 -

O ntr ieles ép reuvespa rdu réecr oissante,on choisit l aplu scour te,puis la p lusc ourte parmi celles qui lui sont compatibles, puis ...Ce choix mène-t-il au déroulement d"un nombre d"épreuves maximal?

Glouton 2 -

O ntrielesévénementspardatesdecommencementcroissantesetongloutonne:onchoi- ...Même question.

Glouton 3 -

O nt riecet tefois les événement sp arn ombred "intersectionsc roissant: on ch oisitd "abord celui qui intersecte le moins d"événements, puis ...Même question.

Glouton 4 -

O nt riel esévénemen tspar dat esde fin cr oissanteset on glou tonne: on ch oisitl "épreuve patibles à la première...Même question.3

IREM DE LYON

Une résolution

Glouton 1 -

N onop timal.C ontre-exemple: `k

i L"algorithme choisiti: une épreuve alors que deux sont possibles.

Glouton 2 -

N onop timal.C ontre-exemple: L"algorithme choisit une épreuve au lieu de plusieurs.

Glouton 3 -

N onop timal.C ontre-exemple: a

L"algorithme choisitaet trois événements seront choisis au total. Alors que l"on peut clai- rement en choisir 4.

Glouton 4 -

O ptimal.

On notefla date de fin la plus petite.

Soit¡AE{f1,f2,...,fk} un ensemble de dates de fin d"épreuves définissant une solution optimale avecf1Çf2Ç¢¢¢Çfk. optimal (même nombre d"épreuves). On note ensuitef0la date de fin la plus petite parmi les dates de fin d"épreuves compa- tibles avecf(c"est à dire les épreuves de date de débutÈf). Sif26AEf0, on remplace une épreuve correspondant àf2par une épreuve correspondant àf0, cela est possible puisquef0compatible avecfetf0Éf2Ç.... L"ensemble¡00AE {f,f0,...,fk} est donc également optimal (même nombre d"épreuves).

3 Monnaie

1.

O ndisp osede p iècesd emon naie(san sli mited "effectifs)de 18 ch loubis, 7 ch loubise t1 c hloubi.

On gloutonne ainsi : on utilise des pièces de 18 chloubis tant qu"on peut, puis des pièces de 7 tant

qu"on peut, puis des pièces de 1. Cette gloutonnerie donnera-t-elle une réponse optimale? 2.

La même g loutonneriecon duit-elleà u nnombr eminimal de p iècesl orsqueles pièces s ontdes

pièces 10, 5, 2 et 1?4

IREM DE LYON

3.

S oitp2N,pÊ2. La même gloutonnerie conduit-elle à un nombre minimal de pièces lorsque les

pièces sont des pièces de 1,p,p2,p3, ...,pk?

Une résolution

1.

L "existencede p iècesde 1 c hloubiassu reque l "algorithmedon neu nef açond ep ayer.M aisl "algo-

rithme ne renvoie pas une solution optimale.

Avec Xcas :Xcas

monnaie(n,a,b,c) :={ localna,nb,nc; na:=iquo(n,a) ;n:=irem(n,a) ; nb:=iquo(n,b) ;n:irem(n,b) ; nc:=iquo(n,c) ;n:=irem(n,c) ; return(na,nb,nc,n) ;

} : ;monnaie(21,18,7,1)renvoie (1,0,3,0). Le dernier 0 signifie que tout est payé : avec 1 pièce de 18

chloubis et 3 de 1 chloubi. Alors qu"on peut payer avec 3 pièces seulement (3 pièces de 7). 2.

A vecx cas: Xcas

monnaie(n,a,b,c ,d) :={ localna,nb,nc,nd; na:=iquo(n,a) ;n:=irem(n,a) ; nb:=iquo(n,b) ;n:irem(n,b) ; nc:=iquo(n,c) ;n:=irem(n,c) ; nd:=iquo(n,d) ;n:=irem(n,d) ; return(na,nb,nc,nd,n) ; } : ;La réponse de l"algorithme est optimale dans ce cas.

Une solution optimale :

(a) u tiliseau plu sune p ièced e5 (sinon on r emplace2 pièces de 5 par u nepièce de 10 ), (b) au plu s2 pièces de 2 (sinon o nr emplace3 p iècesde 2 p aru nede 5 + u nede 1 ). (c) au plu s1 pièce de 1 (sinon o nr emplace2 p iècesde 1 p aru nepièce de 2 ).

La somme payée avec les pièces de 1, 2, 5 est donc d"au plus 1Å2£2Å5AE10. Elle ne vaut pas

10 (sinon on remplace par une pièce de 10). Elle vaut donc au plus 9. Le nombre de pièces de 10

utilisées est donc égal àbn10 c, c"est à dire le nombre calculé par l"algorithme glouton.

Pour payer le reste, c"est à diren:AEmod(n,10), une solution optimale payera en pièces de 1 et 2

au plus 1Å2£2AE5 chloubis. Cette somme est en faitÇ5 (sinon ...) et le nombre de pièces de 5

utilisés est doncbn5 c.

De même pour le nombre pièces de 2.5

IREM DE LYON

3. L "algorithmeest op timaldan sce c aségalement . Xcas money(n,p,k) :={ localj , liste ; liste :=seq []; pourj de k jusque 0 pas¡1faire liste := liste ,( iquo(n,p^j ) ) ; n:=irem(n,p^j ) ; fpour; returnliste ; } : ;Une solution optimale utilise : (a) au plu sp¡1 pièces valantpk¡1(sinon on en remplaceppar une pièce depk). (b) au plu sp¡1 pièces valantpk¡2(sinon on en remplaceppar une pièce depk¡1). (c) La somme payée avec les pièces de 1,p, ...,pk¡1est donc d"au plus : le nombre de pièces depkchloubis utilisées dans une solution optimale pour payernchloubis est doncbnp kc, c"est à dire le nombre déterminé par l"algorithme ...et ainsi de suite (lien avec algo-

rithme des divisions en cascade pour l"écriture d"un nombre en basep).4 Deux algorithmes sur des graphes

4.1 Couplage

SoitGun graphe, on appelle couplage tout ensemble d"arêtes tel que deux arêtes quelconques de cet

ensemble ne sont jamais incidentes à un sommet commun. Les arêtes du graphe ci-dessous sont pon-

dérées. On aimerait déterminer un couplage de poids maximal. Appliquer le principe glouton (c"est à

dire : choisir l"arête de poids maximal, puis l"arête de poids maximal parmi les arêtes que l"on peut en-

core choisir ...). Aboutit-on à un couplage de poids maximal?abcdf e

46318975

2 6

IREM DE LYON

Une résolution

Le choix glouton mène à choisir d"abord l"arête de poids 9 :abcdf e

46318975

2 puis l"arête de poids 6 : abcdf e

46318975

2 Ce couplage a un poids de 9Å6AE15 et n"est pas maximal :abcdf e

46318975

2

4.2 Arbre de poids maximal

Algorithme de Kruskal.

Un arbre dans un grapheGest un sous-graphe qui ne possède aucun cycle. Les arêtes de l" arbre ci-

dessous sont pondérées. Le choix glouton (on choisit l"arête de poids maximal, puis l"arête de poids

maximal parmi celles qui peuvent encore être choisies...) mène-t-il à un arbre de poids maximal?

On admettra : "Tous les arbres couvrants d"un graphe connexeGont le même nombre d"arêtes (à savoir

n¡1 oùnest le nombre de sommets).»7

IREM DE LYON

Une résolution

On choisit l"arête de poids maximal, puis l"arête de poids maximal parmi celles qui peuvent encore être

choisies... : le principe est le même que pour le couplage mais la contrainte n"est plus la même...

Le choix glouton mène à choisir d"abord l"arête de poids 9 :abcdf e

46318975

2 puis l"arête de poids 8 : abcdf e

46318975

2 puis l"arête de poids 7 : abcdf e

46318975

2 l"arête de poids 6 : 8

IREM DE LYON

abcdf e

46318975

2 et enfin l"arête de poids 5 : abcdf e

46318975

2

Cet algorithme porte le nom d"algorithme de Kruskal. Il mène toujours à un arbre couvrant de poids

maximal (cf paragraphe suivant).

Ici le caractère maximal est évident puisque les poids des arêtes non choisies sont tous strictement in-

férieurs au min des poids des arêtes choisies, tout échange diminuerait donc le poids total.

On pourrait avoir une situation a priori plus ambiguë avec par exemple (le deuxième 8 n"est pas choisi

par l"algorithme car il fermerait un cycle) :abcdf e

46388975

2

4.3 Matroïde

1.

Les couplages d "ungr aphec onstituentu nefa milled "ensembles" héréditaire»: si u nensemb leH

d"arêtes est un couplage du grapheGalors tout ensembleH0d"arêtes contenu dansHest aussi un couplage du grapheG.9

IREM DE LYON

Les ensembles d"arêtes d"un grapheGengendrant un graphe sans cycle vérifient également cette

propriété d"hérédité : si un ensembleHd"arêtes engendre un graphe sans cycle alors tout en-

sembleH0d"arêtes contenu dansHengendre aussi un graphe sans cycle. 2.

F ormulationd el "algorithmeg loutonpour un couple ( E,I) oùEest un ensemble fini d"éléments

(par exemple : l"ensemble des arêtes d"un graphe) etIune famille de parties deEhéréditaire (par

exemple, la famille des couplages ou la famille des graphes sans cycles d"un graphe). Les éléments

deIseront nommés parties indépendantes.Entréele couple (E,I)et une fonction poidsw(à valeurs positives) définie surE.TraitementJ:AE?,A:AEETantQueA6AE?e:AEélément deAde poids maximalA:AEA¡eSiJÅeest une partie indépendante alorsJ:AEJÅeFinTantQue

SortieJ

L"algorithme se termine toujours (puisqueEest fini). Sous certaines conditions (voir ci-dessous), il donnera une partie indépendante de poids maximal. 3. La familledesensemblesd"arêtesd"ungrapheengendrantungraphesanscyclevérifielapropriété d"échange (on ne le démontrera pas ici) : " siHetH0sont des ensembles d"arêtes du grapheG

engendrant un graphe sans cycle et si¯¯H0¯¯ÇjHjalors il existe un élémentedeHtel queH0Åe

engendre un graphe sans cycle.»

De façon plus générale, un système (E,I) héréditaire sera appelé matroïde s"il vérifie la propriété

d"échange : "siHetH0sont des parties indépendantes et si¯¯H0¯¯ÇjHjalors il existe un élémente

deHtel queH0Åeest une partie indépendante.» (a)

Vér ifierqu ela f amilledes couplages d "ung raphen ep ossèdepas l ap ropriétéd "échange.

(b)

Vér ifierq uep ouru nsystème hérédita irequ in "estp asu nm atroïdel "algorithmeglou ton

énoncé ci-dessus peut ne pas mener à une partie indépendante de poids maximal. (c)

Vér ifierq ue,p ourun mat roïde,l "algorithmeglou tonci- dessusmène à u nep artiein dépen-

dante de poids maximal (et en particulier, l"algorithme de Kruskal donne un arbre couvrant de poids maximal).

Une résolution

a -

Le c ouplagesu ivantabcdf

e

46318975

2 10

IREM DE LYON

ne peut pas être "complété» en un couplage par une arête du couplage : abcdf e

46318975

2 b -

O na vu un exemp lep lusha utav ecles cou plages.

De façon plus générale :

Soit (E,I) un système héréditaire ne vérifiant pas la propriété d"échange. SoientIetJdeux parties

indépendantes avecjIjÇjJjtelles que pour toute2J¡I,IÅen"est pas une partie indépendante.

NotonspAEjIj. Soitwdéfinie surEpar :

w(e):AE8 >:pÅ2 poure2I pÅ1 poure2J¡I

0 sinon

L"algorithme va d"abord épuiser les éléments deI, toute arête éventuellement ajoutée ensuite sera

de poids nul. L"algorithme construit donc une partie de poidsp(pÅ2)AEp2Å2p, ce qui n"est pas maximal puisqueJpèse au moins (pÅ1)2AEp2Å2pÅ1. c -

S oitIAE{e1;e2;...;en} une partie indépendante obtenue par l"application de l"algorithme (les élé-

quotesdbs_dbs33.pdfusesText_39

[PDF] formuler une demande poliment

[PDF] demander un service par mail

[PDF] demander un service poliment

[PDF] sms pour demander un service

[PDF] demander quelque chose avec politesse

[PDF] comment demander quelque chose par mail

[PDF] comment demander un service ? quelqu un

[PDF] demander une faveur ? quelqu'un

[PDF] exemple mail demande d information

[PDF] demandeur d'asile allocation

[PDF] demandeur d'asile définition

[PDF] demande d'asile en france procedure

[PDF] différence entre demandeur d'asile et réfugié politique

[PDF] un demandeur d'asile peut il travailler

[PDF] qu'est ce que le droit d'asile