Calculabilité et complexité

Ce cours traite de la théorie de la décidabilité, de celle de la complexité. On s’y intéresse en particulier à la notion de difficulté des problèmes.

Un simulateur de machines de Turing est disponible ici.

Supports de cours

		Dans ce cours, on introduit les problématiques de la matière. On y parle ensuite d’automates à états finis, et de techniques pour prouver la non-rationnalité d’un langage.
		On introduit la notion de machine de Turing, et on en étudie plusieurs variantes.
		On étudie ici l’expressivité des machines de Turing. On verra pour cela les notions de reconnaissabilité, et de calculabilité.
		On s’intéresse dans ce cours à la notion de décidabilité, et on y construit une machine universelle.
		On voit dans ce cours le problème de l’arrêt, premier problème indécidable. On parle ensuite de réduction, ce qui nous permet d’établir l’indécidabilité d’autres problèmes. On finit par le théorème de Rice, qui montre par réduction l’indécidabilité d’une large classe de problèmes.

Exercices

			Problèmes, codages, et modèles de calcul.
			Langages réguliers et lemme de l’étoile.
			Exercices autour des machines de Turing.

Examens passés

			Contrôle continu 2022-2023.
			Devoir maison 2022-2023.
			Examen final, première session, 2022-2023