RAM réelle

En informatique , et plus particulièrement en géométrie computationnelle , une RAM réelle ( random-access machine ) est un modèle mathématique d'un ordinateur capable de calculer avec des nombres réels exacts au lieu des nombres binaires à virgule fixe ou à virgule flottante utilisés par la plupart des ordinateurs actuels. La RAM réelle a été formulée par Michael Ian Shamos dans sa thèse de doctorat de 1978.

La partie « RAM » du nom du modèle RAM réel signifie « machine à accès aléatoire ». Il s'agit d'un modèle de calcul qui ressemble à une version simplifiée d'une architecture informatique standard. Il se compose d'un programme enregistré , d'une unité de mémoire informatique composée d'un ensemble de cellules et d'une unité centrale de traitement avec un nombre limité de registres . Chaque cellule ou registre de mémoire peut stocker un nombre réel. Sous le contrôle du programme, la RAM réelle peut transférer des nombres réels entre la mémoire et les registres, et effectuer des opérations arithmétiques sur les valeurs stockées dans les registres.

Les opérations autorisées comprennent généralement l'addition, la soustraction, la multiplication et la division, ainsi que les comparaisons, mais pas le module ou l'arrondi aux nombres entiers. La raison pour laquelle il faut éviter les opérations d'arrondi et de module des nombres entiers est que l'autorisation de ces opérations pourrait donner à la RAM réelle des quantités déraisonnables de puissance de calcul, lui permettant de résoudre des problèmes PSPACE-complets en temps polynomial.

Lors de l'analyse des algorithmes pour la RAM réelle, chaque opération autorisée est généralement supposée prendre un temps constant .

Des bibliothèques de logiciels telles que LEDA ont été développées pour permettre aux programmeurs d'écrire des programmes informatiques qui fonctionnent comme s'ils étaient exécutés sur une RAM réelle. Ces bibliothèques représentent des valeurs réelles à l'aide de structures de données qui leur permettent d'effectuer des calculs et des comparaisons avec les mêmes résultats que ceux produits par une RAM réelle. Par exemple, dans LEDA, les nombres réels sont représentés à l'aide du leda_realtype de données, qui prend en charge les racines k -ièmes pour tout nombre naturel k , les opérateurs rationnels et les opérateurs de comparaison. L'analyse temporelle de l'algorithme RAM réel sous-jacent utilisant ces types de données réels peut être interprétée comme comptant le nombre d'appels de bibliothèque nécessaires à un algorithme donné.

• Dans le modèle de la machine de Turing , l'unité de calcul de base implique un bit. Par conséquent, la complexité temporelle et spatiale des algorithmes numériques dépend du nombre de bits nécessaires pour représenter les nombres. En revanche, dans le modèle de la RAM réelle, l'unité de calcul de base implique un nombre réel, quel que soit le nombre de bits nécessaires pour le représenter. Cette différence est importante lors de l'analyse d'algorithmes tels que l'élimination gaussienne : cet algorithme nécessite un nombre polynomial d'opérations arithmétiques sur les nombres réels, il est donc polynomial dans le modèle de la RAM réelle ; cependant, les nombres utilisés dans les calculs intermédiaires peuvent (s'ils sont implémentés de manière naïve) croître de manière exponentielle, de sorte que son temps d'exécution dans le modèle de la machine de Turing est exponentiel.
• La RAM réelle ressemble beaucoup à la machine ultérieure de Blum-Shub-Smale . Cependant, la RAM réelle est généralement utilisée pour l'analyse d'algorithmes concrets en géométrie computationnelle , tandis que la machine de Blum-Shub-Smale constitue plutôt la base des extensions de la théorie de la complétude NP au calcul des nombres réels.
• Une alternative à la RAM réelle est le modèle RAM de type Word , dans lequel les entrées d'un problème et les valeurs stockées dans la mémoire et les registres sont supposées être des entiers avec un nombre fixe de bits. Le modèle RAM de type Word peut effectuer certaines opérations plus rapidement que la RAM réelle ; par exemple, il permet des algorithmes de tri d'entiers rapides , tandis que le tri sur la RAM réelle doit être effectué avec des algorithmes de tri par comparaison plus lents . Cependant, certains problèmes de géométrie computationnelle ont des entrées ou des sorties qui ne peuvent pas être représentées exactement à l'aide de coordonnées entières ; voir par exemple la configuration de Perles , un arrangement de points et de segments de ligne qui n'a pas de représentation de coordonnées entières.