Dimitri Watel

COMPLEXITÉ DES ALGORITHMES

Autre(s) enseignant(es) : Olivier Hudry

Page officielle du cours

Ce cours est commun entre l'ENSIIE (cours OPTI1-ICA) et le MPRO (cours TC). La complexité algorithmique étudie la difficulté intrinsèque des problèmes, en particulier vis-à-vis du temps nécessaire à leur résolution. On donne une introduction à l'étude des classes de complexité, en s'appuyant sur divers problèmes d'optimisation combinatoire, principalement de graphes.
  1. Complexité des problèmes de décision
  2. Machines de Turing
  3. Classes de complexité
  4. Réductions et complétude
  5. Théorème de Cook-Levin
  6. Problèmes d'optimisation
  7. Codage des entrées
  8. Autres classifications

TDs

  1. Problèmes de décision et machines de Turing (Correction)
  2. Classes de complexité (Correction)
  3. Réductions et complétude (Correction)
  4. Problèmes d'optimisation (Correction)
  5. Codage des entrées (Correction)

Annotations du tableau

Autres

Changer de langue : Français English