Quel modèle de calcul est "le meilleur"?

En 1937, Turing décrit une machine de Turing. Depuis lors, de nombreux modèles de calcul ont été décrits dans le but de trouver un modèle ressemblant à un vrai ordinateur, mais suffisamment simple pour concevoir et analyser des algorithmes.

En conséquence, nous avons une douzaine d'algorithmes pour, par exemple, le problème SORT pour différents modèles de calcul. Malheureusement, nous ne pouvons même pas être sûrs qu'une implémentation d'un algorithme avec le temps d'exécution O (n) dans un mot RAM avec des opérations de vecteur de bits autorisées fonctionnera plus rapidement qu'une implémentation d'un algorithme avec le temps d'exécution O (n⋅logn) dans un mot RAM (je parle bien sûr de "bonnes" implémentations).

Je veux donc savoir lequel des modèles existants est "le meilleur" pour concevoir des algorithmes et je recherche une étude à jour et détaillée sur les modèles de calcul, qui donne le pour et le contre des modèles et de leur proximité avec la réalité.

J'ai toujours considéré le modèle Word RAM standard comme "le meilleur" à votre sens. Tous ceux qui ont appris à programmer dans un langage comme C (ou des équivalents approximatifs comme Java, etc.) ont précisément ce modèle en tête lorsqu'ils pensent à un ordinateur.

Bien sûr, vous avez parfois besoin de généralisations en fonction des régimes dans lesquels vous travaillez. Le modèle de mémoire externe est un modèle important à garder à l’esprit. Cela s'applique non seulement lorsque vous travaillez avec des disques, mais également pour comprendre (vous obliger à vous soucier de) le cache. Bien sûr, le traiter trop sérieusement peut également conduire à des résultats absurdes, car le modèle de mémoire externe pure ne compte pas le calcul. Une autre généralisation du mot RAM concerne le parallélisme, mais là nous sommes tous un peu confus pour le moment :)

$O(n)$$O(n \lg n)$$n$$n$

Une dernière remarque sur les algorithmes et la "réalité": gardez toujours à l'esprit ce que vous essayez d'accomplir. Lorsque nous travaillons dans des algorithmes, nous essayons de résoudre les problèmes les plus difficiles (par exemple SAT sur 50 variables ou trier un milliard de nombres). Si vous essayez de trier 200 nombres ou de résoudre SAT sur 20 variables, vous n'avez pas besoin d'algorithme sophistiqué. C'est pourquoi la plupart des algorithmes sont en réalité triviaux. Cela ne dit rien de mal à propos de la recherche algorithmique - nous nous trouvons justement intéressés par ce 1/1000 inhabituel des vrais problèmes difficiles à résoudre ...

Il n'existe pas de modèle informatique totalement satisfaisant pour analyser les algorithmes avec tristesse, même dans ce que l'on pourrait considérer comme un paramètre traditionnel. Cela suppose que toutes les données sont facilement accessibles et que l’espace de travail est effectivement illimité.

