[PDF] ´ECOLE JEUNES CHERCHEURS EN ALGORITHMIQUE ET





Previous PDF Next PDF



Fonctions

Lecture graphique. 5. 9. Lecture graphique. 6. 10. Lecture graphique : paraboles Fonction : 2nd degré et valeur absolue ... Fonction affine par morceaux.



´ECOLE JEUNES CHERCHEURS EN ALGORITHMIQUE ET

29?/03?/2004 Réseaux de régulation génétique affines par morceaux ... réalisables qui sont ordonnées en fonction de leur valeur objective.



Réflexion géographique sur la distance une approche par les

23?/02?/2017 La distance n'aurait-elle pas partout la même valeur la même ... spatiale et qui a été muni d'une fonction mathématique de distance.



La contribution du design de lespace de vente à lévolution du

07?/03?/2015 Grille de lecture du design expérientiel de l'espace de vente basée sur la co-? création de valeur avec le chaland .



Reliefs et patrimoine géomorphologique. Applications aux parcs

18?/11?/2010 Pour faciliter la lecture du document huit planches ... représentation graphique



Troubles du langage (Troubles with Language).

L'apport de NIEDERBERGER dans Troubles d'apprentissage de la lecture et totalement la fonction du langage et l'on pervertit sa valeur affective ...



English?french Dictionary

absolute value : valeur absolue added value tax : taxe sur la valeur ajoutée ... improve : améliorez bonifions



RECHERCHE 4 : TOURISME ET TERRITOIRE : GERER LE

02?/12?/2020 fonction touristique de certaines (infra)structures touristiques et une opportunité pour le (re)dé- ploiement d'un tourisme plus local.

´ECOLEJEUNESCHERCHEURS

EN

ALGORITHMIQUE

ET

CALCULFORMEL

Grenoble29marsau2avril2004

Tabledesmatieres

Cours1

OptimisationCombinatoire

MarcDemange...........................3

Algorithmespourl'imagedesynthese

NathalieRevol.......................140

-Arithm´etiquedesordinateurs

ArnaudTisserand......................182

-Arithm´etiqueexacte

PaulZimmerman......................234

SystemesHybrides

Expos

´es269

i exp´erimentale

Larecherched'informationconceptuelle

Index279

ii

Avant-Propos

mainesdel'algorithmiqueetducalculformel. deleurdiscipline. etinformatique: th´eoriedesGraphes. -Calculformeletapplications. -Codageetcryptographie. -Algorithmiquedutexteetdug´enome. hybrides. -Arithm´etiquedesordinateurs. -G´eom´etriealgorithmique. -Algorithmiquecombinatoire.

Envoussouhaitantuneexcellentelecture,

Mars2004

Lecomit´ed'organisation

iii

Comit´escientique

Jean-GuillaumeDumas,MCal'UJF,LMC

Jean-Guillaume.Dumas@imag.fr

DominiqueDuval,Professeural'UJF,LMC

Dominique.Duval@imag.fr

Christiane.Frougny@liafa.jussieu.fr

Jean-MichelMuller,DRCNRS,ENSLyon,LIP

Jean-Michel.Muller@ens-lyon.fr

NatachaPortier,MCal'ENSLyon,LIP

Natacha.Portier@ens-lyon.fr

Comit

´ed'organisation

Jean-GuillaumeDumas,MCal'UJF,LMC

NatachaPortier,MCal'ENSLyon,LIP

Pageweb

EtienneFarcot,doctorantINPG,LMC

Gestionnanciere

CorinneKabsch,AILMC-CNRS

Afcheetski

Cl´ementPernet,doctorantUJF,LMC

Supportdecoursetexpos´es

AudeRondepierre,doctorantINPG,LMC

iv

D´eroulementdel'´ecole

Coursetexpos´es:

chercheurs.

MaisonJeanKuntzmann

110avenuedelaChimie

DomaineUniversitaire

SaintMartind'Heres-France

Repasdemidi

Bibliothèque

des

Sciences

Amphi Weil

IEPE GETA

MJK

UFR IMA

E NSI MAG IRMA

Vous etes ici^

Avenue de la bibliothèque

TRAM B

Rue de la Chimie

CICG

Terminus du tram

Restaurant Diderot

Université Pierre Mendès France

Planningdelasemaine

Leplanningestlesuivant:

v vi

Soutiens

Universit´eJosephFourier,Grenoble

http://www.ujf-grenoble.fr/ http://www.imag.fr/

CentreNationaldelaRechercheScientique

