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 |
+ | |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. |
+ | |references=* Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey Ullman. |
− | Hopcroft, Rajeev Motwani, and Jeffrey Ullman. |
||
* Introduction to the Theory of Computation by Michael Sipser. |
* 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:36, 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 |