La science informatique est une science formelle, son objet d'étude est le calcul²¹, calcul au sens large, c'est-à-dire pas exclusivementarithmétique, mais en rapport avec tout type d'information que l'on peut représenter de manière symbolique par une suite de nombres. Ainsi, par exemple, textes, séquences d'ADN, images, sons ou formules logiques peuvent faire l'objet de calculs. Selon les contextes, on parle d'un calcul, d'un algorithme, d'un programme, d'une procédure, etc.

*Calculabilité

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 lacalculabilité que les scientifiques se sont posé les questions « qu'est-ce qu'un modèle de calcul ? » et « est-ce que tout est calculable ? » et ont tenté d'y répondre formellement.

Il existe de nombreux modèles de calcul, mais les deux principaux sont la « machine de Turing » et le « lambda calcul ». Ces deux systèmes formels définissent 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.

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é).

*Algorithmique

L'algorithmique est l'étude comparative des différents algorithmes. Tous les algorithmes ne se valent pas : le nombre d'opérations nécessaires pour arriver à un même 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) :

• soit l'évolution peut être indépendante de la taille des données, on parle alors de complexité constante ;
• soit le nombre d'opérations peut augmenter selon un rapport logarithmique, linéaire, polynomial ou exponentiel (dans l'ordre décroissant d'efficacité et pour ne citer que les plus répandues) ;
  • une augmentation exponentielle de la complexité aboutit très rapidement à des durées de calcul déraisonnables pour une utilisation en pratique,
  • tandis que pour une complexité polynomiale (ou meilleure), le résultat sera obtenu après une durée de calcul réduite, même avec de grandes quantités de 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.

*Cruptologie

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 deDé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.

Rechercher sur le site