Computability and complexity

Formalisation de la notion de problème - Formalisation de la notion d'algorithme - Machine de Turing - Décidabilité - Ensembles dénombrables et non dénombrables - Indécidabilité - Réduction - Ensembles récursivement énumérables - Théorème de Rice - Complexité en temps - La classe P - La classe NP - Complétude pour la classe NP - Théorème de Cook - Réduction polynomiale - La classe PSpace - Complétude pour la classe PSpace

Le cours vise à familiariser les étudiants avec certains concepts fondamentaux de l'informatique, à savoir les théories de la décidabilité et la complexité.

A l'issue du cours, les étudiants devront être à même de définir rigoureusement ces notions (ainsi que l'outillage mathématique nécessaire pour arriver à ces définitions: machine de Turing, notion de réduction, etc), de les illustrer par des cas concrets, d'en expliquer la portée, et d'expliquer leur mise en pratique. Par exemple, on attendra des étudiants qu'ils puissent comprendre et expliquer une preuve de complexité qui n'a pas été vue au cours, mais on ne demandera pas aux étudiants de trouver une preuve qui n'aurait pas été étudiée.

Connaissances et compétences pré-requises ou co-requises

-Notions de mathématiques discrètes et notions de logique
-Compréhension intuitive de la notion d'algorithme et de la notion de codage

Cours ex cathedra complétés par des exercices faits en classe et quelques devoirs

Références, bibliographie et lectures recommandées

M. Sipser, Introduction to the theory of computation, PWS Publisher, 053494728X
P. Wolper, Introduction à la Calculabilit́e, Dunod, 978-2-10-049981-6

Contacts

Jean-François Raskin

Campus

Plaine

Méthode(s) d'évaluation

• Autre

Autre

Examen oral avec préparation écrite portant sur la théorie et les exercices.

Langue(s) d'évaluation

• français
• anglais