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 TuringLangages et décidabilité* Réductions* Complexité en temps déterministe* Complexité en temps non-déterministe* Réductions polynomiales et complétude
+
|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.
 
|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.

Revision as of 14:39, 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