Lien de la note Hackmd
Definition Statistiques: comptage et representation de donnees
Definition Probabilite: phenomene dont on extrait un modele
Optimisation combinatoire
On a une grille, on veut la remplir pour que ca devienne un echequier via un algorithme
Est-ce que notre algo est deterministe ? Oui, car on a toujours le meme resultat avec la meme entree.
Si la couleur d’une case est aleatoire, l’algo n’est plus deterministe.
Definition Un algo est stochastique si a l’interieur il y a de l’aleatoire
1
2
3
# algo
rand()
#algo
L’aleatoire provient de l’entree
Il existe des programmes stochastisques et deterministes.
rand() est-il deterministe ?
\[\Omega=\{A,B,C,D\}\\ \begin{cases} P(A)\in[0,1], \text{idem pour } B,C\text{ et } D\\ P(A)+P(B)+P(C)+P(D) = 1 \end{cases}\]Oui. C’est dingue, hein ?
Exemple
Nous sommes une population, on mesure la probabilite d’avoir 20 ans.
\[\underbrace{P(20)}_{P(A)}=0.36\]
Maintenant avec la meteo:
\[\Omega=\{\text{beau},\text{pluie},\text{couvert}\}\\ \begin{cases} P(\text{beau}) = 0.51\\ P(\text{pluie}) = 0.01\\ P(\text{couvert}) = 1 - 0.21 - 0.01 \end{cases}\]Faire action avec la proba $P$
Retour sur la meteo:
\[\begin{cases} P(\text{beau}) = 0.3\\ P(\text{pluie}) = 0.5\\ P(\text{couvert}) = 0.2 \end{cases}\]
Le probleme: certaines variables aleatoires ne sont pas independante (salaire, categorie pro, etc.)
SUDOKU
On doit ecrire un programme qui resout le sudoku
| 1 | |||
|---|---|---|---|
| 2 | |||
| 3 | |||
| 2 | $\square$ |
On a \(4^{12}=16,7M\) de valeur possibles.
On va bruteforce, cad visiter plein de chemins possibles pour remplir. Les $16$ millions de possibilites de remplissage vont baisser mais vont rester elevees.
La resolution prend du temps :(
Mais, au lieu de faire un algo bete, on fait quoi ?
On rentre dans un probleme d’optimisation combinatoire.
On enumerait les nombres de remplissage possible
Mais pourquoi un probleme d’optimisation ?
On obtient un espace a 12 axes, la solution est quelque part dans l’espace
On cherche le minimum ou le maximum de la fonction
\(x_{\text{sol}}=\text{arg min}_xf(x)\)
Ah et evidemment pas moyen que ce soit une fonction convexe.
Pour les gens du fond:
Resolution de Sudoku
| . | . | . | . |
|---|---|---|---|
| . | 2 | 3 | . |
| 1 | . | . | . |
| . | . | . | 4 |
Quand on ne sait pas, on fait de l’equiprobable
Mais on sait, c’est un sudoku:
\[P(\begin{matrix} \begin{vmatrix} 3 &1\\ 4&2 \end{vmatrix} &\begin{vmatrix} 4 &2\\ 3&1 \end{vmatrix}\\ \begin{vmatrix} 1 &4\\ 2&3 \end{vmatrix} &\begin{vmatrix} 2 &3\\ 1&4 \end{vmatrix}\\ \end{matrix}) = 1\\ P(\begin{matrix} \begin{vmatrix} 1 &1\\ 1&2 \end{vmatrix} &\begin{vmatrix} 1 &1\\ 1&1 \end{vmatrix}\\ \begin{vmatrix} 1 &1\\ 1&1 \end{vmatrix} &\begin{vmatrix} 1 &1\\ 1&4 \end{vmatrix}\\ \end{matrix}) = \varnothing\]On peut pas juste ecrire notre solution comme ca…
“Certaines solutions sont plus vraies que d’autres” Le camarade qui a dit un truc important
Par “vrai”, on veut dire proche de la solution $\equiv$ peu d’erreur
La prob est plus elevees que le reste
La meteo de Gulli
\(\begin{matrix} P(A&\cap&B)\\ \text{beau} &&\text{Londres}\\ \text{temps} = \{\text{pourri, ...}\} &&\text{lieu} = \{\text{Londres, Paris, ...}\} \end{matrix}\)
- $T$ VA pour rpz le temps
- $P(T=\text{beau})=0.6$, $P(T=\text{pourri})=0.1$, …
- $V$ vecteur aleatoire, \(V=(V_1,...,V_n)\), \(V_i\) var aleatoire
Exemple
$W$ weather, $L$ location, $N$ thune de Xavier NIEL.
$P(W=w,L=l)\equiv$ proba qu’il fasse \(\color{red}{\underbrace{\boxed{\text{w a l}}}_{\text{beau a Londres}}}\)
\[\begin{aligned} P(A\cap B)&=P(A\vert B).P(B) \\ = P(B\cap A) &= P(B\vert A).P(A)\\ &\Rightarrow P(A\vert B)=\frac{P(A\cap B)}{P(B)} \end{aligned}\]
Retour au SUDOKU
\[y=\begin{matrix} \begin{vmatrix} y_1 &\\ &1 \end{vmatrix} &\begin{vmatrix} &\\ 2&x_p \end{vmatrix}\\ \begin{vmatrix} 3 &\\ & \end{vmatrix} &\begin{vmatrix} &\\ &4 \end{vmatrix}\\ \end{matrix}\\ y=(0,0,0,0,0,\color{red}{1},\color{green}{2},0,\color{blue}{3},0,0,0,0,0,0,\color{orange}{4})\\ y=(y_1,...,y_{15})\\ y_6=1\\ x=(x_1,x_2,x_3,x_4,x_6,\color{red}{0},\color{green}{0},x_p,\color{blue}{0},\dots)\\ x'=(1,1,1,1,1,\color{red}{0},\color{green}{0},1,\color{blue}{0},\dots)\]En solution:
\[\color{green}{P(}x'\color{green}{)}= \begin{matrix} \begin{vmatrix} 1 &1\\ 1&0 \end{vmatrix} &\begin{vmatrix} 1&1\\ 0&1 \end{vmatrix}\\ \begin{vmatrix} 0&1\\ 1&1 \end{vmatrix} &\begin{vmatrix} 1&1\\ 0&1 \end{vmatrix}\\ \end{matrix}\color{green}{=?}\\ \color{green}{P(}x''\color{green}{)}= \begin{matrix} \begin{vmatrix} 1&2\\ 3&0 \end{vmatrix} &\begin{vmatrix} 3&4\\ 0&1 \end{vmatrix}\\ \begin{vmatrix} 0&1\\ 4&3 \end{vmatrix} &\begin{vmatrix} 4&3\\ 2&0 \end{vmatrix}\\ \end{matrix}\color{green}{=?}\\\]