Introduction à la calculabilité


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

INFO0016-1

Durée :

30h Th, 30h Pr

ECTS :

2e épreuve ingénieur civil électricien (électronique)		6,5
2ème épreuve ingénieur civil informaticien		5,5
2e licence en informatique		6

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 :

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: Sébastien Jodogne - Tél. 04/366 26 43 - e-mail jodogne@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

ULg : Administration de l'Enseignement et des Etudiants - Affaires Académiques
Responsable de l'information : Monique Marcourt, directrice A.E.E.
Date de validité des données : 23/01/2004
Réalisation SEGI