Algorithmique Rappel de probabilite

Description

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

Informations

• Publié par: pefav
• Nombre de lectures: 56
• 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)