L3 MASS P ESD Mathematiques Appliquees Annee

Description

Niveau: Supérieur, Licence, Bac+3
L3 MASS P/ESD - Mathematiques Appliquees Annee 2011-2012 TD n?5 : Algorithmes et graphes Exercice 1 : Parcours en profondeur et applications On considere le graphe suivant : 1.1. Appliquer l'algorithme de parcours en profondeur a partir du sommet 1. 1.2. En deduire si le graphe est fortement connexe ou non. S'il ne l'est pas, determiner l'ensemble des composantes connexes. 1.3. Determiner s'il y a des circuits dans le graphe. 1.4. Reprendre la question 1.2. a l'aide du parcours en largeur. Exercice 2 : Parcours en largeur et applications Le reseau informatique d'une entreprise est represente par le graphe qui suit. Les sommets representent les serveurs et les aretes indiquent le temps necessaire pour faire passer une information d'un ordinateur a l'autre. 2.1. Effectuer le parcours en largeur du graphe a partir de l'ordinateur A. 2.2. Un employe travaillant sur l'ordinateur A envoie un document a un collegue utilisant l'or- dinateur K. Combien de temps faudra-t-il au minimum pour que le document lui parvienne si les connections entre ordinateur prennent toutes le meme temps (mettre toutes les valeurs du graphe a 1) ? 2.3. Meme question avec les temps ecrits sur le graphe. 2.4. Le serveur F tombe subitement en panne a cause d'un virus. Combien de temps faut-il maintenant pour envoyer un document de A a K (avec les temps ecrits sur le graphe) ? 1

• graphes sans circuits


• parcours en largeur


• duree reelle


• meme question avec les temps ecrits sur le graphe


• code tache


• tache critique

Informations

• Publié par: vehot
• Nombre de lectures: 44
• Langue: Français

Extrait

TD 5

Algorithmique Rappeldeprobabilit´e: Deux´eve´nementsE 1 etE 2 sont ditsind´sdantepenpaorsliil´tabibsdleueeqivrrxaeueˆmnetneem temps est Pr[E 1 ∩ E 2 ] = Pr[E 1 ]×Pr[E 2 ]. Danslecasleplusge´ne´ralo`uE 1 etE 2 rimeseas´nceptsaantspendnd´eenti:ano,nones

Pr[E 1 ∩ E 2 ] = Pr[E 1 |E 2 ]×Pr[E 2 ] = Pr[E 2 |E 1 ]×Pr[E 1 ],

ou`Pr[E 1 |E 2 r´esentelaper]litie´ocdntioinnleelprobabdeE 1 e´nndontta´eE 2 . Quand on a un ensemble d’e´v´enementsnonne´cessairementinde´pendants,ona:

