 | | |
| 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 français. L'ouvrage de référence est rédigé en français.
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 :
|
| P. Wolper, Introduction à la calculabilité (3ième édition), Dunod, 2006.
Ouvrage de référence obligatoire reprenant exactement la matière enseignée. |
|
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 |
|
