Chapitre 1

Modèles informatiques

L’aube de l’informatique moderne, dans les années qui ont immédiatement suivi la Seconde Guerre mondiale, a été caractérisée non seulement par l’ingéniosité pratique dans la construction des premières machines à calculer, mais aussi par l’établissement de bases théoriques solides qui guideront le développement de la discipline pour les décennies à venir. Dans ce chapitre, nous explorerons certains des modèles informatiques les plus influents qui ont jeté les bases de la compréhension et de la construction de systèmes informatiques.

1.1 La machine de Turing :
Définir les limites du calcul

En 1936, bien avant la construction des premiers ordinateurs électroniques, le mathématicien britannique Alan Turing a publié un article fondateur intitulé « Sur les nombres calculables, avec une application au problème de l'entscheidung ». Dans ce travail, Turing a proposé un modèle abstrait d'ordinateur, maintenant universellement connu sous le nom de Turing Machine . Il ne s’agissait pas d’une machine physique au sens traditionnel du terme, mais plutôt d’une construction théorique, d’une expérience de pensée conçue pour répondre à une question fondamentale et profondément philosophique : quels problèmes peuvent être résolus par un processus algorithmique, c’est-à-dire par une séquence finie d’instructions sans ambiguïté ?

Une machine de Turing est conceptuellement composée de :

Un ruban infini : Imaginez un ruban illimité dans les deux sens, divisé en cellules contiguës.

Chaque cellule peut contenir un seul symbole d'un alphabet fini, qui comprend au moins un symbole spécial pour indiquer une cellule vide (souvent noté « B » ou « □ »).

