v2.11.0 (5449)

Enseignement scientifique & technique - MITRO202 : Calculabilité

Domaine > Mathématiques.

Descriptif

Ce cours met l'accent sur la calculabilité indépendamment des problèmes de complexité. Une donnée est effectivement calculable ou non, indépendamment des conditions en temps ou en mémoire.
Nous passerons en revue les différentes théories de la calculabilité ainsi que le principal résultat qui est la thèse de Church.
Nous verrons en particulier la théorie des combinateurs et le lambda-calcul.
Nous verrons quelques théorèmes d'’impossibilité qui en découlent.
Nous montrerons comment la théorie de types résout les paradoxes, la correspondance de Curry-Howard et la réalisabilité.

Mots-clé: Fonctions partielles récursives, Unlimited Register Machine, machine de Turing, théorie des combinateurs, lambda-calcul, typage, logique intuitionniste, isomorphisme de Curry-Howard.

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'ingénieur

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS
  • Crédit d'UE électives acquis : 2.5

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme Echange international non diplomant

La note obtenue rentre dans le calcul de votre GPA.

Programme détaillé

 

Veuillez patienter