Cette page présentera ce que j'ai choisi de partager de mon année de préparation à l'agrégation de mathématiques option D (informatique) à l'université de Rennes 1 en 2020-2021. Elle sera mise à jour au fur et à mesure.

Cours

• Cours de Lambda-calcul (4h), proposé par Alan Schmitt (Licence WTFPL)

Leçons

Les plans suivants ont été réalisés par Antoine Dequay, Julien Duron, Fabrice Étienne et moi. Ils sont tous sous licence WTFPL.

• 903 : Exemples d'algorithmes de tri. Complexité (PDF, source)
• 931 : Schémas algorithmiques. Exemples et applications.
• 921 : Algorithmes de recherche et structures de données associées.
• 909 : Langages rationnels. Exemples et applications.
• 925 : Graphes : représentations et algorithmes.
• 914 : Décidabilité et indécidabilité. Exemples.
• 926 : Analyse des algorithmes : complexité. Exemples.
• 913 : Machines de Turing. Applications.
• 916 : Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.
• 901 : Structures de données: exemples et applications.
• 907 : Algorithmique du texte: exemples et applications.
• 928 : Problèmes NP-complets : exemples de réductions
• 912 : Fonctions récursives primitives et non primitives. Exemples.
• 927 : Exemples de preuve d'algorithme : correction, terminaison.
• 930 : Sémantique des langages de programmation. Exemples
• 915 : Classes de complexité : exemples.
• 923 : Analyses lexicale et syntaxique : applications.
• 918 : Systèmes formels de preuve en logique du premier ordre : exemples.
• 924 : Théories et modèles en logique du premier ordre. Exemples.
• 932 : Fondements des bases de données relationnelles.
• 929 : Lambda-calcul pur comme modèle de calcul. Exemples

Développements

Les développements suivants ont été réalisés par Antoine Dequay, Julien Duron, Fabrice Étienne et moi. Ils sont tous sous licence WTFPL.

• Tout tri par comparaison s'effectue en Ω(n log n) (PDF, source)
• L'arithmétique de Presburger est décidable (PDF)
• Le problème de séparation par automate est NP-complet (PDF)