# COURS : Analyse d'Algorithmes et Génération Aléatoire
###### tags: `AAGA` `Cours`

[TOC]

## Génération aléatoire en général

Les PRNG sont contruits avec une idée d'itération
> Définition
* Soit $\mathit E\in\mathit N$, l'ensemble dans lequel on souhaite générer des nombres
* Soit $\mathcal f:\mathit E \to \mathit E$
* Soit $X_{0} \in \mathit E$, la graine
* Alors $X_{n+1}=f(X_{n})$

> Propriété
* $\exists \lambda \in \mathit N^*$, période du générateur pour $X_0$ (avec $\lambda \leq |E|)$
* $\exists n_0 \leq \lambda$ | $\forall n \geq n_0, X_{n+\lambda}=X_n$

> Preuve de l'existence de $\lambda$
* Soit m=|E| et E : {E_0,E_1,E_2,...,E_m-1}
* Soit la suite $X_0, X_1, X_2, ..., X_{m-1}. X_m, X_{m+1}, X_{m+k}$ avec $k\in N^*\gt 1$
* **Preuve** :
<!-- * $\mathit E$ étant un ensemble fini
* $X_{m+k}\in E$, il y a donc répétition
* tq $X_{m+k}=X_m$ $\forall k \gt 0$
* QED $k=\lambda$ et est appelé période du générateur -->

## Génération aléatoire d'entier
## Génération aléatoire de structures combinatoires de bases
## Génération aléatoire de structures arborescentes

## SUITE
### Model A
Nombre de sommet predef

### Model B
Proba d'apparition d'une arete entre deux sommets fixée

### Distribution des degrés
C'est la probabilité d'avoir des sommets de degrés $k$ dans le graphe.
Cette probabilité suit une loi binomiale car c'est totalement indépendant du reste du graphe.

##### Exemples
> ordonnées = Probabilité du degrés
> abscisse = Degrés

Il s'agit d'un grand graphe gnp

Les courbes sont les attentes théoriques, les points les mesures expérimentales

### Phase de transition
C'est un phénomène très classique de la physique, il s'agit des plateaux représentant les différentes phases. L'exemple classique est celui de l'eau :

Et ce phénomène apprait aussi surprenanament dans les graphes aléatoires.

Ces phases représente l'apparition d'une propriété précise, un seuil critique va se dégager et sous ce dernier la propriété n'a aucune chance d'apparaitre dans les graphes tirés aléatoirement.
Il est a noter que le paramètre variable ici est le nombre de sommets.

### Théorème du composant géant

### Diamètre et rayon du graphe
Le diamètre est utile car il permet d'avoir la distance max entre deux points du graphe.


### Taille caractéritique du chemin dans $G_{n,p}$
Cetta taille est définie par la formule $L \approx \frac{Ln \ n}{...}$