Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-1-3 [2011/07/12 14:23] (current)
baptiste created
Line 1: Line 1:
 +<html>
 +<h2>Calculabilité et complexité</h2>
 +
 +<p>Resp.: J.-M. Autebert</p>
 +
 +<h3>Objectifs</h3>
 +
 +<p>Discerner les problèmes que l'on peut théoriquement résoudre avec une
 +machine. Évaluer la difficulté en temps et en espace des problèmes que l'on
 +peut résoudre.</p>
 +
 +<h3>Plan du cours</h3>
 +
 +<ul>
 +<li> Modèles de calcul :
 +<ul>
 +<li> Machines de Turing (MT) : définitions, programmation, variantes,
 + complexités en temps et en espace, non déterminisme, énumération.  </li>
 +<li> Machines RAM : définitions, équivalence avec les MT (complexité).  </li>
 +<li> Fonctions récursives.</li>
 +</ul></li>
 +
 +<li> Décidabilité et indécidabilité :
 +<ul>
 +<li> Propriétés des langages R et RE.  </li>
 +<li> MT universelles.  </li>
 +<li> Réduction.  </li>
 +<li> Problèmes indécidables.</li>
 +</ul></li>
 +
 +<li> Complexité :
 +<ul>
 +<li> Comparaison des classes de complexité (temps, espace, déterministe
 + et non déterministe).  </li>
 +<li> Exemples de problèmes : satisfaisabilité, circuits booléens,
 + graphes, ...  </li>
 +<li> Réduction et complétude.  </li>
 +<li> Exemples de problèmes P-complets, NP-complets, PSPACE-complets, ...  </li>
 +<li> Calcul parallèle (classe NC).</li>
 +</ul></li>
 +</ul>
 +
 +<h3>Pré-requis</h3>
 +
 +<p>Théorie des automates.</p>
 +
 +<h3>Bibliographie</h3>
 +<ul>
 +<li> J. E. Hopcroft and J. D. Ullman, //Introduction to Automata Theory,
 + Languages and Computation//.
 + Addison-Wesley, 1974.</li>
 +<li> M. Sipser, //Introduction to the Theory of Computation//.
 + PWS publishing Company, 1997.</li>
 +<li> J.-M. Autebert, //Calculabilité et Décidabilité//.
 + Masson, 1992.</li>
 +<li> P. Wolper, //Introduction à la calculabilité//.
 + InterÉditions, 1991.</li>
 +<li> H. R. Lewis and C. Papadimitriou, //Elements of the theory of
 + computation//.
 + Prentice-Hall, 1981.</li>
 +<li> C. Papadimitriou, //Computational complexity//.
 + Addison-Wesley, 1995.</li>
 +<li> D. Welsh, //Codes and Cryptography//.
 + Clarendon Press, 1988.</li>
 +<li> J. Stern, //Fondements mathématiques de l'informatique//.
 + McGraw-Hill, 1990.</li>
 +</ul>
 +
 +<h3>Équipe pédagogique</h3>
 +<table border''"2">
 +<tr><td>J.-M. Autebert</td>
 +<td>PU</td>
 +<td>Univ. Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +<tr><td>A. Micheli</td>
 +<td>MC</td>
 +<td>Univ. Paris 7</td>
 +<td>LIAFA</td>
 +</tr></table>
 +</html>
 +
 +==== Les années précédentes ====
 +
 +  * [[2009-2010-C-1-3|Année 2009-2010]]
 +  * [[2008-2009-C-1-3|Année 2008-2009]]
 +
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA