Accueil
Connexion
DENIF –
Documents d’Enseignement Numériques en Informatique Fondamentale
Thèmes
Cursus
Enseignants
Algorithmes d'approximation
Thème :
Algorithmique
–
Cursus :
ENS-Lyon - M1
2004 - 2005
TDs
Guillaume Theyssier
TD 1 : Empaquetage et arbres de Steiner
TD 2 : La méthode du mille feuilles
TD 3 : Dominer, couvrir, colorier...
TD 4 : Après le centre, l'asymétrie
TD 5 : Indépendance et espérance
TD 6 : Forces et faiblesses de la randomisation
TD 7 : PTAS et sac-à-dos
Examens
Nicolas Schabanel
,
Guillaume Theyssier
Partiel
Partiel (en anglais)
Correction du Partiel
Examen
Examen (en anglais)
Correction de l'Examen
2003 - 2004
TDs
Emmanuelle Lebhar
TD 1 : Travelling Salesman Problem et Arbre de Steiner
TD 2 : Couvertures et compagnie
TD 3 : Surfacteur minimum
TD 4 : Mille-feuille et k-centre
TD 5 : Coupe-circuits de sommets
TD 6 : Méthode de l'espérance conditionnelle
TD 7 : FPTAS et sac-à-dos
TD 8 : Minimisation du temps d'exécution total
TD 9 : Dualité en programmation linéaire
TD 10 : Arrondi LP et couverture par ensembles
TD 11 : Schéma primal-dual et ordonnancement hétérogène
Examens
Partiel
Correction du Partiel
Examen