L'année 2018-2019 j'ai préparé l'agrégation de mathématiques option
informatique. Je tiens à remercier l'ensemble des élèves de ma promo et
l'ensemble des enseignants de cette préparation à l'agrégation pour l'aide
et les idées qu'ils m'ont apportés pendant cette année. Je remercie plus
particulièrement Pierre
Le Barbenchon et Émilie
Tézenas pour leur aide en mathématiques et nos séances de travail.
Voici quelques documents de travail que j'ai rédigé pendant ma
préparation. Je ne garantie pas la correction de ces documents : ils
comportent probablement des fautes d'orthographes, des coquilles, des
typos, des phrases ambigue voir même des erreurs. J'essaierais dans la
mesure du possible de corriger les erreurs qui me seront signalées.
Ces documents sont librement inspirés du travail des nos prédécesseurs.
Je me suis essentiellement basée sur les sites suivants: la minerve,
le couteau suisse de l'agrégation,
le travail d'Aude
Le Gluher, le travail de Joshua
Peigner ainsi que quelques références supplémentaires.
Voici ma liste de couplages pour les leçons de mathématiques et
d'informatique (pdf).
Leçons de mathématiques
Vous trouver ici les métaplans
des leçons ainsi que la liste de nos développements.
Développements
L'algorithme de Berlekamp permet de factoriser des polynômes à
coeffiscients dans un corps fini: preuve de sa terminaison et de sa
correction (pdf).
La caractérisation de la fonction Gamma sur R (pdf).
Le théorème de Cauchy-Lipchitz permet de prouver l'existance
et l'unicité de solution pour un problème de Cauchy: la preuve est
effectuer dans le cas global à l'aide du théorème de point fixe (pdf).
Le cardinal du cône nilpotent sur les corps finis: la preuve
utilise un résultat d'algèbre linéaire (pdf).
Le dénombrement des zéros d'une solution d'équation différentielle
vérifiant certaines propriétés: on donne alors un équivalent à ce nombre
de zéros (pdf).
La décomposition de Dunford permet d'écrire un endomorphisme
sous une forme plus facile à manipuler: la décomposition de Dunford peut
se calculer via la méthode de Newton (pdf).
Étude du groupe O(p,q) et plus particulièrement d'un de ces
isomorphismes: on utilise l'exponentielle de matrices pour établir cet
isomorphisme (pdf).
Le théorème des extremums liés: et son application à la
minimisation de fonction via l'inégalité d'Hadamard: la preuve du
théorème s'effectue via les sous-variétés, selon la leçon on va plus ou
moins vite (pdf).
Le processus de Galtson-Watson étudie la transmission du nom
de famille dans une population: j'ai coupé au montage ce développement (pdf).
Étude des générateurs de SL2(Z) via une action sur
le demi-plan de Poincaré: attention ce développement est très long (pdf).
L'algorithme du gradient à pas optimal permet de minimiser une
fonction à plusieurs variable en utilisant une descente de gradiant:
étude de la performance (pdf).
Étude des générateurs du groupe circulaire: ce développement a
été également coupé au montage (pdf).
Calcul de l'intégrale de Fresnel: un moyen de calculer une
intégrale non triviale (pdf).
Étude des isométries du cube et application au coloriage via
l'action du groupe des permutations sur les isométries (pdf).
La méthode de Kacmarz permet de résoudre des systèmes
linéaires via une suite de projection orthogonale (pdf).
Le dénombrement des matrices diagonales sur les corps finis:
ce développement a été coupé au montage (pdf).
La méthode de Newton permet de calculer les zéros d'une
fonction: évaluation de ses performances (pdf).
La série génératrice des nombres de Bell permet de compter le
nombre de partitions d'un ensemble de n éléments (pdf).
La série génératrice des nombres de Bernoulli: cette série se
calcule via une série de Fourier (pdf).
La loi de la réciprocité quadratique permet de calculer la
valeur du symbole de Legendre pour deux éléments d'un corps fini (pdf).
La formule sommatoire de Poisson et ses applications à la
focntion spéciale Théta de Jacobi et au théorème de Shannon: plusieures
applications de la transformée de Fourier (pdf).
Étude des sommes de deux carrés à l'aide des entiers de Gauss:
ce développement a été coupé au montage (pdf)
Étude de l'équation de Sophie Germain qui est un cas
particulier de l'équation de Fermat avec des nombres premiers
particuliers: ce développement est long et pas facile à mémoriser (pdf).
Convergence d'une suite de polygones vers le barycentre du
polynôme initial (pdf).
Étude de l'image de la fonction exponentielle sur les matrices
à l'aide de la structure des images de la fonction exponetielle (pdf).
Le théorème central limite important en probabilité (pdf).
Le théorème de Weierstrass via les polynomes de Bernstein: la
version probabilisé (pdf).
Le théorème de Weierstrass via la convolution: la version
historique utilisant les approximations de l'unité (pdf).
Leçons d'informatique
Vous trouverez ici les métaplans
des leçons, le plan détaillé des leçons, mon mémoire
sur la leçon 913 (Machine de Turing) ainsi que la liste de nos
développements.
Plans plus ou moins détaillés
Leçon 901: Structures de données. Exemples et applications. (pdf)
Leçon 903: Exemples d'algorithmes de tri. Correction et complexité. (pdf)
Leçon 907: Algorithmique du texte. Exemples applications. (pdf)
Leçon 909: Langages rationnels et automates finis. Exemples et
applications. (pdf)
Leçon 912: Fonctions récursives primitives et non primitives.
Exemples. (pdf)
Leçon 913: Machines de Turing. Applications. (pdf)
Leçon 914: Décidabilité et indécidabilité. Ecxemples. (pdf)
Leçon 916: Formules du calcul propositionnel : représentation, formes
normales, satisfiabilité. Applications. (pdf)
Leçon 918: Systèmes formels de preuve en la logique du premier ordre.
Exemples. (pdf)
Leçon 921: Algorithmes de recherche et structures de données
associées. (pdf)
Leçon 923: Analyses lexicale et syntaxique. Applications. (pdf)
Leçon 925: Graphes: représentations et algorithmes. (pdf)
Leçon 926: Analyse des algorithmes: complexité. Exemples. (pdf)
Leçon 927: Exemples de preuve d'algorithme: correction et terminaison.
(pdf)
Leçon 928: Problèmes NP-Complet: exemples et réductions. (pdf)
Leçon 929: Lambda-calcul pur comme modèle de calcul. Exemples. (pdf)
Leçon 930: Sémantique des langages de programmation. Exemples. (pdf)
Leçon 931: Schémas algorithmiques. Exemples et applications. (pdf)
Développements
Le problème 2SAT est NL-complet et donc dans P: on étudie un
problème d'accessibilité dans un grape (pdf).
Calcul d'alignement optimaux permettant de savoir à quel point
deux motifs sont identiques: calcul de distances d'édition (pdf).
L'approximabilité ou non du problème TSP: preuve de la
2-approximabilité du problème TSPE et de la non-approximabilité du
problème TSP dans le cas où P est différent de NP (pdf).
Étude de l'automate des occurences: l'automate minimal qui
reconnaît un motif m (pdf).
Recherche et insertion dans un B-arbre et son efficacité dans
le cadre des bases de données relationnelles (pdf).
La caractérisation de l'ensemble premier dans le cadre
d'analyse syntaxique LL(1) (pdf).
Une caractérisation de l'ensemble RE à l'aide de fonction
mu-récursive: ce développement utilise des éléments de la preuve de
l'équivalence entre les machines de Turing et les foncitons
mu-récursives sans rien redémontrer (pdf).
La complétude du système de preuve de la déduction naturelle:
la preuve nous permet de manipuler les notions d'induction sur un arbre
de preuve et les modèles de Herbrand (pdf).
La complétude de la logique de Hoare partielle: on ne vérifie
pas la terminaison du programme à l'aide de cette logique (pdf).
L'algorithme de Dijkstra permet de calculer le plus court
chemin à partir d'une origine unique lorsque les poids sont strictement
positifs grâce à i,e file de priorité: preuve de sa correction, sa
terminaison et sa complexité (pdf).
Équivalence des sémantiques à petits et grands pas pour le
langage IMP: cette preuve nous fait manipuler deux types d'inductions:
l'induction structurelle et l'induction sur un arbre de preuve (pdf).
Le langage engendré par la grammaire Gpost est LL(1):
cette preuve consiste à montrer qu'une grammaire est LL(1) puis qu'un
langage est bien engendré par une grammaire donnée (pdf).
Preuve de la correction partielle de la factorielle via la logique
de Hoare: ce développement a été coupé au montage (pdf).
Une machine de Turing est une fonction mu-récursive: on ne
fait qu'un sens de la preuve qui consiste à définir une fonction
mu-récursive pour chacun des comportements d'une machine de Turing (pdf).
Le fonctionnement de Prolog pour les règles de Hoare dans le
cas propositionnel et du premier ordre: preuve de la correction de la
résolution dans ce cas particulier (pdf).
Une fonction récursive est lambda-définissable: on fait
également qu'un sens de la preuve, le plus facile, qui consiste à
définir des combinateurs et des lambda-termes (pdf).
Le théorème de Savitch exprimant l'équivalence entre le
déterministe et le non-déterministe dans le cas de la complexité en
espace: un corollaire important de ce théorème est l'égalité des classes
PSPACE et NPSPACE (pdf).
Le problème de séparabilité par un automate est NP-complet:
c'est l'occasion de faire une réduction polynomiale proprement (pdf).
Le théorème de Scott et son application au théorème de Rice
dans le cadre du lambda-calcul (pdf).
Le tri par tas est un tri par comparaison optimal basé sur la
structure de données du tas: érude de sa correction, sa terminaison et
sa complexité (pdf).
Le tri topologique n'est pas un tri par comparison car il est
basé sur l'ordre induit par un graphe: étude de sa correction, sa
terminaison et sa complexité (pdf).
La transformation de Tseintin permet de convertir une formule
de la logique propositionnelle en sa forme normale conjonctive en temps
linéaire: cette transformation donne une formule équisatisfiable (pdf).
La structure de données Union-Find permet de manipuler une
partion d'un ensemble de données: étude de cette structure de données et
deux de ces types concrets (pdf)
ou étude de la complexité amortie d'un des types concrets (pdf).
Le problème de validité en logique du premier ordre est
indécidable: cette preuve manipule et effectue une réduction (pdf).