Une tête : Un mécanisme capable de se positionner sur une cellule spécifique de la bande. Cette tête a la capacité de lire le symbole présent dans la cellule actuelle, d'écrire un nouveau symbole dans la même cellule et de se déplacer d'une position vers la droite ou la gauche le long de la bande.
Un ensemble fini d'états : La machine est dans un état spécifique à tout moment. Cet ensemble d'états est fini et comprend un état initial (à partir duquel le calcul commence) et un ou plusieurs états finaux (ou d'acceptation), qui indiquent la fin d'un calcul réussi.
Une fonction de transition : Le cœur de la machine de Turing est sa fonction de transition. Cette fonction, qui peut être représentée sous forme de tableau ou d'ensemble de règles, détermine le comportement de la machine à chaque étape. En fonction de l'état actuel de la machine et du symbole lu par la tête, la fonction de transition spécifie de manière unique trois actions : Le symbole à écrire dans la cellule actuelle (qui pourrait être le même symbole lu). La direction dans laquelle la tête doit bouger (gauche, droite ou, dans certaines définitions, rester immobile). Le nouvel état dans lequel la machine doit passer.
Le symbole à écrire sur la cellule actuelle (qui pourrait être le même symbole lu).
La direction dans laquelle la tête doit se déplacer (à gauche, à droite ou, dans certaines définitions, rester immobile).
Le nouvel état dans lequel la machine doit entrer.

L'importance conceptuelle de la Machine de Turing est extraordinaire. Il a fourni une formalisation précise et rigoureuse du concept intuitif d’algorithme. L’idée clé est que tout processus informatique pouvant être décrit par un ensemble fini de règles non ambiguës peut être simulé par une machine de Turing.

Cette notion est formalisée dans la Thèse Church-Turing , un principe fondamental (non prouvable mathématiquement mais largement accepté) qui stipule que toute fonction calculable par un humain suivant un ensemble de règles mécaniques peut être calculée par une machine de Turing.

La Machine de Turing a non seulement fourni une définition pratique de la calculabilité, mais a également permis d'explorer les limites intrinsèques du calcul. Par exemple, Turing lui-même a utilisé son modèle pour démontrer l'existence de problèmes indécidables , c'est-à-dire des problèmes pour lesquels il n'existe aucun algorithme (et donc aucune machine de Turing) capable de fournir une réponse définitive (oui ou non) pour toutes les instances possibles. Un exemple emblématique est le Halting Problem : étant donné un programme (ou une machine de Turing) et ses entrées, est-il possible de déterminer si le programme terminera son exécution ou continuera à s'exécuter indéfiniment ? Turing a prouvé qu’il n’existe pas d’algorithme général pour résoudre ce problème.

1.2 Le modèle de Von Neumann :
L'architecture des ordinateurs modernes

Alors que la machine de Turing représentait un modèle théorique de calcul, l'architecture proposée par John von Neumann, en collaboration avec d'autres pionniers tels que John Presper Eckert et John William Mauchly, a fourni le plan conceptuel sur lequel repose la grande majorité des ordinateurs modernes. Cette architecture, décrite pour la première fois dans un rapport influent de 1945 intitulé « Première ébauche d'un rapport sur l'EDVAC », introduit quelques principes fondamentaux qui définissent encore la structure de nos ordinateurs aujourd'hui :

Unité centrale de traitement (CPU) : Le « cerveau » de l'ordinateur, responsable de l'exécution des instructions. Le CPU est divisé en : Unité de contrôle (CU) : Récupère les instructions de la mémoire, les décode et génère les signaux de contrôle nécessaires pour coordonner les autres composants du système. Unité arithmétique-logique (ALU) : Effectue des opérations arithmétiques (addition, soustraction, multiplication, division) et logiques (ET, OU, NON) sur les données.
Unité de contrôle (CU) : Récupère les instructions de la mémoire, les décode et génère les signaux de contrôle nécessaires pour coordonner les autres composants du système.
Unité arithmétique-logique (ALU) : Effectue des opérations arithmétiques (addition, soustraction, multiplication, division) et logiques (ET, OU, NON) sur les données.
Mémoire : Utilisée pour stocker à la fois les données à traiter et les instructions du programme. Cette mémoire est conceptuellement organisée comme une séquence d'emplacements, chacun identifié par une adresse unique. La mémoire permet d'accéder directement à n'importe quel emplacement dans un temps relativement constant (mémoire vive ou RAM).
Périphériques d'entrée/sortie (E/S) : Permettent à l'ordinateur d'interagir avec le monde extérieur. Les périphériques d'entrée vous permettent de saisir des données et des commandes dans l'ordinateur (par exemple, clavier, souris), tandis que les périphériques de sortie vous permettent d'afficher ou de transmettre les résultats du traitement (par exemple, moniteur, imprimante).
Bus : Système de conducteurs (fils ou traces sur une carte de circuit imprimé) qui sert de voie de communication entre les différents composants du système. Il existe généralement trois types principaux de bus : Bus de données : Transporte les données entre le processeur, la mémoire et les périphériques d'E/S. Bus d'adresse : Spécifie l'adresse de la mémoire ou du périphérique d'E/S auquel l'accès est effectué. Bus de contrôle : Transporte des signaux de contrôle qui coordonnent les opérations entre différents composants.
Bus de données : Transporte les données entre le processeur, la mémoire et les périphériques d'E/S.
Bus d'adresse : Spécifie l'adresse de la mémoire ou du périphérique d'E/S auquel l'accès est effectué.
Bus de contrôle : Transporte des signaux de contrôle qui coordonnent les opérations entre les différents composants.

Un élément conceptuel fondamental de l'architecture de von Neumann est le concept de programme stocké . Cela signifie que les instructions du programme et les données sur lesquelles elles opèrent sont stockées dans la même mémoire. Cette idée apparemment simple représentait une rupture cruciale avec les premiers ordinateurs, où les instructions étaient souvent câblées directement dans le matériel ou stockées sur des supports séparés.

Le programme stocké offre une énorme flexibilité, car il vous permet de modifier le comportement de l'ordinateur simplement en chargeant un nouveau programme en mémoire. Il vous permet également de traiter les instructions comme des données, ouvrant la voie à des techniques avancées telles que la modification du code au moment de l'exécution.

Bien que l'architecture de von Neumann ait été incroyablement influente et soit à la base de la plupart des ordinateurs que nous utilisons aujourd'hui, elle présente également certaines limites inhérentes. Le plus connu est le goulot d'étranglement de von Neumann . Étant donné que les données et les instructions doivent passer par le même bus mémoire, la vitesse d'exécution du processeur peut être limitée par la rapidité avec laquelle les données et les instructions peuvent être extraites de la mémoire. Pour pallier cette limitation, plusieurs techniques ont été développées, comme l'utilisation de mémoires cache et d'architectures alternatives. Une architecture alternative importante est l'architecture Harvard , utilisée dans certains systèmes spécialisés tels que les processeurs de signaux numériques (DSP), qui sépare physiquement la mémoire d'instructions de la mémoire de données, permettant d'accéder simultanément aux deux.

1.3 Théorie de l'information de Shannon :
Mesurer l'incertitude

Parallèlement au développement des premiers ordinateurs et à la formalisation des modèles informatiques, les travaux pionniers de Claude Shannon sur la théorie de l'information , publiés dans son article fondateur de 1948 « Une théorie mathématique de la communication », ont fourni un cadre théorique rigoureux pour quantifier et comprendre le concept d'information. Ces travaux ont eu un impact profond non seulement sur l’informatique, mais également sur l’ingénierie des télécommunications et bien d’autres domaines.

Shannon a défini l'information en termes de réduction de l'incertitude. Autrement dit, l’information contenue dans un message est proportionnelle à la surprise qu’il génère. Plus un événement ou un message est inattendu, plus il véhicule d’informations. Pour quantifier cette idée, Shannon a introduit l'unité d'information fondamentale : le bit (chiffre binaire). Un bit représente la quantité d'informations nécessaires pour résoudre une incertitude entre deux alternatives également probables (par exemple, le résultat d'un tirage au sort).

