Agrégation Informatique: Première Année Préparation

Formaliser une proposition en logique propositionnelle et construire sa table de vérité.

Démontrer la validité d'un raisonnement en utilisant les règles d'inférence (modus ponens, modus tollens).

Écrire des formules en logique des prédicats du premier ordre avec quantificateurs.

Définir formellement un ensemble et démontrer des propriétés ensemblistes par manipulation formelle.

Effectuer une preuve par l'absurde et par contraposée.

Effectuer une preuve par récurrence simple sur les entiers naturels.

Appliquer le raisonnement par récurrence pour prouver la correction d'algorithmes simples.

Appliquer les principes de dénombrement (addition, multiplication) pour résoudre des problèmes combinatoires.

Calculer des arrangements et des combinaisons pour résoudre des problèmes de dénombrement.

Appliquer la formule du binôme de Newton pour développer des expressions et prouver des identités.

Résoudre une relation de récurrence linéaire à coefficients constants (cas homogène et non homogène).

Définir un espace probabiliste discret et calculer des probabilités d'événements simples.

Appliquer les probabilités conditionnelles et le théorème de Bayes à des problèmes concrets.

Calculer l'espérance et la variance d'une variable aléatoire discrète.

Écrire une fonction récursive simple (ex: factorielle, Fibonacci) et tracer son arbre d'appels.

Définir et distinguer les notations asymptotiques O, Ω et Θ avec des exemples formels.

Calculer la complexité temporelle dans le pire des cas et la complexité spatiale d'un algorithme itératif.

Résoudre une récurrence simple par la méthode de substitution (ex: T(n) = T(n-1) + c).

Appliquer le théorème maître pour résoudre des récurrences de type diviser pour régner.

Comparer la complexité de deux algorithmes et justifier formellement lequel est plus efficace.

Transformer une fonction récursive terminale en une version itérative équivalente.

Expliquer pourquoi la transformation d'une récursion non terminale requiert une pile explicite.

Implémenter une liste chaînée simple avec les opérations d'insertion, suppression et recherche.

Expliquer le principe d'une table de hachage, le rôle de la fonction de hachage et la résolution des collisions par chaînage.

Implémenter les opérations d'une table de hachage avec chaînage.

Définir la complexité amortie et l'appliquer à l'analyse des opérations sur un tableau dynamique.

Implémenter le tri par insertion et analyser sa complexité dans le meilleur et le pire des cas.

Implémenter l'algorithme du tri fusion (merge sort) et prouver sa complexité en O(n log n).

Implémenter l'algorithme du tri rapide (quicksort) en portant une attention particulière à la fonction de partition.

Analyser la complexité du tri rapide dans le meilleur cas, le cas moyen (intuitivement) et le pire cas.

Décrire la propriété d'un tas binaire (heap) et son implémentation à l'aide d'un tableau.

Implémenter les opérations d'un tas binaire et les utiliser pour réaliser le tri par tas (heapsort).

Expliquer et implémenter le tri par comptage (counting sort) et le tri par base (radix sort), en analysant leurs conditions d'application.

Démontrer la borne inférieure Ω(n log n) pour les tris par comparaison en utilisant le modèle de l'arbre de décision.

Définir formellement un arbre binaire et ses propriétés (hauteur, profondeur, taille).

Implémenter un arbre binaire de recherche (ABR) avec les opérations d'insertion et de recherche.

Analyser la complexité des opérations sur un ABR dans le meilleur et le pire des cas.

Implémenter l'opération de suppression dans un ABR en gérant les trois cas (0, 1 ou 2 enfants).

Expliquer la problématique du déséquilibre d'un ABR et le principe des arbres auto-équilibrants.

Décrire le principe d'un arbre AVL, le facteur d'équilibre et effectuer les rotations simples et doubles sur des exemples.

Définir un graphe (orienté/non orienté, pondéré/non pondéré) et ses représentations (matrice/liste d'adjacence).

Implémenter le parcours en largeur (BFS) et l'utiliser pour calculer les plus courts chemins en nombre d'arêtes.

Implémenter le parcours en profondeur (DFS) de manière récursive et itérative.

Appliquer les algorithmes de parcours pour déterminer les composantes connexes d'un graphe non orienté.

Appliquer les algorithmes de parcours pour déterminer les composantes fortement connexes d'un graphe orienté.

Implémenter l'algorithme de Dijkstra en utilisant une file de priorité pour les plus courts chemins à poids positifs.

Prouver la correction de l'algorithme de Dijkstra par récurrence sur l'ensemble des sommets finalisés.

Comparer les cas d'usage et les complexités de Dijkstra et Bellman-Ford.

Implémenter l'algorithme de Prim pour trouver un arbre couvrant de poids minimum.

Implémenter la structure Union-Find avec compression de chemins et union par rang.

Implémenter l'algorithme de Kruskal en utilisant la structure Union-Find.

Identifier la sous-structure optimale et le chevauchement des sous-problèmes dans un problème donné.

Comparer les approches descendante (mémoïsation) et ascendante (tabulation) sur un exemple simple.

Formuler la relation de récurrence pour la longueur de la plus longue sous-séquence commune (LCS).

Implémenter une solution par programmation dynamique (tabulation) pour le problème LCS.

Formuler la relation de récurrence pour le problème du sac à dos (0/1).

Implémenter une solution par programmation dynamique pour le sac à dos (0/1) et analyser sa complexité.

Rédiger une preuve de correction d'un algorithme de programmation dynamique par récurrence sur les sous-problèmes.

Définir formellement un automate fini déterministe (AFD) et simuler son exécution.

Construire un AFD pour un langage régulier simple.

Définir formellement un automate fini non déterministe (AFN) et le différencier d'un AFD.

Convertir un AFN en AFD par la construction des sous-ensembles.

Convertir une expression régulière en un AFN en utilisant l'algorithme de Thompson.

Convertir un AFD en une expression régulière en utilisant l'algorithme de Kleene.

Énoncer le lemme de pompage pour les langages réguliers et l'utiliser pour prouver qu'un langage n'est pas régulier.

Définir une grammaire hors-contexte (CFG) et un automate à pile (AP).

Construire un automate à pile pour un langage hors-contexte simple (ex: {aⁿbⁿ | n ≥ 0}).

Définir formellement une machine de Turing (MT) et simuler son exécution.

Construire une machine de Turing pour un langage non hors-contexte (ex: {aⁿbⁿcⁿ | n ≥ 0}).

Énoncer la thèse de Church-Turing et définir les notions de langage récursif et récursivement énumérable.

Définir formellement le problème de l'arrêt (HALT) et démontrer son indécidabilité par diagonalisation.

Définir les classes de complexité P et NP et la notion de NP-complétude.

Expliquer le concept de réduction polynomiale et son usage pour prouver la NP-complétude d'un problème (ex: SAT vers 3-SAT).

Écrire des fonctions simples en OCaml avec typage statique, pattern matching et récursivité.

Utiliser les types algébriques (variants, records) pour modéliser des structures de données.

Implémenter des fonctions d'ordre supérieur (map, filter, fold) et expliquer leur utilité.

Définir un type algébrique pour un arbre binaire et y implémenter les opérations de recherche et d'insertion.

Implémenter le tri fusion en OCaml de manière purement fonctionnelle.

Implémenter l'algorithme de parcours en largeur (BFS) en OCaml en utilisant une file fonctionnelle.

Expliquer les concepts d'immutabilité et de transparence référentielle et leurs avantages.