Composante
École Nationale Supérieure d'Électrotechnique d'Électronique d'Informatique d'Hydraulique et des Télécommunications
Objectifs
- Savoir ce qu'est un calcul, un modèle de calcul et les limites de ce que peut faire un ordinateur (résultats d'incalculabilité et d'indécidabilité)
- Comprendre ce que signifie qu'un problème est difficile
- Comparer des problèmes en terme de calculabilité et de complexité
- Comprendre et savoir utiliser des idiomes et patrons de conceptions pour structurer une applications
Description
La matière est composée de deux parties. Une partie théorique présente la notion de calcul au travers de plusieurs modèles de calcul, comme les machines de Turing, les fonctions récursives ou le calcul quantique. Elle en expose les limites par des résultats d'indécidabilité et d'incalculabilité. Cette partie présente par ailleurs la complexité des problèmes tant en temps (P, NP, NP-complétude) qu'en espace (PSPACE). La partie appliquée expose des approches modernes de la programmation : décorateurs/annotations, inversion de contrôle et injection de dépendances, proxy, programmation par aspects.