Enseignement

MPSI (2014)

Cours d'option informatique en MPSI.

Liens utiles:

• l'environnement WinCaml
• référence du langage Caml (en)
• téléchargement de Caml
• un bon livre d'algorithmique (en)
• cours d'introduction à l'informatique du MIT (en)

Cours et sujets de TP :

• semaine 1 (introduction à Caml light) :

  • pdf du cours
  • sujet de tp
  • corrigé tp1 Lisez bien le corrigé !

• semaine 2 (introduction à Caml light, partie 2) :

  • pdf du cours
  • sujet du tp2 (DM)
  • corrigé du tp2

• semaine 3 (correction tp2) :

  • sujet du tp3 (avec des éléments de cours)
  • corrigé du tp3

• semaine 4 (types algébriques et listes) :

  • pdf du cours
  • moult fonctions sur les listes dans une bibliothèque OCaml

• semaine 5 (révisions) :

  • pdf résumé sur Caml
  • exercices divers
  • (corrigé bref des exercices)

• semaine 6 (DS n°1) :

  • corrigé MPSI5
  • corrigé MPSI1 et 2

• semaine 7 (diviser pour régner) :

  • pdf du cours

• semaine 8 (diviser pour régner) :

  • sujet du tp5 (TP + DM)
  • fonctions d'aide
  • corrigé
  • graphe de complexité des tris

• semaine 9 (structures de données 1) :

  • cours

• semaine 10 (structures de données 1, suite) :

  • tp 6
  • fonctions d'aide
  • corrigé du tp6 (ne lire qu'en dernier recours)

• semaine 11 (structures de données 2) :

  • cours
  • mots à compter (dernière partie du cours)

• semaine 12 (structures de données 2, suite) :

  • même cours qu'en semaine 11
  • sujets TPs pour s'entraîner (ancien cours de Vincent Simonet, sous license GPL) :
    • arbres binaires de recherche
    • allocateur mémoire (listes)
    • compression LZW (voir aussi la page wikipédia de l'algorithme)

• semaine 13 :

  • DS commun mercredi 28 mai 2014 de 14h à 16h (salle M069 a priori)
    • bases du langage
    • listes
    • diviser pour régner
    • structures de données
  • sujet du ds
  • corrigé du ds
  • horaire habituel: séance de révisions
    • possibilité d'y déplacer une colle du mercredi après-midi
    • refaire d'anciens TDs, exercices...

• semaine 14 (programmation dynamique) :

  • pdf du cours
  • code Caml annexe

• semaine 15 :

  • correction du DS n°2
  • exercices du cours précédent

• Semaine 16 :

  • tp bonus : labyrinthe (© Vincent Simonet)
  • solution étendue (en OCaml) à fin d'illustration
  • vidéo du programme OCaml en action
  • démo en javascript (compilé depuis OCaml via js_of_ocaml)

• Semaine 17 :

  • Pour ceux qui le souhaitent, les fractales se dessinent bien avec l'interface Graphics de la semaine dernière. Notons en particulier Le flocon de Koch et l'ensemble de Julia.
    • pour le flocon, on peut commencer par générer une liste de segments à tracer, puis implémenter flat_map : ('a -> 'b list) -> 'a list -> 'b list pour transformer chacun de ces segments en une liste de plus petits segments. On itère ce procédé un nombre fixe (par exemple 4) de fois et on trace le contour décrit par les segments.
    • pour l'ensemble de Julia, on s'intéresse à la suite z(n+1) = z(n)² + c avec z et c des nombres complexes. Par exemple on peut choisir c = 0.295 + 0.01i. Pour chaque point z = x+iy du plan, on calcule le nombre d'itérations nécessaire pour que |z| > 2 (avec une limite), et ce nombre d'itérations donne la couleur du point en x, y. Penser à zoomer (diviser les coordonnées par 200 pour passer de coordonnées pixel aux coordonnées dans Z) pour voir quelque chose.
    • galerie

Révisions de Vacances

Je vous conseille de réviser attentivement les cours pendant l'été, pour ne pas prendre de retard en début de spé. Je répondrai à toute question par mail.

En passant, ce blog a de magnifiques visualisations d'algorithmes (par exemple de tris).

Contact

Pour me contacter, écrire à simon point cruanes arobase inria point fr.