Mathématiquement, la quantité d'informations (H) d'un événement avec une probabilité p de se produire est définie comme :

H = -log₂(p)

Où le logarithme est en base 2, reflétant la nature binaire du bit.

La théorie de l'information de Shannon a fourni les outils mathématiques fondamentaux pour :

Mesurer la quantité d'informations contenues dans une source de données ou un message. Cela nous a permis de définir la capacité maximale d'un canal de communication (théorème dit de Shannon-Hartley).
Comprendre les limites théoriques de la compression des données . La théorie de Shannon fixe une limite inférieure à la taille à laquelle un ensemble de données peut être compressé sans perte d'informations (entropie).
Concevoir des systèmes de communication fiables même en présence de bruit ou d'interférences. La théorie des codes correcteurs d'erreurs, développée à partir des travaux de Shannon, permet d'ajouter de la redondance aux données transmises afin que les erreurs introduites par le canal de communication puissent être détectées et corrigées.

Le concept de bit, dérivé de la théorie de Shannon, est devenu l'unité fondamentale pour représenter et manipuler l'information dans les systèmes informatiques. Chaque élément de données, chaque instruction, chaque image ou son dans un ordinateur est finalement codé sous forme de séquence de bits.

Les modèles informatiques de Turing et von Neumann, ainsi que la théorie de l'information de Shannon, représentent les piliers théoriques sur lesquels le domaine de l'informatique a été construit et continue d'évoluer. La machine de Turing a fourni une définition formelle de la calculabilité et nous a permis d'explorer les limites du calcul algorithmique. L'architecture de von Neumann offrait une conception pratique et flexible pour la fabrication d'ordinateurs électroniques, qui ont dominé l'industrie pendant des décennies.

Enfin, la théorie de l'information de Shannon fournissait un cadre mathématique pour comprendre et gérer l'information, un élément central de tout système informatique. Comprendre ces concepts fondamentaux est non seulement essentiel pour les étudiants en informatique, mais offre également une perspective approfondie sur les racines intellectuelles de cette discipline qui continue de transformer notre monde.