 | | |
| INFO0016-1 | Introduction to the theory of computation
|
|
| Durée : | 30h Th, 30h Pr |
|
| Nombre de crédits : |
| Master en ingénieur civil en informatique, à finalité approfondie, 1re année | | 5 |
|
| Master en sciences informatiques, à finalité approfondie, 1re année | | 6 |
|
| Master en ingénieur civil en informatique, à finalité spécialisée en gestion, 1re année | | 5 |
|
| Master en sciences informatiques, à finalité spécialisée en gestion, 1re année | | 6 |
|
| Master en sciences informatiques | | 6 |
|
| Master en bioinformatique et modélisation, à finalité approfondie, 1re année | | 6 |
|
|
|
| Nom du professeur : | Pierre Wolper |
|
Langue(s) du cours :
|
| Langue anglaise |
|
Organisation et évaluation :
|
| Enseignement au premier quadrimestre, examen en janvier |
|
Contenus du cours :
|
| 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é. |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| A l'issue de ce cours, l'étudiant aura une bonne connaissance de la théorie relative aux limites des systèmes informatiques et en comprendra le sens. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| Notions de programmation |
|
Activités d'apprentissage prévues et méthodes d'enseignement :
|
| 1er semestre - Cours théorique, séances d'exercices.
Le cours théorique est donné en anglais, les séances d'exercices en anglais et/ou français. L'ouvrage de référence est rédigé en français, mais des livres similaires en anglais sont disponibles.
Les séances d'exercices permettent la familiarisation avec les concepts introduits au cours théorique. |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Cours en présentiel. |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Ouvrage de référence recommandé reprenant exactement la matière enseignée:
P. Wolper, Introduction à la calculabilité (3ième édition), Dunod, 2006.
Ouvrage de référence en anglais:
Michael Sipser, Introduction to the Theory of Computation, CENGAGE Learning Custom Publishing, 2012 |
|
Modalités d'évaluation et critères :
|
| Interrogation facultative au cours du semestre; examen écrit combinant théorie et exercices (pas d'oral). |
|
Stage(s) :
|
| |
|
Remarques organisationnelles :
|
| Des informations concernant ce cours peuvent être consultées à l'adresse Web : http://www.montefiore.ulg.ac.be/~pw/cours/calc.html |
|
Contacts :
|
| Enseignant: P. Wolper - Tél. 04/366 20 99 - e-mail Pierre.Wolper@ulg.ac.be |
|
