ECTS
3 crédits
Composante
UFR Sciences et Montagne
Heures d'enseignement
- CMCours Magistral7,5h
- TDTravaux Dirigés7,5h
- TPTravaux Pratiques12h
Plan du cours
CM : Ce cours a pour but d'apprendre des algorithmes et à les classifier en fonction de leur temps d'exécution. Étude du comportement asymptotique (en notation grand-O). Conception et analyse d'algorithmes respectant les principes "diviser pour régner", "programmation dynamique", "gloutons", etc… Introduction à la théorie de la NP-complétude et réductions polynomiales.
TD : Exercices visant à maîtriser les concepts vus en cours. Analyser la complexité temporelle des différents algorithmes.
TP : Implémentation et comparaison d'algorithmes complexes.Résolution de problèmes NP-complets (heuristique, utilisation de SAT-solver). Langage au choix.