Qu'est-ce que l'informatique ?
Partie 3 sur 3
6Une science, une technique, une industrie
L’informatique a plusieurs visages. Elle est d’abord une science, avec ses modèles, ses théorèmes et ses limites démontrées, une branche des mathématiques à part entière. Elle est aussi une discipline d’ingénieur, qui construit des systèmes fiables dans le monde réel, et une industrie qui pèse sur l’économie et la souveraineté des pays. Les sous-sections qui suivent présentent les grands résultats théoriques, accessibles sans formation mathématique particulière.
6.1La machine de TuringApprofondir
Avant même que les premiers ordinateurs électroniques fonctionnent, des mathématiciens se sont demandé ce qu’une machine peut calculer. En 1936, le Britannique Alan Turing décrit une machine abstraite, réduite à trois éléments :
- un ruban infini, divisé en cases, dont chacune contient un symbole ou rien ;
- une tête de lecture et d’écriture, placée sur une case, qui peut lire le symbole, en écrire un autre et se déplacer d’une case à gauche ou à droite ;
- une table de règles finie, qui dit, selon l’état de la machine et le symbole lu, quoi écrire, où aller et dans quel état passer.
Exemple : une machine qui ajoute 1 à un nombre écrit en binaire. Elle part du chiffre le plus à droite, dans un état appelé « retenue », et n’a besoin que de trois règles.
| État | Symbole lu | Symbole écrit | Déplacement | État suivant |
|---|---|---|---|---|
| retenue | 1 | 0 | une case à gauche | retenue |
| retenue | 0 | 1 | aucun | fin |
| retenue | case vide | 1 | aucun | fin |
Ce modèle paraît rudimentaire, mais il est universel. Turing montre qu’une seule machine bien construite, dite machine universelle, peut lire sur son ruban la table de règles d’une autre machine et l’imiter : c’est, dix ans avant sa réalisation, l’idée du programme enregistré. La même année, l’Américain Alonzo Church arrive à une définition équivalente du calcul par une autre voie, le lambda-calcul. La thèse de Church-Turing affirme que tout ce qui est calculable par une méthode systématique l’est par une machine de Turing. Ce n’est pas un théorème, car « méthode systématique » n’a pas de définition mathématique, mais aucun contre-exemple n’a jamais été trouvé : un ordinateur de 2026 ne calcule rien de plus qu’une machine de Turing, il calcule seulement beaucoup plus vite.
6.2Ce qu’aucun programme ne pourra faireApprofondir
Le résultat le plus célèbre de Turing est négatif. Il démontre qu’aucun programme ne peut décider, pour n’importe quel programme et n’importe quelle donnée, si ce programme finira un jour son calcul ou tournera sans fin. C’est le problème de l’arrêt. Le raisonnement, par l’absurde, tient en quelques lignes.
- Supposons qu’il existe un programme
ARRÊT(P, x)qui répond toujours correctement « s’arrête » ou « tourne sans fin » quand on lui donne un programmePet une donnéex. - Construisons alors le programme
PARADOXE(P): il appelleARRÊT(P, P); si la réponse est « s’arrête », il entre dans une boucle infinie ; si la réponse est « tourne sans fin », il s’arrête aussitôt. - Que fait
PARADOXE(PARADOXE)? S’il s’arrête, c’est queARRÊTa répondu « tourne sans fin » : contradiction. S’il tourne sans fin, c’est queARRÊTa répondu « s’arrête » : contradiction encore. - L’hypothèse de départ est donc fausse : le programme
ARRÊTne peut pas exister.
Cette branche de l’informatique théorique, la calculabilité, fixe les limites absolues de la discipline. Le théorème de Rice, démontré en 1953, généralise le résultat : aucune propriété non triviale du comportement d’un programme ne peut être décidée automatiquement dans tous les cas. Les conséquences sont très concrètes : aucun outil ne pourra jamais trouver tous les bogues d’un programme quelconque, ni reconnaître à coup sûr tous les logiciels malveillants (voir le coin cyber). Les outils réels contournent la difficulté : ils acceptent de se tromper parfois, ou de répondre « je ne sais pas ».
6.3Mesurer l’informationApprofondir
En 1948, l’ingénieur américain Claude Shannon publie Une théorie mathématique de la communication, qui fonde la théorie de l’information. Son idée centrale : la quantité d’information apportée par un message mesure la surprise qu’il provoque. Un événement de probabilité p apporte log2(1/p) unités d’information, appelées bits (contraction de l’anglais binary digit, chiffre binaire).
- Le résultat d’un pile ou face équilibré (p = 1/2) apporte log2 2 = 1 bit : il faut exactement un chiffre binaire pour le noter.
- Le résultat d’un dé à six faces apporte log2 6 ≈ 2,585 bits. Comme on ne peut pas écrire une fraction de chiffre, il faut 3 bits pour noter un lancer, mais on peut noter 5 lancers en 13 bits au lieu de 15, car 65 = 7 776 ≤ 213 = 8 192.
- Un message certain (p = 1) n’apporte aucune information : log2 1 = 0.
La moyenne de l’information apportée par une source s’appelle l’entropie. Une pièce truquée qui tombe sur pile 9 fois sur 10 a une entropie d’environ 0,47 bit par lancer seulement : ses résultats sont prévisibles, donc compressibles. C’est le principe de la compression de données : un texte en français, très redondant, contient bien moins d’information que le nombre de bits qui servent à l’écrire. Shannon estimait en 1951 que l’anglais écrit porte de 0,6 à 1,3 bit par lettre, alors qu’on en stocke 8 par caractère. La même théorie fixe la vitesse maximale à laquelle un canal bruité, comme une liaison radio, peut transmettre sans erreur ; elle sous-tend les codes correcteurs d’erreurs du Wi-Fi, de la 5G ou des QR codes.
6.4Le coût d’un calcul : la complexitéApprofondir
Savoir qu’un problème est calculable ne suffit pas : encore faut-il le résoudre dans un temps raisonnable. La complexité mesure le nombre d’opérations, ou la mémoire, qu’il faut pour résoudre un problème en fonction de la taille n des données. Le tableau montre pourquoi l’ordre de grandeur compte davantage que la vitesse de la machine.
| Nombre d’opérations | n = 10 | n = 100 | n = 1 000 | n = 1 million |
|---|---|---|---|---|
| n (parcourir une liste) | 10 ns | 100 ns | 1 µs | 1 ms |
| n log2 n (bon algorithme de tri) | 33 ns | 0,7 µs | 10 µs | 20 ms |
| n2 (comparer chaque paire) | 100 ns | 10 µs | 1 ms | 17 min |
| 2n (essayer toutes les combinaisons) | 1 µs | 40 000 milliards d’années | hors de portée | hors de portée |
Les problèmes que l’on sait résoudre en un temps polynomial, comme n2 ou n3, forment la classe P. Ceux dont on peut au moins vérifier rapidement une solution forment la classe NP, qui contient P : retrouver le meilleur trajet d’un livreur passant par 50 villes est très difficile, mais vérifier qu’un trajet proposé fait moins de 1 000 km est immédiat. Savoir si P = NP est l’une des plus grandes questions ouvertes des mathématiques : l’Institut Clay l’a inscrite en 2000 parmi ses sept « problèmes du millénaire », dotés chacun d’un million de dollars. La sécurité de la cryptographie repose sur cette difficulté : un chiffrement est sûr tant qu’aucun algorithme rapide ne permet de le casser.
6.5Une discipline d’ingénieur et une industrieApprofondir
L’autre visage de l’informatique est celui de l’ingénierie : concevoir des systèmes qui fonctionnent dans le monde réel, avec des contraintes de coût, de délai, de fiabilité et de sécurité. Un logiciel bancaire ou le système de pilotage d’un métro comptent des millions de lignes de code, écrites par des centaines de personnes, et doivent fonctionner des années sans interruption. Le génie logiciel, la gestion de projet ou l’exploitation des centres de données sont nés de ces exigences.
L’informatique est enfin une industrie et un enjeu politique. En France, le Plan Calcul, lancé en 1966, visait à doter le pays d’une industrie informatique indépendante ; l’Institut de recherche en informatique et en automatique (IRIA, aujourd’hui Inria) a été créé dans ce cadre en 1967. La question de la souveraineté numérique, c’est-à-dire de la maîtrise des technologies dont dépend un pays, n’a jamais quitté le débat public depuis.
Pour s’exercer
Exercice 2 : faire tourner la machine de Turing
Exécutez la machine du Tableau 2 sur le ruban 0111, puis sur le ruban 111, la tête partant chaque fois du chiffre le plus à droite. Qu’obtient-on ?
Voir la réponse
Sur 0111 : les trois 1 deviennent des 0 l’un après l’autre, puis le 0 devient 1 et la machine s’arrête. On obtient 1000, c’est-à-dire 7 + 1 = 8. Sur 111 : les trois 1 deviennent des 0, puis la tête arrive sur la case vide à gauche, y écrit 1 et s’arrête. On obtient 1000 : la troisième règle permet au nombre de s’allonger d’un chiffre.
Exercice 3 : combien de bits ?
(a) Combien de bits faut-il au minimum pour donner un numéro différent à chacune des 26 lettres de l’alphabet ? (b) Quelle quantité d’information apporte un code PIN à quatre chiffres tiré au hasard ? (c) Et un mot de passe de 8 caractères tirés au hasard parmi 26 lettres minuscules ?
Voir la réponse
(a) 4 bits donnent 24 = 16 numéros, trop peu ; 5 bits en donnent 25 = 32, assez. Il en faut donc 5 (l’information exacte, log2 26 ≈ 4,7 bits, est inférieure). (b) Il y a 104 = 10 000 codes possibles : log2 10 000 ≈ 13,3 bits. (c) 268 ≈ 2,1 × 1011 possibilités, soit 8 × 4,7 ≈ 37,6 bits. Chaque bit supplémentaire double le nombre d’essais nécessaires à un attaquant : c’est pourquoi on parle de l’entropie d’un mot de passe.
Exercice 4 : un antivirus parfait est-il possible ?
Un éditeur affirme que son antivirus reconnaît à coup sûr n’importe quel logiciel malveillant, y compris ceux qui n’existent pas encore. Que penser de cette promesse ?
Voir la réponse
Elle est impossible à tenir. Être malveillant est une propriété du comportement d’un programme ; d’après le théorème de Rice (section 6.2), aucun programme ne peut la décider dans tous les cas. Le chercheur américain Fred Cohen l’a démontré dès 1984 pour les virus informatiques. Les antivirus réels combinent des signatures de logiciels connus et des règles de comportement suspect : ils ratent certains logiciels malveillants et en signalent parfois à tort. C’est une raison de plus pour multiplier les protections au lieu de tout miser sur un seul outil.
Exercice 5 : l’effet de la taille des données
Un programme dont le nombre d’opérations croît comme n2 traite 10 000 fiches en 1 seconde. Combien de temps lui faut-il pour 100 000 fiches ? Et un programme en 2n, qui traite 40 éléments en 1 seconde, combien de temps met-il pour 50 éléments ?
Voir la réponse
Les données sont 10 fois plus nombreuses ; le temps est multiplié par 102 = 100 : 100 secondes. Pour le second programme, 10 éléments de plus multiplient le temps par 210 = 1 024 : environ 17 minutes. Avec 60 éléments, il faudrait plus de 12 jours. Acheter une machine deux fois plus rapide ne fait gagner qu’un élément.
7Repères chronologiques
L’histoire complète fait l’objet de l’article Histoire de l’ordinateur. Les dates suivantes donnent les grandes étapes.
- Blaise Pascal construit la Pascaline, une machine à additionner et à soustraire mécanique.
- Le métier à tisser de Joseph Marie Jacquard est commandé par des cartes perforées : une forme de programme.
- Ada Lovelace publie un algorithme destiné à la machine analytique de Charles Babbage, qui ne sera jamais construite.
- Les machines à cartes perforées d’Herman Hollerith dépouillent le recensement américain ; son entreprise est l’un des ancêtres d’IBM.
- Alan Turing définit mathématiquement ce qu’est un calcul.
- L’ENIAC, premier calculateur électronique programmable à usage général, entre en service aux États-Unis ; John von Neumann décrit l’architecture à programme enregistré.
- Invention du transistor aux laboratoires Bell.
- Claude Shannon fonde la théorie de l’information.
- Premier circuit intégré, qui réunit plusieurs composants sur une même puce.
- Philippe Dreyfus crée le mot « informatique ».
- Premier échange sur ARPANET, l’ancêtre d’Internet.
- Premier microprocesseur commercial, l’Intel 4004 : un processeur entier sur une seule puce.
- L’IBM PC lance la diffusion massive de l’ordinateur personnel.
- Tim Berners-Lee invente le Web au CERN, le laboratoire européen de physique des particules.
- Les smartphones à écran tactile mettent un ordinateur connecté dans chaque poche.
- Les intelligences artificielles génératives, capables de produire du texte et des images, arrivent auprès du grand public.