Accueil - Recherche par Faculté - Par enseignant - Par cours


INFO0016-1

Introduction à la calculabilité

[ english version ]

Durée :30h Th, 30h Pr
Crédits/ECTS :
2e épreuve ingénieur civil électricien (électronique)6,5
2e épreuve ingénieur civil informaticien5,5
2e licence en informatique6
2e année du grade de master en sciences informatiques, à finalité spécialisée6
Titulaire(s) :Pierre Wolper
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.
Notes de cours : P. Wolper, Introduction à la calculabilité (2ième édition), InterEditions, 2001.
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 pw@montefiore.ulg.ac.be
Assistant: Xavier Hainaut - Tél. 04/366 26 34 - e-mail hainaut@montefiore.ulg.ac.be(legay@montefiore.ulg.ac.be)
Remarques : Des informations concernant ce cours peuvent être consultées à l'adresse Web : http://www.montefiore.ulg.ac.be/~pw/cours/calc.html

Eléments en ligne :
Informations additionnelles
Information d'horaire et de local, transparents et énoncés d'exercices




ULg : Administration de l'Enseignement et des Etudiants - Affaires Académiques
Responsable de l'information : Monique Marcourt, direction A.E.E.
Date de validité des données : 27/02/2006
Réalisation SEGI