[PDF] [PDF] ´ECOLE JEUNES CHERCHEURS EN ALGORITHMIQUE ET

[PDF] Fonctions - Free

Lecture graphique : paraboles 6 Fonction affine par morceaux Donner l' expression de la fonction affine f dont la représentation graphique est la droite suivantes : la fonction carrée, cube, valeur absolue, inverse, racine et une fonction affine Un campeur arrive dans un camping et souhaite installer sa tente dans un 

[PDF] Pour une mathématique vivante en seconde

tracé et lecture de graphiques, notation indicielle et fonctionnelle b) Règles de liée à la valeur absolue sur R Il s'agit de minimiser Un campeur décide de passer ses vacances au camping de 6) Toutes les fonctions affines sont décroissantes 7) Quel que en deux et on superpose les deux morceaux On déchire le 

[PDF] Bilan 2010/2011 du GPS Mathématiques Altkirch - Académie de

5 mai 2011 · 6° Notion de fonction Lecture graphique, en particulier résolution La valeur absolue permet de parler facilement affine liée à la dérivée 1) Calculer, pour chaque offre, le prix pour 30 morceaux téléchargés par an Un campeur veut planter sa tente en un endroit situé au bord d'un sentier reliant le 

[PDF] ´ECOLE JEUNES CHERCHEURS EN ALGORITHMIQUE ET

29 mar 2004 · Une méthode de factorisation absolue des polynomes en deux Réseaux de régulation génétique affines par morceaux Objets graphiques pour les mathématiques et l'informatique En vous souhaitant une excellente lecture, réalisables qui sont ordonnées en fonction de leur valeur objective

[PDF] Table des matières - CORE

2 déc 2008 · Tableau 2 2 – Fonctions et facettes de l'attachement à la marque – d'après chahuté et la remise en question de leur valeur ajoutée incessante, sur la première rencontre dans des champs disciplinaires variés, permettant d'affiner la La lecture du graphique confirme visuellement ces résultats

[PDF] page de TITRE (pas numérotée) - International Association for

(nécessité d'affiner l'étude, par le recours à des entretiens notamment ; étude Tableau 7 Répartition des énoncés en fonction du type d'éléments imposés et en dans les Lois de l'imitation (en 1890), pour qui la lecture des graphiques devait déterminer l'écart-moyen ils omettent de calculer la valeur absolue des 

[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 candidat déclare etre en instance d'examen

[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

´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