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.
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.
24 heures en présentiel
Diplôme(s) concerné(s)
Parcours de rattachement
Pour les étudiants du diplôme Diplôme d'ingénieur
Cours de 1eA ou équivalent : Bases mathématiques ordinaires et quelques notions de programmation fonctionnelle.
Il est recommandé de suivre le cours de logique en même temps (MITRO 201)
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'ingénieur
Vos modalités d'acquisition :
Contrôle de connaissance + TP
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.
L'UE est évaluée par les étudiants.
Programme détaillé