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/notes_comp_19_20.pdf
+
|slides=https://www.lrde.epita.fr/~adrien/comp.html
 
}}
 
}}

Latest revision as of 14:31, 7 October 2020

Titre

Introduction à la calculabilité et à la complexité

Sigle

COMP

Enseignant

Adrien Pommellet

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
  • 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.
Support
Journaux