Fondements théoriques de l’informatique
Mis à jour le
Responsable(s) : Mme Agnes PLATEAU ALFANDARI, M. Stephane ROVEDAKIS
- Cours
Envie d'en savoir plus sur cette formation ?
Afin d’obtenir les tarifs, le calendrier de la formation, en distanciel, en présentiel, le lieu de la formation et un contact, remplissez les critères suivants :
Afficher le centre adapté à mes besoins
Afin d’obtenir les tarifs, le calendrier de la formation et le lieu de la formation, remplissez les critères suivants :
-
Durée : 50 heures
-
Package
-
6 crédits
Présentation
Public, conditions d'accès et prérequis
Prérequis
Etre admis.e à la préparation à l'agrégation d'Informatique.
Objectifs
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.
Compétences et débouchés
Informations pratiques
Contact
-
Département : EPN05 - Informatique
-
Tel : 01 58 80 87 99
-
Email : jean-mathieu.codasse@lecnam.net
-
Adresse : 2 rue Conté - 75003 Paris
Programme
Contenu
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é :
- Modèle de calcul. Machines de Turing : définition, principales variantes (ruban bi-infini 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.