Séance pratique
Durée2h30Présentation et objectifs
L’objectif de cette séance est de vous aider à maîtriser des notions importantes en informatique. Un assistant de programmation intelligent tel que GitHub Copilot, que vous avez peut-être déjà installé, sera capable de vous fournir une solution à ces exercices en se basant uniquement sur un nom de fichier judicieusement choisi.
Dans un objectif de formation, nous vous conseillons de désactiver ces outils dans un premier temps.
À la fin de l’activité pratique, nous vous suggérons de reprendre l’exercice avec ces outils activés. Suivre ces deux étapes améliorera vos compétences tant fondamentales que pratiques.
L’implémentation des solutions n’est pas indispensable, privilégiez le travail collaboratif sur papier.
Contenu de l’activité
1 — Le problème du sac à dos
Le problème est le suivant (cité de Comer et al.).
Un voleur qui cambriole un magasin veut emporter la charge la plus précieuse qui peut être transportée dans un sac à dos capable de porter au maximum $W$ livres de butin. Le voleur peut choisir de prendre n’importe quel sous-ensemble de $n$ objets dans le magasin. Le $i$ème objet vaut $v_i$ dollars et pèse $w_i$ livres, où $v_i$ et $w_i$ sont des entiers. Quels objets le voleur devrait-il prendre ?
Remarque : Le problème est appelé le problème du sac à dos 0-1 parce que le voleur peut soit prendre un objet soit le laisser, mais ne peut pas prendre une fraction d’un objet.
Pour cet exercice, nous allons créer un fichier knapsack.py
et implémenter diverses solutions au problème du sac à dos 0-1.
En parallèle, nous allons créer un fichier test_knapsack.py
pour tester les fonctions implémentées dans knapsack.py
.
Nous ne vérifierons pas seulement la justesse des fonctions mais aussi leur efficacité.
Comme paramètres de base, nous considérerons les valeurs suivantes :
- Le poids maximum que le sac à dos peut porter : $W = 50$.
- La liste des poids des objets : $weights = [10, 20, 30]$.
- La liste des valeurs des objets : $values = [60, 100, 120]$.
Deux ensembles de paramètres supplémentaires seront considérés pour les tests :
- $W = 15$, $weights = [12, 7, 11, 8, 9]$, $values = [24, 13, 23, 15, 16]$.
- $W = 30$, $weights = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]$, $values = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]$.
Le premier ensemble de paramètres est suffisamment petit pour vous permettre de calculer les résultats à la main. Les deux autres ensembles de paramètres sont plus grands et nécessiteront l’implémentation d’algorithmes efficaces et vous permettront de ressentir la complexité de chaque approche.
1.1 — Solution à la main
Oubliez le programme, prenez un stylo et du papier et considérez le premier exemple de test. Listez toutes les combinaisons possibles d’objets qui peuvent être pris, et pour chacune d’elles, calculez le poids total et la valeur totale. Ensuite, déterminez la combinaison qui maximise la valeur totale sans dépasser le poids maximum que le sac à dos peut porter. Cette solution vous aidera à comprendre le problème et les résultats attendus.
1.2 — Une solution récursive
La première fonction à implémenter est une solution récursive au problème du sac à dos 0-1. La fonction doit avoir la signature suivante :
def knapsack_recursive(W: int, weights: List[int], values: List[int]) -> int:
""" Recursive solution to the 0-1 knapsack problem.
In:
- W: the maximum weight the knapsack can carry
- weights: the list of weights of the items
- values: the list of values of the items
Out:
- the maximum value that can be carried in the knapsack
"""
pass
La solution récursive est simplement basée sur la propriété de sous-structure optimale du problème : si la charge la plus précieuse inclut l’objet $i$, alors la charge restante doit être la charge la plus précieuse pesant au maximum $W - w_i$ que le voleur peut prendre parmi les objets originaux, en excluant l’objet $i$._
1.3 — Une solution récursive avec mémoïsation
Une deuxième étape consiste à implémenter une solution récursive avec mémoïsation. La fonction doit avoir la signature suivante :
def knapsack_recursive_memo(W: int, weights: List[int], values: List[int]) -> int:
""" Recursive solution with memoization to the 0-1 knapsack problem.
In:
- W: the maximum weight the knapsack can carry
- weights: the list of weights of the items
- values: the list of values of the items
Out:
- the maximum value that can be carried in the knapsack
"""
pass
La solution récursive avec mémoïsation consiste à stocker les résultats des sous-problèmes dans une table pour éviter de les recalculer.
1.4 — Une solution de programmation dynamique
Une troisième étape consiste à implémenter une solution de programmation dynamique au problème du sac à dos 0-1. La fonction doit avoir la signature suivante :
def knapsack_dp(W: int, weights: List[int], values: List[int], n: int) -> int:
""" Dynamic programming solution to the 0-1 knapsack problem.
In:
- W: the maximum weight the knapsack can carry
- weights: the list of weights of the items
- values: the list of values of the items
- n: the number of items
Out:
- the maximum value that can be carried in the knapsack
"""
pass
Contrairement à la solution de mémoïsation, la solution de programmation dynamique remplit la table de manière ascendante.
1.5 — Une solution gloutonne
La dernière étape consiste à implémenter une solution gloutonne au problème du sac à dos 0-1. La fonction doit avoir la signature suivante :
def knapsack_greedy(W: int, weights: List[int], values: List[int]) -> int:
""" Greedy solution to the 0-1 knapsack problem.
In:
- W: the maximum weight the knapsack can carry
- weights: the list of weights of the items
- values: the list of values of the items
Out:
- the maximum value that can be carried in the knapsack
"""
pass
La solution gloutonne consiste à sélectionner l’élément avec le ratio valeur-poids maximum jusqu’à ce que le sac à dos soit plein.
Questions :
- Que pouvez-vous dire de la solution gloutonne comparée aux autres solutions ?
2 — Optimisez vos solutions
Ce que vous pouvez faire maintenant, c’est utiliser des outils d’IA tels que GitHub Copilot ou ChatGPT, soit pour générer la solution, soit pour améliorer la première solution que vous avez proposée ! Essayez de le faire pour tous les exercices ci-dessus, pour voir les différences avec vos solutions.
Pour aller plus loin
3 — Le problème du sac à dos fractionnaire
Considérez désormais que vous pouvez prendre une fraction de chaque objet et pas nécessairement sont entièreté.
Quelle serait la solution gloutonne à cette variante du problème ? Quelle est la complexité de cette solution gloutonne et que peut-on dire du résultat obtenu ?
Pour aller au-delà
Vous venez donc de voir plusieurs types de solutions algorithmiques :
- diviser pour régner
- programmation dynamique
- gloutonne
Il existe d’autres familles d’algorithmes. Nous étudierons les approches basées sur l’intelligence artificielle lors de la prochaine session, mais vous pouvez désormais vous intéresser aux méthodes dites :
- Monte Carlo
- Las Vegas
- Backtracking
- Satisfaction de contraintes
- Programmation linéaire
En vous documentant sur ces méthodes, trouvez un problème approprié pour chacune d’elles.