Durée
26h Th, 26h Pr
Nombre de crédits
Enseignant
Langue(s) de l'unité d'enseignement
Langue anglaise
Organisation et évaluation
Enseignement au premier quadrimestre, examen en janvier
Horaire
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, à distance, hybride)
Cours en présentiel.
La classe contient 70 places. Si une place sur deux est utilisée, un système de réservation est mis en place pour accueillir les 35 premiers inscrits. Le système est remis à zéro toutes les semaines. Tous les cours sont podcastés.
Adaptations organisationnelles liées au contexte sanitaire
Evaluation en présentiel possible:
Examen écrit mélangeant théorie (compréhension via des vrai ou faux, restitution de preuves) et exercices similaires aux séances d'exercices.
Evaluation à distance imposée par la situation sanitaire:
Examen écrit à réaliser à domicile dans des conditions d'examen, mélangeant théorie (uniquement vrai/faux avec justification) et exercices similaires aux séances d'exercices.
Le pdf des questions d'examen est disponible sur le dox à l'heure de l'examen. Le scan des réponses de l'étudiant est à soumettre sur la plateforme de soumission https://submit.montefiore.ulg.ac.be
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
Vous trouverez ci-dessous les modalités d'évaluation envisagées pour les examens en présentiel et à distance ainsi que celle souhaitée en cas de session hybride. En fonction de l'évolution sanitaire, la modalité choisie vous sera communiquée au plus tard un mois avant le début de la session d'examen.
Examen écrit combinant théorie et exercices (pas d'oral).
Stage(s)
Remarques organisationnelles
Tous les documents du cours sont disponibles dans un répertoire dox:
https://dox.uliege.be/index.php/s/v2rwRkkAGXzPjDA
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 et les liens hebdomadaires pour réserver une place dans le local.
Contacts
Quentin Louveaux
q.louveaux@uliege.be
04/366 27 89