Algorithmique et calculabilité

Durée

30h Th, 20h Pr

Nombre de crédits

Enseignant

Emilie Charlier

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

Langue française

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

Dans ce cours, on développe des pistes liées à la question fondamentale suivante : tout problème (en admettant, au préalable, qu'il puisse être codé par un ordinateur) peut-il être résolu par un programme informatique ?
Pour formaliser cette question, les notions d'algorithme et de fonction calculable sont définies de façon rigoureuse au moyen des machines de Turing. On abordera principalement les thèmes suivants : fonctions primitives récursives, fonctions récursives, fonctions calculables, machines de Turing, machines universelles, thèse de Church-Turing, problèmes décidables, le problème de l'arrêt, réduction, langages décidables et acceptables, le théorème de Cook, la théorie de la complexité, problèmes NP-complets,...
Le cours se termine par la présentation de quelques problèmes NP-complets bien connus dans d'autres branches des mathématiques (optimisation, théorie des graphes, ...) comme par exemple, le problème du voyageur de commerce.

Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement

Au terme de ce cours, l'étudiant maîtrisera les notions fondamentales issues de la théorie de la calculabilité et de la complexité ainsi que les preuves sous-jacentes. L'étudiant aura, en particulier, intégré les concepts de fonction calculable et de problème de décision. Il/elle sera capable d'expliquer, au moyen de réductions ad hoc, que certains problèmes ne présentent pas de solution algorithmique. Il/elle sera à même de construire des machines de Turing simples et de prouver la NP-complétude de problèmes classiques.

Savoirs et compétences prérequis

Aucune connaissance informatique n'est nécessaire.

Activités d'apprentissage prévues et méthodes d'enseignement

Cours théorique avec "tableau et craies" en interaction avec les étudiants. Dans les séances d'exercices, les étudiants sont face à des exercices qu'ils doivent résoudre.

Mode d'enseignement (présentiel, à distance, hybride)

Cours donné exclusivement en présentiel


Explications complémentaires:

Le cours théorique est consacré principalement aux aspects théoriques des machines de Turing et de la complexité. Les séances de répétition permettent de présenter la résolution d'exercices mais surtout l'illustration et la concrétisation des concepts vus au cours.
Si le nombre d'étudiants est supérieur ou égal à 5, le cours se donnera avec tableau et craie, en interaction avec les étudiants. Sinon, les modalités d'organisation seront discutées au premier cours.

Lectures recommandées ou obligatoires et notes de cours

Les notes de cours sont disponibles en pdf sur eCampus.

Le cours oral délimitera la matière exacte.

Quelques sources d'information possibles :

• R. Cori, D. Lascar, Logique Mathématique, Dunod, 1993.
• M. R. Garey, D. S. Johnson, Computers and Intractability, A guide to the Theory of
  NP-Completeness, W. H. Freeman and Company, 1979.
• P. Lecomte, Algorithmique et calculabilité, notes de cours 1994-1995.
• H. R. Lewis, C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
• M. Rigo, Algorithmique et calculabilité, notes de cours 2009-2010.
• A. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Society. Second Series 42, 230-265, 1936.
• P. Wolper, Introduction à la calculabilité, Dunod, 2006.

Modalités d'évaluation et critères

Examen(s) en session

Toutes sessions confondues

- En présentiel

évaluation orale


Explications complémentaires:

Examen oral en session. L'examen porte sur la théorie et ses applications directes illustrées lors des séances d'exercices. On pourra par exemple demander de résoudre de petits exercices au tableau ou sur feuille.

Stage(s)

Remarques organisationnelles et modifications principales apportées au cours

Ce cours de master est organisé un an sur deux : 2021-2022, 2023-2024...

Des compléments d'information sont disponibles sur eCampus.

Contacts

Émilie Charlier

Département de Mathématique (B37)
Quartier Polytech 1
Allée de la Découverte,12
B-4000 Liège

Tél. : +32 4 366.93.84
E-mail : echarlier@uliege.be

 


 

Association d'un ou plusieurs MOOCs