Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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)