Résolution de problèmes algorithmiques
On peut distinguer trois types de problèmes.
1. Résolution de problèmes algorithmiques
La résolution complète de problèmes au moyen d’une panoplie d’algorithmes. Par exemple :
- Sortir d’un labyrinthe
- Gagner au jeu des allumettes de Fort Boyard
- Plus court chemin entre deux points : TryAlgo in Paris
On trouve souvent ce problème dans les concours tels que Prologin, Google Code Jam, Meta Hacker Cup, ICPC, etc. Les organisateurs doivent avoir eux-mêmes la solution pour lancer le concours, et les candidats doivent la trouver.
2. Recherche opérationnelle
Là, on ne cherche plus à résoudre un problème complètement mais à trouver la meilleure solution possible, maximisant un certain score ou critère.
- Parcourir un maximum de Paris en 15 heures
- Heuristiques, comme pour rechercher un bon coup au go : Monte-Carlo Tree Search
En concours, on peut penser à Google Hash Code ou Primers. Les organisateurs n’ont pas besoin de connaître la meilleure solution.
3. La vraie vie
Là, le problème est que les problèmes sont souvent mal posés. Il faut donc en plus modéliser un problème, pour ensuite repasser au niveau 2 ci-dessus.
- Comment résoudre le problème du chômage ? Demandez à Paul Duan.
Il s’agit un peu de ce qu’on trouve dans les hackathons :
« Tiens, voilà nos données, vas-y, résous la faim dans le monde avec. »