Difference between revisions of "Courses/COMP"
From LRDE
| (5 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Course |
{{Course |
||
| + | |visible=Yes |
||
|title=Introduction à la calculabilité et à la complexité |
|title=Introduction à la calculabilité et à la complexité |
||
|acronym=COMP |
|acronym=COMP |
||
| Line 9: | Line 10: | ||
|optional course=non |
|optional course=non |
||
|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 et notions nécessaires à la compréhension du problème P = NP et des classes de complexité. |
| + | |content=Voir polycopié. |
||
| − | |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=Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey Ullman. |
|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. |
Introduction to the Theory of Computation by Michael Sipser. |
||
| − | |slides=https://www.lrde.epita.fr/~adrien/ |
+ | |slides=https://www.lrde.epita.fr/~adrien/comp.html |
}} |
}} |
||
Latest revision as of 15:31, 7 October 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 et notions nécessaires à la compréhension du problème P = NP et des classes de complexité. |
| Plan |
Voir polycopié. |
| Documentation |
|
| Support | |
| Journaux |