AccueilLicence généraleInformatiqueEnseignementsCalculabilité et sémantique

Licence InformatiqueUE Calculabilité et sémantique

Contenu

Objectifs : 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. Une initiation à la sémantique des langages de programmation, tant impératifs que fonctionnels, permet d’appréhender d’une façon différente la programmation et les preuves de correction nécessaire qui en découlent. Par la pratique d’un langage de programmation fonctionnel, la thèse de Church-Turing et la notion de typage sont abordées à travers l’utilisation du λ-calcul.

Spécificités de la programmation fonctionnelle : types algébriques, filtrage, fonctions d’ordre supérieur, combinateurs

Sémantique d’un langage impératif simple : sémantiques opérationnelle (présentation à grand pas, à petit pas, interpréteur d’un langage jouet) et dénotationnelle (rôle du point fixe, équivalence de programmes, équivalence avec la sémantique opérationnelle)

Calculabilité : machines de Turing déterministes et langages récursifs, machines universelles, problème de l’arrêt, fonctions récursives

Calcul fonctionnel : sémantique d’un langage fonctionnel, λ-calcul pur (β-réduction, normalisation, codage des entiers, thèse de Church-Turing)

Évocation de la complexité de problèmes : classes P et NP, exemples de problèmes NP-complets

Langue utilisée

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

Volume des enseignements

  • Cours magistraux : 18 heures
  • Travaux dirigés : 32 heures
  • Travaux pratiques : 10 heures

Les formations qui utilisent cet enseignement