Aller au contenu

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) :

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 :

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) :

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 :

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

Licence Creative Commons
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.