Portail nationalFormations hybrides

Fondements théoriques de l’informatique

Code UE : USSI5J

  • Cours
  • 6 crédits

Responsable(s)

Agnes PLATEAU ALFANDARI

Stephane ROVEDAKIS

Public, conditions d’accès et prérequis

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

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 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.

Modalité d'évaluation

  • Contrôle continu
  • Examen final

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez

Contact

EPN05 Informatique
2 rue conté 33.1.10A
75003 Paris
Tel :01 40 27 22 58
Swathi RANGANADIN RAJASELVAM

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé