Premier jour (13 mars) :
- présentation générale :
- quelques mots sur l’algorithmique dans les programmes de math. et d’ISN,
- algorithme et programme,
- types de questions qu’on peut se poser pour comprendre un algorithme,
- programmation avec Xcas,
- terminaison, validité, complexité d’un algorithme et un problème de complexité adapté au lycée,
- iterated function systems : quelques algorithmes graphiques pour rire un peu en fin de journée.
Devoir à la maison : le problème des reines sur l’échiquier (pas de chance, c’est écrit « pour » Python...).
Deuxième jour (22 mars) :
- différents paradigmes de programmation : exposé par Emmanuel Coquery (département d’informatique de l’UCBL, LIRIS) ;
- algorithmes de tri (principe, mise en œuvre, complexité) : tri sélection, tri rapide ;
- aparté : arbres en algorithmique ;
- algorithmes gloutons : problème du gymnase (question du critère), problème du monnayeur ;
- essai de synthèse.
Troisième jour (dimanche 1er avril) :
- tri fusion ;
- problème du rendu de monnaie : comment déterminer si l’algorithme glouton est optimal pour un système de pièces donné ? problème et corrigé (Centrale 2001, tiré du site de l’UPS) ;
- algorithmes gloutons pour les arbres (recherche d’un arbre couvrant, algorithme de Dijkstra) ;
- parcours d’un arbre (en largeur, en profondeur) ;
- coloriage d’un graphe.
Commentaires