Complexité, calculabilité
|
RT0806 | ||||||||||||||||||||||||||||||||||||||||||||
Semestre : 8 | ECTS : 3 | 30 points | |||||||||||||||||||||||||||||||||||||||||||
Année universitaire : 2023 / 2024 | |||||||||||||||||||||||||||||||||||||||||||||
Responsable : Pascal Mignot Département : Informatique (UFR SEN) |
|
||||||||||||||||||||||||||||||||||||||||||||
Volume
horaire :
|
|||||||||||||||||||||||||||||||||||||||||||||
Modalités de contrôle des
connaissances :
|
|||||||||||||||||||||||||||||||||||||||||||||
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 |