Problèmes d’algorithmique¶
Avec Christoph Dürr, j’anime le site TryAlgo, qui regorge de problèmes algorithmiques.
Apprendre à coder¶
Essayez une heure de code : hourofcode.org/fr (notamment pour les enfants)
La plate-forme d’apprentissage France-ioi
JJ’s Code Week, du 8 au 14 décembre 2014
Stage de Python pour lycéens (par Science ouverte et Prologin)
Sujets de TP¶
Concours de programmation¶
On vous donne un problème à résoudre (par ex. trouver un chemin dans un labyrinthe qui mène à la sortie), des contraintes sur les données du problème (la taille du labyrinthe) et vous devez coder un programme qui renvoie, pour une instance donnée en entrée respectant les contraintes, une solution.
Les limites de temps font que votre programme doit non seulement renvoyer une solution correcte, mais de plus dans un temps raisonnable.
Prologin¶
Ouvert aux jeunes de 20 ans et moins : d’octobre à mai. Les sujets écrits des épreuves régionales couvrent des domaines variés de l’informatique théorique, par exemple :
amidakuji : The Final Problem (+ vidéo d’introduction, activez les sous-titres)
algorithme du lièvre et de la tortue : The Two-Ring Machine
2-approximation du voyageur de commerce : Distributions tempérées
jeux sur les arbres : Quart de singe
contamination dans les arbres : The Game
graphes dans certains jeux Nintendo : Dance floor
algorithmes streaming : Prologin Plays Pokémon
bin packing : Death Note
ordonnancement de tâches : The Shining
couverture minimale : MRKRPXZKRMTFRZ
code de Huffman : The Marchand Identity
arbre couvrant minimal distribué : The Imitation Game
à composante historique : Enigma
d’autres problèmes en vrac : MinisterMind, Comic-Con, Memento Somniare
ACM/ICPC¶
Le concours ACM/ICPC est un concours de programmation en C, C++ ou Java à destination des étudiants en licence ou master. La particularité : 10 problèmes, 5 heures, 3 étudiants, 1 seul clavier par équipe. C’est terrible.
Pour s’entraîner :
Le vivier d’exercices UVa Online Judge et son outil pour tester ses fichiers de test UVa Toolkit
La version polonaise spoj.com
La version chinoise poj.org
Les références bibliographiques ci-dessous.
Autres concours¶
Avec Alexis Comte et Stéphane Henriot, nous avons rédigé une liste des différents concours de programmation. En voici quelques-uns notables.
Google Code Jam : concours annuel débutant en avril, composé d’excellents sujets parfois très difficiles.
Codeforces : un site russe anglophone avec des concours fréquents d’excellente qualité (plusieurs par mois).
Bibliographie¶
Je ne recommande pas le Cormen que je trouve trop lourd, en revanche :
Programmation efficace de Vie-Dürr : implémentations efficaces en Python.
Éléments d’algorithmique de Beauquier, Berstel, Chrétienne (surnommé le BBC) : une référence pour les calculs de complexité et arbres équilibrés qui fait bien la distinction entre types abstraits (par ex. une file à priorité) et structures de données (par ex. un tas).
Algorithms de Sedgewick : jusqu’à notre livre, la seule référence d’une explication claire de l’algorithme de Knuth-Morris-Pratt.
La Faute à l’algo¶
La Faute à l’algo est une émission de 6 minutes sur Nolife coréalisée avec Michel Blockelet, sur le rôle grandissant de l’algorithmique dans nos vies.
