Apprentissage du code par la pratique

Salut à tous,

Il y a quelques jours avec Loick on s'est mis en tête d'essayer de faire quelques exos de programmation à but pédagogique et tournés vers la pratique du code (on bosse tous les deux chez CodinGame). On s'est donc lancé dans ce mini-projet parce que l'idée nous bottait bien et parce que la plate-forme nous semble appropriée pour faire des choses sympas. Nous avons fait deux exos pour essayer, chacun dans leur style et j'aimerais les partager avec vous pour savoir ce que vous en pensez :

Apprendre rapido un algo de tri simple (plutôt facile)

Apprendre un algo de recherche de chemin le plus court (plus difficile)

L'idée c'est de savoir si on devrait continuer à en faire d'autres, et pour cela, vos retours, idées et critiques sont les bienvenues.

Merci!

Frédéric

Le bubblesort me fait penser à une conf donnée par Stepanov où il s'attaquait à ces cours et exos qui commençaient toujours par montrer des mauvais algos, que personne n'utilise jamais en plus. Typiquement, le bubblesort n'est pas une base de l'algorithmie qu'il faut montrer à chaque fois. Pourquoi ne pas commencer par un truc plus intelligent à base de tri dichotomique ?

L'idée d'une telle plateforme est très intéressante sinon. Il faudra d'ailleurs montrer en quoi elle se distingue de France IOI.

PS: les ignore ne servent à rien ici.
PPS: les zones devraient être à taille dynamique (proportionnelles) et non absolues. J'ai un écran large, et pourtant tout ne rentre pas – et non, CTRL-moins n'est pas une réponse.

Merci pour ton retour.

cin.ignore() : les squelettes de code sont générés automatiquement en fonction du problème dans les 20 langages supportés, et je confirme que certains générateurs insèrent parfois des trucs inutiles (mais pas bloquant).

Salut,

