Les documents présentés ici sont un support pour le cours d'option informatique de MPSI que je dispense au LIV depuis 2011 (en colaboration avec M. de Falco et V. Prunet, puis avec L. Pottier et J-P. Tecourt). Pour commencer, voici un document résumant ces cours.
Ci-dessous sont présentés des slides un peu plus détaillés, en particulier en ce qui concerne les exemples en Caml.
Les slides ne sont (volontairement) a priori pas écrits pour servir de support au professeur lors de son cours (les slides sont souvent trop denses pour cela) mais contiennent tous les éléments qui doivent être connus par les étudiants.
Notons enfin que le langage de programmation servant d'illustration est le Caml (si vous programmez en OCaml (ou un autre langage), il faudra adapter les programmes proposés).

1. Introduction à l'algorithmique
   
   • Qu'est-ce qu'un algorithme ?
   • CAML pour les nuls
     • Types et Opérations élémentaires
     • Variables
     • Fonctions
   • Boucles: If, For, While
   • Algorithmes récursifs
2. Prouvons que nos algorithmes sont corrects
   
   • Terminaison + Correction d'un algorithme
   • Exemples d'algorithmes itératifs et de leurs preuves de correction
     • Somme des n premiers entiers
     • Exponentiation, calcul de n^c
     • Recherche de maximum dans un tableau
     • Logarithme en base b
     • Évaluation de polynôme
     • Tri (par sélection) des éléments d'un tableau
     • Calcul de pgcd : Algorithme d'Euclide
   • Exemples d'algorithmes récursifs
     • Somme des n premiers entiers
     • Exponentiation, calcul de n^c
3. Complexité temporelle des algorithmes
   
   • Introduction à la complexité temporelle
   • Somme des n premiers entiers, naïf : O(n) ou, en réfléchissant : O(1)
   • Évaluation de Polynômes de degré n, Méthode de Horner O(n)
   • Exponentiation rapide, O(log c)
   • Recherche dans un tableau de longueur n : non trié O(n), trié O(log n)
4. Algorithmes de Tri de n éléments (et leur complexité temporelle)
   
   • Algorithme de Tri par Sélection, O(n²)
   • Algorithme de Tri par Insertion, O(n²) en pire cas
   • Algorithme de Tri à Bulles, O(n²) en pire cas
   • Algorithme de Tri Fusion, O(n log n) en pire cas
   • Au delà du Tri Fusion
   • Algorithme de Tri Rapide (DS 2013/14), O(n²) en pire cas, O(n log n) en moyenne
   • Algorithme de Tri par Tas (DS 2012/13, concours E3A 2006), O(n log n) en pire cas
5. Diviser pour Régner
   
   • Diviser pour Régner
   • Multiplication de matrices n*n
     • Algorithme naïf, O(n³)
     • Algorithme de Strassen, O(n^2.8)
   • Multiplication de Polynômes de degré n
     • Algorithme naïf, O(n²)
     • Algorithme de Karatsuba, O(n^1.585)
     • Transformée de Fourier (DS 2011/12), O(n log n)
6. Programmation dynamique
   
   • Problème de Rendu de Monnaie (rendre un montant M avec un système de n types de pièces)
   • Problèmes de Décision/d'Optimisation
   • Problème de Rendu de Monnaie : algorithme glouton et 1er algorithme exact (complexité : temps et espace O(Mn))
   • Programmation dynamique
   • Problème de Rendu de Monnaie : 2nd algorithme exact (complexité : temps O(Mn) et espace O(M))
   • Problème du Sac-à-Dos (avec/sans remise)
   • Pour les Exemples d'application suivants, nous proposons des algorithmes naifs, puis utilisant Diviser pour régner, et enfin par Programmation dynamique.
     • Nombres de Catalan : Chasse aux fantômes (Section 2 du DS 2014/15, concours Centrale-Supélec 2009)
     • Multiplication d'une séquence de matrices (Section 2 du DS 2015/16)
     • Distance d'édition : Similarité entre 2 séquences (Section 1 du DS 2016/17)
     • Élément majoritaire dans une séquence (Section 2 du DS 2016/17)
7. Graphes et Arbres
   
   • Graphes et Arbres
   • Arbres et Arbres Binaires en CAML
   • Parcours en profondeur (DFS) et en largeur (BFS) (Application : DS 2012/13)
   • Exemples de programmation dynamique dans les arbres (Couverture-sommet et ensemble dominant)