Calculabilité et complexité

Nous utiliserons essentiellement les documents rédigés par Emmanuel Filiot et Yannick Le Bras.

Cours

  1. Eléments de culture scientifique informatique, indécidabilité du problème de l'arrêt
  2. Terminaison
  3. Correction
  4. Notation asymptotique : O() et Θ() (Sylvie Hamel)
  5. Complexité concrète
  6. Introduction à la théorie de la complexité
  7. Indécidabilité

Exercices

  1. Complexité concrète (Etienne Payet)
  2. P, NP, réductions
  3. Décidabilité/Indecidabilité

Travaux pratiques

Une initiation au système Coq (téléchargement) à partir des premiers chapitres de l'ouvrage collectif Software Foundations traduits en français par Tom Hirschowitz.
  1. Les bases, squelette
  2. L'induction, squelette
  3. Quiz Coq #1 (David Pichardie)
  4. Les structures de données, squelette

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

Bibliographie


Valid HTML5