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)