Accueil  >>  Master  >>  Informatique  >>  Technologies de l'information et web  >>  Calculabilité et complexité
  • Domaine : Masters du domaine SCIENCES, TECHNOLOGIES, SANTE
  • Diplôme : Master
  • Mention : Informatique
  • Parcours : Technologies de l'information et web
  • Unité d'enseignement : Calculabilité et complexité
Nombre de crédits de l'UE : 3
Code APOGEE : INF1095M
UE Obligatoire 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
Total du volume horaire
30 h
* Ces horaires sont donnés à titre indicatif.
    Programme - Contenu de l'UE :
Cette UE prend part dans l’informatique théorique, au même titre que la compilation, et fait suite à la théorie des langages formels de licence.Historiquement, après les résultats d’incomplétude dus à Goedel, Church et Turing s’est posée la question de ce qu’on peut calculer avec un algorithme. Encore fallait-il formaliser la notion d’algorithme : Church s’est basé sur les notions de fonctions, ses travaux ont donné lieu au lambda-calcul et à la programmation fonctionnelle en général ; Turing a formalisé une machine (théorique) universelle, les machines de Turing, qui ont donné lieu à la programmation impérative. Ces travaux ont conduit à la thèse de Church-Turing et au développement de techniques de calculabilité. On peut ainsi donner sens à la notion de problème de décision décidable (et indécidable) et chercher à déterminer des classes de complexité de problèmes décidables, par exemple P et NP.L’UE se découpe en trois parties :- Machines de Turing : reconnaissance de langages, calcul de fonctions, extensions des machines de Turing, grammaires générales, fonctions mu-récursives, fonctions récursives.- Indécidabilité : thèse de Church-Turing, machines de Turing universelles, problème de l’arrêt, problèmes indécidables à propos des machines de Turing et des grammaires, langages récursivement énumérables, langages récursifs, théorème de Rice.- Complexité (via les machines de Turing) : classe P, SAT (satisfaisabilité booléenne), classe NP, NP-complétude, théorème de Cook.
http://liris.cnrs.fr/~sbrandel/wiki/doku.php?id=ens:mif15
    Modalités de contrôle des connaissances et Compétences 2018-2019 :
TypeLibelléNatureCoef. 
CTContrôle TerminalCT : M1if09 ComplexiteEcrit session 1 / Ecrit session 21.5
CCContrôle ContinuCC : M1if09 ComplexiteContrôle Continu1.5
    Liste des autres Parcours / Spécialité / Filière / Option utilisant cette UE :
Date de la dernière mise-à-jour : 13/04/2018
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='16773' ORDER BY UE_ID_FK ASC, PAR_ID_FK ASC