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)
Des petits challenges Blockly à résoudre dans un labyrinthe
Nous avons créé les stages Girls Can Code en 2014 avec Prologin
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)
Les projets des jeunes
Nos conseils de projets de code (initialement pour l’option ICN qui n’existe plus faute d’adoption)
Les ressources Terra Numerica
Les ressources Pixees
Les ressources de Marie Duflot-Kremer VP médiation de la SIF (avec âges)
Le Castor informatique du CM1 à la terminale passé par 700k étudiants
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
ICPC¶
Le concours ICPC est un concours de programmation en C, C++, Java parfois Python à 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.
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 (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.
