Option informatique, seconde année
Devoirs
- Le premier devoir de spé MP1 portait sur les arbres binaires : les arbres d'intervalles (extrait et adapté de CCP 2010) et le codage de Huffman (partie algorithmique de Mines 2006).
Il donné avec une proposition de correction.
Un devoir plus difficile a été proposé en parallèle : c'est le sujet du concours des ENS 1997 (non couplé au concours de l'X à l'époque). Il contient des parties non encore vues dans le cours et est parfois mal rédigé. Le corrigé proposé contient des déviations par rapport au sujet afin de donner des réponses qui ont semblé raisonnables.
- Le deuxième DS portait sur le problème SAT, posé aux mines en 2010.
Le sujet plus difficile était le problème d'info-math des ENS de 2017, sur les mots (infinis) sans carré.
- Le troisième DS était le sujet des mines 2012 (hors l'exercice sur les langages).
Il était accompagné du rapport du jury.
Le corrigé reprend l'intitulé des questions, pour une lecture plus fluide.
Les étudiants pouvaient choisir de traiter le sujet X-ENS 2016, lui aussi accompagné de son rapport. Il contenait une question fausse, minimisée par le rapport mais néanmoins supprimée du texte fourni sur le site de l'école polytechnique ...
TP
Les TP sont rassemblés dans un poly. Les corrigés sont donnés après la fin des séances.
- Septembre : le TP 01 portait sur le tracé des arbres binaires et la structure d'arbre binaire de recherche équilibré AVL.
- Les 10 et 17 octobre le TP 02 compresse et décompresse un texte avec la méthode de Huffman.
- TP 03 (7 et 14 novembre) : on définit une structure de file de priorité persistante avec des tas sous forme d'arbre et on l'utilise pour chercher des propriétés sur les nombres de Huffman et d'autres nombres, appelés ici nombres taupins.
- Le TP 04 (21 et 28 novembre) programme la satisfiabilité d'une formule logique et l'applique à deux enigmes.
- Le TP 05 (5 et 12 décembre) étudie la coloration d'un graphe en reprenant le sujet X 2018.
- Le TP 06 (9 et 16 janvier) résout les sudokus par une méthode de backtracking.
- Le TP 07 (23 et 30 janvier) programme l'algorithme de Tarjan de recherche des composantes fortement connexes.
- Les 6 et 13 février, on traite le chapitre 6 du polycopié : la méthode de Ford-Fulkerson et algorithme de Edmonds-Karp de recherche d'un flot maximal.
- Le 12 mars a débuté un le TP 08 sur les langages dérivés.
- Un TP supplémentaire dans le poly, sur les expressions régulières.