ECTS
4 crédits
Composante
Collège Sciences et Technologies pour l’Energie et l’Environnement (STEE)
Volume horaire
39h
Description
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é.
Objectifs
À 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.
Heures d'enseignement
- Informatique fondamentale - CMCours Magistral19,5h
- TDTravaux Dirigés10,5h
- TPTravaux Pratique9h
Pré-requis obligatoires
Algorithmique I
Contrôle des connaissances
100% Contrôle Continu Intégral.
L’évaluation se fait sur la base de deux contrôles continus écrits de 1h30 maximum.
Compétences acquises
Compétences | Niveau d'acquisition | |
---|---|---|
Mise en œuvre de méthodes et d'outils du champ disciplinaire | Analyser et interpréter les résultats produits par l'exécution d'un programme: terminaison, test , complexité | 1 - Notion |
Expliquer et documenter la mise en œuvre d'une solution Informatique. | 3 - Maitrise | |
Caractériser le rôle des tests et des preuves de correction dans le développement des logiciels et mettre en œuvre des tests élémentaires et des invariants de boucle | 3 - Maitrise | |
Appliquer des approches raisonnées de résolution de problèmes complexes : modèle formel d'un problème, réduction et complétude de problèmes | 3 - Maitrise | |
Identification d'un questionnement au sein d'un champ disciplinaire | Choisir, sur des critères objectifs, les structures de données et construire les algorithmes les mieux adaptés à un problème donné. | 3 - Maitrise |