Worldlex Wiki En informatique théorique , le modèle Word RAM (word random-access machine) est un modèle de calcul dans lequel une machine à accès aléatoire effectue des opérations arithmétiques et bit à bit sur un mot de Michael Fredman et Dan Willard l'ont créé en 1990 pour simuler des langages de programmation comme le C.
machine abstraite similaire à une machine à accès aléatoire , mais avec une mémoire et une longueur de mot finies. Il fonctionne avec des mots d'une taille maximale de des entiers jusqu'à n. Puisque le modèle suppose que la taille des mots correspond à la taille du problème, c'est-à-dire que pour un problème de taille modèle transdichotomique . Le modèle permet d'effectuer des opérations arithmétiques et des opérations bit à bit, y compris les décalages logiques, en temps constant (le jeu d'instructions précis supposé par un algorithme ou une preuve utilisant le modèle peut varier).Algorithmes et structures de données
Dans le modèle RAM, le tri des entiers peut être effectué de manière relativement efficace. Yijie Han et Mikkel Thorup ont créé un algorithme randomisé pour trier les entiers en un temps moyen de O(n) (en notation Big O ) , tandis que Han a également créé une variante déterministe avec un temps d'exécution de O( n) .
Le problème du prédécesseur dynamique est également fréquemment analysé dans le modèle Word RAM, et en a été la motivation initiale. Dan Willard a utilisé des essais rapides de type y pour le résoudre en temps O(n), ou plus précisément, O(n), où Michael Fredman et Willard ont également résolu le problème en utilisant des arbres de fusion en temps O(n). Avec des arbres de recherche exponentiels , une requête peut être effectuée en O (n) .
Des résultats supplémentaires concernant le modèle RAM sont répertoriés dans l'article sur la recherche par plage .
Les limites inférieures applicables aux algorithmes de mémoire RAM de mots sont souvent prouvées dans le modèle de sonde cellulaire .