k k−1 E] = P Pr[∩ i=1 i r[E 1 ]×Pr[E 2 |E 1 ]×Pr[E 3 |E 1 ∩ E 2 ]. . .Pr[E k E| ∩ i ]. i=1

Exercice 1:Coupe minimale dans un graphe SoitGntve´eecenemllueueisulpteteˆrasrapheungrect´conn-nro,eone´vaeitnsentrelesnsommets. UnecoupeCdansGtuesnsneblem’aedteˆruqseoisiselnve,ene`lGdevient non-connexe. Unecoupe minimaleutsenadiarecedupconeamepamixnureuoceesletmila.eeLil´tmeniedetrouvprobl`em NP-complet. L’id´eedel’algorithmeestdechoisiruniform´ementuneareˆteetdefusionnerlesdeuxsommets enunseulsommetenmettantsurcesommetlesarˆetesquiarrivaientauxdeuxsommetsinitiauxet enenlevantlesboucles.Onappellecetteope´rationunecontraction.Oegrapheˆmmeselivnioqteu initialn’avaitqu’uneseuleareˆteentrechaquesommet,legrapheayantsubiunecontractionpeut encontenirauplusdeux.Ceprocessusdiminued’uneunite´lenombredesommets.L’algorithme effectuedescontractionsjusqu’`acequelenombredesommetssoite´gal`a2etretournecommevaleur lenombred’arˆetesentrecesdeuxpoints.

1.Montrerqu’unecontractiond’areˆtenediminuepaslavaleurd’unecoupeminimalesionn’enl`eve pasd’areˆted’unecoupeminimale. 2. Soitkla valeur d’une coupe minimale. Montrer queGa au moinskn/.seteˆra2 3. SoitE i env´´el’entdenemdeˆetehciopesaenraisurC`alair1,pout-aip`eeme´e≤i≤n−2. (a) Montrerque Pr[E 1 ]≥1−2/n. i−1 (b) Montrerque Pr[E 2 |E 1 ]≥1−2/(n−[1)etqenPrue´nrelameptulgse´E i |∩ E j ]≥1−2/(n−i+1). j=1 2 (c)Montrerquelaprobabilit´etrouverunecoupeminimaleparceproc´ed´eestaumoins. n(n−1)

4.Montrercommentobtenirunalgorithmedontlaprobabilite´d’e´checsoit<1/eet donner sa complexit´eo`ueonSin.ieerp´´eenmhtiragoludesabaestltechecsoilit´ed’´paorabibevtuuqle aussi petite que l’on veut, par exemple 1/nqu,tlesleelxelpmoca?e´ti

Exercice 2:Curetlˆottiviarsnusgndenaphrae 1. Rappelerl’algorithme de Floyd-Warshall pour calculer la distance minimale entre tout couple de sommetsetdonnersapreuveetsacomplexit´e. 3 2.Montrerqu’ilpermetdecalculerlaclˆoturetransitiveenΘ(n) en temps. 3.Montrerques’ilexisteunalgorithmequicalculelacloˆturetransitived’unematricen×nenA(n) additions,multiplicationsd’e´le´mentsd’unsemi-anneauetsiA(3n)≤c∙A(ne´rnle)pouruc >0 et toutnentier positifs, alors il existe un algorithme de multiplication avecM(n) =O(A(n)) additions et multiplications. 4. Montrerque si le produit de deux matricesn×nen´eullccareetpueˆtM(n) additions et mul- tiplications et si 4∙M(n/2)≤M(n) etM(2n)≤c∙M(n) pour uncet toutnallcoˆuter,arslo transitive se calcule enA(n) =O(M(n)) additions et multiplications. 5.Montrerquelesemi-anneauboole´enB= ({0,1},∨,∧,0,1) n’est pas un anneau. log 72 6. SoitAetBdeux matricesn×nullcenereptuesacpeorudtieennes.Lbool´eO(n∙(logn=) ) 2.82 O(ne.terutoˆlvitisnar,ainireselacsiquretao)´pibanoisn

Exercice 3:Distance minimale entre tout couple de sommets Soitungraphenon-orient´e,connect´e,avecunensembledesommetsV={1, . . . , n}et|E|=m areˆtesdepoidsunitaire.OnnoteAennelacebool´ejda’necartamdecin×netA ij =A ji 1=ise’tlerˆa ´ (i, j) est dansEe´odnnnosit0enttaEn.A, la matrice des distancesDest une matrice d’entiers positifs telle queD ij vaut la longueur du plus court chemin entre le sommetiet le sommetj. Les diagonales deAetDtruocsulsnimehcvenal.Lt0iaeder’d`mtepaehnurgemaxestldespimum entre toute paire de sommets. Le but de cet exercice est de montrer que pour toute paire de sommets le calcul de la plus courte distance (APD) et le calcul d’un plus court chemin (APSP) entre deux sommets, peut se faire en unpeuplusducoˆutMM(n) d’une multiplication de 2 matricesn×nr´eydlo.FhslaW-raomtnoltn 3 commentre´soudreceprobl`emeenΘ(nsecaahtnteetobnrepassercanepasd´rehc`ehcnO.)aelqu 3 multiplication matricielle peut s’implanter plus rapidement qu’enO(n). 0 0 1) SoitG(V, Eapridesemoemstlegr)obteaphe¸alpneunaenutnacnteeetrˆueaqchrei6=j∈V 0 00 quisont`adistance1ou2dansG. On noteraAla matrice d’adjacence deGetDla matrice des 0 plus courtes distances dansG. 2 a) Montrer que siZ=A, alors il existe un chemin de longueur 2 dansGentre chaque paire de sommetsietjsi et seulement siZ ij >0. De plus, la valeur deZ ij est le nombre de chemins distincts de longueur 2 entreietj. 0 b)Supposonsquelediam`etredeGsoit au plus 2. Montrer queGest un graphe complet et exprimer 0 dans ce casDen fonction deAetA.

2

2)Enge´n´eral,Graerrtiberiatnemavutruoiiandetm`epgrand≤n. a) Montrer alors que pout toute pairei, j∈V, 0 –SiD ij est paire, alor sD ij = 2D ij . 0 −1 –SiD ij est impaire, alorsD ij = 2D ij . 0 Onend´eduitquelamatriceDea´eullccveuepacerteˆtDelpsulsei´oedsotsutlaparitnconnaˆı courts chemins. b) Montrer que pour chaque paire de sommets distinctsietjdansG, –Pour chaque voisinkdei,D ij −1≤D kj ≤D ij + 1. –Il existe un voisinkdeitel queD kj =D ij −1.

c) Montrer que pour chaque paire de sommets distinctsietjdeG, 0 0 D –SiD ij est paire, alors kj ≥D i pour chaque voisinkdeidansG. j 0 0 –SiD i sD≤Dpour chaque voisinkdeidansG. De plus, il existe un voisin j est impaire, alor kj ij 0 0 kdeidansGtel queD <D. kj ij SoitΓ(i) l’ensemble des voisins deidansGetd(ide´egrdeel)isationedd´En.iueralacartce´ir suivante: Pour toute paire de sommets distinctsietjdeG: P 0 0 siD≥D –D ij est paire si et seulement k∈Γ(i) kj ij d(i). P 0 0 –D ij est impaire si et seulement siD dD <(i) k∈Γ(i) kj ij P 0 d) Montrer comment calculerDen utilisant une multiplication matricielle. Remarquez k∈Γ(i) kj queZ ii =d(i) pour toutipretosopalersuoranglrotimhree´ucrsifpourcalculerD. Analyser sa complexite´entermedemultiplicationmatricielleutilisantlafonctionT(n, δ`o)uδdelt`maietrese du graphe. 3) Pour calculer la matrice des plus courts chemins, on va utiliser une sous-routine BPWM qui calculeunt´emoinduproduitdedeuxmatricesboole´ennes. SoitAetBictrmauxdeolsrelrpdoiutesbool´eeennes.AP=ABest tel queP ij = 1 s’il existe un te´moinktel queA ik =B kj = 1. On se propose de chercher un algorithme qui calcule une matrice Wtel queW ij rpdoiu.tmo´eduinesnttu a)Supposonsqu’iln’existequ’unseulte´moin.MontrercommentcalculerWen effectuant une seule multiplication matricielle. 2 Ilexisteunalgorithmerandomis´eenO(MM(n) lognnnens.Ocaurpo)laerullcdecirtamiome´tse chercherapasa`construirecetalgorithme. Pourcalculerlespluscourtscheminsentrechaquepairedesommets,onnevapasd´ecrireex- 3 plicitement tous les chemins car sinon on peut utiliser un tempsΩ(n).

3