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= |
+ | |content=Machines de TuringLangages et décidabilité* Réductions* Complexité en temps déterministe* Complexité en temps non-déterministe* Réductions polynomiales et complétude |
| − | |references= |
+ | |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 15:38, 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 |
Machines de TuringLangages et décidabilité* Réductions* Complexité en temps déterministe* Complexité en temps non-déterministe* Réductions polynomiales et complétude |
| Documentation |
|
| Support | |
| Journaux |