Courses/COMP

From LRDE

Revision as of 14:39, 15 January 2020 by Adrien Pommellet (talk | contribs)
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