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

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 nécessaires à la compréhension du problème P = NP et des classes de complexité.

Plan
  • 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
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