L’objectif de cette UE est de donner aux étudiants les connaissances de base en calculabilité-décidabilité  et formaliser la calculabilité en s’appuyant sur le modèle de Machine de Turing. De plus, le but de cette UE est d’initier les étudiants aux :

- Méthodes formelles de raisonnement permettant de construire les preuves de terminaison et de correction partielle d’un algorithme,

 - Aux techniques pour estimer la complexité d’un algorithme.

Les thématiques abordées sont :

• Calculabilité et limitation des algorithmes,
• Modèle de machine de Turing,
• Programmation de la machine de Turing,
• Correction totale des algorithmes,
• Complexité et classes de complexité.

À la fin de cette UE, vous serez capable de :

• Analyser la calculabilité d’un problème : décidabilité, semi-décidabilité et indécidabilité,

• Formaliser la notion de calculabilité au sens de Turing: modèle de Machine de Turing,

• Programmer la Machine de Turing,

• Apporter la preuve de correction totale d'un algorithme : preuve de terminaison et de correction partielle,

• Estimer la complexité d’un algorithme correct et déterminer la classe de complexité d’un problème.

Algorithmique I

1ère session : 100% Contrôle Continu écrit

L’évaluation se fait sur la base de deux contrôles continus écrits de 1h30 maximum.

2ème session : 100% examen terminal écrit.