Courses/COMP

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	https://www.lrde.epita.fr/~adrien/notes_comp_19_20.pdf
Journaux