Programme de l'agrégation

Programmation

Voir les éléments à connaître en C, Ocaml, Python et JavaScript.

Algorithmes

Notions	Commentaires
Notion de programme comme mise en œuvre d’un algorithme. Paradigme impératif structuré, paradigme déclaratif fonctionnel, paradigme logique.	On ne présente pas de théorie générale sur les paradigmes de programmation, on se contente d’observer les paradigmes employés sur des exemples. La notion de saut inconditionnel (instruction GOTO) est hors programme. On mentionne le paradigme logique uniquement à l’occasion de la présentation des bases de données.
Caractère compilé ou interprété d’un langage.	Transformation d’un fichier texte source en un fichier objet puis en un fichier exécutable. Différence entre fichiers d’interface et fichiers d’implémentation.
Représentation des flottants. Problèmes de précision des calculs flottants.	On illustre l’impact de la représentation par des exemples de divergence entre le calcul théorique d’un algorithme et les valeurs calculées par un programme. Les comparaisons entre flottants prennent en compte la précision.
Terminaison. Correction partielle. Correction totale.Variant. Invariant.	La correction est partielle quand le résultat est correct lorsque l’algorithme s’arrête, la correction est totale si elle est partielle et si l’algorithme termine.
Analyse de la complexité d’un algorithme. Complexité dans le pire cas, dans le cas moyen. Notion de coût amorti.	On limite l’étude de la complexité dans le cas moyen et du coût amorti à quelques exemples simples.

Bonnes pratiques

Notions	Commentaires
Spécification des données attendues en entrée, et fournies en sortie/retour.	On entraîne les étudiants à accompagner leurs programmes et leurs fonctions d’une spécification. Les signatures des fonctions sont toujours précisées.
Annotation d’un bloc d’instructions par une précondition, une postcondition, une propriété invariante.	Ces annotations se font à l’aide de commentaires.
Programmation défensive. Assertion. Sortie du programme ou exception levée en cas d’évaluation négative d’une assertion.	L’utilisation d’assertions est encouragée par exemple pour valider des entrées ou pour le contrôle de débordements. Plus généralement,les étudiants sont sensibilisés à réfléchir aux causes possibles (internes ou externes à leur programme) d’opérer sur des données invalides et à adopter un style de programmation défensif. Les étudiants sont sensibilisés à la différence de garanties apportées selon les langages, avec l’exemple d’un typage faible en C et fort en OCaml. On veille à ne pas laisser penser que les exceptions servent uniquement à gérer des erreurs.
Explicitation et justification des choix de conception ou programmation.	Les parties complexes de codes ou d’algorithmes font l’objet de commentaires qui l’éclairent en évitant la paraphrase.

Validation et tests

Notions	Commentaires
Jeu de tests associé à un programme.	Il n’est pas attendu de connaissances sur la génération automatique de jeux de tests; un étudiant est capable d’écrire un jeu de tests à la main, donnant à la fois des entrées et les sorties correspondantes attendues. On sensibilise, par des exemples, à la notion de partitionnement des domaines d’entrée et au test des limites.
Graphe de flot de contrôle. Chemins faisables. Couverture des sommets, des arcs ou des chemins (avec ou sans cycle) du graphe de flot de contrôle.	Les étudiants sont capables d’écrire un jeu de tests satisfaisant un critère de couverture des instructions (sommets) ou des branches (arcs) sur les chemins faisables.
Test exhaustif de la condition d’une boucle ou d’une conditionnelle.	Il s’agit, lorsque la condition booléenne comporte des conjonctions ou disjonctions, de ne pas se contenter de la traiter comme étant globalement vraie ou fausse mais de formuler des tests qui réalisent toutes les possibilités de la satisfaire. On se limite à des exemples simples pour lesquels les cas possibles se décèlent dès la lecture du programme.

Récursivité et induction

Notions	Commentaires
Récursivité d’une fonction. Récursivité croisée. Organisation des activations sous forme d’arbre en cas d’appels multiples.	On se limite à une présentation pratique de la récursivité comme technique de programmation. Les récurrences usuelles : 𝑇(𝑛)=𝑇(𝑛−1)+𝑎𝑛,𝑇(𝑛)=𝑎𝑇(𝑛/2)+𝑏, ou 𝑇(𝑛)=2𝑇(𝑛/2)+𝑓(𝑛) sont introduites au fur et à mesure de l’étude de la complexité des différents algorithmes rencontrés. On utilise des encadrements élémentaires ad hoc afin de les justifier; on évite d’appliquer un théorème-maître général.
Ensemble ordonné, prédécesseur et successeur, prédécesseur et successeur immédiat. Éléments minimal. Ordre produit, ordre lexicographique. Ordre bien fondé.	On fait le lien avec la notion d’accessibilité dans un graphe orienté acyclique. L’objectif n’est pas d’étudier la théorie abstraite des ensembles ordonnés mais de poser les définitions et la terminologie.
Ensemble inductif, défini comme le plus petit ensemble engendré par un système d’assertions et de règles d’inférence. Ordre induit. Preuve par induction structurelle.	On insiste sur les aspects pratiques : construction de structure de données et filtrage par motif. On présente la preuve par induction comme une généralisation de la preuve par récurrence.

