USSI5J

Fondements théoriques de l’informatique


6 crédits Agnès PLATEAU et Stéphane ROVEDAKIS EPN05 - Informatique Unité spécifique de type cours

Publié Du 01-09-2022 au 31-08-9999

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és de validation

  • Contrôle continu
  • Examen final

Thésaurus du Cnam :

  • Aucune indexation

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
EPN05 Informatique
Nom du contact
Swathi RANGANADIN RAJASELVAM
Numéros de téléphone
01 40 27 22 58
Adresse postale
2 rue conté 33.1.10A
Paris 75003