Option Informatique Mpsi / Mp

Je mets sur cette page mon cours d’option informatique (langage OCaml) donné aux lycées Saint-Louis et Chaptal, pour les deux années Mpsi et Mp/Mp*. J’y ajoute une liste de 160 exercices corrigés pour acquérir de bonnes bases sur la syntaxe OCaml.

Chapitre 1 — Éléments de syntaxe OCaml

Survolez 💬 devant le titre pour une description.

Valeurs, expressions et types de base en OCaml. Produits cartésiens, évaluation des expressions et premières conventions de syntaxe. Types, valeurs, expressions
Liaisons globales avec let et locales avec let…in. Distinction entre liaison d’un identificateur à une valeur et référence dont le contenu peut être modifié. Liaisons globales ou locales, références
Définition et application des fonctions, application partielle et fonctions anonymes. Récursivité, paramètres de type et polymorphisme. Introduction à la syntaxe des fonctions
Opérateurs arithmétiques sur les entiers et les flottants, comparaisons et opérations booléennes. Concaténation des chaînes de caractères et règles de typage associées. Opérateurs binaires
Fonctions mathématiques intégrées, affichage et conversions entre types de base. Signatures et exemples des opérations usuelles. Quelques fonctions intégrées usuelles
Listes homogènes et construction récursive à partir de la liste vide. Tête, queue, notation des listes et concaténation. Les listes en OCaml
Tableaux de taille fixe, lecture et modification d’un élément. Tableaux de tableaux et différences de représentation et d’usage avec les listes. Les tableaux en OCaml
Fonctions des modules String, List, Array, Random, Char et Sort. Signatures et exemples pour les chaînes, listes, tableaux et tirages pseudo-aléatoires. Quelques bibliothèques utiles
Branchements if…then…else, boucles for et while et séquences d’instructions. Contraintes de typage et portée des identificateurs dans les blocs. Boucles et tests
Types énumérés, types sommes et enregistrements. Constructeurs, paramètres de type et définitions récursives de structures de données. Définitions de type
Filtrage par motifs avec match…with. Reconnaissance des différentes formes d’une valeur et définitions récursives fondées sur sa structure. Pattern-matching
Exceptions : définition, déclenchement et interception. Fonctions raise, failwith et invalid_arg, puis traitement des cas d’erreur avec try…with. Les exceptions
Fonctions sur les listes et les tableaux : longueur, somme, inversion et cumuls. Exemples de tri fusion, d’exponentiation et d’insertion dans un tableau trié. Exemples de fonctions

Chapitre 2 — Définitions de type

Survolez 💬 devant le titre pour une description.

Nombres complexes représentés par des enregistrements en coordonnées cartésiennes ou polaires. Conversions, conjugaison, module, argument et opérations arithmétiques. Les nombres complexes (solution 1)
Type somme réunissant les représentations cartésienne et polaire d’un complexe. Constructeurs paramétrés et filtrage pour adapter chaque opération à la représentation utilisée. Les nombres complexes (solution 2)
Représentations cartésienne et polaire portées directement par des couples de flottants dans un type somme. Conversions et opérations définies par filtrage. Les nombres complexes (solution 3)
Rationnels représentés par un constructeur Q et un couple d’entiers. Conversion en flottant, simplification par le pgcd, addition et multiplication. Un type pour les rationnels
Entiers naturels définis récursivement par zéro et la succession. Conversions, addition, produit, différence, comparaisons, division et pgcd sur cette représentation. Un type récursif pour les entiers

Chapitre 3 — La structure de pile

Survolez 💬 devant le titre pour une description.

Structure de pile et principe « dernier entré, premier sorti ». Sommet, empilement, dépilement et opérations élémentaires de cette structure. Notion de pile
Pile représentée par un enregistrement à champ mutable. Création, test de vacuité, empilement et dépilement par modification de ce champ. Enregistrement à un champ mutable
Pile de capacité fixée représentée par un tableau et une position de sommet. Tests, empilement, dépilement et consultation du sommet. Piles de taille maximum avec un tableau
Pile définie par des constructeurs récursifs. Création, test de vacuité, empilement et dépilement à l’aide du filtrage. Définition récursive par constructeur
Pile organisée en liste de blocs stockés dans des tableaux. Gestion des blocs lors des empilements et dépilements, sans capacité globale fixée à l’avance. Implémentation par listes de blocs

Chapitre 4 — Les files d’attente

Survolez 💬 devant le titre pour une description.