http://www.cnrs.fr/

Algorithmique,LangageetProgrammation

http://www.liafa.jussieu.fr/%7Ealp/

R´egionRhˆone-Alpes

http://www.cr-rhone-alpes.fr/ http://www.inria.fr/ vii

Ann´eespr´ec´edentes

1996Nicehttp://www.essi.fr/ecole-AMI/

2002Lille,http://www.li.fr/ejc2002/

viii

Conf´erences

sit

´eJosephFourier,Grenoble)

LouisRoch,ENSIMAG,Grenoble)

CNRS,Grenoble)

Paris)

1 2

OptimisationCombinatoire

Responsable:MarcDemange

Conf´erencier:MarcDemange

Sommaire

1Introduction5

2Voyageurdecommerce:unm´etierdifcile9

difciles12

4Approchedifcile:unproblemesauvage15

5 ?-MinTSP:approximationarapportconstant19

5.1Approcher

5.2ApprocherMinTSP

?????apartird'un2-couplageminimum....24 3 R

´ef´erences46

4 voyageurdecommerce

MarcDemange

ESSEC demange@essec.fr

Resume

trouvefascinant.

Avertissement

1Introduction

5 f1;:::;ngdetouteslessolutions qualite. fonctiondesproprietesd'approximation. brouillonalamain!

1.1TSP:unehistoiredejalongue

ndesdonnees. 6 l'autre. dodecaedreregulier:le

Jeuicosien(source[37])

ch.10et[26],ch.1. a[26],ch.1eta[36].

1.2TSP:sequencefascination

sommet. 7

1.3TSP:lafamille

seformuleainsi: (v1;v2;:::vn)etsavaleurestc(T)=Pn1 i=1c(vivi+1)+c(vnv1).Leproblemeconsiste alorsadetermineruntourdevaleurminimum. 8 bibliographiques.

2Voyageurdecommerce:unmetierdicile

peutresoudreceprobleme.Ainsi,leparadigme hhpoetiquo-nafiidont(entreautres)laRe-

2.1LaclasseNP-complet(NP-C):unbrefapercu

(reponseouiounon)comme (probleme) polynomialement unereductionpolynomiale/de touteinstanceI

1estpositive.Lecaracterepolynomialdela

1tel quen

1;c'estencesensque2

9 referernotammenta[18,31].

2.2MinTSPetNP-C

leproblemeduCyclehamiltonien,noteHC. passantunefoisetuneseuleenchaquesommet.

Theoreme2.1[18]

MinTSPdestNP-complet.

peut^etrerepresenteeentempspolynomial). 10

2.3NPO:problemesd'optimisationdeNP

testde 11 deproblemesdiciles obtention. objectifsetleursenjeux. 12 dicilesouentoutcasmalresolues. tionrealisablepourchaqueinstance. autresparametresdel'instance. l'algorithmepourleprobleme. 13 inversantlesensdel'optimisation. deminimisation:

JDenitionI3.1Approximationstandard.

JDenitionI3.2Approximationdierentielle.

OnditqueAgarantitlerapportdierentielsi:

8I;(!(I)(I))=(!(I)(I))(I)

15,20,29,30]).

14 rapportconstantdierentde1: pourunproblemedeminimisation. p,onparledeschemacomplet.

4Approchedicile:unproblemesauvage

Theoreme4.1

15 c(i;j)=1si(i;j)2E c(i;j)=nf(n)sinon del'instance. theoremeprecedentpermetd'etablirque: 16 max=wmin.Un

Plus-Proche-Voisin

output:Cyclehamiltonien.

Choisirunsommetinitialv;

Tantqu'ilrestedessommetsnonvisitesfaire

Analysedel'algorithmePlus-Proche-Voisin

sii=1.Leco^utdelasolutiongloutonneest=P n i=1c(i;i1).Consideronsalorsune c(s(j);s(j1))c(s(j);s(j)1).Onendeduit: 17

Ennotanta

j=1aj=P n peutsupposerjJjn=2;onaalors: X j2J aj+jJjwmax(2)

Parailleurs,d'apreslarelation(1)

nX j=1 c(s(j);s(j1))X j2J aj+jJjwmin(3)

Parconsequent,commeP

et(3): w minn=2+jJjmax nwmin12+w max

2wmin:

max=(2wmin)quivaut asymptotiquementw labornegarantiepartoutalgorithme. pourtouteinstance,lerapport(1")[1=2+w max=(2wmin)].

3);j=1:::k2;(2k2;2k)gontpourvaleur1=w

