[PDF] Algorithmique - Cours et Travaux Dirigés Ecole Normale Supérieure





Previous PDF Next PDF



Banque MP inter-ENS – Session 2021

algorithme de Dijkstra avec une file de priorités implémentée à l'aide d'un tas stocké dans un tableau. Il faut savoir quand ces algorithmes sont applicables.



Routage distribué - et les algorithmes de plus court chemin

Inria Paris - DI ENS http://www.di.ens.fr/~busic/ · ana.busic@inria.fr. Paris Algorithme 1 : Dijkstra. Données : G = (V A



Rappel sur les algorithmes de plus court chemin

On cherche `a calculer le plus court chemin de tous les sources vers une destination fixée i ∈ V . Dijkstra. Algorithme 1 : Dijkstra. Données : G = (V A





Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale

L'algorithme de Dijkstra que l'on étudie ici ne fonctionne que sur les Cet algorithme tr`es célébre de gestion des partitions est dû `a Tarjan? Le calcul ...



Projet 1: Arbres couvrants minimaux par lalgorithme de Kruskal

Un arbre couvrant minimal est un sous-ensemble de A de A tel que : – chaque algorithme de Dijkstra). L'astuce de l'algorithme de Johnson consiste `a n ...







2M226 - Combinatoire et Graphes

26 juil. 2018 di = { di pour i<n − dn di − 1 pour i ≥ n − dn. Démonstration ... Algorithme 1 : Algorithme de Dijkstra. Données : Un sommet s d'un ...



SAGA: A Fast Incremental Gradient Method With Support for Non

In Section 2 we describe the SAGA algorithm a novel incremental terpret Dijkstra's set intersection as a primal algorithm instead of a dual block ...





A Proof Method based on Folding Lemmas: Applications to

algorithm and for Dijkstra's descending subsequence algorithm. 1 Introduction. In Fri92] a method was developed for proving implications of the form:.



Priority Mutual Exclusion: Specification and Algorithm

m priority levels (m can be any natural number) the algorithm has O(m) Dijkstra



Brief Introduction to Provable Security

http://www.di.ens.fr/users/mabdalla. 1 Introduction. The primary goal of cryptography is to enable parties to communicate securely over an insecure.



Algorithms for the Edge-Width of an Embedded Graph

15/02/2012 O(nlog n) time in the weighted case using Dijkstra's algorithm; ... //www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf 2008.



Modèles et algorithmes des réseaux Routage distribué et les

http://www.di.ens.fr/~busic/ l'ensemble d'arcs autorisés). Page 5. Dijkstra. Algorithme 1 : Dijkstra. Données : G = (V A



Algorithmique - DI ENS

6.5.5 Algorithme de Dijkstra . Un binôme est un ensemble de deux balles pour lesquelles l'algorithme a déjà testé si elles étaient de la même couleur et ...



A taxonomy of nite automata minimization algorithms

18/05/1994 elegant minimization algorithm di ers from all other known ... Dijkstra E.W. A discipline of programming



A taxonomy of nite automata minimization algorithms

18/05/1994 elegant minimization algorithm di ers from all other known ... Dijkstra E.W. A discipline of programming

Algorithmique-CoursetTravauxDirigés

EcoleNormaleSupérieuredeLyon

Rédaction

Etudiants-scribes,MIM2003et2004

Cours

YvesRobert

TravauxDirigés

YvesCaniouetEricThierry

2003-2004-2005

2

Tabledesmatières

1Introduction:calculdex

n 11

2Diviserpourrégner19

3Programmationdynamique35

4Algorithmesgloutons51

3

5Tri63

6Graphes87

4

7Tablesdehachage119

8Analyseamortie123

9NP-Complétude127

10Algorithmesd'approximation145

5 6

Préface

nes'estrenducompteduchangement!

YvesCaniou.

Lyon,Mai2005

YvesRobert

Biblio

chapitre): française.

NP-complets.

7 leursexercicesincroyables 8

Sinon,j'aimebien:

finedesproblèmesdetri ductionauxschémasd'approximation. quicontientunemined'exercicesoriginaux titrerésumebienlecontenu. 9 10

Chapitre1

Introduction:calculdex

n

1.1Énoncéduproblème

Onétudieleproblèmeducalculdex

n

Onposey

0 1 ,y 2 ,...,y i-1 jepeuxcalculery i y i =y j ·y k

Lebutestd'atteindrex

n leplusvitepossible,i.e.detrouver

