4. Calculabilité et algorithmique
Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agit là de l'un des célèbres théorèmes de Kurt Gödel. L'informatique rejoint la logique mathématique puisque l'on montre qu'il y a équivalence entre les mécanismes des langages de programmation décrits plus haut et la notion de calculabilité inventée par les logiciens. De cette unification résulte notamment qu'il ne saurait exister de programme permettant de vérifier tant la correction que la terminaison de tout programme. Le calcul a ses limites !
L'algorithmique s'attache à l'élaboration d'algorithmes efficaces pour résoudre les problèmes reconnus comme calculables. Cette discipline s'organise selon quelques grands principes généraux. Par exemple, pour traiter efficacement des problèmes de recherche d'information de forme complexe, il s'avère utile de superposer aux données un type de graphe particulier qui soit un arbre (en un sens voisin de ce qu'entendent les généalogistes). On crée alors une superstructure artificielle qui guide l'accès rapide aux données : c'est ce que l'on appelle une structure de données. De tels principes permettent d'accéder à des ensembles de données de natures très diverses. Ils sous-tendent également les programmes capables de reproduire certains aspects bien délimités de l'activité humaine, par exemple le jeu d'échec. Une algorithmique mise en place intelligemment permet – sans miracle – d'imiter une petite partie de l'intelligence humaine.
La qualité d'un algorithme ou d'un programme se jauge au nombre d'opérations de base qu'il met en jeu pour parvenir à ses fins, reflété par le nombre d'instructions effectuées par l'ordinat […]
… pour nos abonnés, l'article se prolonge sur 3 pages…
