# Cour 12 -- Algorithme

###### tags `cour` `M1 S1` `Algorithme`
[Somaire](/ueYXUIJIQ6C6hcYzKYeojA#)\
[precedent](/nbznABCGTgmt_Gqn5zgYXw)
> [time= 7 dec 2020]

[TOC]

## Algorithmes gloutons (suite)

On a toujours besoin d'une preuve d'optimalité pour admettre qu'il donne bien une solution optimal.

Le probleme de la caissiere est le meme que le probleme des cassettes.

### Problème de la caissière
taille des paniers: $x_1, \cdots, x_n$
On veut ordonner les paniers pour minimiser le temps total d'attente.

#### Algo glouton:
Prendre dans l'ordre: $\gamma(1) \cdots \gamma(n)$\
tel que: $x_{\gamma(1)} \leq x_{\gamma(2)} \leq \cdots \leq x_{\gamma(N)}$

Montrer que tout autre ordre dans un temps d'attente total est superieur au temps pour $\gamma$

$$
Cout(\pi) = \sum_{k=1}^{n} (N - k + 1) x_{\pi}(k)
$$

$(N - k + 1) x_{\pi}(k)$ est le temps du $k^{ieme}$ panier contribut à l'attente

$$
\gamma \text{ est optimal si } \forall \pi\\
cout(\pi) \geq cout(\gamma)
$$

Soit $\pi$ une solution réalisable.
On montre qu'il existe des solutions intermédiare:
$$
cout(\pi) \geq\\
cout(\pi') \geq\\
\cdots\\
cout(\pi^{(n-1)}) = cout(\gamma)
$$

Rapelle de la derniere fois, il restait a démontrer que:
$$
\begin{align}
cout(\pi) - cout(\pi')
&= (N - i + 1)(x_{\pi(i)} - x_{\pi(j)}) + (N - j + 1)(x_{\pi(j)} - x_{\pi(i)})\\
&=(N - i + 1)(x_{\pi(i)} - x_{\pi(j)}) - (N - j + 1)(x_{\pi(i)} - x_{\pi(j)})\\
&=(N - i + 1 - N + j - 1)(x_{\pi(i)} - x_{\pi(j)}) \\
&=( i + j )(x_{\pi(i)} - x_{\pi(j)}) \geq 0\\
\end{align}
$$

ou les paniers i et j on été intervertis

Dans l'algorithme glouton est optimal.

## exemple 2: choix de taches
En entrée:
- N tâche avec temps de début et temps de fin: $(d_1, f_1) \cdots (d_n, f_n)$

En sortie:
- le plus grand nombre de taches (optimalité)
- pouvant être réalisées sans chvauchement (réalisable)

### Algo glouton
Trier les taches par ordre de fin croissantes.
Sélectionner les taches une à une si elle ne chevauche pas les autres déja sélectionnées.

### Preuve d'optimalité
soit $\gamma$ l'ordre goulon:
$$
f_{\gamma(1)} \leq f_{\gamma(2)} \leq \cdots f_{\gamma(k)}
$$


Prenons une autre solution **réalisable** $\pi$ et montrons que $cout(\pi) \leq cout(\gamma)$
où $cout(\pi) =$ le nombre de tâches dans $\pi$


Si $cout(\gamma) \geq cout(\pi)$, alors on à terminé

Si i minimum t.q $\pi(i) \neq \gamma(i)$.

++observation 1++:
$$
fin(\pi(i)) \geq fin(\gamma(i))
$$
Parceque $\gamma$ c'est l'algo glouton et que l'lago choisit la prochaine tâche réalisable en ordre croissant

++observation 2++:
$$
debut(\pi_{i + 1}) > fin(\pi_i)
$$

car $\pi$ est réalisable

++observation 3++:
$$
debut(\gamma(i)) > fin(\gamma(i - 1)) = fin(\pi(i - 1))
$$
On construit $\pi'$ à partir de $\pi$ t.q:
- $cout(\pi') \geq cout(\pi)$
- $\pi'$ réalisable (bien su!)
- La partie commune entre $\pi'$ et $\gamma$

#### Cas 1
$$
debut(\pi(i)) > fin(\gamma(i))
$$

Dans ce cas la solution
$$
\pi' = \pi(1) \cdots \pi(i - 1) \gamma(i) \pi(i) \cdots \pi(k)
$$
- reste réalisable (Cas et Obs 3)
- $cout(\pi') = codut(\pi) + 1$
- $\pi'(1) = \gamma(1) \cdots \gamma(i) = \pi'(i)$

#### Cas 2
$$
debut(\pi(i)) \leq fin(\gamma(i))
$$
prenons plutot
$$
\pi' = \pi(1) \cdots \pi(i - 1) \gamma(i) \pi(i + 1) \cdots
$$
- réalisable (obs3 et obs 1)
- $cout(\pi') = cout(\pi)$
- $\pi'$ a une tache en commun en $\gamma$

$$
cout(\pi) \leq cout(\pi') \leq \cdots \leq cout(\gamma)
$$


Si à la fin on arrive à une solution $\pi^{(n)} > cout(\gamma)$
et qu'on a épuisé les différences

C'est impossible car $\gamma$ aurrait aussi choisis ces taches qui restent réalisables.

Donc on a bien:
$$
cout(\pi) \leq \cdots \leq cout(\gamma)
$$

## Algorithme d'approximation
Pour certains problèmes NP-difficiles parfois un algo non-optinal peut donner une solution en temps polynomial proche d'une solution optimale (en coût).

Def: Pour les problmèemes de minimisation on dit qu'un algotithme A est une $\alpha\text{-approximation}$ si:
- $\forall x cout(A(x)) \leq \alpha OPT(x)$ (le cout de la solution optimale)
- $\forall w cout(A(x)) \geq OPT(x)$ (pour les problemes de maximisation)

### equilibrage des tâches
En entrée:
- n tache de durée $t(1) \cdots t(n)$
- m un nombre de processurs pour les réaliser

En sortie:
- une affectation des ta^ches aux processeurs, c'est a dire une fonction P(i) = j
- "la tache i est affectée au processeur j" $1 \leq j \leq m$

qui minimise:
- $cout(P) = \max_{j} \{\sum_{i} t(i) \}$

Ce probleme est le problmee "makespan"

Ce probleme est un probleme NP difficile.

#### Algo glouton
Prendre les taches une à une les attribuer au processeur le moins chargé jusqu'a maintenant.

Cette algo est bien sur pas optimal.

En revance ici on a une 2 approximation

#### Algo 2
Si on tie les taches t.q:
$$
t(1) \geq t(2) \geq \cdots \geq t(n)
$$
Puis on attribut les tache comme l'algo gouton précédent.
Cette algo une 3/2 approximation

### poposition
L'algo glouton 1 est une 2 approx

#### Lemme 1
Soit t une liste de tâches m le nb de processeurs
$$
OPT(t, m) \geq \max_{i} t(i)
$$

le processeur a qui on attribue cette ta^che travailel au moins t(i)

#### Lemme 2
$$
OPT(t, m) \geq \frac{1}{m} \sum_{i=1}{n} t(i)
$$

### preuve
Regardons l'instant k où on place la derniere tâche sur le processeur le plus chargé, supposons que ce processeur soit j.

Soit $\mathscr{C}$ la charge sur le processeur j.
1. $t(k) \leq OPT$ (lemme 1)
2. $\mathscr{C} \leq OPT:$\
$$
\begin{align}
\mathscr{C}
&= \frac{1}{m} \sum_{j'=1} \mathscr{C}\\
&\leq \frac{1}{m} \sum_{j'=1} \text{charge}(j')\\
&\leq \frac{1}{m} \sum_{j'=1} t(i)\\
&\leq OPT
\end{align}
$$

$cout \leq \mathscr{C} + t(k) \leq 2 OPT$

## Min vertex cover
Entrée:
- G non-orienté

Sortie:
- S un sous-ensemble des sommets qui couvre toutes les arretes du graphe (critere de réalisabilité)
- de taille min (cout min)

Trouver un algo j glouton simple qui donne une 2 approx pour ce problème NP-difficile.