Documents (algorithmique mars 2012)
mardi 27 mars 2012
par , ,
par , ,
Documents proposés pendant le stage des 13 et 22 mars 2012.
Mise à jour le 27 mars : ajout des documents du 22 mars.
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.
Documents joints
- Introduction générale
- Programmation avec Xcas et Python
- Terminaison, validité, complexité
- Triangles : complexité pour le lycée
- IFS : des algorithmes graphiques
- DM : les reines sur l'échiquier
- Tri sélection
- Tri rapide
- Arbres
- Algorithmes gloutons : gymnase
- Algorithmes gloutons : monnaie
- Essai de synthèse
- Problème du monnayeur (énoncé)
- Problème du monnayeur (corrigé)
- Algorithmes gloutons : arbres couvrants et (...)
- Parcours d'un arbre
- Coloration d'un graphe
- Tri fusion
- Les fichiers xcas
Commentaires