La science informatique est une science formelle, dont l’objet d’étude est le calcul au sens large, c’est-à-dire, non pas exclusivement arithmétique, mais en rapport avec tout type d’information que l’on peut représenter par une suite de nombres. Par conséquent, des textes, des séquences d’ADN, des images, des sons ou des formules logiques peuvent faire l’objet de calculs. Selon le contexte, on parle d’un calcul, d’un algorithme, d’un programme, d’une procédure.
Un algorithme se définit telle une méthode systématique permettant de réaliser des calculs afin d’obtenir des résultats. On cite souvent l’exemple de l’algorithme d’Euclide permettant le calcul du « Plus grand commun diviseur » (PGCD) qui remonte au moins à 300 ans avant J.-C. Avant cela, le simple fait d’utiliser un abaque demande d’avoir réfléchi à un moyen systématique (et correct) d’utiliser cet outil pour réaliser des opérations arithmétiques. Ce n’est cependant que depuis les années 1930, avec les débuts de la théorie de la calculabilité, que les scientifiques se sont posés les questions « qu’est-ce qu’un modèle de calcul ? », « est-ce que tout est calculable ? » et ont tenté d’y répondre formellement.
On trouve divers modèles de calcul. Les deux principaux sont la « machine de Turing » et le « lambda calcul ». Ces deux systèmes formels produisent des objets qui peuvent représenter ce qu’on appelle des procédures de calcul, des algorithmes ou des programmes. Ils définissent ensuite un moyen systématique d’appliquer ces procédures, c’est-à-dire de calculer.
L’algorithmique est l’étude comparative des différents algorithmes. Tous les algorithmes ne sont pas aussi efficaces et pertinents : le nombre d’opérations utiles afin d’obtenir un même résultat varie d’un algorithme à l’autre. Ce nombre d’opérations, appelé la complexité algorithmique, est le sujet de la théorie de la complexité des algorithmes, qui constitue une préoccupation essentielle en algorithmique.
