Exposé n° 91 : Algorithmique efficace : survol grâce au « problème du nombre manquant »

Un algorithme est une méthode informatique de résolution d’un problème. Les algorithmes sont omniprésents dans notre quotidien : pour la prise de décisions, pour optimiser ses dépenses, pour planifier un repas, pour décorer une pièce, … Pour résoudre un problème donné, certains algorithmes se révèlent plus efficaces que d’autres, que ce soit en rapidité d’exécution ou en consommation mémoire. Cette notion d’efficacité sera mise en évidence à partir d’un problème informatique fort simple, résolu à l’aide de différents algorithmes. Soit un tableau à N-1 positions qui contient des nombres entiers distincts entre 1 et N. Un des nombres entre 1 et N est donc absent, il faut l’identifier. Nous présenterons des algorithmes de plus en plus performants pour résoudre ce problème.

Exposé proposé par Olivier Delgrange.