INFO0016-1

Durée

26h Th, 26h Pr

Nombre de crédits

	Master en sciences informatiques, à finalité spécialisée en "computer systems security"	5 crédits
	Master en sciences informatiques, à finalité spécialisée en "computer systems security" (double diplômation avec HEC)	5 crédits
	Master en science des données, à finalité spécialisée	5 crédits
	Master : ingénieur civil en science des données, à finalité spécialisée	5 crédits
	Master : ingénieur civil en informatique, à finalité spécialisée en "management"	5 crédits
	Master : ingénieur civil en informatique, à finalité spécialisée en "intelligent systems"	5 crédits
	Master : ingénieur civil en informatique, à finalité spécialisée en "intelligent systems" (double diplômation avec HEC)	5 crédits
	Master en sciences informatiques, à finalité spécialisée en "management"	5 crédits
	Master : ingénieur civil en informatique, à finalité spécialisée en "computer systems security"	5 crédits
	Master : ingénieur civil en informatique, à finalité spécialisée en "computer systems security" (double diplômation avec HEC)	5 crédits
	Master en sciences informatiques, à finalité spécialisée en "intelligent systems"	5 crédits
	Master en sciences informatiques, à finalité spécialisée en "intelligent systems" (double diplômation avec HEC)	5 crédits

Enseignant

Quentin Louveaux

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

Langue anglaise

Organisation et évaluation

Enseignement au premier quadrimestre, examen en janvier

Horaire

Horaire en ligne

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.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, I.3, II.1, III.1, III.2 du programme d'ingénieur civil en science des données.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, III.1, III.2 du programme d'ingénieur civil en informatique.

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, à distance, hybride)

Cours donné exclusivement en présentiel

Explications complémentaires:

Cours en présentiel.

Supports de cours, lectures obligatoires ou recommandées

Autre(s) site(s) utilisé(s) pour les supports de cours
- dox (https://dox.uliege.be/index.php/s/GScGPUZj6Qc79EW)

Informations complémentaires:

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(s) en session

Toutes sessions confondues

- En présentiel

évaluation écrite ( questions ouvertes )

Explications complémentaires:

Examen écrit combinant théorie et exercices (pas d'oral).

Stage(s)

Remarques organisationnelles et modifications principales apportées au cours

Tous les documents du cours sont disponibles dans un répertoire dox:

https://dox.uliege.be/index.php/s/GScGPUZj6Qc79EW

Ce répertoire contient les slides, les slides annotés durant les cours, les exercices, éventuellement les exercices annotés, les examens précédents.

Contacts

Quentin Louveaux
q.louveaux@uliege.be
04/366 27 89

Introduction to the theory of computation