Modèle abstrait de machine séquentielle pour l'analyse d'algorithmes représentant un processeur opérant sur un tableau de cellules mémoire non borné, chacune accessible en temps unitaire par adresse, et un ensemble standard d'opérations primitives ; utilisé pour étudier la complexité en temps et en espace en supposant un coût unitaire pour l'arithmétique et un accès mémoire en temps constant.

Principe

Considérer les étapes algorithmiques comme des opérations effectuées par un processeur central avec accès mémoire indexé en temps constant et un jeu d'instructions fixe, isolant le coût algorithmique des détails d'implantation matérielle.

Démonstration

Analyser un algorithme de tri d'entiers en comptant le nombre d'opérations primitives (comparaisons, affectations, chargements/stocks mémoire) exécutées sur une RAM à adressage direct ; exprimer le temps d'exécution en fonction de la taille de l'entrée en supposant que chaque accès mémoire coûte une unité de temps.

Mauvaise application

Supposer un accès en temps unitaire pour des entiers arbitrairement grands stockés dans une seule cellule sans tenir compte de leur longueur en bits, ou appliquer les coûts de la RAM à des architectures réelles avec caches hiérarchiques et latences non uniformes.

Conséquence

Fournit un modèle simple et calculable qui donne des bornes asymptotiques en temps et en espace indépendantes de la machine, facilitant la comparaison d'algorithmes.

Inversion

Un modèle qui traite la mémoire comme un accès strictement séquentiel (par exemple une bande de machine de Turing) où l'accès à la i-ème cellule peut exiger un temps proportionnel à i, inversant l'hypothèse d'accès aléatoire.

Limite

Ne modélise pas le calcul parallèle ou distribué, les hiérarchies de cache, ni les effets matériels de bas niveau ; les conventions varient quant au coût unitaire de l'arithmétique sur entiers non bornés ; exclut les ressources stochastiques ou quantiques.

Tension sémantique

Concurrence avec le modèle de machine de Turing (mouvements fins de la tête et bande) et les variantes word-RAM (taille de mot bornée), où les notions de coût et d'unité mémoire diffèrent.

Synthèse

Modèle de calcul séquentiel simplifié supposant un accès mémoire indexé en temps constant et des opérations primitives pour se concentrer sur le coût algorithmique tout en abstrahant les détails matériels, adapté à l'analyse asymptotique quand l'hypothèse de coût unitaire est acceptable.