Conception d'algorithmes et applications

Ana Bu

Description

Introduction aux algorithmes probabilistes

Informations

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

Extrait

Conception d’algorithmes et applications (LI325)
Cours 9: Introduction aux algorithmes probabilistes

Anaci´ˇsuB
http://www.di.ens.fr/ busic/LI325.html
~
[e-mail]

Motivation
Trirapide(aussiappele´”trideHoare”,QuickSort):
QuickSort
Entr´ees: Un tableauTden.esl´c
Sorties: Le tableauTiosserrcna.tri´etl’oddans
1Sin≤1,RetournerT
2eml´teniris´eunohCxdeT(pivot).
3edtneme´le´erhaqueautmparantcnEocTa`x, former les sous-tableaux
T≤e´´l(tsemen≤x) etT>en(t´sel´em>x).
4TrierT≤etT>en utilisant QuickSort.
RetournerT≤,x,T>.
5
Propri´et´es:
Op`ereuniquementsurlas´equence`atrier(trisurplace).
I
Pirecas:complexit´equadratique.
I
Ex:sipivotesttoujourslepremier´el´ementetletableauesttri´e.

L’algorithme RandQuickSort

Une “solution” :
RandQuickSort
Entr´ees: Un tableauTden.esl´c
Sorties: Le tableauTire´adsn’ldoerrcotissant.
1Sin≤1,RetournerT
2ohCrisi´euneml´tenxdeT(pivot)au hasard.
3mparEncohaquantce´ertuaedtneme´leT`ax, former les sous-tableaux
T≤st(´le´neme≤x) etT>ents(´el´em>x).
4TrierT≤etT>en utilisant RandQuickSort.
RetournerT≤,x,T>.
5

Rappelsdeprobabilit´es

(Casdesespacesfinisoude´nombrables.)
Unseapecedrpobabilit´esest un couple(Ω,P)ou`Ωest un ensemble
I
+
etP: Ω→Rune fonction telle que :
X
P(ω) = 1.
ω∈Ω
Prpbonoedcnitenof´eeuppelesta.ilab´eit
I
Interpretation :Ωmeneatriatste´´lesr´esulnsembledsee’ltenu’dse
experiencenonde´terministe,chaquee´le´mentω∈Ωreprnteu´esen
re´sultat“´ele´mentaire”possiblequiaune“chance”(probabilit´e)
P(ω)de se produire.
I
Exempled’uneexperience:jeterunde´(non-pipe´)
Ω ={1,2,3,4,5,6}.
P(1) =P(2) =. . .=P(6) = 1/6.

´
Ev´enements

Une´´vnemeentest une partieAdeΩtilibaborpaS.t:es´e
I
X
P(A) =P(ω).
ω∈A

I
Interpretation:un´ev´enementestuner´euniondetouslesr´esultats
´ele´mentairescorrespondanta`uner´eponsepositivea`unequestion
portantsurl’exp´erienceetsaprobabilite´estlasommedes
probabilit´esdese´ve´nementse´l´ementairesquilecomposent.
Exemple(jetd’und´e).
I
L’´eve´nement“ler´esultatestunnombrepair”:A={2,4,6}.
P(A) = 1/2.

Variableal´eatoire,esp´erance,variance

I
Uneavirbaelre´ealoiatX: Ω→Vnsunrsdaaleuoitcva`nnutsnofee
ensembleVe´onoidu(nfi.e)blramb
Nousn’allonsconside´rericiquelesv.a.`avaleursr´eelles(V⊂R).
I
Notation :P(X=a) =P({ω∈Ω :X(ω) =a}).
I
L’cerenase´pd’une v.a. :
X
E(X) =X(ω)P(ω)
ω∈Ω
X
=aP(X=a).
a∈V

Note:Toutev.a.re´ellen’apasforcementuneesp´erance(sil’espace
Ωvediutpeieers´la.)regrtsninfi,ie
I
Exemple(jetd’unde´).Variableal´eatoireX(ω) =ω.
E(X) = 1∗1/6 + 2∗1/6 +. . .+ 6∗1/6 = 3.5

Variableal´eatoire,espe´rance,variance

Uneeviaareableal´irtoX: Ω→Vusnseutenofcntion`avaleursdan
I
ensembleVfi(inoud´enombrable).
Nousn’allonsconsid´erericiquelesv.a.a`valeursre´elles(V⊂R).
Notation :P(X=a) =P({ω∈Ω :X(ω) =a}).
I
I
L’espe´erancd’une v.a. :
X
E(X) =X(ω)P(ω)
ω∈Ω
X
=aP(X=a).
a∈V

Note:Toutev.a.r´eellen’apasforcementuneespe´rance(sil’espace
Ωespeire´sal,infinitdtuerevi)reg.
Exemple(jetd’und´e).Variableale´atoireX(ω) =ω.
I
E(X) = 1∗1/6 + 2∗1/6 +. . .+ 6∗1/6 = 3.5
Supposons que :P(1) = 1/12,P(2) =P(3) =P(4) =P(5) = 1/6,
P(6) = 1/4. AlorsE(X) = 47/12 = 3.917

I
Propri´ete´detiraede´le´niancel’esp´er:
SoientXetYueeevpxsac.ads.eruelˆmdmelit´eseteprobabi
a,b∈RlsroravalA.toeaeirblial´eaZ=aX+bY:erefii´v

E(Z) =aE(X) +bE(Y).

Lavariancevenu’dt:esleel´e.r.a
I

2
Var(X) =E((X−E(X)) ).

(un indicateur de dispersion)
Note:Unev.a.quiauneesp´erancepeutnepasavoirdevariance.
I
Proprie´t´es:
2 2
Var(X) =E(X)−(E(X)).
2
Var(aX+b) =a Var(X).

Inde´pendance

I
Intuitivement:deuxe´v´enements(oudeuxv.a.)sontinde´pendantssi
l’information obtenue sur l’un ne modifie pas la connaissance qu’on
a de l’autre.
I
Def.e´xueDtsenemenv´AetBsoi:tnssnead´dpetnni

P(A∩B) =P(A)P(B).

Inde´pendance

I
Intuitivement:deux´eve´nements(oudeuxv.a.)sontinde´pendantssi
l’information obtenue sur l’un ne modifie pas la connaissance qu’on
a de l’autre.
Def.stnemeneDeux´ev´AetBtnosenepd´ini:ssntda
I

P(A∩B) =P(A)P(B).

Exemple(jetd’unde´non-pip´e).
I
Lese´ve´nementsA={2,4,6}etB={1,2,3}ne sont pas
ind´ependants:
P(A) = 1/2,P(B) = 1/2, maisP(A∩B) = 1/6et
P(A)P(B) = 1/4.