Génie logiciel (#AGREG)

• Analyse : phases de développement ; diagrammes associés (diagrammes de cas d’utilisation, d’état, de séquence, de classes, etc.).
• Conception : conception orientée objet (exceptions, principes SOLID, patrons de conception). Une connaissance exhaustive des patrons de conception n’est pas exigible à cette épreuve.
• Tests :
  • Assertions, jeux de tests, tests en boîte blanche/noire.
  • Notion de test fonctionnel appliqué aux tests unitaires, comportementaux et d’intégration.
  • Notion de test non-fonctionnel : tests de performances, tests d’intrusions.
• Tests avancés : bouchons de test (mock ), notion de couvertures de test, mutation testing.
• Qualité logicielle : métriques de code (complexité cyclomatique, métriques d’Halstead, indice de maintenabilité).
• Gestion de projet : intégration & livraison continue, gestionnaire de code source (e.g., Git).

Programmation Objet et fonctionnelle (#AGREG)

• Programmation objet : objets, classes, héritage, polymorphisme de sous-typage.
• Programmation fonctionnelle : ordre supérieur, structures immuables, polymorphisme paramétrique.

Programmation web (#AGREG)

• Réseau : Adressage et transfert des documents via le protocole HTTP (notion d’URL, de types de paramètres, de verbes HTTP), requêtes HTTP (envoi/réception implicite via HTML/CSS ou explicite via JavaScript).
• Représentation : principes de mise en forme des documents web via le standard CSS (notions de classes et d’attributs CSS).
• Programmation : Accès et modification du contenu et de l’environnement d’une page web (objets navigator, document).

Informatique et société (#AGREG)

• Points clés du RGPD.
• Impact environnemental du numérique. Notion d’écoconception.
• Enjeux d’éthique du numérique et valeurs sous-jacentes.
• Cybersécurité : notions de vulnérabilité, menace, attaque ; chiffrement symétrique et asymétrique.

Données

Types et abstraction

Notions	Commentaires
Type prédéfini (booléen, entier, flottant). Pointeur. Type paramétré (tableau). Type composé. Tableaux statiques. Allocation (malloc) et désallocation (free) dynamique.	On se limite à une présentation pratique des types, en les illustrant avec les langages du programme. Un étudiant est capable d’inférer un type à la lecture d’un fragment de code, cependant toute théorie du typage est hors programme.
Définition d’une structure de données abstraite comme un type muni d’opérations.	On parle de constructeur pour l’initialisation d’une structure, d’accesseur pour récupérer une valeur et de transformateur pour modifier l’état de la structure. On montre l’intérêt d’une structure de données abstraite en terme de modularité. On distingue la notion de structure de données abstraite de son implémentation. Plusieurs implémentations concrètes sont interchangeables. La notion de classe et la programmation orientée objet sont hors programme.
Distinction entre structure de données mutable et immuable.	Illustrée en langage OCaml.

Il s’agit de montrer l’intérêt et l’influence des structures de données sur les algorithmes et les méthodes de programmation.
On insiste sur la distinction entre une structure de données abstraite (un type muni d’opérations ou encore une interface) et son implémentation concrète. On montre l’intérêt d’une structure de données abstraite en terme de modularité. Grâce aux bibliothèques, on peut utiliser des structures de données avant d’avoir programmé leur réalisation concrète.

Structures de données séquentielles

Notions	Commentaires
Structure de liste. Implémentation par un tableau, par des maillons chaînés.	On insiste sur le coût des opérations selon le choix de l’implémentation. Pour l’implémentation par un tableau, on se fixe une taille maximale. On peut évoquer le problème du redimensionnement d’un tableau.
Structure de pile. Structure de file. Implémentation par un tableau, par des maillons chaînés.
Structure de tableau associatif implémenté par une table de hachage.	La construction d’une fonction de hachage et les méthodes de gestion des collisions éventuelles ne sont pas des exigibles du programme.
Sérialisation.	On présente un exemple de sérialisation d’une structure hiérarchique et d’une structure relationnelle.

On présente les structures de données construites à l’aide de pointeurs d’abord au tableau avant de guider les étudiants dans l’implémentation d’une telle structure.

Structures de données hiérarchiques

Notions	Commentaires
Définition inductive du type arbre binaire. Vocabulaire : nœud, nœud interne, racine, feuille, fils, père, hauteur d’un arbre, profondeur d’un nœud, étiquette, sous-arbre.	La hauteur de l’arbre vide est−1. On mentionne la représentation d’un arbre complet dans un tableau.
Arbre. Conversion d’un arbre d’arité quelconque en un arbre binaire.	La présentation donne lieu à des illustrations au choix du professeur. Il peut s’agir par exemple d’expressions arithmétiques, d’arbres préfixes ( trie ), d’arbres de décision, de dendrogrammes, d’arbres de classification, etc.
Parcours d’arbre. Ordre préfixe, infixe et postfixe.	On peut évoquer le lien avec l’empilement de blocs d’activation lors de l’appel à une fonction récursive.
Implémentation d’un tableau associatif par un arbre binaire de recherche. Arbre bicolore.	On note l’importance de munir l’ensemble des clés d’un ordre total.
Propriété de tas. Structure de file de priorité implémentée par un arbre binaire ayant la propriété de tas.	Tri par tas.
Structure unir & trouver pour la représentation des classes d’équivalence d’un ensemble. Implémentation par des arbres.	On commence par donner des implémentations naïves de la structure unir trouver qui privilégient soit l’opération unir, soit l’opération trouver, avant de donner une implémentation par des arbres qui permet une mise en œuvre efficace des deux opérations. L’analyse de la complexité de cette structure est admise.

On présente les manipulations usuelles sur les arbres en C et en OCaml. Il n’est pas attendu d’un étudiant une maîtrise technique de l’écriture du code d’une structure de données arborescente mutable à l’aide de pointeurs, mais il est attendu qu’il sache l’utiliser.

Structures de données relationnelles

Il s’agit de définir le modèle des graphes, leurs représentations et leurs manipulations. On s’efforce de mettre en avant des applications importantes et si possibles modernes : réseau de transport, graphe du web, réseaux sociaux, bio-informatique. On précise autant que possible la taille typique de tels graphes.

Notions	Commentaires
Graphe orienté, graphe non orienté. Sommet (ou nœud); arc, arête. Boucle. Degré (entrant et sortant). Chemin d’un sommet à un autre. Cycle. Connexité, forte connexité. Graphe orienté acyclique. Arbre en tant que graphe connexe acyclique. Forêt. Graphe biparti.	Notation : graphe 𝐺 = (𝑆,𝐴), degrés 𝑑+(𝑠) et 𝑑−(𝑠) dans le cas orienté. On n’évoque pas les multi-arcs. On représente un graphe orienté par une matrice d’adjacence ou par des listes d’adjacence.
Pondération d’un graphe. Étiquettes des arcs ou des arêtes d’un graphe.	On motive l’ajout d’information à un graphe par des exemples concrets : graphe de distance, automate fini, diagramme de décision binaire.

On présente les manipulations usuelles sur les graphes en C et en OCaml. La présentation en C s’effectue à travers des tableaux statiques. Pour la représentation en liste d’adjacence, on peut considérer un tableau à deux dimensions dont les lignes représentent chaque liste avec une sentinelle ou un indicateur de taille en premier indice.

Bases de données

Notions	Commentaires
Vocabulaire des bases de données : tables ou relations, attributs ou colonnes, domaine, schéma de tables, enregistrements ou lignes, types de données.	On présente ces concepts à travers de nombreux exemples. On s’en tient à une notion sommaire de domaine : entier, flottant, chaîne ; aucune considération quant aux types des moteurs SQL n’est au programme. Aucune notion relative à la représentation des dates n’est au programme ; en tant que de besoin on s’appuie sur des types numériques ou chaîne pour lesquels la relation d’ordre coïncide avec l’écoulement du temps. Toute notion relative aux collations est hors programme ; en tant que de besoin on se place dans l’hypothèse que la relation d’ordre correspond à l’ordre lexicographique usuel.
Clé primaire.	Une clé primaire n’est pas forcément associée à un unique attribut même si c’est le cas le plus fréquent. La notion d’index est hors programme.
Entités et associations, clé étrangère.	On s’intéresse au modèle entité–association au travers de cas concrets d’associations 1 − 1, 1 − ∗, ∗ − ∗. Séparation d’une association ∗ − ∗ en deux associations 1 − ∗. L’utilisation de clés primaires et de clés étrangères permet de traduire en SQL les associations 1 − 1 et 1 − ∗.
Requêtes SELECT avec simple clause WHERE (sélection), projection, renommage AS. Utilisation des mots-clés DISTINCT, LIMIT, OFFSET, ORDER BY. Opérateurs ensemblistes UNION, INTERSECT et EXCEPT, produit cartésien.	Les opérateurs au programme sont +, -, *, / (on passe outre les subtilités liées à la division entière ou flottante), =, <>, <, <=, >, >=, AND, OR, NOT, IS NULL, IS NOT NULL.
Jointures internes T1 JOIN T2 ... JOIN Tn ON φ, externes à gauche T1 LEFT JOIN T2 ON φ.	On présente les jointures (internes) en lien avec la notion d’associations entre entités.
Agrégation avec les fonctions MIN, MAX, SUM, AVG et COUNT, y compris avec GROUP BY.	Pour la mise en œuvre des agrégats, on s’en tient à la norme SQL99. On présente quelques exemples de requêtes imbriquées.
Filtrage des agrégats avec HAVING.	On marque la différence entre WHERE et HAVING sur des exemples.

Compléments AGREG : bases de données

• Création, suppression, modification de tables au travers du langage de requêtes SQL.
• Opérateurs de l’algèbre relationnelle et leurs propriétés : application à l’optimisation de requêtes.

Algorithmique

Algorithmes probabilistes, algorithmes d’approximation

Notions	Commentaires
Algorithme déterministe. Algorithme probabiliste( LasVegas et MonteCarlo ).	On s’en tient aux définitions et à des exemples choisis par le professeur. On mentionne l’intérêt d’une méthode Las Vegas pour construire un objet difficile à produire par une méthode déterministe (par exemple, construction d’un nombre premier de taille cryptographique). Quelques exemples possibles :𝑘-ième minimum d’un tableau non trié, problème des huit reines, etc.
Problème de décision. Problème d’optimisation. Instance d’un problème, fonction de coût. Notion d’algorithme d’approximation.	Seule la notion d’algorithme d’approximation est au programme. L’étude de techniques générales d’approximation est hors programme. On indique, par exemple sur le problème MAX2SAT, que la méthode probabiliste peut fournir de bons algorithmes d’approximation.

Exploration exhaustive

Notions	Commentaires
Recherche par force brute. Retour sur trace ( Backtracking ).	On peut évoquer l’intérêt d’ordonner les données avant de les parcourir (par exemple par une droite de balayage).
Algorithme par séparation et évaluation ( Branch and bound ).	On peut évoquer sur des exemples quelques techniques d’évaluation comme les méthodes de relaxation (par exemple la relaxation continue).

L’objectif est de donner des outils de conception d’algorithmes et de parvenir à ce que les étudiants puissent, dans une situation simple, sélectionner une stratégie pertinente par eux-mêmes et la mettre en œuvre de façon autonome. Dans les cas les plus complexes, les choix et les recommandations d’implémentation sont guidés.

Décomposition d’un problème en sous-problèmes

Notions	Commentaires
Algorithme glouton fournissant une solution exacte.	On peut traiter comme exemples d’algorithmes exacts : codage de Huffman, sélection d’activité, ordonnancement de tâches unitaires avec pénalités de retard sur une machine unique.
Exemple d’algorithme d’approximation fourni par la méthode gloutonne.	On peut traiter par exemple : couverture des sommets dans un graphe, problème du sac à dos en ordonnant les objets.
Diviser pour régner. Rencontre au milieu. Dichotomie.	On peut traiter un ou plusieurs exemples comme : tri par partition-fusion, comptage du nombre d’inversions dans une liste, calcul des deux points les plus proches dans une ensemble de points; recherche d’un sous-ensemble d’un ensemble d’entiers dont la somme des éléments est donnée; recherche dichotomique dans un tableau trié. On présente un exemple de dichotomie où son recours n’est pas évident : par exemple, la couverture de 𝑛 points de la droite par 𝑘 segments égaux de plus petite longueur.
Programmation dynamique. Propriété de sous-structure optimale. Chevauchement de sous-problèmes. Calcul de bas en haut ou par mémoïsation. Reconstruction d’une solution optimale à partir de l’information calculée.	On souligne les enjeux de complexité en mémoire. On peut traiter un ou plusieurs exemples comme : problème de la somme d’un sous-ensemble, ordonnancement de tâches pondérées, plus longue sous-suite commune, distance d’édition (Levensh-tein).

L’objectif est de donner des outils de conception d’algorithmes et de parvenir à ce que les étudiants puissent, dans une situation simple, sélectionner une stratégie pertinente par eux-mêmes et la mettre en œuvre de façon autonome. Dans les cas les plus complexes, les choix et les recommandations d’implémentation sont guidés. Les listes d’exemples cités en commentaires ne sont ni impératives ni limitatives.

Algorithmique des textes

Notions	Commentaires
Recherche dans un texte. Algorithme de Boyer-Moore. Algorithme de Rabin-Karp.	On peut se restreindre à une version simplifiée de l’algorithme de Boyer-Moore, avec une seule fonction de décalage. L’étude précise de la complexité de ces algorithmes n’est pas exigible.
Compression. Algorithme de Huffman. Algorithme Lempel-Ziv-Welch.	On explicite les méthodes de décompression associées.

Algorithmique des graphes

Notions	Commentaires
Notion de parcours (sans contrainte). Notion de parcours en largeur, en profondeur. Notion d’arborescence d’un parcours.	On peut évoquer la recherche de cycle, la bicolorabilité d’un graphe, la recherche de plus courts chemins dans un graphe à distance unitaire.
Accessibilité. Tri topologique d’un graphe orienté acyclique à partir de parcours en profondeur. Recherche des composantes connexes d’un graphe non orienté.	On fait le lien entre accessibilité dans un graphe orienté acyclique et ordre.
Recherche des composantes fortement connexes d’un graphe orienté par l’algorithme de Kosaraju.	On fait le lien entre composantes fortement connexes et le problème 2-SAT.
Notion de plus courts chemins dans un graphe pondéré. Algorithme de Dijkstra. Algorithme de Floyd-Warshall.	On présente l’algorithme de Dijkstra avec une file de priorité en lien avec la représentation de graphes par listes d’adjacences. On présente l’algorithme de Floyd-Warshall en lien avec la représentation de graphes par matrice d’adjacence.
Recherche d’un arbre couvrant de poids minimum par l’algorithme de Kruskal.	On peut mentionner l’adaptation au problème du chemin le plus large dans un graphe non-orienté.
Recherche d’un couplage de cardinal maximum dans un graphe biparti par des chemins augmentants.	On se limite à une approche élémentaire; l’algorithme de Hopcroft-Karp n’est pas au programme. Les graphes bipartis et couplages sont introduits comme outils naturels de modélisation; ils peuvent également constituer une introduction aux problèmes de flots.

Une attention particulière est portée sur le choix judicieux du mode de représentation d’un graphe en fonction de l’application et du problème considéré. On étudie en conséquence l’impact de la représentation sur la conception d’un algorithme et sur sa complexité (en temps et en espace). On se concentre sur l’approfondissement des algorithmes cités dans le programme et le ré-emploi de leurs idées afin de résoudre des problèmes similaires. La connaissance d’une bibliothèque d’algorithmes fonctionnant sur des principes différents mais résolvant un même problème n’est pas un objectif du programme.

Algorithmique pour l’intelligence artificielle et l’étude des jeux

Notions	Commentaires
Apprentissage supervisé.	Algorithme des 𝑘 plus proches voisins avec distance euclidienne. Arbres 𝑘 dimensionnels. Apprentissage d’arbre de décision : algorithme ID3 restreint au cas d’arbres binaires. Matrice de confusion. On observe des situations de sur-apprentissage sur des exemples.
Apprentissage non-supervisé.	Algorithme de classification hiérarchique ascendante. Algorithme des 𝑘-moyennes. La démonstration de la convergence n’est pas au programme. On observe des convergences vers des minima locaux.
Jeux d’accessibilité à deux joueurs sur un graphe. Stratégie. Stratégie gagnante. Position gagnante. Détermination des positions gagnantes par le calcul des attracteurs. Construction de stratégies gagnantes.	On considère des jeux à deux joueurs (𝐽1 et 𝐽2 ) modélisés par des graphes bipartis (l’ensemble des états contrôlés par 𝐽1 et l’ensemble des états contrôlés par 𝐽2 ). Il y a trois types d’états finals : les états gagnants pour 𝐽1 , les états gagnants pour 𝐽2 et les états de match nul. On ne considère que les stratégies sans mémoire.
Notion d’heuristique. Algorithme minmax avec une heuristique. Élagage alpha-beta.
Graphe d’états. Recherche informée : algorithme A*.	On souligne l’importance de l’admissibilité de l’heuristique, ainsi que le cas où l’heuristique est également monotone.

Cette partie permet d’introduire les concepts d’apprentissage, de stratégie et d’heuristique. Ce dernier est abordé par des exemples où l’heuristique est précisément définie mais sans en évaluer la performance. La connaissance des théories sous-jacentes aux algorithmes de cette section n’est pas un attendu du programme. Les étudiants acquièrent une familiarité avec les idées qu’ils peuvent réinvestir dans des situations où les modélisations et les recommandations d’implémentation sont guidées.

Intelligence artificielle (#AGREG)

• Mesures de similarité pour l’apprentissage machine.
• Données d’entraînement et données de test, choix des descripteurs.
• Enjeux d’éthique (biais d’apprentissage, transparence).

Gestion des ressources de la machine

Gestion de la mémoire d’un programme

Notions	Commentaires
Utilisation de la pile et du tas par un programme compilé.	On présente l’allocation des variables globales, le bloc d’activation d’un appel.
Notion de portée syntaxique et durée de vie d’une variable. Allocation des variables locales et paramètres sur la pile.	On indique la répartition selon la nature des variables : globales, locales, paramètres.
Allocation dynamique.	On présente les notions en lien avec le langage C : malloc et free, pointeur nul, type void*, transtypage, relation avec les tableaux, protection mémoire ( segmentation violation ).

Gestion des fichiers et entrées-sorties

Notions	Commentaires
Interface de fichiers : taille, accès séquentiel.
Implémentation interne : blocs et nœuds d’index ( inode ).	On présente le partage de blocs ( avec liens physiques ou symboliques ) et l’organisation hiérarchique de l’espace de nommage.
Accès, droits et attributs.	On utilise sur des exemples les fonctions d’accès et d’écriture dans les différents modes.
Fichiers spéciaux : flux standard (entrée standard stdin, sortie standard stdout, sortie d’erreur standard stderr) et redirections dans l’interface système ( shell ).	On présente la notion de tube ( pipe ).

Les seules notions exigibles sont celles permettant à un programme de gérer l’ouverture, la fermeture et l’accès à un ou plusieurs fichiers, selon les modalités précisées en annexes. On attend toutefois d’un étudiant une expérience du montage d’un support de fichiers amovible, de la gestion des droits d’accès à des parties de l’arborescence, de la création et du déplacement des parties de l’arborescence et de la gestion des liens physiques et symboliques. Le professeur expose également ses étudiants à la réalisation d’enchaînements de programmes via des tubes ( pipes ).

Gestion de la concurrence et synchronisation

Notions	Commentaires
Notion de fils d’exécution. Non-déterminisme de l’exécution.	Les notions sont présentées au tableau en privilégiant le pseudo-code; elles sont mises en œuvre au cours de travaux pratiques en utilisant les bibliothèques POSIX pthread (en langage C) ou Thread(en langage OCaml), au choix du professeur, selon les modalités précisées en annexe. On s’en tient aux notions de base : création, attente de terminaison.
Synchronisation de fils d’exécution. Algorithme de Peterson pour deux fils d’exécution. Algorithme de la boulangerie de Lamport pour plusieurs fils d’exécution.	On illustre l’importance de l’atomicité par quelques exemples et les dangers d’accès à une variable en l’absence de synchronisation. On présente les notions de mutex et sémaphores.

L’apprentissage des notions liées au parallélisme d’exécution se limite au cas de fils d’exécutions ( threads ) internes à un processus, sur une machine. Les problèmes d’algorithmes répartis et les notions liées aux réseaux et à la communication asynchrone sont hors programme. Les concepts sont illustrés sur des schémas de synchronisation classiques : rendez-vous, producteur-consommateur. Les étudiants sont également sensibilisés au non-déterminisme et aux problèmes d’interblocage et d’équité d’accès, illustrables sur le problème classique du dîner des philosophes.

Architecture (#AGREG)

• Circuits combinatoires/séquentiels, machine de Mealy, machine de Moore.
• Description et fonctionnement d’une machine de von Neumann (introduction à la programmation assembleur : instructions de calcul, instructions de branchement, accès à la mémoire et aux registres, instructions système).
• Exécution d’un appel de fonction, concept de pile.
• Hiérarchie mémoire.
• Typologie des machines parallèles (classification de Flynn, classification de Raina, machines multi-coeurs, supercalculateurs).
• Représentation des nombres à virgule flottante. Problèmes de précision des calculs flottants et de dépassement de capacité. Notion de mode d’arrondi.

Systèmes d’exploitation (#AGREG)

• Séquence de démarrage : de l’initialisation aux processus utilisateur.
• Abstractions fournies par le système : accès au matériel, répartition équitable des ressources, accès aux fichiers (dont open, read, write et close).
• Liens entre système d’exploitation et applications : adressage physique et virtuel, notion de pagination, MMU, interruptions, appels systèmes, gestion des processus (dont fork, wait, waitpid), gestion du temps (ticks et implémentation du temps partagé).
• Isolation et interaction entre les processus : espace mémoire d’une application, communication entre applications (pipe, mmap).
• Concurrence : modèles de cohérence (forte, faible, PRAM et au relâchement) et d’équité. Construction des mutex et sémaphores à partir des instructions atomiques test and set. Schéma lecteurs rédacteurs.
• Émulation et virtualisation : types d’hyperviseurs (natif, hébergé) et conteneur.
• Virtualisation matérielle et para-virtualisation.

Réseaux (#AGREG)

• Caractéristiques des réseaux et performances associées :
  • réseaux d’accès, réseaux de coeur ;
  • topologies de réseaux : point à point, à diffusion ;
  • performances : débit de transmission, délai, taux de perte.
• Modélisation en couches : OSI, TCP/IP, encapsulation.
• Transmission :
  • Adressage : adresses MAC, IPv4, IPv6 ;
  • Routage : principes ; système de nom de domaine (DNS) ; routage à vecteur de distance (algorithme de Bellman-Ford), routage par état de liens (algorithme de Dijkstra) ;
  • Solutions de transport : principes ; TCP, UDP.
• Programmation réseau : API Socket en Python et en C, à l’aide d’un aide-mémoire fourni.

Logique

Syntaxe des formules logiques

Notions	Commentaires
Variables propositionnelles, connecteurs logiques, arité.	Notations : ¬, ∨, ∧, →, ↔.
Formules propositionnelles, définition par induction, représentation comme un arbre. Sous-formule. Taille et hauteur d’une formule.	Les formules sont des données informatiques. On fait le lien entre les écritures d’une formule comme mot et les parcours d’arbres.
Quantificateurs universel et existentiel. Variables liées, variables libres, portée. Substitution d’une variable.	On ne soulève aucune difficulté technique sur la substitution. L’unification est hors programme.

Le but de cette partie est de familiariser progressivement les étudiants avec la différence entre syntaxe et sémantique d’une part et de donner le vocabulaire permettant de modéliser une grande variété de situations (par exemple, satisfaction de contraintes, planification, diagnostic, vérification de modèles, etc.). L’étude des quantificateurs est l’occasion de formaliser les notions de variables libres et liées, et de portée, notions que l’on retrouve dans la pratique de la programmation. On implémente uniquement les formules propositionnelles sous forme d’arbres.

Sémantique de vérité du calcul propositionnel

Notions	Commentaires
Valuations, valeurs de vérité d’une formule propositionnelle. Satisfiabilité, modèle, ensemble de modèles, tautologie, antilogie. Équivalence sur les formules. Conséquence logique entre deux formules.	Notations 𝑉 pour la valeur vraie, 𝐹 pour la valeur fausse. Une formule est satisfiable si elle admet un modèle, tautologique si toute valuation en est un modèle. On peut être amené à ajouter à la syntaxe une formule tautologique et une formule antilogique; elles sont en ce cas notées ⊤ et ⊥. On présente les lois de De Morgan, le tiers exclu et la décomposition de l’implication. On étend la notion à celle de conséquence 𝜙 d’un ensemble de formules Γ: on note Γ ⊧ 𝜙. La compacité est hors programme.
Forme normale conjonctive, forme normale disjonctive. Mise sous forme normale.	Lien entre forme normale disjonctive complète et table de vérité. On peut représenter les formes normales comme des listes de listes de littéraux. Exemple de formule dont la taille des formes normales est exponentiellement plus grande.
Problème SAT, 𝑛-SAT, algorithme de Quine.	On incarne SAT par la modélisation d’un problème (par exemple la coloration des sommets d’un graphe).

Par souci d’éviter trop de technicité, on ne présente la notion de valeur de vérité que pour des formules sans quantificateurs.

Déduction naturelle

Notions	Commentaires
Règle d’inférence, dérivation. Définition inductive d’un arbre de preuve.	Notation ⊢. Séquent 𝐻1,... , 𝐻𝑛 ⊢ 𝐶. On présente des exemples tels que le modus ponens (𝑝, 𝑝 → 𝑞 ⊢ 𝑞) ou le syllogisme barbara (𝑝 → 𝑞 , 𝑞 → 𝑟 ⊢ 𝑝 → 𝑟). On présente des exemples utilisant les règles précédentes.
Règles d’introduction et d’élimination de la déduction naturelle pour les formules propositionnelles. Correction de la déduction naturelle pour les formules propositionnelles.	On présente les règles pour ∧, ∨,¬ et →. On écrit de petits exemples d’arbre de preuves (par exemple ⊢ ( 𝑝 → 𝑞 ) → ¬ ( 𝑝 ∧ ¬ 𝑞 ), etc.).
Règles d’introduction et d’élimination pour les quantificateurs universels et existentiels.	On motive ces règles par une approche sémantique intuitive.

Il s’agit de présenter les preuves comme permettant de pallier deux problèmes de la présentation précédente du calcul propositionnel : nature exponentielle de la vérification d’une tautologie, faible lien avec les preuves mathématiques. Il ne s’agit, en revanche, que d’introduire la notion d’arbre de preuve. La déduction naturelle est présentée comme un jeu de règles d’inférence simple permettant de faire un calcul plus efficace que l’étude de la table de vérité. Toute technicité dans les preuves dans ce système est à proscrire. Il ne s’agit pas d’implémenter ces règles mais plutôt d’être capable d’écrire de petites preuves dans ce système. On peut également présenter d’autres utilisations de règles d’inférences pour raisonner.

Langages formels

Langages réguliers

Notions	Commentaires
Alphabet, mot, préfixe, suffixe, facteur, sous-mot.	Le mot vide est noté 𝜀.
Langage comme ensemble de mots sur un alphabet. Opérations régulières sur les langages (union, concaténation, étoile de Kleene). Définition inductive des langages réguliers.
Expression régulière. Dénotation d’un langage régulier.	On introduit les expressions régulières comme un formalisme dénotationnel pour les motifs. On note l’expression dénotant le langage vide ∅, celle dénotant le langage réduit au mot vide 𝜀, l’union par |, la concaténation par juxtaposition et l’étoile de Kleene par une étoile.
Expressions régulières étendues.	Le lien est fait avec les expressions régulières de la norme POSIX, mais on ne développe aucune théorie supplémentaire à leur sujet et aucune connaissance au sujet de cette norme n’est exigible.

Automates finis

Notions	Commentaires
Automate fini déterministe. État accessible, co-accessible. Automate émondé. Langage reconnu par un automate.	On insiste sur la richesse de systèmes dont le fonctionnement peut être modélisé par un automate.
Transition spontanée (ou 𝜀-transition). Automate fini non déterministe.
Déterminisation d’un automate non déterministe.	On fait le lien entre l’élimination des transitions spontanées et l’accessibilité dans un graphe. On aborde l’élimination des transitions spontanées et plus généralement les constructions d’automates à la Thompson sur des exemples, sans chercher à formaliser complètement les algorithmes sous-jacents.
Construction de l’automate de Glushkov associé à une expression régulière par l’algorithme de Berry-Sethi.	Les notions de langage local et d’expression régulière linéaire sont introduites dans cette seule perspective.
Passage d’un automate à une expression régulière. Élimination des états. Théorème de Kleene.	On se limite à la description du procédé d’élimination et à sa mise en œuvre sur des exemples d’automates de petite taille; cela constitue la preuve du sens réciproque du théorème de Kleene.
Stabilité de la classe des langages reconnaissables par union finie, intersection finie, complémentaire.
Lemme de l’étoile.	Soit 𝐿 le langage reconnu par un automate à 𝑛 états : pour tout 𝑢 ∈ 𝐿 tel que \|𝑢\| ≥ 𝑛, il existe 𝑥, 𝑦, 𝑧 tels que 𝑢 = 𝑥𝑦𝑧, \|𝑥𝑦\| ≤ 𝑛, 𝑦 ≠ 𝜀 et 𝑥𝑦 ∗ 𝑧 ⊆ 𝐿.

Grammaires non contextuelles

Notions	Commentaires
Grammaire non contextuelle. Vocabulaire : symbole initial, symbole non-terminal, symbole terminal, règle de production, dérivation immédiate, dérivation. Langage engendré par une grammaire, langage non contextuel. Non contextualité des langages réguliers.	Notations : règle de production →, dérivation immédiate ⇒, dérivation ⇒∗. On montre comment définir une expression arithmétique ou une formule de la logique propositionnelle par une grammaire. On peut présenter comme exemple un mini-langage fictif de programmation ou un mini-langage de balisage. Sont hors programme : les automates à pile, les grammaires syntagmatiques générales, la hiérarchie de Chomsky.
Arbre d’analyse. Dérivation à gauche, à droite. Ambiguïté d’une grammaire. Équivalence faible.	On présente le problème du «sinon pendant» ( dangling else ).
Exemple d’algorithme d’analyse syntaxique.	On peut présenter au tableau un algorithme ad hoc d’analyse syntaxique par descente récursive (algorithme top-down ) pour un langage de balisage fictif ( par exemple, la grammaire de symbole initial 𝑆 et de règles de production 𝑆 → 𝑇𝑆\|𝑐, 𝑇 → 𝑎𝑆𝑏 sur l’alphabet {𝑎,𝑏,𝑐}). On ne parle pas d’analyseur LL ou LR. On ne présente pas de théorie générale de l’analyse syntaxique.

Chaîne de compilation (#AGREG)

• Analyse lexicale, analyse syntaxique (principes de l’analyse descendante).
• Analyse sémantique élémentaire (arbre de syntaxe abstraite, environnement, analyse de portée, typage).
• Génération de code vers une machine à pile.

Décidabilité et classes de complexité

Notions	Commentaires
Problème de décision. Taille d’une instance. Complexité en ordre de grandeur en fonction de la taille d’une instance. Opération élémentaire. Complexité en temps d’un algorithme. Classe P.	Les opérations élémentaires sont les lectures et écritures en mémoire, les opérations arithmétiques, etc. La notion de machine de Turing est hors programme. On s’en tient à une présentation intuitive du modèle de calcul (code exécuté avec une machine à mémoire infinie). On insiste sur le fait que la classe P concerne des problèmes de décision.
Réduction polynomiale d’un problème de décision à un autre problème de décision.	On se limite à quelques exemples élémentaires.
Certificat. Classe NP comme la classe des problèmes que l’on peut vérifier en temps polynomial. Inclusion P ⊆ NP.	Les modèles de calcul non-déterministes sont hors programme.
NP-complétude. Théorème de Cook-Levin (admis) : SAT est NP-complet.	On présente des exemples de réduction de problèmes NP-complets à partir de SAT. La connaissance d’un catalogue de problèmes NP-complets n’est pas un objectif du programme.
Transformation d’un problème d’optimisation en un problème de décision à l’aide d’un seuil.
Notion de machine universelle. Problème de l’arrêt.

On prend soin de distinguer la notion de complexité d’un algorithme de la notion de classe de complexité d’un problème. Le modèle de calcul est une machine à mémoire infinie qui exécute un programme rédigé en OCaml ou en C. La maîtrise ou la technicité dans des formalismes avancés n’est pas un objectif du programme.

Compléments AGREG : Calculabilité, complexité

• Modèle de calcul. Machines de Turing : définition, principales variantes (ruban biinfini vs infini, machine à plusieurs rubans). La machine de Turing est le modèle de calcul retenu pour l’étude des notions qui suivent.
• Calculabilité : universalité, décidabilité, indécidabilité. Problème de l’arrêt.
• Complexité : complexité en temps et en espace, classe P. Acceptation par certificat, classe NP. Réduction polynomiale. NP-complétude. Théorème de Cook.
  La notion de machine de Turing non déterministe n’est pas exigible aux épreuves 1, 2 et 3.a de l’écrit, ni aux épreuves orales.