La science informatique est une science formelle, son objet d'étude est le calcul, calcul au sens large, c'est-à-dire non limité exclusivement à la manipulation des nombres, mais de tout type d'information formelle que l'on peut traiter de manière systématique tel que : textes, couleurs, données, valeurs logiques. Selon les contextes, on parle d'un calcul, d'un algorithme, d'un programme, d'une procédure, etc.
Un algorithme est une manière systématique de procéder pour arriver à calculer un résultat. Un des exemples classiques est l'algorithme d'Euclide du calcul du « Plus grand commun diviseur » (PGCD) qui remonte au moins à 300 ans av. J.-C.
Mais il s'agit déjà d'un calcul complexe ; encore avant cela, le simple fait d'utiliser un abaque demande d'avoir réfléchi sur un moyen systématique (et correct) d'utiliser cet abaque pour réaliser des opérations arithmétiques.
Des algorithmes existent donc depuis l'Antiquité, mais ce n'est que depuis les années 1930, avec les débuts de la théorie de la calculabilité que les scientifiques se sont posés la question « qu'est ce qu'un modèle de calcul ? » et « est-ce que tout est calculable ? ». Une des premières choses a été pour les scientifiques de répondre de manière formelle à ces deux questions.
Il existe de nombreux modèles de calcul, mais les deux plus centraux sont les « machine de Turing » et le « lambda calcul ». Ces deux systèmes formels définissent des objets qui peuvent représenter ce qu'on appelle de 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.
Le résultat le plus important de la calculabilité est probablement la thèse de Church qui postule que tous les modèles de calcul ont la même puissance. C'est-à-dire qu'il n'existe pas une procédure que l'on pourrait exprimer dans un modèle mais pas dans un autre.
Un deuxième résultat fondamental est l'existence de fonctions incalculables. Une fonction étant ce que calcule une procédure ou un algorithme (ceux-ci désignant plutôt comment faire le calcul). On peut montrer qu'il existe des fonctions, bien définies, pour lesquelles il n'existe pas de procédure pour les calculer. L'exemple le plus connu étant probablement le problème de l'arrêt qui montre qu'il n'existe pas de machine de Turing calculant si une autre machine de Turing donnée s'arrêtera (et donc donnera un résultat) ou non. Selon la thèse de Church-Turing, tous les modèles de calcul sont équivalents, par conséquent ce résultat s'applique aussi aux autres modèles, ce qui inclut les programmes et logiciels que l'on peut trouver dans les ordinateurs courants. À noter qu'il existe un lien très fort entre les fonctions que l'on ne peut pas calculer et les problèmes que l'on ne peut pas décider (voir Décidabilité et indécidabilité).
Une fois la notion de calcul définie, la suite a été de se consacrer à l'algorithmique, c'est-à-dire l'étude des algorithmes.
Le but est trouver effectivement des procédures correctes et de les comparer entre elles. En effet, tous les algorithmes ne se valent pas : le nombre d'opérations nécessaires pour arriver au résultat diffère d'un algorithme à l'autre. Ce nombre d'opération, appelé la complexité algorithmique est le sujet de la théorie de la complexité des algorithmes, qui constitue une préoccupation essentielle en algorithmique.
La complexité algorithmique sert en particulier à déterminer comment le nombre d'opérations nécessaires évolue en fonction du nombre d'éléments à traiter (la taille des données) :
Nous arrivons maintenant un problème ouvert fondamental en informatique : « P est-il égal à NP ? »
En simplifiant beaucoup : P est « l'ensemble des problèmes pour lesquels on connaît un algorithme efficace » et NP « l'ensemble des problèmes pour lesquels on connaît un algorithme efficace pour vérifier une solution à ce problème ».
Et en simplifiant encore plus : existe-t-il des problèmes difficiles ? Des problèmes pour lesquels il n'existe pas d'algorithme efficace.
Cette question est non seulement d'un grand intérêt théorique mais aussi pratique. En effet un grand nombre de problèmes courants et utiles sont des problèmes que l'on ne sait pas résoudre de manière efficace. C'est d'ailleurs un des problèmes du prix du millénaire et le Clay Mathematical Institute s'est engagé à verser un million de $ aux personnes qui en trouveraient la solution.
Comme nous venons de le dire : c'est un problème ouvert, donc formellement il n'y a pas de réponse reconnue. Mais, en pratique, la plupart des spécialistes s'accordent pour penser que P≠NP, c'est-à-dire qu'il existe effectivement des problèmes difficiles qui n'admettent pas d'algorithme efficace.
Ce type de problème de complexité algorithmique est directement utilisé en cryptologie. En effet les méthodes de cryptologie modernes reposent sur l'existence d'une fonction facile à calculer qui possède une fonction réciproque difficile à calculer. C'est ce qui permet de chiffrer un message qui sera difficile à décrypter (sans la clé).
La plupart des chiffrements (méthode de cryptographie) reposent sur le fait que la procédure de Décomposition en produit de facteurs premiers n'a pas d'algorithme efficace connu. Si quelqu'un trouvait un tel algorithme il serait capable de décrypter la plupart des cryptogrammes facilement. On sait d'ailleurs qu'un calculateur quantique en serait capable, mais ce genre d'ordinateur n'existe pas, en tout cas pour le moment.
Plus récemment, et à la frontière avec la logique mathématique : la correspondance de Curry-Howard a jeté un pont entre le monde des démonstrations formelles et celui des programmes.
Citons aussi l'étude de la mécanisation des procédés de calcul et de pensée qui a permis de mieux comprendre la réflexion humaine, et apporté des éclairages en psychologie cognitive et en linguistique.