Calculabilité et complexité
- Code de l'UE INFOM113
-
Horaire
30Quadri 2
- Crédits ECTS 5
- Langue
- Professeur
Ce cours vise à donner une introduction aux théories de calculabilité et de complexité dans l'informatique.
Ce cours vise à donner une introduction aux théories de calculabilité et de complexité dans l'informatique.
Dans une première partie on parle des notions de base comme le concept d'algorithme, les ensembles dénombrables, les fonctions calculables, les ensembles (semi-)décidables et les problèmes insolubles. Dans une deuxième partie, on étudie quelques modèles de calcul comme les langages de programmation, le lambda-caclcul, les fonctions récursives, et les machines de Turing, et on introduit quelques résultats-clés de la calculabilité: le problème d'arrêt, le théorème de Rice, la relation entre interprétation et compilation et les projections de Futamura. Dans une troisième partie, on introduit la théorie de la complexité et on parle des classes de complexité P, NP, et coNP, et on parle des problèmes NP-complets et leur pertinence.
Cours ex-cathédra.
Examen écrit. L'examen comporte des questions de compréhension et de reproduction.
Formation | Programme d’études | Bloc | Crédits | Obligatoire |
---|---|---|---|---|
Master 120 en sciences informatiques, à finalité spécialisée en data science | Standard | 0 | 5 | |
Master 60 en sciences informatiques | Standard | 0 | 5 | |
Master 120 en sciences informatiques, à finalité spécialisée en software engineering | Standard | 0 | 5 | |
Master 60 en sciences informatiques | Standard | 1 | 5 | |
Master 120 en sciences informatiques, à finalité spécialisée en software engineering | Standard | 1 | 5 | |
Master 120 en sciences informatiques, à finalité spécialisée en data science | Standard | 1 | 5 |