Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter l’auteur pour une utilisation commerciale) suivant la licence CC-by-nc-sa.
Nicolas Patrois propose quatre sites pour travailler et faire travailler la programmation, l’algorithmique et les mathématiques. Les deux premiers sont en anglais et peuvent donc se prêter à des activités pluridisciplinaires. Les deux suivants (en français) ont déjà été abordés dans cette revue : une piqûre de rappel peut s’avérer utile.
a) Code Abbey
Ce site russe [1] en anglais est tout récent (fin 2013) mais il propose un petit forum et plus de cent cinquante problèmes classés par catégories (les volumes selon la terminologie du site) :
- Beginner’s problems, des problèmes plutôt simples (calculs de sommes, de médianes, suite de Collatz, calcul modulaire, tri à bulle, suite de Fibonacci)
- Simple Math, des mathématiques pour le collège et le lycée (triplets pythagoriciens, suites, équation du second degré, PGCD, fonctions affines)
- Geometry basics, de la géométrie cartésienne plane (rotations, distance à un segment, courbes de Bézier, théorème de Pythagore)
- Simple Puzzles, pas toujours si simples (parenthésages corrects, recherche de chemin, interpréteur de Brainfuck++ [2], collier de perles, permutations)
- String Tricks, des chaînes de caractères (code César, palindromes, compter les voyelles, distance de Levenshtein, permutations circulaires, compression, expressions régulières)
- Game Logic, quelques simulations de jeux (pierre-papier-ciseau, serpent, échecs, jeux de dés, morpion, jeu de la vie, jeu de 2048)
- Graph Algorithms, leur construction et utilisation (génération de graphes, Dijkstra, voyageur de commerce, détection de cycle)
- Physics and Modelling, modélisation (notes de musique et gamme tempérée, balistique, probabilités, algorithme génétique)
- Advanced Math, des mathématiques au-delà du lycée (régression linéaire, gradient, inverse modulo, cryptographie ElGamal)
- Brainfuck puzzles, écrire un programme dans ce langage (écrire un nombre, addition, division par 2, Fibonacci, carrés)
- Challenges, la qualité de la solution amène un second défi (optimiser un résultat dans un graphe ou un jeu, la longueur du code Brainfuck)
- Popular algorithms, des algorithmes classiques (tas binaire, plusieurs tris simples, problème du sac à dos, algorithmes de compression)
Les catégories ne s’excluent pas les unes des autres, par exemple le problème Vowel Count est dans les catégories Beginner’s problems et String Tricks . Celui-ci demande de compter les voyelles de « mots ». Pour chaque problème, le site fournit plusieurs exemples pertinents, souvent très commentés et expliqués en détail avec quelques suggestions d’algorithmes ou de méthodes. Parfois, une page complémentaire est créée sur le wiki du site, un lien vers une ressource externe est souvent donné.
Par exemple, le site propose d’étudier le jeu de Tic-Tac-Toe (morpion). Il donne une suite des neuf mouvements et demande à partir duquel un des joueurs a gagné ou s’il y a match nul. Par exemple, pour la suite de mouvements 7-5-4-1-9-2-8-3-6 (voir ci-dessous les numéros des cases du jeu), le septième coup est gagnant. Pour s’amuser, le haut de la page propose d’y jouer seul au clavier.
Le site précise les informations données (elles sont dans le premier cadre gris). Il peut donner une liste de nombres à factoriser ou le plateau de jeu du serpent. Ces informations ne sont pas les mêmes d’un participant à l’autre ou d’un essai à l’autre si la réponse est erronée. La réponse est la plupart du temps une suite de nombres à coller dans le deuxième cadre gris, la forme précise est donnée, par exemple la précision minimale des nombres flottants. En cas d’erreur, la bonne réponse est donnée pour comparer avec la fausse. Le site exige de plus de copier l’intégralité du code utilisé pour résoudre le problème, ce qui est pratique si la réponse est refusée.
Ici, il est donné quinze listes de neuf mouvements pour le morpion. J’ai réussi ce problème, la page signale la présence de mon code source en Python. Noter qu’on peut stocker plusieurs codes mais dans des langages différents.
Ce site peut intéresser des élèves de TS spécialité ISN et leurs professeurs qui cherchent des idées de projets ou d’exercices d’entraînement.
b) Project Euler
Ce site propose un nouveau problème chaque week-end, ce qui donne un total de plus de 450 problèmes, majoritairement de mathématiques : arithmétique très souvent, parfois d’analyse ou de géométrie, parfois de théorie des jeux, de théorie des graphes ou de topologie. Les problèmes ne sont pas triés par catégories.
Le niveau est élevé, notamment après avoir résolu la première centaine de problèmes. Ils sont très souvent à tiroirs : pour résoudre le problème x, la résolution préalable du problème y (avec y < x) est fortement conseillée pour ne pas avoir à réinventer la roue ou pour trouver des algorithmes et des solutions plus rapides. De plus, un problème qui semble être géométrique peut cacher une étude arithmétique pour accélérer le programme qui, sans elle, tournerait pendant quelques années. Il est couramment admis qu’un programme qui tourne plus d’une minute n’est pas satisfaisant même s’il m’est arrivé de laisser tourner un code pendant quelques semaines.
L’énoncé de chaque problème est illustré la plupart du temps par un ou deux exemples. Chaque problème a une seule réponse possible, le code de l’algorithme utilisé n’est pas exigé puisque certains problèmes peuvent se résoudre à la main ou à la calculette.
Prenons par exemple le premier problème. Il s’agit de trouver la somme de tous les entiers strictement inférieurs à 1000 qui sont multiples de 3 ou de 5. Entrez la réponse dans la première zone de texte et le code anti-robot dans la deuxième.
Si votre réponse est fausse, vous obtiendrez la page frustrante avec le petit bonhomme qui doit encore se creuser la tête.
Une fois la bonne réponse donnée, on voit enfin le petit bonhomme qui se repose. Ici, je suis le 50998e à avoir résolu le problème 67 qui demande de calculer la plus grande somme dans une pyramide de nombres entiers (un seul nombre par ligne). Le cadre en bas indique que j’ai dorénavant accès au fil du forum dédié à ce problème, que je peux lire les solutions des autres et poster la mienne.
Ci-dessous, le début du forum pour le premier problème, les deux premiers ont répondu en assembleur.
Ce site pourra intéresser les habitués des problèmes du bulletin vert et les meilleurs étudiants du supérieur.
c) Deux autres sites
Les professeurs de collège et de lycée pourront se pencher sur le site du Castor informatique, un équivalent du concours Kangourou depuis 2010. Le concours se passe sur un ordinateur, chaque élève devant le sien pendant 45 minutes. Les sujets sont classés par niveau : sixième/cinquième, quatrième/troisième, seconde, première/terminale ou toutes les questions en une heure. Les questions peuvent être des QCM ou des applets sur lesquelles on répond directement. Les tâches sont variées : appliquer un algorithme simple, trier une liste, utiliser des transformations du plan, minimiser ou maximiser un trajet, utiliser la logique de Boole voire répondre à une question juridique.
Pour une initiation à la programmation proprement dite, le site de France IOI propose des cours d’algorithmique, de programmation et des exercices en relation, organisés en six niveaux. Les deux premiers sont accessibles à tous. Pour accéder aux deux suivants, il faut résoudre leurs exercices de déblocage. Quant aux deux derniers, il faut valider les niveaux précédents pour les débloquer. Le site accepte les réponses en C, C++, Pascal, OCaml, Java, JavaScool et Python, elles ont souvent des contraintes de temps d’exécution ou de mémoire et imposent des bibliothèques de programmation spécifiques à France IOI.