Site de l'Université | English version
Année académique 2014-2015Données en date du : 20/12/2014
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ée5
Master en sciences informatiques, à finalité approfondie, 1re année5
Master en ingénieur civil en informatique, à finalité spécialisée en gestion, 1re année5
Master en sciences informatiques, à finalité spécialisée en gestion, 1re année5
Master en sciences informatiques5
Master en bioinformatique et modélisation, à finalité approfondie, 1re année6
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 et les séances d'exercices sont donnés en anglais. 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 :  
Examen écrit combinant théorie et exercices (pas d'oral). Un bonus est attribué pour une participation active aux cours théorique et aux séances d'exercices.
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
Assistant: Isabelle Mainz



Accueil

Bacheliers, masters, masters complémentaires et agrégations

Formations continues

Doctorat

Recherche par enseignant

Recherche par cours

Administration de l'Enseignement et des Etudiants - Responsable de l'information : Monique Marcourt, Direction générale à l'Enseignement et à la Formation - Réalisation SEGI