Analyse d'algorithmes (INFO003_INFO)
Présentation
Heures d'enseignement
| Cours Magistral | 7,5h | |
| Travaux Dirigés | 7,5h | |
| Travaux Pratiques | 12h |
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.