Intégrer La Prépa des INP
Intégrer une école
S'inscrire
Livret d'accueil
Composante
ENSEIRB-MATMECA
Code interne
EI8IF228
Description
Ce module présente les notions principales de calculabilité et de complexité.
Plan
Notions de calculabilité
Définition formelle : mots, language, problème
Machine de Turing, MT Universelle
Existence de fonctions non calculables
Exemples de problèmes indécidables
Principe de réduction
Classes de complexité
Exemples de problèmes NP-complet
Pré-requis obligatoires
Algorithmique, Automate et notion de complexité.
Syllabus
Notions de calculabilité
Définition formelle : mots, language, problème
Machine de Turing, MT Universelle
Existence de fonctions non calculables
Exemples de problèmes indécidables
Principe de réduction
Classes de complexité
Exemples de problèmes NP-complet
Modalités de contrôle des connaissances
Évaluation initiale / Session principale - Épreuves
| Type d'évaluation | Nature de l'épreuve | Durée (en minutes) | Nombre d'épreuves | Coefficient de l'épreuve | Note éliminatoire de l'épreuve | Remarques |
|---|---|---|---|---|---|---|
| Contrôle Continu Intégral | Contrôle Continu | 1 |