La lecture à portée de main
Description
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