 | |
| INFO0016-1 | Introduction to the theory of computation
 |
|
| Durée : | 30h Th, 30h Pr |
|
| Crédits/ECTS : |
| Master en ingénieur civil en informatique, à finalité approfondie, 1re année | | Premier quadrimestre | | 5 |
|
| Master en sciences informatiques, à finalité approfondie, 1re année | | Premier quadrimestre | | 6 |
|
| Master en ingénieur civil en informatique, à finalité spécialisée en gestion, 1re année | | Premier quadrimestre | | 5 |
|
| Master en sciences informatiques, à finalité spécialisée en gestion, 1re année | | Premier quadrimestre | | 6 |
|
| Master en sciences informatiques | | Premier quadrimestre | | 6 |
|
| Master en bioinformatique et modélisation, à finalité approfondie, 1re année | | Premier quadrimestre | | 6 |
|
|
|
| Titulaire(s) : | Pierre Wolper |
|
| Langue : | Langue anglaise |
|
| Aperçu général : | Introduction à la notion de procédure effective. Ensembles dénombrables et non dénombrables. Automates finis et à pile. Grammaires formelles et leur relation à la théorie des automates. Machines de Turing et thèse de Turing-Church. Théorie des fonctions récursives. Problèmes insolubles par une procédure effective. Introduction à la NP complétude et à la théorie de la complexité. |
|
| Objectif du cours : | Introduire les bases théoriques des limites des systèmes informatiques et en faire comprendre le sens. |
|
| Pré-requis : | Notions de programmation |
|
| Travaux pratiques : | Séances d'exercices permettant la familiarisation avec les concepts introduits au cours théorique. |
|
| Organisation : | 1er semestre - Cours théorique, séances d'exercices.
Le cours théorique est donné en anglais, les séances d'exercices en français. L'ouvrage de référence est rédigé en français. |
|
| Notes de cours : | P. Wolper, Introduction à la calculabilité (3ième édition), Dunod, 2006. |
|
| Evaluation : | Interrogation facultative au cours du semestre; examen écrit combinant théorie et exercices (pas d'oral). |
|
| Contacts : | Enseignant: P. Wolper - Tél. 04/366 20 99 - e-mail Pierre.Wolper@ulg.ac.be(%20Pierre.Wolper@ulg.ac.be
Assistant:) |
|
| Remarques : | Des informations concernant ce cours peuvent être consultées à l'adresse Web : http://www.montefiore.ulg.ac.be/~pw/cours/calc.html |
|
