L'option informatique est une des deux (en fait 3) options en MPSI. On y étudie les débuts de l'algorithmique et des structures de données en mettant l'accent sur la récursivité. La mise en pratique se fait avec un nouveau langage, OCaml, sans que le programme ne prévoie de travaux pratiques, on reste toujours dans le grotesque. La réforme introduit en plus un chapitre ambitieux de logique.
On peut voir ici un calendrier prévisionnel ; bien entendu, il ne sera pas respecté mais il donne un guide sur les chapitres traités. Il sera peut-être ajusté en cours d'année.
Retour
Chapitres du cours
- L'option est présentée avant le début officiel par 2 heures destinées à montrer la dure réalité du caractère très abstrait du cours, en voici le poly.
- Le premier chapitre, moins abrupt, fait la jonction avec Python. On y introduit les types et instructions de base pour une programmation impérative.
- Le second chapitre introduit les listes, on utilise maintenant la récursivité. Le chapitre est assez court mais contient de nombreux exercices (corrigés). Tous ne seront pas abordés en TD et il est utile de s'exercer en résolvant une partie de ceux qui n'ont pas été faits en commun.
- Le troisième chapitre, extrèmement court, présente les construction de types.
- Le quatrième chapitre, non encore rédigé, présente les algorithmes simples de tri : par insertion et par sélection. On les introduit en partant de la définition d'un invariant.
- Le cinquième chapitre présente la méthode diviser-pou-régner depuis plusieurs exemples.
- On revient sur les tris au chapitre 6, où sont introduits le tri-fusion sur les listes et le tri-pivot sur les listes et les tableaux.
Travaux pratiques
- Le premier sujet aborde le problème de la recherche de la somme maximale de k termes non adjacents dans un tableau de différente manières. On commence par un algorithme glouton non exact mais rapide et on arrive à une solution exacte et rapide en passant par une écriture exhaustive itérative puis récursive. L'idée originale vient de B. Obled, enseignant de NSI au lycée Faidherbe. La richesse de ce TP fait qu'il sera abordé lors de 2 séances (4 heures).
- Le TP2 traite des codes de Gray.
- Le TP3 manipule les polynômes avec une représentation creuse.
- Le TP4 étudie le problème SSP (Subset Sum Problem) qui cherche s'il existe une partie d'une suite finie d'entiers dont la somme est recherchée. On étudie successivement une stratégie par brute force, une formulation récursive qui est optimisée à l'aide de la programmation dynamique.
- Le TP5 propose une utilisation de la mémoïsation appliquée au calcul du nombre de murs possibles si on les construits avec deux sortes de briques. C'est l'exposé de la solution proposée par Filliâtre du problème 215 du projet Euler.
Devoirs
Le premier devoir propose 3 sujets prévus pour une heure parmi lesquels chaque étudiant choisit 2 sujets. Il sont de difficulté croissante.
- Le premier sujet est une suite de 10 exercices partagés entre tableaux et listes.
- Le deuxième sujet implémente les opérations ensemblistes sur des ensembles d'entiers représentés pardes listes triées, il est tiré du concours E3A de 2012.
- Le troisième sujet est une adaptation de la première partie du concours X-ENS 2019. Aulieu de parler de sous-mots, on parle de suite extraites et on écrit seulement les algorithmes sous forme récursive sans améliorer la complexité par l'usage de la programmation dynamique. Il comporte de nombreuses questions théoriques.
Le devoir du 7 mai propose aussi 3 parties : 2 sujets courts dont le premier est tiré de E3A 2012, il porte sur l'implémentation des ensembles d'entiers par des listes et le second recherche un minimum local rapidement avec une méthode diviser pour régner.
Le troisième problème, plus long, reprend les deux premières parties de X-ENS 2022 ; il calcule le nombre optimal de multiplications pour un produit de matrices.
Les étudiants de MPSI1 ont eu l'occasion de vivre la fatigue des concours lors d'un concours blanc. Le sujet d'informatique option présentait des développements du tri fusion de listes par l'usage de parties déjà triées dans la liste initiale. Il met l'accent sur la stabilité du tri.