File d’attente dans un tableau circulaire : indices d’entrée et de sortie, file vide ou pleine. Enfilage, défilage, consultation des extrémités et calcul de la taille. Par des tableaux "circulaires"
File d’attente représentée par deux listes. Répartition des entrées et des sorties et inversion d’une liste lorsque la partie destinée au défilage est vide. Implémentation par deux listes
File d’attente fondée sur une liste doublement chaînée. Mise à jour des maillons et des extrémités, enfilage, défilage et parcours de la file. Avec une liste doublement chaînée

Chapitre 5 — Files de priorité, structure de tas

Survolez 💬 devant le titre pour une description.

File de priorité dans un tableau non trié. Insertion simple et recherche de l’élément prioritaire à l’extraction, avec une application au tri. Utilisation d'un tableau non trié
File de priorité maintenue dans un tableau trié. Coût de l’insertion ordonnée, extraction à une extrémité et comparaison avec le tableau non trié. Utilisation d'un tableau trié
Tas binaire représenté dans un tableau et propriété d’ordre entre parents et enfants. Remontée à l’insertion, réorganisation à l’extraction et tri par tas. file de priorité et structure de tas

Chapitre 6 — Dictionnaires, tables de hachage

Survolez 💬 devant le titre pour une description.

Dictionnaires associant des clés à des valeurs. Fonction de hachage, répartition dans une table et problème des collisions. Généralités
Collisions traitées par des listes de couples partageant la même empreinte. Recherche d’une clé, lecture, insertion, mise à jour et suppression dans la table. Gestion des collisions par chaînage
Redimensionnement d’une table de hachage et redistribution des couples dans ses nouvelles cases. Adaptation de l’insertion à l’évolution du nombre d’éléments. Redimensionnement de la table
Exemple de table de hachage alimentée par des clés aléatoires de cinq lettres et des valeurs entières. Insertions successives et observation des redimensionnements de la table. Un exemple
Collisions résolues par sondage dans le tableau, sans listes chaînées. Recherche, insertion, suppression et gestion des cases libérées. Gestion des collisions par sondage

Chapitre 7 — Programmation dynamique

Survolez 💬 devant le titre pour une description.

Coût des calculs récursifs répétés, illustré par les coefficients binomiaux et les parenthésages d’un produit. Mesure du temps et comparaison avec d’autres méthodes de calcul. Les dangers de la récursivité
Mémoïzation des sous-problèmes pour éviter les appels redondants. Tableaux ou listes de résultats appliqués aux coefficients binomiaux et au dénombrement des parenthésages. Techniques de mémoïzation
Chemin de poids maximal dans une pyramide. Calcul des valeurs optimales par programmation dynamique, puis reconstruction d’un chemin réalisant le maximum. Chemin maximal dans une pyramide
Plus longue sous-suite commune de deux suites. Calcul de sa longueur par programmation dynamique et reconstruction d’une solution ou de toutes les solutions. La plus longue sous-suite commune
Distance d’édition entre deux mots par insertions, suppressions et substitutions. Relation de récurrence et mémorisation des distances entre sous-problèmes. Distance d'édition
Sélection de tâches compatibles de poids total maximal. Limites d’une première approche, classement des tâches et programmation dynamique pour reconstruire un ordonnancement optimal. Ordonnancement de tâches pondérées

Chapitre 8 — Le principe « diviser pour régner »

Survolez 💬 devant le titre pour une description.

Tri fusion sur les listes et les tableaux : découpage, appels récursifs et fusion de deux parties triées. Implémentations et étude du coût. Le tri fusion (listes ou tableaux)
Tri rapide d’un tableau par choix d’un pivot et partition. Échanges en place, traitement récursif des sous-tableaux et programmation de l’algorithme. Le « tri rapide » (quick sort) des tableaux
Multiplication de polynômes représentés par des tableaux de coefficients. Comparaison de l’algorithme naïf avec Karatsuba, fondé sur trois produits récursifs, et étude de la complexité. L'algorithme de Karatsuba
Paire de points la plus proche dans le plan. Méthode naïve, tris lexicographiques et division du problème, puis recherche dans la bande entourant la séparation. Les deux points les plus proches
Nombre d’inversions d’une suite. Comparaison du comptage naïf avec une méthode récursive qui compte les inversions lors de la fusion. Calcul du nombre d'inversions

Chapitre 9 — Analyse des algorithmes

Survolez 💬 devant le titre pour une description.

Ordres bien fondés et principe d’induction. Cadre de raisonnement pour les objets récursifs et rôle de la décroissance dans un ordre sans descente infinie. Ordres bien fondés, induction
Terminaison des fonctions récursives à partir d’une mesure dans un ensemble bien fondé. Exemples des coefficients binomiaux, de la fonction d’Ackermann et d’une récursion moins immédiate. Terminaison et correction
Théorème de correction par induction sur les appels récursifs. Vérification des cas de base et de l’étape d’induction sur le calcul des coefficients binomiaux et le tri d’une liste. Preuves de correction
Coût d’un algorithme, taille des données et opérations élémentaires. Notations asymptotiques et ordres de grandeur pour comparer les méthodes. Introduction à la complexité
Récurrences de complexité associées à une diminution de taille ou à une division du problème. Sommation des coûts et exemples d’algorithmes récursifs usuels. Récurrences de complexité usuelles

Chapitre 10 — Arbres binaires

Survolez 💬 devant le titre pour une description.

Type récursif des arbres binaires avec arbre vide, étiquette et deux sous-arbres. Construction d’une feuille et génération d’exemples d’arbres en OCaml. Une définition du type « arbre binaire »
Accès à la racine et aux sous-arbres, échange des fils et arbre miroir. Comptage des feuilles et des nœuds selon leur nombre de fils non vides. Quelques fonctions simples
Hauteur et taille d’un arbre binaire, calculées récursivement. Relations entre nombre de nœuds et hauteur, et cas des arbres complets. Hauteur et taille d'un arbre binaire
Présence d’une étiquette et comptage de ses occurrences. Disjonction des étiquettes de deux arbres et vérification de leur unicité dans un arbre. Tests d'appartenance et d'unicité
Minimum des étiquettes, transformation par une fonction et tests sur tout ou partie des nœuds. Réduction récursive pour calculer notamment la somme ou le produit des étiquettes. Calculs sur les étiquettes
Chemins, profondeur et ascendance d’un nœud. Parcours préfixe, infixe, postfixe et en largeur, avec les fonctions OCaml correspondantes. Parcours dans un arbre binaire
Dénombrement des arbres binaires de taille fixée. Décomposition selon les tailles des sous-arbres gauche et droit et calcul des nombres de Catalan. Arbres binaires ayant n noeuds

Chapitre 11 — Arbres binaires de recherche

Survolez 💬 devant le titre pour une description.

Propriété d’ordre d’un arbre binaire de recherche et vérification de cette propriété. Recherche d’une étiquette, minimum, maximum, successeur et prédécesseur. Fonctions de base sur un ABR
Insertion dans un arbre binaire de recherche, aux feuilles ou à la racine. Construction d’un arbre à partir d’une liste et effet de l’ordre des insertions. Insertion d'un élément dans un ABR
Suppression d’une étiquette dans un arbre binaire de recherche. Retrait du maximum, suppression de la racine et réorganisation conservant l’ordre des étiquettes. Suppression d'un élément dans un ABR
Coût moyen de construction d’un arbre binaire de recherche par insertions dans un ordre aléatoire. Récurrence sur les tailles des deux sous-arbres et équivalent 2n ln(n) du nombre moyen de comparaisons. Calculs de complexité dans les ABR

Chapitre 12 — Logique propositionnelle

Survolez 💬 devant le titre pour une description.

Variables propositionnelles, connecteurs et expressions logiques. Syntaxe des formules et interprétation des opérateurs usuels. Opérateurs et expressions logiques
Distributions de valeurs de vérité et évaluation d’une expression. Tableaux de vérité, satisfiabilité, tautologies, contradictions et équivalence logique. Évaluation d'une expression logique
Formes normales conjonctive et disjonctive. Transformations des expressions à l’aide des identités logiques pour obtenir une conjonction de clauses ou une disjonction de termes. Forme normale conjonctive ou disjonctive
Construction détaillée d’une FNC et d’une FND sur une même expression. Lien entre ces écritures et les lignes de son tableau de vérité. Un exemple de FNC et de FND
Expressions logiques représentées par un type récursif OCaml. Distributions, évaluation et tables de vérité, puis tests de tautologie, satisfiabilité et équivalence et construction d’une forme normale. Logique propositionnelle avec OCaml

Chapitre 13 — Graphes

Survolez 💬 devant le titre pour une description.

Graphes orientés ou non orientés : sommets, arcs, arêtes et degrés. Chemins et premières propriétés qui structurent les représentations et les algorithmes suivants. Définitions générales
Matrices et listes d’adjacence pour représenter un graphe. Description des voisinages et fonctions de conversion entre les deux représentations. Matrices ou listes d'adjacence
Connexité d’un graphe non orienté et composantes connexes. Accessibilité et forte connexité dans le cas orienté. Connexité des graphes
Création d’un graphe et ajout ou suppression d’arcs, d’arêtes et de sommets. Fonctions adaptées aux matrices ou listes d’adjacence et désorientation d’un graphe. Opérations élémentaires sur les graphes
Parcours en largeur et en profondeur, avec leurs programmations BFS et DFS. Exploration des sommets accessibles et calcul des composantes connexes d’un graphe non orienté. Parcours dans un graphe
Chemins de poids minimal dans un graphe pondéré. Floyd-Warshall pour les distances entre sommets et Dijkstra pour les chemins issus d’une source, avec reconstruction et exemples. Problèmes de plus court chemin

Chapitre 14 — Langages

Survolez 💬 devant le titre pour une description.

Alphabets, mots et occurrences de lettres. Concaténation, puissances, préfixes, suffixes, facteurs et mot miroir, avec des représentations et fonctions OCaml. Alphabets, lettres, mots
Langages considérés comme ensembles de mots. Opérations ensemblistes, concaténation et itération pour construire de nouveaux langages. Opérations sur les langages
Langages finis représentés par des listes de mots. Concaténation, itération, réunion et intersection, avec tri et suppression des doublons. Opérations sur les langages finis
Expressions rationnelles : construction syntaxique et langage dénoté. Représentation par un type récursif et interprétation des opérations sur les expressions. Expressions rationnelles
Langages rationnels définis par les expressions rationnelles. Propriétés de cette famille et lien entre les opérations sur les expressions et celles sur les langages. Langages rationnels
Langages locaux décrits par les lettres initiales et finales autorisées et les facteurs de longueur deux interdits. Rôle du mot vide et description équivalente par les facteurs autorisés. Langages locaux
Stabilité des langages locaux par intersection. Contre-exemples pour la réunion et la concaténation, avec les ensembles caractéristiques des langages considérés. Opérations sur les langages locaux
Expressions rationnelles où chaque lettre apparaît au plus une fois. Calcul de l’alphabet et test de linéarité par parcours de l’expression en OCaml. Expressions rationnelles linéaires
Appartenance du mot vide et calcul par induction des lettres préfixes, suffixes et facteurs autorisés de longueur deux. Fonctions OCaml associées à la structure d’une expression rationnelle. Préfixes, suffixes, facteurs de taille 2
Marquage des occurrences de lettres pour rendre une expression rationnelle linéaire. Numérotation lors du parcours et opération inverse de démarquage. Linéarisation d'une expression rationnelle

Chapitre 15 — Automates finis

Survolez 💬 devant le titre pour une description.

Automates finis déterministes : alphabet, états, état initial, états finaux et transitions. Définition de la structure qui servira à reconnaître des mots. Automates finis déterministes (AFD)
Automate déterministe représenté par un enregistrement OCaml à champs mutables. États et lettres sous forme de chaînes, liste de transitions et fonctions d’accès à l’alphabet ou aux états. Un type « AFD » en OCaml
Extension de la fonction de transition des lettres aux mots. Calcul de l’état atteint et test de reconnaissance selon l’état final obtenu. Mots reconnus par un AFD
Automates complets, standards et émondés. Ajout d’un état de blocage, standardisation et calcul des états accessibles ou coaccessibles pour l’émondage. Quelques catégories particulières d'AFD
Construction d’un automate local à partir des lettres préfixes, suffixes et facteurs autorisés. Programmation de l’automate associé à une expression rationnelle linéaire. Automate local associé à un langage local
Automates non déterministes, avec plusieurs états initiaux ou plusieurs destinations pour une transition. Représentation en OCaml, parcours d’un mot et test de reconnaissance. Automates finis non déterministes
Déterminisation par des états représentant des ensembles d’états de l’automate initial. Construction des transitions et d’un automate déterministe reconnaissant le même langage. Déterminisation d'un AFND
Reconnaissance d’un langage rationnel par enchaînement des constructions précédentes. Linéarisation, langage local, automate associé et démarquage des transitions. Reconnaissance d'un langage rationnel
Exemple complet allant d’une expression rationnelle à un automate déterministe. Marquage, calcul des préfixes, suffixes et facteurs, construction de l’automate, démarquage et déterminisation. Un exemple

160 exercices corrigés OCaml