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
Algorithmes à base de provenance pour des requêtes enrichies sur
8 jan. 2021 DI ENS ENS
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 ...
Provenance-Based Algorithms for Rich Queries over Graph Databases
12 fév. 2021 DI ENS ENS
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 ...
Provenance-Based Algorithms for Rich Queries over Graph Databases
12/02/2021 DI ENS ENS
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
CoursYvesRobert
TravauxDirigés
YvesCaniouetEricThierry
2003-2004-2005
2Tabledesmatières
1Introduction:calculdex
n 112Diviserpourrégner19
3Programmationdynamique35
4Algorithmesgloutons51
35Tri63
6Graphes87
47Tablesdehachage119
8Analyseamortie123
9NP-Complétude127
10Algorithmesd'approximation145
5 6Préface
nes'estrenducompteduchangement!YvesCaniou.
Lyon,Mai2005
YvesRobert
Biblio
chapitre): française.NP-complets.
7 leursexercicesincroyables 8Sinon,j'aimebien:
finedesproblèmesdetri ductionauxschémasd'approximation. quicontientunemined'exercicesoriginaux titrerésumebienlecontenu. 9 10Chapitre1
Introduction:calculdex
n1.1Énoncéduproblème
Onétudieleproblèmeducalculdex
nOnposey
0 1 ,y 2 ,...,y i-1 jepeuxcalculery i y i =y j ·y kLebutestd'atteindrex
n leplusvitepossible,i.e.detrouverOpt(n)=min{i/y
i =x n1.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 51.4Méthodedesfacteurs
x n (x p q sipestlepluspetitfacteurpremierden, x n-1·xsinestpremier.
k ),etréciproquement(prendren=33·2 k1.5ArbredeKnuth
n defaçonefficace. 1 2 3 5 7 14192128
10 11 2213 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)
lognThéorème2.lim
n→∞Opt(n)
logn =1Posonsm=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
é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" 15Exercice1.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.iCetteboucleeffectuedoncauplus2?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+1D'oùonendéduitque:
h(T)≥log 3 f(T) hauteur:log 3 !n≂nlog 31.8Référencesbibliographiques
sonttirésdeRawlins[8]. 17 18Chapitre2
Diviserpourrégner
2.1AlgorithmedeStrassen
Calculonsunproduitdematrices:
rs tu ab cd ef ghL'algorithmeclassiquecalculeenAdd(n)=n
2 (n-1)additionsetMult(n)=n 3 multipli- cations.Eneffet,ilyan 2 1V.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] 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