Fondements théoriques de l'informatique
Public Concerné
Etre admis.e à la préparation à l'agrégation d'Informatique.
Objectifs pédagogiques
Préparer les agrégatifs à passer dans les conditions les plus favorables les épreuves écrites et orales du concours de l'agrégation d'informatique.
Contenu de la formation
Logique : syntaxe des formules logiques, sémantique de vérité du calcul propositionnel, déduction naturelle (règles d'inférence, notions d'arbres et de preuves).
Calculabilité, complexité :
Calculabilité, complexité :
- Modèle de calcul. Machines de Turing : définition, principales variantes (ruban biinfini vs infini, machine à plusieurs rubans). La machine de Turing est le modèle de calcul retenu pour l'étude des notions qui suivent.
- Calculabilité : universalité, décidabilité, indécidabilité. Problème de l'arrêt.
- Complexité : complexité en temps et en espace, classe P. Acceptation par certificat, classe NP. Réduction polynomiale. NP-complétude. Théorème de Cook.
Description des modalités de validation
- Contrôle continu
- Examen final
Prévisions d'ouverture
| Groupe | Semestre | Modalité | État d'ouverture | Date du premier cours | Lieux | ||
|---|---|---|---|---|---|---|---|
| USSI5J | Fondements théoriques de l'informatique | 6 | Cours de Jour | - | - | - | - |
Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation
