Calculabilité et complexité
Cursus master ingénierie (CMI) - UFR de mathématique et d'informatiqueParcours Cursus master ingénierie (CMI) - Informatique, systèmes et réseaux
Description
On décrit les modèles les plus généraux de calcul et de décision en informatique (qui sont équivalents) : machine de Turing, grammaire, fonction mu-récursive (avec cas particulier des fonctions récursives primitives). On précise la signification du non-déterminisme dans le calcul et la décision. Ensuite on donne les limites de ces modèles en montrant l'impossibilité de décider généralement certaines questions, comme l'arrêt d'une machine de Turing. Enfin on donne les classes fondamentales de complexité des algorithmes, P, NP et EXP, en particulier les problèmes NP-complets.
Compétences requises
Pré-requis
Algorithmique et Programmation impérative de base (L1, L2) ; Théorie des Langages (L3 S6).
- Savoir faire preuve d'esprit critique face à des « solutions » trop générales
- Comprendre l'équivalence des divers langages informatiques avec la machine de Turing.
- Connaître les limites de l'informatique.
- Maîtriser le non-déterminisme.
- Être capable de classer des problèmes informatiques en : faisables en pratique ; possibles en principe mais infaisables en pratique ; impossibles en principe.
Disciplines
- Informatique
MCC
Les épreuves indiquées respectent et appliquent le règlement de votre formation, disponible dans l'onglet Documents de la description de la formation.
- Régime d'évaluation
- ECI (Évaluation continue intégrale)
Évaluation initiale / Session principale - Épreuves
Libellé | Type d'évaluation | Nature de l'épreuve | Durée (en minutes) | Coéfficient de l'épreuve | Note éliminatoire de l'épreuve | Note reportée en session 2 |
---|---|---|---|---|---|---|
Note 1 : Epreuve écrite | SC | ET | 40 | 1 | ||
Note 2 : Epreuve écrite | SC | ET | 40 | 1 | ||
Note 3 : Epreuve écrite | SC | ET | 40 | 1 |