J'aime bien Codingame. Comme l'a dit lmghs, il faut voir en quoi il se distingue de France IOI.
Le goût que vous mettez à faire des animations soignées me plaît beaucoup; vos explications sont de bonne qualité.
Mais je trouve que le gros point fort de codingame est de proposer des problèmes dont les seules solutions (enfin les seules qui soient raisonnable en terme de temps de calcul) soient des heuristiques (je pense notamment à Mars Lander, à moins qu'il existe un algorithme exact ?).

J'aimerais beaucoup que vous vous dirigiez vers une plateforme d'entraînement sur des exercices de type algorithmes génétiques, algorithmes gloutons, minimax, alpha-bêta, recherche en faisceau, SRBF, A, recuit-simulé, etc… (je vous une liste en vrac des premiers trucs qui me passe par la tête) il existe assez peu de plateformes à proposer l'apprentissage de ces notions. Un tutoriel suivi d'un TP peut être une excellente chose. Bien évidemment il s'agit de donner un aperçu de ces notions qui peuvent être parfois très ardues mathématiquement si on tente de les aborder de façons exhaustive.

Typiquement, le bubblesort n'est pas une base de l'algorithmie qu'il faut montrer à chaque fois.

Je pense que si, au contraire. Pas pour ses applications, car sa complexité est pourrie, et même en pratique il est plus lent que les autres tris quadratiques en temps.
Cependant il constitue un entraînement sympa nécessaire à l'apprentissage. De la même façon qu'on continue d'enseigner Euclide au collège alors qu'on ne fait quasi-plus de géométrie (enfin, plus sous cette forme) dans le supérieur (ça me fait d'ailleurs penser à ça).

Le bubble sort est un gros hack dégueulasse. Même les tris par insertion ou par sélection sont plus intuitifs sur le plan algorithmique. L'étape intéressante d'après, c'est pas les feintes dégueulasses, c'est l'approche dichotomique.

Pourquoi je dis que c'est une feinte dégueulasse : ça part d'un truc pas terrible en O(N²), et on se pose la question comment faire moins de comparaisons. Et puis un jour, quelqu'un partage son astuce de Grand-Mère : "Et si on échangeait deux à deux les éléments contigus mal positionnés? C'est rigolo ! Et si on continuait ? Ouah… c'est trié!". Je reste assez dubitatif face à cette approche. Surtout si on ne se contente que de la donner et pas de permettre aux élèves de chercher une bidouille par eux-même pour qu'il expérimentent la seule chose qui est vraiment importante dans le bubble sort : la recherche d'une solution globale par trial & error.

Mais je trouve que le gros point fort de codingame est de proposer des problèmes dont les seules solutions (enfin les seules qui soient raisonnable en terme de temps de calcul) soient des heuristiques (je pense notamment à Mars Lander, à moins qu'il existe un algorithme exact ?).

En quoi est-ce un point fort puisque le monde entier cherche justement des solutions non-heuristiques a ces problemes ?

Pour Mars Lander ca fait un moment qu'on sait faire des trucs aussi simples tout de meme ! C'est presque insulter 200 ans de recherche sur le sujet.

Pour Mars Lander ca fait un moment qu'on sait faire des trucs aussi simples tout de meme !

"On" peut-être, moi pas. Et ça me permet d'apprendre. Codingame n'a pas pour vocation à être le fleuron de la recherche (enfin, je ne pense pas), mais une plateforme de défis et d'apprentissage.

Tu n'as pas répondu à ma question. En quoi est-ce un point fort d'après toi ?

Et sinon, ce n'est pas tellement par l'informatique et ce genre de plateforme que tu apprendras à résoudre ce genre de problèmes mais plutôt avec en amont un papier, un crayon et un bon bouquin de Commande optimale et qui permet de répondre à des questions comme : quels sont les systèmes observables, contrôlables, stabilisables, etc.
Si la recherche est évidemment toujours très active et féconde là dessus, prétendre qu'on ne peut rien faire sans être le fleuron de la recherche c'est faux vu que beaucoup de résultats forts proviennent d'au moins 70 à 200 ans (et c'est autant exagérer que de dire que faire poser un robot 2D dans un jeu vidéo avec peu de contraintes c'est la même chose que de poser un robot sur Rosae - Ho wait ? C'est exactement ce que tu viens de faire). Mais c'est toujours la même histoire, dès qu'on veut attirer l'attention sur le fait que pour la moindre application "marrante" et pas tout à fait académique il faut sortir la tête du guidon, i.e. du code, pour faire des maths (autre que 2+2) pour obtenir des résultats intéressants, on est taxé d'élitiste académicien.

on est taxé d'élitiste académicien

Je pense que le problème vient du fait (pas seulement sur ce sujet mais sur un grand nombre de ceux sur lesquels tu interviens) que tu ne t'adresses pas à la zone proximale de développement de ton interlocuteur.
La plupart de ton propos est sûrement pertinent, mais souvent à un niveau trop élevé pour que tu sois compris. Les seuls qui soient en mesure de te comprendre n'en tire par profit, d'ailleurs, puisqu'ils connaissent déjà de quoi tu parles.
Mon niveau en mathématique est faible (bac +1). Je commence tout juste à raisonner, et à acquérir les outils de base. Dans ces conditions, me catapulter un livre sur un sujet présupposant une certaine aisance en maths (comme tu viens de le faire) ne m'est d'aucune utilité.
A cela j'ajouterais que c'est un grand bien de faire 2+2 avant de passer à des choses plus ardues, ça fait parti de l'apprentissage. Même remarque pour la simulation 2D avec peu de contraintes, faut passer par là avant de s'attaquer à la commande optimale, je pense.
Et ça répond à ta première question : pour moi c'est un point fort parce que ça me permet de réfléchir au problème, de le résoudre, et progresser. Et c'est suffisant. Les fondations ont autant de valeur que la cathédrale qu'on pose par dessus.