Calculabilité et complexité

Nous utiliserons essentiellement les documents rédigés par Yannick Le Bras que je mets à jour régulièrement. Cette UE de 5 ECTS est organisée en 12 séances de 4h et deux partiels (50/50). Les 10 premières séances comportent une partie cours et une partie TD. Voici le plan prévisionnel de l'UE :

Cours

  1. Eléments de culture scientifique informatique
  2. An impossible program, indécidabilité du problème de l'arrêt
  3. Terminaison
  4. Correction
  5. Notation asymptotique : O() et Θ() (Sylvie Hamel)
  6. Complexité algorithmique

Exercices

  1. Exercices introductifs
  2. Exercices sur les notations asymptotiques
  3. Complexité algorithmique (Etienne Payet)

Evaluation

Contrôle continu : deux partiels sans document ni moyen électronique, 50% + 50%
Deuxième session : examen écrit sans document ni moyen électronique, tout est au programme, 100%

Annales

Ressources


Valid HTML5