Difference between revisions of "Courses/COMP"
From LRDE
Line 10: | Line 10: | ||
|prerequisites=ALGO, THL |
|prerequisites=ALGO, THL |
||
|objectives=Introduire les outils nécessaires à la compréhension du problème P = NP et des classes de complexité. |
|objectives=Introduire les outils nécessaires à la compréhension du problème P = NP et des classes de complexité. |
||
+ | |content=* Machines de Turing * Langages et décidabilité * Réductions * Complexité en temps déterministe * Complexité en temps non-déterministe * Réductions polynomiales et complétude |
||
+ | |references=* Introduction to Automata Theory, Languages, and Computation by John E. |
||
+ | Hopcroft, Rajeev Motwani, and Jeffrey Ullman. |
||
+ | * Introduction to the Theory of Computation by Michael Sipser. |
||
|slides=https://www.lrde.epita.fr/~adrien/notes_comp_19_20.pdf |
|slides=https://www.lrde.epita.fr/~adrien/notes_comp_19_20.pdf |
||
}} |
}} |
Revision as of 14:35, 15 January 2020
Titre |
Introduction à la calculabilité et à la complexité |
---|---|
Sigle |
COMP |
Enseignant | |
Période |
S5, Ing3 |
Public |
Majeure |
Contrôle |
Partiel |
Durée |
1212 h <br /> |
Optionnel |
non |
Module | |
Prérequis |
ALGO, THL |
Objectifs |
Introduire les outils nécessaires à la compréhension du problème P = NP et des classes de complexité. |
Plan |
|
Documentation |
|
Support | |
Journaux |