2017-2018 / INFO0016-1

Introduction to the theory of computation

Durée

30h Th, 30h Pr

Nombre de crédits

 Master en science des données, à finalité5 crédits 
 Master : ingénieur civil en informatique, à finalité5 crédits 
 Master : ingénieur civil en science des données, à finalité5 crédits 
 Master en sciences informatiques, à finalité5 crédits 
 Master en sciences informatiques5 crédits 
 Master en bioinformatique et modélisation, à finalité6 crédits 

Enseignant

Pierre Wolper

Langue(s) de l'unité d'enseignement

Langue anglaise

Organisation et évaluation

Enseignement au premier quadrimestre, examen en janvier

Unités d'enseignement prérequises et corequises

Les unités prérequises ou corequises sont présentées au sein de chaque programme

Contenus de l'unité d'enseignement

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) de l'unité d'enseignement

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.

Savoirs et compétences prérequis

Notions de programmation

Activités d'apprentissage prévues et méthodes d'enseignement

1er quadrimestre - 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 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 93 13 e-mail Pierre.Wolper@ulg.ac.be Assistant: Isabelle Mainz