Upload
vuongthu
View
216
Download
0
Embed Size (px)
Citation preview
Statistique et Informatique (3I005)
2016-2017
Nicolas Baskiotis - Pierre-Henri Wuillemin
Universite Pierre et Marie Curie (UPMC)Laboratoire d’Informatique de Paris 6 (LIP6)
Cours 1 :Probabilites sur des ensembles discrets et
denombrements
1 Introduction et exemples d’applications2 Probabilites sur les ensembles discrets3 Denombrements
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 1 / 28
Description de l’UE
Objectifs du cours
Introduction aux domaines :I de la theorie des probabilites,I de la statistique,
donner des exemples de leur application en informatique,pratiquer les concepts introduits sur des exemples −→ mini-projets.
Organisation
Calcul des probabilites (Nicolas Baskiotis − cours 1 a 6) :I introduction aux probabilites,I exemples d’applications.
L’inference statistique (Pierre-Henri Wuillemin − cours 7 a 11) :I recueil et analyse des donnees,I estimation, tests et validation.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 2 / 28
Description de l’UE (2)
Informations pratiques
Site Web :http://webia.lip6.fr/˜phw/3i005(http://www-connex.lip6.fr/˜baskiotisn pour le debut)Organisation en mini-projets:
I TD/TME 1-4: intro + projet 1,I TD/TME 5-7 : projet 2,I TD/TME 8-11 : projet 3 + revisions.
EvaluationLes trois mini-projets sont notesles mini-projets comptent dans la note finale dans tous les cas !un partiel et un examen.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 3 / 28
Evaluation
Calcul de la note finaleNote de Controle Continu : le partiel (40%),note d’Ecrit : sur 60%, Examen (70%, soit ∼ 40% du total) et note des 3projets (30%)
Exemple
un etudiant a eu 12, 13, et 14 aux mini-projets, 12 au partiel et 11 al’examen. Alors:note de CC : 24/40,note Ecrit : 11 ∗ 0.7 + (13 + 14 + 15)/3 ∗ 0.3 = 11.9/20, donc 35.7/60,note finale : 59.7/100.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 4 / 28
Plan
1 Introduction et exemples d’applications
2 Probabilites sur les ensembles discrets
3 Denombrements
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 5 / 28
De quoi parle ce cours . . .
Qu’est ce que la chance ? le hasard ? le aleas ?Comment mesurer le hasard ?Comment l’utiliser ?Comment modeliser des phenomenes aleatoires ?Comment les etudier ?Comment les caracteriser ?Que peut-on predire ?
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 6 / 28
Definitions
ProbabilitesLa theorie des probabilites : domaine des mathematiques qui etudie lesphenomenes aleatoires,fournit des outils pour etudier les experiences aleatoires :des experiences qui, repetees dans les memes conditions, ne donnentpas necessairement le meme resultat.
Statistique
La statistique : domaine des mathematiques dans lequel on etudie lacollecte, l’analyse, l’interpretation de donnees,en particulier, des donnees stockees dans les bases de donnees, sur leWeb, ...
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 7 / 28
Une (tres) petite histoire des probabilites etstatistiques
−XVIe siecle : prehistoire, (Cardan 1501-1576, Galilee 1564-1642)XVIe-XVIIe : la decouverte du domaine
I Fermat (161x-1665), Pascal (1623-1662)I Huyghens (1629-1695)
XVIIIe − XIXe : developpement et premieres applications scientifiquesI Montmort (1678-1719), de Moivre (1667-1754)I la dynastie Bernouilli : Jacob (1657-1705), Jean (1667-1748), Daniel
(1700-1782), Nicolas (1687-1759)I Bayes (1700-1761)I Buffon (1707-1788), Simpson (1710-1761), D’alembert (1717-1783)I Lagrance (1736-1813), Laplace (1749-1827), Poisson (1781-1840)
XIXe − XXe : theorie de la mesure, axiomatisation, applications multiplesI Tchebychev (1821-1894), Emile Borel (1871-1956), Johann Radon
(1887-1956), Paul Levy (1886-1971), Andreı Kolmogorov (1903-1987)I Gibbs (1839-1903), Boltzmann (1844-1906), Poincare (1854-1912) ,
Pearson (1857-1936), Markov (1856-1922)
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 8 / 28
Applications : informatique fondamentale
algorithmique : tri rapide−→ meilleure performance “en moyenne” que les autres tris ;
“en moyenne” ≈ les valeurs dans le tableau initial sont aleatoires.
structure de donnees : Table de Hashage−→ propriete souhaitee de hashCode : donner des valeurs differentes
aux differentes chaınes de caracteres stockees dans la table de hachage.−→ necessite un modele (probabiliste) des chaınes de caracteres qui
seront stockees.compression de donnees.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 9 / 28
Cryptographie et cryptanalyse
Enigma : machine de cryptage allemandependant la Seconde Guerre mondiale.
Le decryptage des messages par les alliesa ete facilite par un mauvais algorithmede generation de permutations aleatoires.
La securite des communications sur Internetest geree par des algorithmes de cryptographie.
Les algorithmes de cryptographie utilisentdes generateurs de nombres aleatoires.
Reciproquement : les cryptanalystes cherchentles regularites (deviations par rapport al’aleatoire) dans les textes cryptes.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 10 / 28
Fouille de donnees
Systemes de recommandation :Les clients qui ont achete ...ont aussi achete ...
Analyses statistiques desachats/recherches des differents produits
Google Trends : analyse des requeteseffectuees par les utilisateurs de Google.
Applications possibles : suivi des interetsdans une population, detection desepidemies, ...
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 11 / 28
Reconnaissance de la parole, separation desources
http://markus-hauenstein.de
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 12 / 28
Analyse predictive/apprentissage automatique
IA de jeu
Autres exemples :traduction automatique,generation automatique (musique, textes)classification d’images, moteur de rechercheInterface cerveau-machine (BCI)
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 13 / 28
Et bien d’autres...
Decision dans l’incertain ;Modelisation des reseaux ;Communication a travers des canaux bruites ;Analyse des reseaux sociaux ;Bases de donnees probabilistes ;Vehicule autonome (drone, voiture)Physique statistiqueBiologie, Bio-informatiqueTheorie de l’informationsSciences politiques et sociales...
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 14 / 28
Plan
1 Introduction et exemples d’applications
2 Probabilites sur les ensembles discrets
3 Denombrements
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 15 / 28
Une probabilite ?
Trois sachets, un croissant . . .
Pourquoi a-t-on unechance sur 3 de trouver lecroissant ?Est-ce toujours le cas ?
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 16 / 28
Une probabilite ?
Trois sachets, un croissant . . .
Pourquoi a-t-on unechance sur 3 de trouver lecroissant ?Est-ce toujours le cas ?
La probabilite d’un evenement
c’est la frequence d’apparition de l’evenement, le nombre de fois ou ilapparaıt rapportee au nombre d’experiences.Notion d’evenement, d’experience et de repetition.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 16 / 28
Un peu plus complique
30 croissants, 30 pains au chocolat, 20 pains aux raisins, 10 pains aulait, 10 chaussons
Qu’est ce qui est equiprobable ?Quelle est la probabilite :
d’un pain au chocolat ?si 5 croissants ont ete tiresavant ?qu’un pain soit tire ?
Plusieurs tirages
Qu’elle est la probabilite :de tirer aucun croissants au bout de deux tirages ? au bout de trois ?de tirer au moins un croissant ?
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 17 / 28
Probabilites sur les ensembles discrets
Pour modeliser une experience aleatoire :
Nous avons besoin des notions de :evenement elementaire : un resultat simple non compose de l’experienceevenement : un resultat simple ou compose de plusieurs evenementselementaires de l’experienceunivers : l’ensemble de tous les resultats possibles
FormalisationSoit Ω, un ensemble denombrable, appele univers,
I Ω represente l’ensemble des resultats possibles d’une experience aleatoire
un element ω ∈ Ω est un evenement elementaire,un sous-ensemble E de Ω est un evenement.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 18 / 28
Probabilites sur les ensembles discrets
Exemple : lancer simultane de trois des
evenement elementaire : (i, j, k) ∈ 1, . . . 63
L’univers (l’ensemble des evenements possibles) estΩ = (i, j, k) | i ∈ 1, .., 6, j ∈ 1, .., 6, k ∈ 1, .., 6 =(1, 1, 1), (1, 1, 2), ..., (1, 2, 1), (1, 2, 2)..., (6, 6, 6),card(Ω) = 63 = 216Si on considere chaque de equilibre, alors chaque evenement
elementaire est equiprobable : ∀(i, j, k) ∈ Ω,P ((i, j, k)) =1
216.
E = (1, 1, 1), (2, 2, 2), ...(6, 6, 6) represente l’evenement : les 3 des sontegaux .
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 19 / 28
Bien definir un probleme
Probleme du prince de Toscanne
Pourquoi en lancant trois des, obtient-on plus souvent un total de 10 pointsqu’un total de 9 points, alors qu’il y a 6 facons d’obtenir ces deux totaux?
9 pts 10 pts6 + 2 + 1 6 + 3 + 15 + 2 + 2 6 + 2 + 25 + 3 + 1 5 + 4 + 14 + 3 + 2 5 + 3 + 24 + 4 + 1 4 + 4 + 23 + 3 + 3 4 + 3 + 3
Premier reflexe : definir les evenements et l’univers !
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 20 / 28
Bien definir un problemeProbleme du prince de Toscanne
Pourquoi en lancant trois des, obtient-on plus souvent un total de 10 pointsqu’un total de 9 points, alors qu’il y a 6 facons d’obtenir ces deux totaux?
9 pts 10 pts6 + 2 + 1 6 + 3 + 15 + 2 + 2 6 + 2 + 25 + 3 + 1 5 + 4 + 14 + 3 + 2 5 + 3 + 24 + 4 + 1 4 + 4 + 23 + 3 + 3 4 + 3 + 3
Soit Ωi,j,k l’evenement : les chiffres i,j,k sont affiches sur les des, sans tenircompte de l’ordre :
pour i ≥ j ≥ k,Ωi,j,k = (i, j, k), (j, i, k), (j, k, i), (k, j, i), (k, i, j), (i, k, j)
Il y a 6 evenements Ωi,j,k qui donnent une somme a 10, et 6 qui donnent unesomme a 9.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 20 / 28
Bien definir un problemeProbleme du prince de Toscanne
Pourquoi en lancant trois des, obtient-on plus souvent un total de 10 pointsqu’un total de 9 points, alors qu’il y a 6 facons d’obtenir ces deux totaux?
9 pts 10 pts6 + 2 + 1 6 + 3 + 15 + 2 + 2 6 + 2 + 25 + 3 + 1 5 + 4 + 14 + 3 + 2 5 + 3 + 24 + 4 + 1 4 + 4 + 23 + 3 + 3 4 + 3 + 3
Les evenements Ωi,j,k ne sont pas “equiprobables” :si i 6= j 6= k 6= i, alors 6 manieres d’obtenir le resultat, P(Ωi,j,k) = 6
216 ,
si i = j 6= k, alors 3 manieres, P(Ωi,j,k) = 3216
si i = j = k, alors une seule possibilite, P(Ωi,j,k) = 1216
P(i + j + k = 9) = 6+3+6+6+3+1=25216 et P(i + j + k = 10) = 6+3+6+6+3+3=27
216
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 20 / 28
Probabilites sur des ensembles discrets (2)Mesure de probabilite : caracterise l’alea
elle definie une probabilite pour chaque evenement, qui correspond a lafrequence d’apparition de l’evenement par definition, entre 0 et 1la probabilite de l’univers est de 1 : au moins un des evenements del’univers se realise lors d’une experiencela probabilite qu’aucun evenement arrive est donc de 0.
Elle est entierement definie par les probas des evenements elementaires.
FormalisationSoit P(Ω) l’ensemble des sous-ensembles de Ω. Une mesure deprobabilite sur Ω est une fonction P : P(Ω)→ [0, 1] verifiant:
I P(Ω) = 1 (Ω est l’evenement certain),I pour tout evenement E, P(E) ≥ 0,I Pour toute suite (Ei)i∈N d’evenements deux a deux disjoints (incompatibles,
Ei ∩ Ej = ∅, i 6= j) : P(⋃
i Ei) =∑
i P(Ei).
Fonction de masse p associee a P : ∀ω ∈ Ω, p(ω) = P (ω)Pour tout evenement E: P(E) =
∑ω∈E p(ω)
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 21 / 28
Probabilites sur des ensembles discrets (3)Probabilite uniforme
Considerons un ensemble fini Ω. La probabilite uniforme sur Ω est definiepar la fonction de masse : p(ω) = 1
card(Ω) .
En particulier pour tout evenement E, P(E) =card(E)
card(Ω).
Interpretation: si on repete (indefiniment) l’experience aleatoire
le resultat de l’experience sera ω avec une frequence de P(ω),un evenement E se produit avec une frequence P(E)→ le resultat appartient a l’ensemble E avec une frequence P(E).
Exemple : lancer simultane de trois des
Soit E l’evenement : La somme des trois chiffres est inferieure stricte a 5,alors
P(E) =4
256.
En effet : E = (1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1).N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 22 / 28
Probabilites sur des ensembles discrets (4)
Proprietes
P(∅) = 0, (∅ est l’evenement impossible)P(E) = 1− P(E) (E : complementaire de E dans Ω),P(E ∪ F) = P(E) + P(F)− P(E ∩ F)
E ⊂ F ⇒ P(F) = P(F\E) + P(E)⇒ P(E) ≤ P(F)(F\E : ensemble des elements de F qui ne sont pas dans E),P(⋃
i Ei) ≤∑
i P(Ei)
Exemple : lancer simultane de trois des
Quelle est la probabilite :d’obtenir aucun 6 ?Que la somme fasse 9 ou que i = j = k ?
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 23 / 28
Plan
1 Introduction et exemples d’applications
2 Probabilites sur les ensembles discrets
3 Denombrements
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 24 / 28
Le probleme des partisProbleme du Chevalier de Mere (Pascal, Fermat)
Deux joueurs jouent a pile ou face
128 euros sont en jeu, 64 de la poche de chacun;le premier joueur marque 1 point si pile sort, sinon c’est le second;le premier qui arrive a 7 points gagne tout.La partie s’arrete sur un score donne (x, y) subitement;comment repartir equitablement l’argent ?
En particulier :
si le score est de (6, 6) ?si le score est de (6, 5) ?si le score est (1, 0) ?si le score est (6, 0) ?
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 25 / 28
Le probleme des partisProbleme du Chevalier de Mere (Pascal, Fermat)
Deux joueurs jouent a pile ou face
128 euros sont en jeu, 64 de la poche de chacun;le premier joueur marque 1 point si pile sort, sinon c’est le second;le premier qui arrive a 7 points gagne tout.La partie s’arrete sur un score donne (x, y) subitement;comment repartir equitablement l’argent ?
Solution de FermatOn note p pour pile, f pour face;soit p le nombre de points manquant au premier joueur, q au second pourgagner;une succession de partie : une sequence pffppf ..
denombrer les parties favorables a chaque joueur.
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 25 / 28
Denombrements
Denombrement de n-uplets
Soit E un ensemble fini de taille n, et k un entier.nombre de k-uplets d’elements de E: nk (tirage avec remise, ordonne)nombre de k-uplets d’elements distincts (tirage sans remise, ordonne,nombre d’arrangements de k parmi n) : Ak
n = n× (n− 1)× ...× (n− k + 1)
Nombre de permutations (cas n = k): n! = n× (n− 1)× ...× 1
Exemple du jeu de 52 cartes.
On peut :I tirer avec ou sans remiseI considerer la sequence des cartes (tirage ordonne) ou l’ensemble obtenu
(non ordonne).
Quelle est la probabilite d’obtenir :I que des dames sur 4 tirages ?I 1,2,3,4 de la meme couleur et dans l’ordre ?I d’obtenir une configuration donnee apres un melange aleatoire ?
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 26 / 28
Nombre de sous-ensembles
Nombre de sous-ensemblesLe nombre de sous-ensembles distincts de cardinal k contenus dans E:Ck
n = n!k!(n−k)! (tirage sans remise non ordonne, Ck
n s’appelle aussi lenombre de combinaisons de k parmi n elementsFormule du binome de Newton
(x + y)n =
n∑k=0
Cknxn−kyk ⇒ card (P(Ω)) = 2n
Ckn =
Akn
k! .
Tirage de 2 cartes sans remise
Quelle probabilite de n’obtenir aucune dame ?C2
481326 = 0.149
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 27 / 28
Denombrements : exemples (2)
Exemple : PMU
Un joueur parie toujours sur le meme resultat :pour le quarte : les chevaux 1, 2, 3 et 4 vont terminer la course enpremier (dans cet ordre).
pour le 2 sur 4 : les chevaux 1 et 2 seront dans les 4 premiers arrives.
On suppose qu’il y a toujours 15 chevaux dans une course, et que l’ordred’arrivee des chevaux suit une probabilite uniforme.
Quelle est la probabilite que le joueur gagne au quarte et au 2 sur 4 ?
N. Baskiotis (UPMC, LIP6) Probabilite, Statisitques et Informatique - 3I005 28 / 28