ECOLE POLYTECHNIQUE F ´ ED´ ERALE DE - cours, examens
a) Appliquer l’algorithme de Dijkstra sur ce graphe Commencer au sommet 1 b) Modifier l’algorithme de Dijkstra pour qu’il fournisse pour chaque sommet vle plus court chemin du sommet de d´epart sa vet l’ensemble des sommets qui font partie de ce chemin 4 Dijkstra et Moore-Bellman-Ford
Introduction à lalgorithmique - cours-examensorg
24 1 Algorithme de Bellman-Ford 571 Exercices 574 24 2 Plus courts chemins à origine unique dans les graphes orientés sans circuit 575 Exercices 577 24 3 Algorithme de Dijkstra 577 Exercices 582 24 4 Contraintes de potentiel et plus courts chemins 583 Exercices 587 24 5 Démonstrations des propriétés de plus court chemin 589 Exercices 594
Examen de Théorie des Graphes - EPITA
J4 Appliquer l’algorithme de Dijkstra jVjfois, à partir de chacun des sommets u de G0 On obtient ainsi plusieurs tableaux du donnant les distances entre u et les autres sommets de G0 (Figure (e) ) J5 Construire la matrice finale avec D(u,v) = du(v) h(v)+h(u), qui donne les distances dans G (Figure (f) ) J6 Retourner la matrice D ainsi
Examen de Théorie des Graphes
n’est pas pondéré (ce n’était pas précisé), ou avec un appel de Dijkstra ((jEj+ jVj)logjVj avec l’implémentation du cours) si le graphe est pondéré; dans les deux cas l’excentricité est la plus grande distance trouvée Pour le rayon et le diamètre, on répète cet algorithme depuis les jVjsommets
Algorithmique et Structures de Données Examen écrit (2h)
5 Ecrire une relation de récurrence concernant la complexité moyenne de cet algorithme 6 Montrer que cet algorithme a une complexité moyenne en O(n) 7 Montrer qu'une telle complexité est optimale 3 Algorithme de Dijkstra On rappelle qu'un graphe est constitué d'un ensemble de noeuds et d'un ensemble d' arêtes qui sont des paires de noeuds
Notes de cours Algorithmique Avancée: Master 1
ramener à un modèle de calcul plus formel tel celui de la machine de uring T Lorsqu'un calcul s'arrête en un temps ni et que le résultat nal fournit la réponse au problème on dit alors que ce calcul est un algorithme
Algorithmique et Modélisation - Introduction
8 Énumération de l’ensemble des chemins d’un graphe Algorithme de Dijkstra 9 Approche algébrique pour explorer l’ensemble des chemin Algorithme de Danzig Exploration intelligente 10 Exploration Algorithme de minimax 11 Exploration (2) Algorithme alpha/beta Algorithmique et Modélisation 9 / 13
Cours d’Algorithmique et structures de données 1
– Etape 4 : Traduction de l’algorithme dans un langage de programmation Les étapes 1, 2 et 3 se font sans le recours à la machine Si on veut rendre l’algo-rithme concret ou pratique, il faudrait le traduire dans un langage de programmation Nous dirons alors qu’un programme est un algorithme exprimé dans un langage de programmation
METHODES QUANTITATIVES DE GESTION
Algorithme de Welsh et Powell 1 Numéroter les sommets par ordre décroissant de leur degré (degré = nombre d’arêtes issues d’un sommet) Poser i = 1 (couleur) et N = X (sommets non encore colorés) 2 Donner la couleur i au sommet de N qui a le plus petit numéro 3 Soit Ni = { sommets non colorés non adjacents à un sommet de
Introduction ã L Algorithmique By Thomas H Cormen Charles E
Introduction ã L Algorithmique By Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein pdf algorithmique cours et formation gratuit les meilleurs livres d algorithmique cours 01 introduction l algorithmique introduction l algorithmique cours et exercices introduction la thorie algorithmique de l information initiation lalgorithmique cours tlcharger en pdf introduction l
[PDF] algorithme de ford plus long chemin PDF Cours,Exercices ,Examens
[PDF] Algorithme de héron Terminale Mathématiques
[PDF] Algorithme de loi continue / densite Terminale Mathématiques
[PDF] Algorithme de mathématiques 2nde Mathématiques
[PDF] Algorithme de maths 1ère Mathématiques
[PDF] Algorithme de maths 2nde Mathématiques
[PDF] Algorithme de mesure d'angle 1ère Mathématiques
[PDF] Algorithme de niveau Seconde 2nde Mathématiques
[PDF] algorithme de parcours en largeur PDF Cours,Exercices ,Examens
[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens
[PDF] Algorithme de Pythagore 2nde Mathématiques
[PDF] ALGORITHME DE PYTHAGORE ( TI-84 plus ) 2nde Mathématiques
[PDF] algorithme de recherche dans un tableau PDF Cours,Exercices ,Examens
[PDF] algorithme de recherche dichotomique PDF Cours,Exercices ,Examens
Examen de Théorie des Graphes
EPITA ING1 2014 S2; A. DURET-LUTZ
Durée : 1 heure 30Corrigé
Document au torisé: une seule page A4 manuscrite (r ecto/verso). Cet examen se dér oulesans calculatrice, téléphone, ou autre appareil électroménager. Répondez dans l escadr esde façon clair eet concise. Le barème, in dicatif,corr espondà une note sur 26,5.1 Graphe de Herschel (5,5 points)
On considère le graphe suivant :abc
defgh ijk. Précisez les caractéristiques de ce graphe :1.(0,5pt)Rayon
Réponse :3
2.(1pt)Diamètre
Réponse :4
3.(0,5pt)État(s) du centre
Réponse :a,b,c,e,f,g,i,j,k(c.-à-d. tous saufdeth, dont l"excentricité est 4)4.(0,5pt)MailleRéponse :4
5.(0,5pt)Nombre chromatique
Réponse :2
6.(0,5pt)Taille de la plus grande clique
Réponse :2
7.(2pt)Ce graphe est-il planaire? Justifiez votre réponse.
Réponse :Oui, par exemple :ab
c defgh i jk Les réponses annonçant fièrement que 18=e3n6=3116=27 rapportent (toutaussi fièrement) 0, car j"ai insisté suffisamment souvent sur le fait que cette inégalité n"est
qu"unecondition nécessairepour qu"un graphe soit planaire.12 Graphes planaires (10 points)
Dans cet exercice on ne considère que des graphes simples, planaires, et non-orientés. Pour un tel
grapheG= (V,E), on noten=jVjle nombre de sommets,e=jEj/2 le nombre d"arêtes, etfle nombre de faces. Ledegré moyend"un graphe est1n v2Vdeg(v).1.(2pts)Justifiez que 3f2e.
Réponse :SiFest l"ensemble des faces,åx2Fdeg(x) =2ecar chaque arête appartient à deux face.
D"autre part toute facexpossède au minimum 3 arêtes, donc deg(x)3 et 2e=x2Fdeg(x)3f.2.(2pts)Un graphe planaire connexe peut-il contenir deux cliques de taille 4? Justifiez-vous.
Réponse :Sans aucun problème. Chaque 4-clique est un graphe planaire, et il n"est pas difficile de les
relier pour obtenir un graphe connexe. Par exempleOn peut ainsi construire un graphe planaire avec autant de 4-clique que l"on souhaite.
3.(2pts)OnconsidèrelegrapheG= (V,E)définiparV=f1,2,...,ngetE= (f1,2gf3,4,...,ng)[
(f3,4,...,ng f1,2g). Vers quelle valeur tend le degré moyen lorsquentend vers l"infini?Réponse :Le sommetsf1,2gsont de degrén2, et les sommetsf3,4,...,ngsont de degré 2. Cela nous
donne un degré moyen de2(n2)+(n2)2n
=48/nqui tend vers 4 lorsquen!¥.4.(2pts)Justifiez que le degré moyen d"un graphe planaire est strictement inférieur à 6.
Réponse :On sait que
åv2Vdeg(v) =2e. Et comme le graphe est planaire, il vérifiee3n6.On en déduit que
1n v2Vdeg(v)6n12n <6.5.(2pts)Considérons un graphe planaire dans lequel tous les sommetsvont un degré deg(v)4. Montrez que lestrois quartsdes sommets ont forcément un degré strictement inférieur à 7.Réponse :Preuve par l"absurde. Si trois quarts des sommets ont un degré7, alors que le dernier quart
n"a qu"un degré4 alors le degré moyen est(37+4)/4=25/4>6 ce qui contredit le fait que le graphe est planaire d"après la question précédente.3 Iso-morflons (2 points)Le graphea
b cdefg hij est-il isomorphe au graphe 09217 8 536
4?
Page 2
Réponse :
Les deux graphes sont isomorphes. Voici une correspondance possible entre leurs états :A B C D E F G H I J
0 9 2 1 7 8 5 3 6 44 Algorithme de Johnson (9 points)
(a)BC DA367532
4 (b)x BC DA367532
40000 (c)x BC DA
3670h(C) =0h(A) =7h(B) =4h(D) =1(d)BC
DA 000 1111 (e)v A B C D h(v)74 01d
A(v)0 0 1 0
dB(v)1 0 1 1
dC(v)0 0 0 1
dD(v)1 1 1 0(f)A B C D
A0 3 8 6
B2 0 5 4
C74 01
D52 2 0L"algorithme de Johnson calcule les distancesD(u,v)pour toutes les paires de sommets(u,v)2V2d"un graphe orientéG= (V,E,`)ne possédant pas de cycle négatif. Il fonctionne en plusieurs étapes,
illustrées par les figures ci-dessus. La figure(a)représente le graphe fourni en entrée, et le tableau(f)
est la sortie qui donne les distances pour toutes les paires.JOHNSON(G):
J1. Ajouter un nouveau sommet xau graphe, et le connecter à tous les autres sommets, avec un poids nul. (Figure(b).) J2. Exécuter l"algorithme de Bellman-For dà partir du sommet x, pour calculer la distanceh(y)entre xet chaque sommety. (La figure(c)montre les distancesh(y)obtenus, ainsi que l"arbre des plus courts chemins associés.) J3. Créer un nouveau graphe G0= (V,E,`0)dans lequel`0(u,v) =`(u,v)+h(u)h(v). (Figure(d).) Dans le grapheG0ainsi obtenu, tous les poids sont nécessairement positifs. J4. Appliquer l"algorithme de Dijkstra jVjfois, à partir de chacun des sommetsudeG0. On obtient ainsi plusieurs tableauxdudonnant les distances entreuet les autres sommets deG0. (Figure(e).) J5. Constr uirela matrice finale avec D(u,v) =du(v)h(v) +h(u), qui donne les distances dansG. (Figure(f).) J6.Retourner la mat riceDainsi construite.
Le but de l"exercice est de calculer la complexité de cet algorithme. Vous exprimerez toutes les com-
plexités en fonction dejEjet/oujVj, la taille du graphe fourni en entrée. Vous pouvez supposer que le
graphe est connexe pour simplifier vos réponses.Page 3
On suppose que le graphe est représenté avec une liste d"adjacence pour énumérer facilement les voi-
sins, ainsi qu"avec une matrice de poids pour trouver rapidement un poids ou tester l"existence d"un arc (poids6=¥).1.(1.5pt)Quelle est la complexité de l"étape J1?
Réponse :Ajouterxdans le tableau des liste d"adjacence coûteraQ(jVj)car il ajVjvoisins. Ajouter
l"état dans la matrice est plus pénible : il faudraQ(jVj2)opérations pour agrandir la matrice
de façon naïve. (Ceux qui veulent utiliser des astuces pour agrandir la matrice de façon plus
efficace doivent se justifier.) DoncQ(jVj2).2.(1.5pt)Quelle est la complexité de l"étape J2? Réponse :Bellman-Ford tourne enQ(jEj jVj).3.(1pt)Quelle est la complexité de l"étape J3?Réponse :Sil"onrespectelesujetàlalettre,ilestécrit"Créerunnouveaugraphe".Doncilfaudracopier
la matrice d"adjacence en la mettant à jour, demandant ainsiQ(jVj2)opérations. (Copier laliste d"adjacence se fait enQ(jEj), c"est moins, et ce n"est même pas utile : on peut réutiliser
la même.) Une autre interprétation possible (plus proche d"une mise en oeuvre réelle de l"algorithme) et de modifier la matrice du graphe en place. Il suffit de parcourir lesjEjéléments de la liste d"adjacence pour savoir quelle case de la matrice mettre à jour. On fait doncQ(jEj) opérations dans ce cas.4.(1.5pt)Quelle est la complexité de l"étape J4? Réponse :Le Dijkstra du cours tourne enQ((jEj+jVj)logjVj)ce qui vaut aussiQ(jEjlogjVj)puisque le graphe est connexe. Il est possible de le faire descendre la complexité àQ(jEj+jVjlogjVj) en utilisant un tas de Fibonacci. Dans les tous les cas, il faut multiplier cette complexité par jVj, puisqu"on le répète pour chaque valeur.Donc les réponses acceptées étaientQ(jVjjEjlogjVj)ouQ(jVj(jEj+jVjlogjVj)).5.(0.5pt)Quelle est la complexité de l"étape J5?
Réponse :On itère sur toutes les paires(u,v), doncQ(jVj2).6.(1pt)En déduire la complexité totale de l"algorithme de Johnson.
Réponse :La complexité est celle de l"étape J3, qui domine toutes les autres. On a doncQ(jEj
jVjlogjVj)ouQ(jEj jVj+jVj2logjVj)selon l"implémentation de tas choisie.7.(2pt)Sous quelle condition l"algorithme de Johnson serait-il préférable à l"algorithme de Floyd-