Algorithmes probabilistes

Description

Parmi les algorithmes probabilistes, on peut distinguer deux grandes classes : les algorithmes de Las Vegas et ceux de Monte Carlo.

Informations

• Publié par: Force_IT
• Nombre de lectures: 10
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

re
MIT1ann´ee-2012/13ModuleAlgo2
TD4 : Algorithmes probabilistes

1.eCarMontLasVlo`agesaeD
Parmi les algorithmes probabilistes, on peut distinguer deux grandes classes : les algo-
rithmes deLas Vegaset ceux deMonte Carlo.

D´efinition1(AlgorithmedeLasVegas)Un algorithme probabiliste est dit deLas
Vegase´retlusuqtarli’ilscsroertcO.pnraelenvoieesttoujourgoald’rademethriLas Vegas
a`tempsmoyenf(ntn´rtueeee)urtosipoxde taillenerunpo´ealeclecuroglmhtia’l,sneen
untempsdontl’esp´eranceestborne´eparf(n).

1.1thrigoaluneritCurs.lecodansnt´ee´essarpVsgeemaL

D´efinition2(AlgorithmedeMonteCarlo)Un algorithme probabiliste est dit deMonte
Carlodea’aplr.enOunlleithmlgornctireoravctunecorpeibab´tilnones’idlnoennu´rseluat
deMonte Carloruerrea`λisuoteenr´etrenteourtou,pbalitie´,ealrpboorithmerquel’alg
unre´sultatfauxeststrictementinf´erieurea`λ.
Danslecasd’unprobl`emeded´ecision(`are´ponse«Oui»ou«Non»), on parle d’algorithme
deMonte Carlo=eopsn´e(rvetiga´eenncatsnietuotruopiserrunulitae´arel`aer«Non»),
l’algorithmer´epond«Non»1.ilab´eitenucborpeva
On parle d’algorithme deMonte Carlor`aaleersriepuorbilat´eusennitsruuaomnicean-po
sitiveetuneinstancen´egative,laprobabilite´der´epondre«Oui»est strictement comprise
entre 0 et 1.

1.2CtirenulaogrithmeMonteCarloe´rptnesade´elsnurcos.
SoitΠunproble`mepourlequelondisposed’unalgorithmeMonteCarloAqui, pour toute
instance de tailleneetutnune’s,ce´xusempsauplTA(nteecrrcoseen´rpenoteodnnue),
avecprobabilite´aumoinspA(nirogemhtnulatn’deleme´agposendis).OVqui, pour toute
instance de taillenpsemnteeusplaume`lborpdice´d,eeponsepossibleauettuoet´rTV(n)
silare´ponseestcorrecte.
1.3.eΠeml`obthmegoriunaDlonnerelrpoprugesaaLVs

1.4.on´eexticul’esp´erieuresurtnmesp’dnaecedosnnDore´pusenrobenure

2.´eRrre’ruetcuddnoi
SoitΠunproble`meded´ecisionetAmhtiroglaCetnoMerraeo`rllanirueu´trelapeuoruna
Π,dontonsupposequ’ilesta`probabilite´d’erreurauplusα, avec 0< α <1.
Soit 0< ε < αedtnseneadd´epnsinitiop´ete´redneibmoC.Aualp,pserruoce´eaiss,sustnon
assurerquelaprobabilit´ed’avoirunere´ponsecorrectesoitaumoins´egale`a1−ε?

1

re
MIT1ann´ee-2012/13

Module Algo2

3.pmocedsessalCet´xile
La classeZPP(Zero-error Probabilistic Polynomial Time) est la classe des langages pour
lesquelsondisposed’unalgorithmeLasVegasdetempsd’ex´ecutionpolynomialenesp´e-
rance.
On noteRP(Randomized Polynomial Time) etco-RPles classes suivantes.

De´finition3RPest la classe des langagesLpour lesquels on dispose d’un algorithme
probabilisteAlynopspotelqmialeus’tacu´eexeripuatnmetnesac
1
– Six∈L, alors P(A(x) accepte)≥
2
– Six6∈L, alors P(A(x) accepte) = 0

D´efinition4co-RPest la classe des langagesLpour lesquels on dispose d’un algorithme
probabilisteAtlleuqelonymoaituceatnas´xe’teenspmpirupasec
1
– Six6∈L, alors P(A(x) accepte)≤
2
– Six∈L, alors P(A(x) accepte) = 1
Montrer queZPP=RP∩co-RP.

4.ioere´tatsaldebiurceSo
Danscetexercice,oncherchea`ge´ne´rerunesourcedebitsal´eatoireuniforme`apartird’une
sourcedeBernoullideparame`trepnnu,incontleetdoamsixfie´ntdaeneps.segarits´dnitnos
Defa¸con´equivalente,oncherchea`produireunlancerdepileoufacenonbiaise´`apartir
d’unepi`ecede´se´quilibr´ee.
On se fixe l’algorithme suivant : on effectue successivement des pairs de lancers avec la
pi`eced´es´equilibre´e.Onarreˆtede`squeleslancerssontdiff´erents.
4.1Donner le pseudo-code de l’algorithme.
4.2-se´rselutuoidnseadistribntetquelemeruˆseuqserpenmierethmitorlg’auqlertreMno
tatsestuniforme.Onadmettraquelestiragesdel’algorithmesontind´ependants.
4.3it´ne´tarednoibnu’llirequispourlagterigaseedeBnruombnolestndyemoreeleuQ
al´eatoire?Quelleenestlavariance?

2