minettouteslesautresar^etesontpour valeurM=w ([1=2+M=2]k1)=k(1")[1=2+w max=(2wmin)]pourk1=".

Letheoremesuivantresumecetteanalyse:

Theoreme4.2

Plus-Proche-Voisingarantitlerapport1=2+w

max=(2wmin);l'analyseestasymptotiquement optimale. 18

5MinTSP:approximationarapportconstant

max=wmintelles

EtantdonneeunecliqueK

graphepartielT=(V;E d'unarbredeG. 19 approchegarantissantlerapport2. ameliorerl'algorithmeinitial. 20

CHRFD(AlgorithmedeChristofides)

output:Cyclehamiltonien. V

0 fsommetsdedegreimpairdansTg;

Endeduireuncyclehamiltonien.

Analysedel'algorithmeCHTFD

valeurdececycle:~=c(T)+c(M)(4) c(T)(5)

2c(M)(6)

=3=2(7) metriqueduvoyageurdecommerce: 21

MinTSP.

Exemple:promenadeenFrance

Angers24650452154591295128778

Caen339353697292232183730

Calais112697593289519621

Lille685608222573522

Lyon634461770489

Nantes384115841

Paris349490

Rennes831

Strasbourg

Arbredevaleurminimum(valeur1905km)

22
23

Cycleoptimal(valeur2578km)

5.2ApprocherMinTSP

1;2apartird'un2-couplageminimum.

MinTSP

ensembledecyclesM= assembleainsi indiquesurleschemaci-apres. 24

Assembler-Cycles1,2

output:Cyclehamiltonien. 1;

Pouri 2akfaire

Assembler(;i)

ouAssemblerestdeniepar

Assembler

input:Deuxcycles;0 output:Cycle.

Effacerunear^etelapluslourdedeetde0;

Analysedel'algorithmeAssembler-Cycles12

utilisees.

2-couplageM

Premierassemblage

25

Secondassemblage

Dernierassemblage-Solution

ietantdetailleau contientaumoinsunear^etedevaleur2.Onnote

1;:::;pl'etatdeapresp1assemblages

1;:::;p)Pp

i=1c(i)+p;de plussil'inegaliteestuneegalite,alors consideronsl'assemblageentre

1;:::;petp+1.

Supposonsd'abordquec(

1;:::;p) i=1c(i)+p.Danscecas: c(

1;:::;p+1)c(1;:::;p)+c(p+1)+2<

p+1X i=1 c(i)+p+2 etdonc c(

1;:::;p+1)

p+1X i=1 c(i)+(p+1)

1;:::;p+1.

Simaintenant,c(

1;:::;p)=Pp

1;:::;p+1.

1;:::;k)=c(M)+n=3.Comme

26
1;2.

Diculted'approximation

lemontreletheoreme4.1. d'approximation.

1;2(etdoncaussi

Lecaseuclidien`

27
lynomiale. hhscalingandroundingiide degeneralite.

Phase(1)

lesquelles: (b)ladistanceentredeuxvillesestauplus64n +16. hhinstance approchee 88n
Lv2). (i)V0satisfaitlesconditions(a)et(b); solutiondevaleurL

8n(0=8+p2n)L8n(0=8+2n).

28
(V 0)88n

L(V)+2n.

0;danscecas,pour

0(cas(ii))touslessommetsdeV

se garantirpourV

Unschemad'approximationsurV

Phase(2)

PouruneinstanceV

coordonneespairesdansK.ParhypothesesurV

0,lesvillesavisitersontal'interieurdes

ville. isontdelongueur2 Ni. quatresegments,onplace2 Nip. V acetypedetours. 29
ab N2 niveau 1niveau 2niveau 3

Grilletranslateede(a;b)

enfaitlenoyaudelademonstration. salongueur. lignetraversee,asavoir2 soitdeniveauiest2 N2quotesdbs_dbs46.pdfusesText_46

[PDF] Le cancer

[PDF] Le cancer de la peau

[PDF] Le cancer et les divisions cellulaire s

[PDF] le cancer nutritionnel

[PDF] Le cancre - Prévert

[PDF] le cancre jacques prévert analyse

[PDF] le Canon

[PDF] Le caoutchouc naturel

[PDF] Le capitaine

[PDF] le capitaine du navire

[PDF] Le Capital humain

[PDF] le capital humain définition

[PDF] le capital marx intégral pdf

[PDF] le capital marx livre 1 pdf

[PDF] Le capitalisme