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.
• Vous trouverez ici un excellent livre sur la complexité, qui aborde la décidabilité dans son premier chapitre.

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é, de décidabilité, et de calculabilité.
		On s’intéresse dans ce cours à la notion d’ensemble dénombrable, et on y construit une machine universelle. Deux problèmes indécidables sont présentés, ce qui nous permet d’établir la différence entre la classe des langages reconnaissables et celle des lanages décidables.
		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.
				Exercices sur les ensembles indénombrables.
				Exercices sur les réductions et les problèmes indécidables.

Examens passés

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