Il ne suffit pas de trouver un algorithme pour résoudre un problème donné. Il faut encore être sûr qu'il ne boucle pas indéfiniment et qu'il permet d'atteindre l'état désiré. En présentant un algorithme simple, élégant mais faux, on amène à réfléchir à la notion de correction d'algorithme.

Ça y est, nous avons trouvé (et formulé) un algorithme qui semble fonctionner parfaitement puisqu’il sʼadapte à tous les exemples que nous lui proposons. Mais comment sʼassurer que cela fonctionnera toujours, même dans des cas auxquels nous nʼavons pas pensé ? Et sʼil ne fonctionne pas, va-t-il simplement sʼarrêter sur un message dʼerreur ou se mettre à boucler indéfiniment en consommant toutes les ressources de mémoires et dʼénergie ? Cette question peut sʼavérer cruciale lorsque des vies humaines sont en jeu.

Baseball à plusieurs bases 

Dans cette version très particulière du baseball, des pions de couleur doivent retrouver leur base. Les bases sont disposées en cercle. À chaque base correspondent deux pions de la même couleur, sauf une qui ne possède qu’un seul pion de sa couleur. Il y a donc, à chaque moment du jeu, un trou dans lʼune ... Lire la suite