Préparation à l'Agrégation Externe de Mathématiques -- Option Informatique


Mise-à-jour : 6 avril 2019



La préparation à l'option D est mise en place en partenariat avec l'Université Denis Diderot (Paris 7), à partir de la rentrée 2017.
Il y eu 100% de réussite à la session 2018 (dont le major du concours "docteurs")! 100% des admissibles à la session 2019 ont été admis.


Équipe enseignante

Béatrice Bérard, Olivier Carton, Romain Demangeon, Arnaud Durand, Mathieu Jaume, Matthieu Journault (resp.), Francois Laroussinie, Michel Pocchiola, Arnaud Sangnier, Tali Sznajder, Christine Tasson

Emploi du temps


Option D : informatique

Les cours, proposés conjointement par Paris 6 et Paris 7, préparent aux épreuves orales d'admission. 2d. Épreuve de leçon d'informatique fondamentale (durée de la préparation : trois heures ; durée de l'épreuve : 50 minutes ; coefficient 4).
Pour chacune de ces deux épreuves : - deux sujets au choix sont proposés par le jury au candidat ; - pour la préparation, le candidat dispose de documents fournis par le jury et peut utiliser ses propres ouvrages s'ils sont autorisés ; - à l'issue de la préparation, le candidat présente au jury un plan détaillé du sujet qu'il a choisi. Ce plan est présenté pendant quinze minutes au maximum. Il est suivi du développement d'une question qui lui est liée. L'épreuve se termine par un entretien avec le jury au cours duquel celui-ci peut éventuellement proposer un ou plusieurs exercices.
La liste des leçons d'Informatique est publiée régulièrement. Pour l'année 2017 : Leçons Informatique.


3d. Épreuve de modélisation (durée de la préparation : quatre heures ; durée de l'épreuve : une heure quinze ; coefficient 4).
Deux textes décrivant une classe de systèmes informatiques sont proposés au candidat. Pour la préparation, le candidat dispose de documents fournis par le jury et peut utiliser ses propres ouvrages s'ils sont autorisés. Il dispose également d'un ordinateur muni des logiciels indiqués au programme. Le candidat présente un exposé construit à partir du texte choisi. Il peut en faire la synthèse, expliciter les relations entre les systèmes et les modèles informatiques présentés, justifier leur pertinence et leur efficacité. Cette présentation peut faire l'usage de l'ordinateur. Le jury intervient à son gré au cours de l'épreuve et conduit le dialogue avec le candidat. Des exemples de textes se trouvent ici (voir option D, bas de la page).

Programme de l'option D

Le programme des épreuves d'admissibilité et d'admission du concours externe de l'agrégation de mathématiques fait l'objet d'une publication sur le site internet du ministère chargé de l'éducation nationale.

Programme des épreuves d'informatique

Les épreuves d'admissibilité (2d. et 3d.) portent sur le programme suivant.

14 Algorithmique fondamentale

Cette partie insiste sur les notions de preuve et de complexité des algorithmes. Elle est relativement indépendante de tout langage de programmation, mais le candidat doit être capable de mettre en oeuvre sur machine les structures de données et les algorithmes étudiés.
(a) Structures de données. Types abstraits : définition des tableaux, listes, piles, files, arbres, graphes (orientés et non orientés), ensembles, dictionnaires, file de priorité. Interface abstraite et implantation concrète.
(b) Schémas algorithmiques classiques : approche gloutonne, diviser pour régner, programmation dynamique. Exemples : algorithme de Dijkstra, tri fusion, plus longue sous-séquence commune.
(c) Complexité. Analyse des algorithmes : relations de comparaison O, et . Analyse dans le pire cas. Exemple d'analyse en moyenne : recherche d'un élément dans un tableau.
(d) Algorithmes de tri et de recherche. Méthodes de tri par comparaison (tri fusion, tri par tas, tri rapide), arbre de décision et borne inférieure du tri par comparaisons. Méthodes de recherche séquentielle et dichotomique. Arbres binaires de recherche. Arbres équilibrés : définition, relation entre la taille et la hauteur, maintien de l'équilibre.
(e) Algorithmes de graphes. Parcours de graphes : algorithmes de parcours en largeur, en profondeur, algorithme de Dijkstra. Arbres couvrants : algorithmes de Prim et de Kruskal. Fermeture transitive.

15 Calculabilité, décidabilité et complexité

(a) Définition des fonctions primitives récursives ; schémas primitifs (minimisation bornée). Définition des fonctions récursives ; fonction d'Ackermann.
(b) Définitions des machines de Turing. Équivalence avec les fonctions récursives.
(c) Universalité. Décidabilité, Indécidabilité. Théorème de l'arrêt. Théorème de Rice. Réduction de Turing. Définitions et caractérisations des ensembles récursifs, récursivement énumérables.
(d) Lambda-calcul pur comme modèle de calcul : définition, propriétés (confluence), stratégies, expressivité.
(e) Complexité en temps et en espace : classe P. Machines de Turing non déterministes : classe NP. Acceptation par certificat. Réduction polynomiale. NP-complétude. Théorème de Cook.

16 Logique et démonstration

(a) Calcul propositionnel : syntaxe et sémantique. Tables de vérité, tautologies, formes normales, forme clausale. Théorème de complétude du calcul propositionnel.
(b) Logique du premier ordre : aspects syntaxiques. Langages, termes, formules. Variables libres et variables liées, substitutions, capture de variables.
(c) Logique du premier ordre : systèmes formels de preuve. Calcul des séquents, déduction naturelle. Algorithme d'unification des termes. Preuves par résolution.
(d) Logique du premier ordre : aspects sémantiques. Interprétation d'une formule dans un modèle. Validité, satisfiabilité. Théories cohérentes, théories complètes. Théories décidables, indécidables. Exemples de théories : égalité, arithmétique de Peano. Théorème de complétude du calcul des prédicats du premier ordre.
(e) Basses de données : modèle relationnel, algèbre relationelle, calcul relationnel, théorème de Codd, calcul conjonctif.

17 Théorie des langages de programmation

(a) Preuve de programmes : correction, terminaison. Méthodes de base : assertions, préconditions et postconditions, invariants et variants de boucles, logique de Hoare, induction structurelle.
(b) Sémantique des langages de programmation : sémantiques opérationnelle et dénotationelle. Application à un langage impératif restreint.
(c) Automates finis. Langages reconnaissables. Existence de langages non reconnaissables. Déterminisation. Propriétés de clôture des langages reconnaissables. Exemples d'application.
(d) Expressions rationnelles. Langages rationnels. Théorème de Kleene.
(e) Grammaires et Langages algébriques. Existence de langages non algébriques. Propriétés de clôture des langages algébriques.
(f) Chaîne de compilation. Analyse lexicale. Analyse syntaxique (principes de l'analyse descendante et ascendante). Analyse sémantique élémentaire (arbre de syntaxe abstraite, table des symboles, analyse de portée, typage, ...).

Programme spécifique de l'épreuve de modélisation, option D.

Sur les sujets suivants, il est attendu moins une capacité à les restituer de manière structurée qu'une connaissance suffisante pour comprendre la problématique d'un texte, en éclairer le contexte, ou encore argumenter (ou critiquer) les solutions que ce dernier propose. En particulier, aucune expérience de programmation assembleur ou système n'est attendue.
(a) Eléments d'architecture des ordinateurs : principaux composants et leurs interactions ; principes des langages assembleurs ;
(b) Représentation des nombres entiers et flottants ;
(c) Eléments sur les systèmes d'exploitation : systèmes de fichiers, processus, gestion de la mémoire.

Programme des épreuves de mathématiques (option D)

Le programme est celui de l'écrit, commun aux options A, B, C, et D.
La liste des leçons est publiée régulièrement. Pour l'année 2017 : Mathématiques pour l'informatique

Épreuve de leçon de mathématiques (durée de la préparation : trois heures ; durée de l'épreuve : 50 minutes ; coefficient 4).
Deux sujets au choix sont proposés par le jury au candidat. Ce dernier dispose, pour la préparation, de documents fournis par le jury et peut utiliser ses propres ouvrages s'ils sont autorisés. A l'issue de la préparation, le candidat présente au jury un plan détaillé du sujet qu'il a choisi. Il est suivi du développement d'une question qui lui est liée. Au cours de l'entretien qui suit, le jury peut éventuellement proposer un ou plusieurs exercices.

La préparation à cette épreuve n'est pas mutualisée entre Paris 6 et Paris 7.