Algorithmique Rappel de probabilite

Publié par

TD 5 Algorithmique Rappel de probabilite: Deux evenements E1 et E2 sont dits independants si la probabilite que les deux arrivent en meme temps est Pr[E1 ? E2] = Pr[E1]? Pr[E2]. Dans le cas le plus general ou E1 et E2 ne sont pas necessairement independants, on a: Pr[E1 ? E2] = Pr[E1|E2]? Pr[E2] = Pr[E2|E1]? Pr[E1], ou Pr[E1|E2] represente la probabilite conditionnelle de E1 etant donne E2. Quand on a un ensemble d'evenements non necessairement independants, on a: Pr[?ki=1Ei] = Pr[E1]? Pr[E2|E1]? Pr[E3|E1 ? E2] . . .Pr[Ek| ? k?1 i=1 Ei]. Exercice 1: Coupe minimale dans un graphe Soit G un graphe connecte, non-oriente avec eventuellement plusieurs aretes entre les n sommets. Une coupe C dans G est un ensemble d'aretes qui si on les enleve, G devient non-connexe. Une coupe minimale est une coupe de cardinalite minimale. Le probleme de trouver une coupe maximale est NP-complet. L'idee de l'algorithme est de choisir uniformement une arete et de fusionner les deux sommets en un seul sommet en mettant sur ce sommet les aretes qui arrivaient aux deux sommets initiaux et en enlevant les boucles.

  • probabilite conditionnelle de e1 etant

  • algorithmique rappel de probabilite

  • probabilite d'echec

  • arete allant de ¬

  • booleennes indexees par les entiers ≤

  • court chemin


Publié le : mardi 19 juin 2012
Lecture(s) : 56
Source : di.ens.fr
Nombre de pages : 4
Voir plus Voir moins
TD 5
Algorithmique Rappeldeprobabilit´e: Deux´eve´nementsE1etE2sont ditsind´sdantepenpaorsliil´tabibsdleueeqivrrxaeueˆmnetneem temps est Pr[E1∩ E2] = Pr[E1]×Pr[E2]. Danslecasleplusge´ne´ralo`uE1etE2rimeseas´nceptsaantspendnd´eenti:ano,nones
Pr[E1∩ E2] = Pr[E1|E2]×Pr[E2] = Pr[E2|E1]×Pr[E1],
ou`Pr[E1|E2r´esentelaper]litie´ocdntioinnleelprobabdeE1e´nndontta´eE2. Quand on a un ensemble de´v´enementsnonne´cessairementinde´pendants,ona:
k k1 E] = P Pr[i=1ir[E1]×Pr[E2|E1]×Pr[E3|E1∩ E2]. . .Pr[EkE| ∩i]. i=1
Exercice 1:Coupe minimale dans un graphe SoitGntve´eecenemllueueisulpteteˆrasrapheungrect´conn-nro,eone´vaeitnsentrelesnsommets. UnecoupeCdansGtuesnsneblemaedteˆruqseoisiselnve,ene`lGdevient non-connexe. Unecoupe minimaleutsenadiarecedupconeamepamixnureuoceesletmila.eeLil´tmeniedetrouvprobl`em NP-complet. Lid´eedelalgorithmeestdechoisiruniform´ementuneareˆteetdefusionnerlesdeuxsommets enunseulsommetenmettantsurcesommetlesarˆetesquiarrivaientauxdeuxsommetsinitiauxet enenlevantlesboucles.Onappellecetteope´rationunecontraction.Oegrapheˆmmeselivnioqteu initialnavaitquuneseuleareˆteentrechaquesommet,legrapheayantsubiunecontractionpeut encontenirauplusdeux.Ceprocessusdiminueduneunite´lenombredesommets.Lalgorithme eectuedescontractionsjusqu`acequelenombredesommetssoite´gal`a2etretournecommevaleur lenombredarˆetesentrecesdeuxpoints.
1.Montrerquunecontractiondareˆtenediminuepaslavaleurdunecoupeminimalesionnenl`eve pasdareˆtedunecoupeminimale. 2. Soitkla valeur d’une coupe minimale. Montrer queGa au moinskn/.seteˆra2 3. SoitEienv´´elentdenemdeˆetehciopesaenraisurC`alair1,pout-aip`eeme´ein2. (a) Montrerque Pr[E1]12/n. i1 (b) Montrerque Pr[E2|E1]12/(n[1)etqenPrue´nrelameptulgse´Ei|∩ Ej]12/(ni+1). j=1 2 (c)Montrerquelaprobabilit´etrouverunecoupeminimaleparceproc´ed´eestaumoins. n(n1)
4.Montrercommentobtenirunalgorithmedontlaprobabilite´de´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.MontrerquilpermetdecalculerlaclˆoturetransitiveenΘ(n) en temps. 3.Montrerquesilexisteunalgorithmequicalculelacloˆturetransitivedunematricen×nenA(n) additions,multiplicationsde´le´mentsdunsemi-anneauetsiA(3n)cA(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 4M(n/2)M(n) etM(2n)cM(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´ejdanecartamdecin×netAij=Aji1=isetlerˆa ´ (i, j) est dansEe´odnnnosit0enttaEn.A, la matrice des distancesDest une matrice d’entiers positifs telle queDijvaut la longueur du plus court chemin entre le sommetiet le sommetj. Les diagonales deAetDtruocsulsnimehcvenal.Lt0iaederd`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=jV 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 siZij>0. De plus, la valeur deZijest 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`epgrandn. a) Montrer alors que pout toute pairei, jV, 0 SiDijest paire, alor sDij= 2Dij. 0 1 SiDijest impaire, alorsDij= 2Dij. 0 Onend´eduitquelamatriceDea´eullccveuepacerteˆtDelpsulsei´oedsotsutlaparitnconnaˆı courts chemins. b) Montrer que pour chaque paire de sommets distinctsietjdansG, Pour chaque voisinkdei,Dij1DkjDij+ 1. Il existe un voisinkdeitel queDkj=Dij1.
c) Montrer que pour chaque paire de sommets distinctsietjdeG, 0 0 D SiDijest paire, alorskjDipour chaque voisinkdeidansG. j 0 0 SiDisDDpour chaque voisinkdeidansG. De plus, il existe un voisin jest impaire, alorkj 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 siDD Dijest paire si et seulementkΓ(i)kj ijd(i). P 0 0 Dijest 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 queZii=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 quePij= 1 s’il existe un te´moinktel queAik=Bkj= 1. On se propose de chercher un algorithme qui calcule une matrice Wtel queWijrpdoiu.tmo´eduinesnttu a)Supposonsquilnexistequunseulte´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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.