|
— |
cours:c-1-3 [2011/07/12 14:23] (current)
baptiste created |
| | + | <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]] |
| | + | |
| | | | |