ALGORITHMES

théorie en 30 secondes

La révolution du XX^e siècle est celle de l’ordinateur. Pourtant, les ordinateurs ne sont rien sans programmes, et les programmes d’un ordinateur ne sont rien d’autre que des algorithmes. Un algorithme n’est pas compliqué : il est juste une liste d’instructions mettant à exécution une tâche où chaque étape est complètement sans ambiguïté. Il peut être mis à exécution par un agent irréfléchi. Le mot algorithme provient d’al-Khwarizmi qui découvrit les procédures infaillibles capables de résoudre certaines équations. Beaucoup de mathématiciens développèrent des idées similaires pendant des siècles, mais ce ne fut pas avant les années 30, avec les travaux de Alan Turing et Alonzo Church, que la notion d’algorithme se fit précise. Turing inventa un appareil contenant un « ruban », le long duquel une « machine de Turing » avance, écrivant et effaçant des symboles en accord avec de strictes règles internes. Turing utilisait cette machine théorique afin de démontrer qu’aucune procédure unique ne pourrait jamais répondre à chaque question mathématique. Même parmi les nombres entiers, il existe des problèmes « non calculables ». Ceci fait écho au théorème d’incomplétude de Gödel et fut un choc dans les mathématiques. Mais c’est lorsque la machine de Turing passa du domaine mathématique abstrait vers le monde réel que l’ordinateur naquit.

CONDENSÉ EN 3 SECONDES

Les algorithmes sont conçus comme des procédures théoriques pour mettre à exécution les tâches mathématiques. On les utilise constamment dans tous les ordinateurs du monde.

RÉFLEXION EN 3 MINUTES

Les plus grandes questions en science des ordinateurs concerne la rapidité des algorithmes. Par exemple, démarrez avec deux grands nombres premiers et multipliez-les ensemble. Le défi est de découvrir les deux nombres originels à partir du résultat final. Il existe un algorithme pour réaliser ceci, mais il peut prendre des millions d’années, même avec le processeur le plus rapide. Existe-t-il une manière plus prompte ? Personne ne le sait. Mais nous espérons que non, parce que c’est ainsi que notre compte en banque en ligne reste en sécurité !

THÉORIES LIÉES

ÉQUATIONS POLYNOMIALES

PROGRAMME DE HILBERT

THÉORÈME D’INCOMPLÉTUDE DE GÖDEL

AL-KHWARIZMI

BIOGRAPHIES EN 3 SECONDES

ALONZO CHURCH

1903–1995

STEPHEN KLEENE

1909–1994

ALAN TURING

1912–1954

STEPHEN COOK

1939–

TEXTE EN 30 SECONDES

Richard Elwes

Chaque programme d’ordinateur code un algorithme, une idée remontant au IX^e siècle.