# TP — L'Algorithme du Vaccin
## Contexte
Vous êtes ingénieur·e en bio-informatique dans un laboratoire pharmaceutique. Une nouvelle épidémie virale se propage, et votre équipe dispose d'un **bioréacteur** capable de produire des anticorps pendant un temps limité.
Vous avez identifié **n variants du virus**, chacun nécessitant :
- un **temps de production** (en heures) pour fabriquer les anticorps correspondants
- une **efficacité estimée** (score de 1 à 100) contre la souche circulante
Le bioréacteur ne peut fonctionner que pendant **T heures** au total. Vous devez choisir quels anticorps produire pour **maximiser l'efficacité totale** du vaccin, sans dépasser le temps disponible.
> Ce problème est directement modélisé par le **problème du sac à dos 0/1** : chaque anticorps est produit entièrement ou pas du tout.
**Exemple de données :**
| Anticorps | Temps (h) | Efficacité | Ratio eff/temps |
|-----------|-----------|------------|-----------------|
| Alpha | 3 h | 40 | 13,3 |
| Bêta | 5 h | 70 | 14,0 |
| Gamma | 2 h | 30 | **15,0** ← meilleur |
| Delta | 7 h | 100 | 14,3 |
| Epsilon | 6 h | 85 | 14,2 |
Temps disponible : **10 heures**
---
## Partie 1 — Comprendre le problème
**Question 1.** En utilisant l'algorithme glouton (trier par ratio efficacité/temps décroissant), quels anticorps choisissez-vous ? Quelle est l'efficacité totale obtenue ?
**Question 2.** Essayez d'autres combinaisons à la main. Trouvez-vous une solution d'efficacité strictement supérieure à celle du glouton ?
**Question 3.** Combien y a-t-il de combinaisons possibles en tout pour `n = 5` anticorps ? Pour `n = 30` ? Qu'en déduisez-vous sur une approche exhaustive ?
---
## Partie 2 — Formulation récursive
Notons `vaccin(i, t)` l'efficacité maximale qu'on peut atteindre en choisissant parmi les `i` premiers anticorps avec un temps restant de `t` heures.
**Question 4.** Quels sont les cas de base de cette fonction récursive ?
**Question 5.** Écrivez la relation de récurrence pour `vaccin(i, t)` sachant que l'anticorps `i` a un temps de production `duree_i` et une efficacité `eff_i`.
**Question 6.** Implémentez la version naïve `vaccin_naif(anticorps, i, t)` :
```python
def vaccin_naif(anticorps, i, t):
# anticorps : liste de tuples (duree, efficacite)
# À compléter
pass
# Test
anticorps = [(3, 40), (5, 70), (2, 30), (7, 100), (6, 85)]
n = len(anticorps)
print(vaccin_naif(anticorps, n, 10)) # doit afficher 140
```
---
## Partie 3 — Version Top-Down (mémoïsation)
**Question 7.** Pourquoi la version naïve recalcule-t-elle des sous-problèmes ? Donnez un exemple de sous-problème qui serait recalculé plusieurs fois.
**Question 8.** Implémentez `vaccin_memo(anticorps, temps_total)` avec mémoïsation :
```python
def vaccin_memo(anticorps, temps_total):
memo = {}
def vaccin(i, t):
# À compléter
pass
return vaccin(len(anticorps), temps_total)
```
**Question 9.** Vérifiez que vous obtenez le même résultat qu'à la Question 6.
---
## Partie 4 — Version Bottom-Up (tableau)
**Question 10.** Remplissez à la main le tableau `tableau[i][t]` pour les **3 premiers anticorps** (Alpha, Bêta, Gamma) avec un temps total de **6 heures** :
| | t=0 | t=1 | t=2 | t=3 | t=4 | t=5 | t=6 |
|---|---|---|---|---|---|---|---|
| i=0 (aucun) | | | | | | | |
| i=1 (Alpha 3h, 40) | | | | | | | |
| i=2 (+Bêta 5h, 70) | | | | | | | |
| i=3 (+Gamma 2h, 30) | | | | | | | |
**Question 11.** Implémentez `vaccin_bottom_up(anticorps, temps_total)` :
```python
def vaccin_bottom_up(anticorps, temps_total):
n = len(anticorps)
# tableau[i][t] = efficacité max avec les i premiers anticorps, temps t disponible
tableau = [[0] * (temps_total + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
duree, eff = anticorps[i - 1]
for t in range(temps_total + 1):
# À compléter
pass
return tableau[n][temps_total]
```
**Question 12.** Vérifiez que vous obtenez 140 pour l'exemple complet (5 anticorps, 10 heures).
---
## Partie 5 — Reconstruction de la solution
**Question 13.** Modifiez `vaccin_bottom_up` pour qu'elle retourne non seulement l'efficacité maximale, mais aussi la **liste des anticorps sélectionnés** :
```python
def vaccin_reconstruction(anticorps, temps_total):
"""
Retourne (efficacite_max, liste_anticorps_choisis)
"""
n = len(anticorps)
tableau = [[0] * (temps_total + 1) for _ in range(n + 1)]
# Remplissage du tableau (identique à vaccin_bottom_up)
# À compléter
# Reconstruction : on remonte le tableau
choisis = []
t = temps_total
for i in range(n, 0, -1):
# À compléter
pass
return tableau[n][temps_total], choisis
```
**Question 14.** Testez votre fonction. Vérifiez que les anticorps sélectionnés ont bien une durée totale ≤ 10 heures et une efficacité totale de 140.
**Question 15.** Quelle est la complexité en temps et en espace de la version bottom-up ? Exprimez-la en fonction de `n` (nombre d'anticorps) et `T` (temps total disponible).
---
## Partie 6 — Bonus : contraintes supplémentaires
**Question 16.** *(Bonus)* En réalité, certains anticorps sont **incompatibles** entre eux (ils réagissent chimiquement). Supposez que les anticorps Alpha et Gamma ne peuvent pas être produits ensemble.
Comment modifieriez-vous l'algorithme pour prendre en compte cette contrainte ? Proposez une approche (pas nécessairement de code).
---
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.