Problèmes d’algorithmique

Avec Christoph Dürr, j’anime le site TryAlgo, qui regorge de problèmes algorithmiques.

Apprendre à coder

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 :

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 :

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 (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

../_images/fautealgo.png

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.

Voir les épisodes.