Présentation du site
Ce site présente mon poly de cours autour du programme de MP2I/MPI, et donc également du programme d’option informatique de MPSI/MP et du tronc commun.
La progression sur les deux années n’est pas indiquée mais les chapitres suivent les programmes.
On pourra trouver des exercices et des TP complets au sein des chapitres.
Attention beaucoup de ces chapitres sont mis en ligne sans avoir été relu ou dans un état très peu avancé. Pour mes élèves, le cours est refait en classe et ne suit pas forcément le poly, ils ont donc une version souvent bien plus complète de certains chapitres. Cela sera amené à être finalisé dans les prochaines années.
Sources
Il serait trompeur d’affirmer que tout ce qui est présenté ici est de mon invention et illusoire de penser que ce serait possible de travailler indépendamment de références.
Voici ici mes principales sources :
Erickson, Algorithms : ma source principale pour la MP2I et une bonne partie de la MPI. Ce livre est exceptionnel et en plus, il est libre, donc on peut librement l’utiliser. Ainsi, des exercices et des exemples sont exactement ceux de ce livre.
Vous pouvez trouver ce livre en ligne ici algorithms.wtf.
Sedgewick, Algorithms : des points de vue intéressants sur les structures de données. Principalement, l’explication des arbres rouges-et-noirs comme binarisation des arbres 2-3.
Cormen, Leiserson, Rivest, Introduction to algorithms : pendant longtemps, la principale source des cours d’algorithmique. Maintenant que d’autres alternatives existent, je trouve les preuves souvent beaucoup trop complexes avec un peu trop d’attention sur les détails plutôt que sur l’idée maîtresse. Beaucoup d’exercices.
Skiena, “The Algorithm Design Manual* : le style de ce livre est un peu particulier, mais il a un point de vue beaucoup plus pragmatique que les autres livres d’algorithmique. Beaucoup d’idées peu développées qui peuvent donc être une grande source d’inspiration.
Vazirani, Approximation algorithms : un livre dédié aux algorithmes d’approximation. Cela constitue une petite partie du programme de MPI, mais ce livre est de très loin la référence la plus riche.
Motwani, Raghavan, Randomized algorithms : un livre dédié aux algorithmes probabilistes. Comme pour le précédent, il s’agit d’une référence dont on n’étudie qu’une minuscule partie en MPI.
Mode de production des documents
J’utilise un système maison construit autour de pandoc
et de templates pour présenter des documents les plus natifs possibles
quel que soit le format.