Description

Brian.Pulfer@unige.ch
Remarques:
Veuillez suivre attentivement les sp´ecifications de l’´enonc´e.
• R´eponses – Essayez d’ˆetre exhaustif dans vos r´eponses. Les r´eponses comme ”oui” et ”non” ne permettent pas d’´evaluer vos connaissances.
• Trac´es – Mettez toujours des ´etiquettes d’axe et des titres pour les trac´es.
• Impl´ementation – Veuillez utiliser exactement les noms fournis pour les fonctions. Vous pouvez utiliser pytest avec le script de test donn´e pour v´erifier votre impl´ementation.
• Soumission
Merci de t´el´echarg´e vos devoirs sur moodle:
– NomPrenom.pdf avec votre rapport pour tout les exercices – tp2.py avec votre implementations
– Pas d’autres fichiers (.pyc, .ipynb, DS Store, pycache , …)
• Pour toute questions et remarques, merci d’utiliser le mail Brian.Pulfer@unige.ch.
1 Knapsack (1 Points)
Le probl`eme du knapsack est le suivant: ´etant donn´e un ensemble d’ ´el´ements avec des poids et des valeurs associ´es, trouvez le sous-ensemble qui maximise la somme des valeurs tout en maintenant la somme des poids sous une valeur constante (taille du sac). Voir Table 1 pour un exemple.
Nr. El´ement´ Poids Valeur
1 10 5
2 3 2
3 7 4
4 12 9
5 1 2
Table 1: Exemple d’´el´ements dans un probl`eme de Knapsack
La solution optimale d´epend du poids que le knapsack peut supporter. Pour une capacit´e de 25, la solution optimale est de choisir les ´el´ements 2, 3, 4, 5 avec un poids total de 23 (< 25) et une valeur totale de 17.
Impl´ementez trois algorithmes greedy. Utilisez le script de test pour v´erifier votre impl´ementation. Les algorithmes continuent d’ins´erer l’´el´ement non pris avec:
a la valeur la plus ´elev´ee; b le poids le plus bas; c le rapport le plus ´elev´e.
Pour chaque algorithme propos´e:
• Indiquez quelle est la complexit´e en temps.
• Indiquez s’il est optimal ou non. Si c’est le cas, prouvez pourquoi. Sinon, donnez un contreexemple.
2 Rendu de monnaie britannique (2 Points)
Avant la d´ecimalisation, la monnaie britannique contenait les pi`eces suivantes:
– la demi-couronne d’une valeur de 30 pence;
– le florin d’une valeur de 24 pence;
– le shilling d’une valeur de 12 pence;
– le sixpence d’une valeur de 6 pence; – le threepence d’une valeur de 3 pence;
– le penny.
Dans cet exercice, on ne prendra pas en compte le demi penny (12 pence) ni le farthing (14 pence). Notez que ’pence’ est le pluriel de ’penny’.
• Donnez un pseudocode correspondant `a l’algorithme Greedy vu en cours pour r´esoudre ce probl`eme.
• Pourquoi peut-on dire que c’est un algorithme de type Greedy?
• Quelle est la complexit´e en temps de cet algorithme?
• Cet algorithme est-il toujours optimal? Si oui, prouvez-le, sinon donnez un contre-exemple. • Impl´ementez cet algorithme (correspondant `a votre pseudocode) en Python au travers d’une fonction compute_change(money, coin_set), ou` money est la monnaie totale qui doit ˆetre chang´ee et coin_set une simple liste ordonn´ee contenant la valeur des pi`eces disponibles pour le change. Cette fonction doit retourner une liste contenant, dans l’ordre, les pi`eces chang´ees contre la somme initiale. Utilisez le script de test pour v´erifier votre impl´ementation.
from tp2 import compute_change
def test_compute_change():
coin_set = [30, 24, 12, 6, 3, 1] assert compute_change(0, coin_set) == [] assert compute_change(2, coin_set) == [1, 1] assert compute_change(4, coin_set) == [3, 1] assert compute_change(10, coin_set) == [6, 3, 1] assert compute_change(33, coin_set) == [30, 3] assert compute_change(100, coin_set) == [30, 30, 30, 6, 3, 1]
1
2
3
4
5
6
7
8
9
10
Listing 1: Code de test pour la fonction compute_change
3 Minimum Spanning Tree (1 Point)
Etant donn´e une matrice d’adjacence sym´etrique´ A d’un graphe G, ou` chaque ´el´ement Ai,j =Aj,i repr´esente le poids des arˆetes reliant les nœuds i et j, impl´ementez l’algorithme de Kruskal qui retourne les arˆetes de l’arbre couvrant minimum (MST). Utilisez le script de test pour v´erifier votre impl´ementation. • Cet algorithme va-t-il toujours trouver un arbre couvrant minimum? Si oui, prouvez pourquoi.
Sinon, donnez un contre-exemple.
4 4-SAT (1 Point)
4-SAT: D´eterminer si une formule bool´eenne en CNF, ou chaque disjonction comprend exactement
4 ´el´ements, est satisfaisable.
Montrez que 4-SAT est NP-Complet.