Vous êtes ici

  1. Accueil
  2. Calculabilité

Calculabilité

Calculabilité

En pratique :

Volume horaire de cours : 24
Volume horaire global de TD : 6
Volume horaire global de TP : 18
Volume horaire globale de travail personnel : 40
Langue principale : français
Nombre de crédits européens : 6

Description du contenu de l'enseignement

Alors que la technologie informatique évolue très vite, la science informatique repose sur des hypothèses qui n'ont pas été mises en cause depuis 80 ans. On peut montrer que toutes les fonctions discrètes imaginables ne peuvent pas être calculées automatiquement. On montre que certaines de ces fonctions sont très simples à concevoir, et qu'il serait très utile de savoir les automatiser. On montre aussi que la nature de ces fonctions ne dépend pas du tout des moyens mis en œuvre pour les automatiser. On montre enfin que même quand une fonction peut être automatisée en principe, il se peut qu'elle ne le soit pas en pratique.

Chaque séance de cours ou de TP dure 2h.
A – Calculabilité (4 séances de cours, 2 séances de travaux pratiques)

  1. Introduction
  2. Théorèmes de Cantor
  3. Le problème de l’arrêt, la réduction calculatoire, le théorème de Rice
  • Travaux pratiques sur les nombres de Cantor

B – Sémantique (5 séances de cours, 10 séances de travaux pratiques)

  1. Syntaxe d’un langage de programmation, le langage WHILE
  2. Définition formelle de la sémantique de ce langage
  3. Programmation dans ce langage ; mise en œuvre de la récursivité
  4. Définition d’un interpréteur
  5. Restriction à un sous-langage, le langage FOR
  6. La thèse de Church
  • TP sur l’idée qu’un programme peut prendre en paramètre un programme :
      Un pretty-printer
  • Un interpréteur
  • Un fragment d’un compilateur

C – Complexité (3 séances de cours)

  1. Définition intuitive ; coût asymptotique ; notations
  2. Les problèmes P et NP ; la réduction polynomiale
  3. Les problèmes NP-complets ; le théorème de Cook

Compétences à acquérir

À l'issue de ce cours, l’étudiant comprendra mieux les limites intrinsèques de l'automatisation des calculs, que ce soit dans l’existence d’une solution à un problème ou dans le coût de calcul d’une solution. Il saura envisager des applications non-triviales dont les données sont des programmes et il saura mettre en œuvre quelques facettes rudimentaires du génie logiciel, ex. le test.
 


Bibliographie, lectures recommandées

  • Livre de référence : Calculateurs, Calcul, Calculabilité, Olivier Ridoux et Gilles Lesventes (Dunod, 2009)
  • Introduction à la calculabilité, Pierre Wolper (Dunod, 3ème édition, 2006)
  • Page web du cours et des travaux pratiques sur l’espace de partage du cours
  • Anciens sujets de contrôle disponibles sur l’espace de partage du cours

http://etudiant.istic.univ-rennes1.fr/current/l2ie/cal


Pré-requis

Profils attendus

Avoir une expérience minimale de la programmation. Avoir suivi le module de programmation fonctionnelle de première année de licence est une aide pour le langage de programmation utilisé en TP mais ce n'est pas un prérequis strict.