Opt(n)=min{i/y

i =x n

1.2Algorithmenaïf

y i =y 0 ·y i-1 Onay n-1 =x n ,lecoûtestdoncden-1.

1.3Méthodebinaire

x n x n/2 ·x n/2 sinestpair, x ?n/2? ·x ?n/2?

·xsinestimpair.

n ,entraduisantSparl'opérationmettre dansl'ordrex 2 ,x 4 ,x 5 ,x 10 ,x 11 ,x 22
,etx 23

Lecoûtestde:

?logn?+ν(n)-1, 11 multiplicationspourtrouvery=x 3 15 =y 5 (on appliquelaméthodebinaire:y 2 ,y 4 ,y 5

1.4Méthodedesfacteurs

x n (x p q sipestlepluspetitfacteurpremierden, x n-1

·xsinestpremier.

k ),etréciproquement(prendren=33·2 k

1.5ArbredeKnuth

n defaçonefficace. 1 2 3 5 7 14

192128

10 11 22
13 2326
15 2530
20 40
6 9 18 2736
12 24
48
4 8 16 17 3334
32
64
12 lesrelieraveclesnoeuds n+1,n+a 1 ,n+a 2 ,...,n+a k-1 =2n (danscetordre),où1,a 1 ,...,a k-1 foisetperdseulement6fois.

1.6Résultatssurlacomplexité

Théorème1.Opt(n)≥?logn?

i x

α(i)

i .Pourlabase,onabieny 0 0 =1. i =y j ·y k .Onaα(i)=α(j)+α(k),par j i-1 i-1 .Onendéduitdoncque i-1 +2 i-1 =2 i

àchaqueétapedel'algorithme.

n→∞

Opt(n)

logn

Théorème2.lim

n→∞

Opt(n)

logn =1

Posonsm=2

k n=α 0 m t 1 m t-1 t oùchaqueα i x d i ,maiscommeonlescalcule"au vol"onpeutlescalculertoussanssurcoût.

Ensuiteoncalculesuccessivement:

y 1 =(x 0 m ·x 1 y 2 =(y 1 m ·x 2 =x 0 m+α 1 )m+α 2 y t =(y t-1 m ·x αt =x n 13 n t·(k+1)+(m-2).

Enremplaçantmpar2

k ,ettpar?log m n?,ontrouveuncoûttotalde ?log m n?(k+1)+2 k log 2 n k (k+1)+2 k 2 k k logn).

1.7Exercices

Exercice1.7.1.Legrandsaut

nepouvezplus. sauts.

1-Sik≥?log

2 (n)?,proposerunalgorithmeenO(log 2 (n))sauts.

2-Sik 2 (n)?,proposerunalgorithmeenO(k+ n 2 k-1 )sauts.

3-Sik=2,proposerunalgorithmeenO(

n)sauts.

Correction.

1-LacomplexitéenO(log

2 ensupposantquel'onak≥?log 2 unétudiantdepuislen

ème

logarithmiquedanslepiredescas.

2-Puisqu'icionnedisposequedek 2 k-1

étagesdans

k-1 )sauts. 14 en"tranches"de n),etdoncunecomplexité finaledanslepiredescaségalementenO( n)sauts.

Exercice1.7.2.Cherchezlastar

(onpeutyarriverenO(n)questions).

3n-?log

2 (n)?-3).

Correction.

êtreeuxaussidesstars.

2-Lorsqu'oneffectueletest

i→j?

ème

test,toutes i←1etj←2 ?si i→j alorsfairej←j+1 sinonfairei←jetj←j+1 i star ←vraietk←1 star )faire ?si k→i alorsfairek←k+1 sinonfairei star ←faux sii star alorsfaireretourner"iestlastar" sinonfaireretourner"iln'yapasdestar" 15

Exercice1.7.3.Bricolage

diamètre.

1-EcrireunalgorithmesimpleenO(n

2 problèmeenmoinsde2n-2essais. (nlogn)essaisdanslepiredescas. 2 )essaispourrésoudreceproblème.

Correction.

1-Algorithme

n(n-1) 2 =O(n 2 tests.

2-Lepluspetitécrouetsonboulon

début sii=j=nalorssortirdelaboucle; siecrou.iAlafindecetteboucle, 16

Cetteboucleeffectuedoncauplus2?n-2tests.

h(T)≥?log 3 f(T)?.ParinductionsurlahauteurdeT: 3 f(T)?. 3 f(T)?estvrai f(T)=f(fd)+f(fg)+f(fd) deplus: 3 f(fc)? 3 f(fd)? 3 f(fg)? k or: f(T)=f(fc)+f(fg)+f(fd) donc: k =3 k+1

D'oùonendéduitque:

h(T)≥log 3 f(T) hauteur:log 3 !n≂nlog 3

1.8Référencesbibliographiques

sonttirésdeRawlins[8]. 17 18

Chapitre2

Diviserpourrégner

2.1AlgorithmedeStrassen

Calculonsunproduitdematrices:

rs tu ab cd ef gh

L'algorithmeclassiquecalculeenAdd(n)=n

2 (n-1)additionsetMult(n)=n 3 multipli- cations.Eneffet,ilyan 2 1

V.Strassenrépondqueoui:soient

p 1 =a(g-h) p 2 =(a+b)h p 3 =(c+d)e p 4 =d(f-e) p 5quotesdbs_dbs22.pdfusesText_28
[PDF] TP Informatique no 8 Algorithme de Dijkstra - Arnaud Jobin

[PDF] TD d 'algorithmique avancée Corrigé du TD 11 : Plus courts chemins

[PDF] corrigé - Irif

[PDF] Algorithmes de factorisation des entiers

[PDF] Reconnaissance de caractères ? l 'aide de réseaux de neurones

[PDF] - Partie 6 - Routage IP

[PDF] Programmation Problème de seuil TI 82-statsfr

[PDF] Correction TD1 algorithme

[PDF] Second degré - Académie en ligne

[PDF] Chapitre 6 Algorithmes numériques

[PDF] LES ÉTAPES DE L 'ALGORITHME DU SIMPLEXE

[PDF] Chapitre 3 Méthode du simplexe - Cours

[PDF] Algorithmique au lycée

[PDF] le programme d 'algorithmique sans ordinateur - Mathématiques

[PDF] Algorithmique programmation en langage C - vol1 - Hal