La machine de Turing à bandes multiples est théoriquement bien spécifiée et de nombreux algorithmes ont été conçus et analysés dans ce modèle au fil des ans. Cependant, pour certains, il n’existe pas suffisamment de liens avec le fonctionnement des ordinateurs réels pour devenir un bon modèle à utiliser au XXIe siècle. D'autre part, le modèle mot-RAM est devenu populaire et semble capturer avec plus de précision le fonctionnement des ordinateurs modernes (opérations sur des mots et non des bits, accès à temps constant aux emplacements de mémoire). Cependant, il y a des aspects qui ne sont pas idéaux. Par exemple, il n’existe pas de modèle de mot RAM unique. Il faut d’abord préciser quelles opérations sur les mots doivent être autorisées en temps constant. Il existe de nombreuses options pour cela sans aucune réponse acceptée. Seconde, la taille de mot w est normalement configurée pour augmenter avec la taille d'entrée (c'est-à-dire au moins aussi vite que log (n)) pour permettre à tout élément en mémoire d'être adressé à l'aide d'un nombre constant de mots. Cela signifie qu'il faut imaginer une classe infinie de machines sur lesquelles votre algorithme est exécuté ou, pire encore, que la machine change au fur et à mesure que vous lui fournissez plus de données. C'est une pensée déconcertante pour le plus pur parmi mes étudiants au moins. Enfin, vous obtenez des résultats de complexité quelque peu surprenants avec le modèle mot-RAM qui peut ne pas correspondre à ceux que l’on apprend en tant qu’étudiant. Par exemple, la multiplication de deux nombres à n bits correspond à O (n) temps dans ce modèle et la simple lecture d'une chaîne de n bits est une opération temporelle sous-linéaire tout à coup. Cela signifie qu'il faut imaginer une classe infinie de machines sur lesquelles votre algorithme est exécuté ou, pire encore, que la machine change au fur et à mesure que vous lui fournissez plus de données. C'est une pensée déconcertante pour le plus pur parmi mes étudiants au moins. Enfin, vous obtenez des résultats de complexité quelque peu surprenants avec le modèle mot-RAM qui peut ne pas correspondre à ceux que l’on apprend en tant qu’étudiant. Par exemple, la multiplication de deux nombres à n bits correspond à O (n) temps dans ce modèle et la simple lecture d'une chaîne de n bits est une opération temporelle sous-linéaire tout à coup. Cela signifie qu'il faut imaginer une classe infinie de machines sur lesquelles votre algorithme est exécuté ou, pire encore, que la machine change au fur et à mesure que vous lui fournissez plus de données. C'est une pensée déconcertante pour le plus pur parmi mes étudiants au moins. Enfin, vous obtenez des résultats de complexité quelque peu surprenants avec le modèle mot-RAM qui peut ne pas correspondre à ceux que l’on apprend en tant qu’étudiant. Par exemple, la multiplication de deux nombres à n bits correspond à O (n) temps dans ce modèle et la simple lecture d'une chaîne de n bits est une opération temporelle sous-linéaire tout à coup.

Cela dit, si vous voulez juste savoir si votre algorithme est susceptible de fonctionner rapidement, l'un ou l'autre fera très probablement :-)

Les modèles ne sont que des modèles. Je ne voudrais pas pousser trop loin; ils parlent de certains aspects de vos algorithmes, mais pas de la vérité.

Je suggérerais que vous utilisiez simplement le modèle de mot RAM standard dans votre analyse et que vous mettiez en œuvre l'algorithme pour voir comment il fonctionnait correctement.

(En réalité, mettre en œuvre votre algorithme sans jamais l'exécuter en dit déjà beaucoup sur lui ... Tout d'abord, il peut être implémenté de manière prouvable.)

Si votre tâche de calcul concerne davantage le déplacement de données que la réalisation d'opérations (arithmétiques), (les ensembles de données sont énormes et ne peuvent même pas être insérés dans la mémoire principale), le modèle I / O (introduit par Aggarwal et Vitter en 1988 ) peut être très précis. Pour des tâches telles que la permutation d’un grand nombre d’éléments dans la mémoire principale, il peut être utile d’utiliser les algorithmes qui sont optimaux en termes d’E / S (dans une implémentation minutieuse).

Pour les ordinateurs multicœurs modernes, la variante parallèle introduite par Arge, Goodrich, Nelson et Sitchinava en 2008 peut être un modèle précis.

Si vous voulez dire "le meilleur" modèle de calcul pour vous rendre la vie plus compliquée, vous pouvez utiliser la machine de turing universelle à 2 états et à 3 symboles de Wolfram.

Avantages : aucun, sauf la sensation de marcher sur la ligne de démarcation entre la raison et la folie;

CONS : tonnes ...

:-D (seulement une blague, je suis fondamentalement d'accord avec les réponses précédentes ...)

Sur une note plus théorique: L’article Ultimate, modèles théoriques de nanoc calculateurs, affirme que le modèle de maillage 3D réversible est le modèle physique optimal de calcul, en ce sens qu’aucun autre modèle physique ne peut être asymptotiquement plus rapide. Des considérations physiques telles que la vitesse de la lumière, le principe de Landauer et le lien de Bekenstein sont discutées.

Pour citer l'extrait:

Nous constatons qu'en utilisant la technologie actuelle, une machine réversible ne contenant que quelques centaines de couches de circuits pourrait surpasser toute machine existante et qu'un ordinateur réversible basé sur la nanotechnologie n'aurait besoin que de quelques microns pour pouvoir surpasser toute technologie irréversible éventuelle.

Nous pensons qu'une implémentation en silicium du maillage 3D réversible pourrait être utile aujourd'hui pour accélérer certains calculs scientifiques et d'ingénierie, et nous proposons que le modèle devienne un centre d'étude future de la théorie des algorithmes parallèles pour un large éventail de problèmes.