Complexité, calculabilité
RT0806
Semestre : 8 ECTS : 3 30 points
Année universitaire : 2023 / 2024
Responsable : 
   Pascal Mignot
Département :
   Informatique
   (UFR SEN)

    

   
Volume horaire :
NatureCMTDTPCMTDiTDTPiTotal
Durée14h 16h    30h 
Modalités de contrôle des connaissances :
Epreuves Nature DS DST EET  Total
Durée 2h 2h 2h 
Points (%) Cas général 1ère session 40 60  100%
2nde session   100 100%
Dispense contr. cont. 1ère session  100  100%
2nde session   100 100%
Objectifs :
Raisonner sur les concepts théoriques de l’informatique
Compétences spécifiques visées :
Connaître les classes des problèmes informatiques
Modéliser les exécutions

Compétences générales visées :
Distinguer les problèmes que l’on peut résoudre en informatique et, parmi eux, ceux que l’on sait pouvoir résoudre efficacement ou pas
Connaissances requises :
Introduction à l’informatique théorique RT0707
Programme :
Machine de Turing
Décidabilité / Indécidabilité
Introduction, définitions et motivations de la théorie de la complexité
La classe P, la classe NP ; Notion de NP-complétude
Parcours où cette matière apparaît comme ECF ou ECD :
Master -DAS
Dernière modification le 18/06/2020 à 9h53