Université Lyon 1
Université de Lyon
Arqus
Accueil  >>  Master  >>  Informatique  >>  M2 Technologies de l'information et web  >>  Modèles de calcul et complexité
  • Domaine : Masters du domaine SCIENCES, TECHNOLOGIES, SANTE
  • Diplôme : Master
  • Mention : Informatique
  • Parcours : M2 Technologies de l'information et web
  • Unité d'enseignement : Modèles de calcul et complexité
Nombre de crédits de l'UE : 3
Code APOGEE : INF1204M
UE Libre pour ce parcours
UE valable pour le semestre 1 de ce parcours
    Responsabilité de l'UE :
URBAIN XAVIER
 xavier.urbainuniv-lyon1.fr
    Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
15 h
Travaux Pratiques (TP)
0 h
Durée de projet en autonomie de l'étudiant (PRJ)
0 h
Durée du stage
0 h
Effectifs Cours magistraux (CM)
210 étudiants
Travaux dirigés (TD)
35 étudiants
Travaux pratiques (TP)
18 étudiants

* Ces horaires sont donnés à titre indicatif.

    Compétences attestées (transversales, spécifiques) :
Non rédigé
    Programme de l'UE / Thématiques abordées :
Le cours décrit trois grands modèles de calcul que sont les machines de Turing, les fonctions récursives et enfin les lambda-calculs.
On s'intéresse d'abord à l'aspect très opérationnel, syntaxique et impératif des machines de Turing. Ce modèle permet de définir des notions de calculabilité : ce qu'il est possible de faire, et de complexité : à quel coût ? Le cours aborde ensuite la description algébrique du comportement des fonctions avec les fonctions récursives de Gödel. La troisième partie est enfin consacrée aux lambda-calculs et aux familles de langages de programmation qui en descendent. Ces trois modèles sont montrés équivalents du point de vue de l'expressivité : bien que très différents, ils décrivent le même ensemble de programmes.

L'un des objectifs est d'acquérir une compréhension de l'objet à programmer et donc indépendance et adaptabilité vis-à-vis des langages disponibles. C'est au travers de la notion de réduction que sont perçus les coûts et contraintes entraînés par l'utilisation de bibliothèques ou solutions externes pour résoudre un problème.
  • Machines de Turing, simplifications
  • Problèmes de décision, réductions
  • Complexité, classes P et NP, complétude
  • Fonctions récursives
  • Lambda-calcul pur, lambda-calculs typés
    Liste des autres Parcours / Spécialité / Filière / Option utilisant cette UE :
SELECT * FROM parcours INNER JOIN ue_parcours ON PAR_ID_FK=PAR_ID INNER JOIN mention ON MEN_ID = PAR_MENTION_FK WHERE PAR_ACTIVATE = 0 AND UE_ID_FK='26119' ORDER BY UE_ID_FK ASC, PAR_ID_FK ASC