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.
• Points extra – Le nombre maximum de points pouvant ˆetre marqu´es pour un TP est de 5, ce qui conduit `a une note de 6. Vous pouvez effectuer l’exercice 2 pour obtenir des points suppl´ementaires. Marquer plus de 5 points est toujours arrondi `a la note 6.
• 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 – tp6.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 Vertex Cover (5 Points)
Vertex-cover est un probl`eme NP-complet. Cependant, nous savons que l’algorithme de 2-approximation suivant est lin´eaire en nombre d’arˆetes et de nœuds:
APPROX-VERTEX-COVER(G):
C = 0
E’ = G.E while E’ is not 0 let (u, v) be an arbitrary edge of E’ C = C U {u, v}
remove from E’ every edge incident on either u or v
return C
1
2
3
4
5
6
7
8
Listing 1: Pseudo-code de l’algorithme d’approximation pour le problem du vertex-cover
• Implementez l’algorithme d’approximation approx_vertex_cover(matrix). L’input de l’algorithme est une matrice d’adjacence sym´etrique n×n matrix (matrix[i][j] indique si les nœuds i et j sont connect´es par une arˆete). L’output est l’ensemble des nœuds s´electionn´es. L’algorithme doit traverser les arˆetes dans l’ordre ((0,1), (0,2)…(n-1,n-1)).
2 Knapsack problem (1 Point extra)
Knapsack problem (0-1) est un probl`eme NP-complet. Cependant, nous savons que l’algorithme de 2-approximation suivant est polynomial:
APPROX-KNAPSACK(I):
R = 0 for j = 1, …, n
Ij = I[j:]
Rj = greedy(Ij)
R = R U Rj
return maximum_element(R)
1
2
3
4
5
6
7
Listing 2: Pseudo-code de l’algorithme d’approximation pour le problem du TSP
• Implementez l’algorithme d’approximation approx_knapsack(weights, values, max_weight). L’input de l’algorithme sont le liste des poids et des valeurs des elements et la capacit´e du knapsack. L’output est la liste des index s´electionn´es par l’algorithme d’approximation.