AccueilLicence généraleInformatiqueEnseignementsCalculabilité

Licence InformatiqueUE Calculabilité

Contenu

Cette unité d'enseignement a pour objectif d'étudier la théorie de la calculabilité pour distinguer les problèmes qu'on peut résoudre en informatique, de ceux qu'on ne peut pas résoudre.

  • Machine de Turing : déterministe (équivalence non-déterministe et multi-ruban)
  • Décider et calculer : langage récursif et récursivement énumérable, fonction calculable et semi-calculable.
  • Propriétés de clotûre des langages récursifs et r.e.
  • Existence de fonctions non calculables par dénombrement (diagonale de Cantor)
  • Problème de l'arrêt
  • Réduction : many-one-réduction Turing
  • Théorème de Rice
  • Universalité et complétude
  • Thèse de Church Turing
  • λ-calcul : termes, beta-réduction, forme normale, terminaison…
  • P, NP, NP-difficile : parler de certificats et montrer des exemples de problèmes NP-difficiles avec le genre de réduction que cela implique (pas un acquis attendu en fin de cours)

Compétences visées

  • Être familiarisé avec les concepts fondamentaux de complexité et calculabilité.
  • Utiliser les concepts fondamentaux de l'informatique (langages formels, logique, et graphes) pour la programmation et la modélisation.
  • Rédiger de manière synthétique et rigoureuse des preuves.
  • Se servir aisément des bases de la logique pour valider ou réfuter un raisonnement.

Langue utilisée

Langue principale utilisée par cet enseignement : Français.

Pré-requis recommandés

  • Langages formels

Volume des enseignements

  • Cours magistraux : 9 heures
  • Travaux dirigés : 21 heures

Les formations qui utilisent cet enseignement