Qual modelo de computação é "o melhor"?

Em 1937, Turing descreveu uma máquina de Turing. Desde então, muitos modelos de computação foram descritos na tentativa de encontrar um modelo que seja como um computador real, mas ainda simples o suficiente para projetar e analisar algoritmos.

Como resultado, temos dezenas de algoritmos para, por exemplo, o problema SORT para diferentes modelos de computação. Infelizmente, nem podemos ter certeza de que uma implementação de um algoritmo com tempo de execução O (n) em uma palavra RAM com operações de vetor de bits permitidas seja executada mais rapidamente do que uma implementação de um algoritmo com tempo de execução O (n⋅logn) em uma palavra RAM (estou falando apenas de implementações "boas", é claro).

Portanto, quero entender qual dos modelos existentes é "o melhor" para projetar algoritmos e estou procurando uma pesquisa atualizada e detalhada sobre modelos de computação, que ofereça prós e contras dos modelos e sua proximidade com a realidade.

Sempre considerei o modelo padrão de RAM do Word o "melhor" no seu sentido. Todo mundo que aprendeu a programar em uma linguagem como C (ou qualquer equivalente solto como Java, etc) tem precisamente esse modelo em mente quando pensa em um computador.

Claro, às vezes você precisa de generalizações, dependendo dos regimes em que trabalha. O modelo de memória externa é importante para se ter em mente. Ele se aplica não apenas quando você trabalha com discos, mas também no entendimento (forçando você a se preocupar com) cache. Obviamente, tratá-lo com muita seriedade também pode levar a resultados sem sentido, uma vez que o modelo de memória externa pura não conta com computação. Outra generalização da palavra RAM é o paralelismo, mas estamos todos um pouco confusos no momento :)

Um algoritmo com tempo de execução certamente será executado mais rapidamente do que um com tempo de execução . É um fato matemático que o primeiro seja mais rápido para grandes :) O tamanho do seu problema pode não ser grande o suficiente para que isso importe. Como você seleciona a classificação, garanto-lhe que será muito difícil vencer a classificação radix com um algoritmo baseado em comparação para um razoável .O ( n lg n ) n $O(n)$$O(n \lg n)$$n$$n$

Uma observação final sobre algoritmos e "realidade": sempre lembre-se do que você está tentando alcançar. Quando trabalhamos em algoritmos, estamos tentando resolver os problemas mais difíceis do mercado (por exemplo, SAT em 50 variáveis ​​ou classificar um bilhão de números). Se você está tentando classificar 200 números ou resolver o SAT em 20 variáveis, não precisa de nenhum algoritmo sofisticado. É por isso que a maioria dos algoritmos na realidade é meio trivial. Isso não diz nada de ruim sobre a pesquisa algorítmica - por acaso nos interessamos por 1/1000 incomuns dos problemas reais que são difíceis ...

Não existe um modelo computacional totalmente satisfatório para analisar tristemente os algoritmos, mesmo no que se poderia considerar um cenário tradicional. Isso pressupõe que todos os dados estejam prontamente acessíveis e que o espaço de trabalho seja efetivamente ilimitado.

A máquina de Turing multi-fita é certamente teoricamente bem especificada e muitos algoritmos foram projetados e analisados ​​nesse modelo ao longo dos anos. No entanto, para alguns, isso não se relaciona suficientemente com o modo como os computadores reais funcionam para realmente ser um bom modelo a ser usado no século XXI. Por outro lado, o modelo de palavra RAM tornou-se popular e parece capturar com mais precisão o funcionamento de computadores modernos (operações em palavras e não bits, acesso constante a locais de memória). No entanto, existem aspectos que são menos que ideais. Por exemplo, não há um modelo de RAM de uma palavra. É preciso primeiro especificar quais operações nas palavras devem ser permitidas em tempo constante. Existem muitas opções para isso, sem uma única resposta aceita. Segundo, o tamanho da palavra w é normalmente definido para aumentar com o tamanho da entrada (que é pelo menos tão rápido quanto log (n)) para permitir que qualquer item na memória seja endereçado usando um número constante de palavras. Isso significa que é preciso imaginar uma classe infinita de máquinas nas quais o algoritmo é executado ou, pior ainda, que a máquina muda à medida que você fornece mais dados. Este é um pensamento desconcertante para os mais puros entre meus alunos, pelo menos. Finalmente, você obtém resultados surpreendentes de complexidade com o modelo de palavra-RAM, que pode não corresponder àqueles que aprendemos quando estudante. Por exemplo, a multiplicação de dois números de n bits é o tempo O (n) neste modelo e a simples leitura de uma sequência de n bits é uma operação de tempo sublinear de repente. Isso significa que é preciso imaginar uma classe infinita de máquinas nas quais o algoritmo é executado ou, pior ainda, que a máquina muda à medida que você fornece mais dados. Este é um pensamento desconcertante para os mais puros entre meus alunos, pelo menos. Finalmente, você obtém resultados surpreendentes de complexidade com o modelo de palavra-RAM, que pode não corresponder àqueles que aprendemos quando estudante. Por exemplo, a multiplicação de dois números de n bits é o tempo O (n) neste modelo e a simples leitura de uma sequência de n bits é uma operação de tempo sublinear de repente. Isso significa que é preciso imaginar uma classe infinita de máquinas nas quais o algoritmo é executado ou, pior ainda, que a máquina muda à medida que você fornece mais dados. Este é um pensamento desconcertante para os mais puros entre meus alunos, pelo menos. Finalmente, você obtém resultados surpreendentes de complexidade com o modelo de palavra-RAM, que pode não corresponder àqueles que aprendemos quando estudante. Por exemplo, a multiplicação de dois números de n bits é o tempo O (n) neste modelo e a simples leitura de uma sequência de n bits é uma operação de tempo sublinear de repente.

Dito tudo isso, se você quiser apenas saber se é provável que seu algoritmo seja executado rapidamente, será mais provável :-)

Modelos são apenas modelos. Eu não iria longe demais; eles dizem algo sobre alguns aspectos de seus algoritmos, mas não toda a verdade.

Gostaria de sugerir que você simplesmente usar o modelo palavra RAM padrão em sua análise e implementar o algoritmo e ver o quão bem ele executa na prática.

(Na verdade, apenas implementar seu algoritmo sem nunca executá-lo já diz muito sobre ele ... Por um lado, ele é comprovadamente implementável.)

Se sua tarefa computacional é mais sobre mover dados do que executar operações (aritméticas) (os conjuntos de dados são enormes para que nem se encaixem na memória principal), então o modelo de E / S (introduzido por Aggarwal e Vitter em 1988 ) pode ser muito preciso. Para tarefas como permutar uma grande variedade de elementos na memória principal, pode ajudar a usar os algoritmos que são ideais para E / S (em uma implementação cuidadosa).

Para computadores modernos com vários núcleos, a variante paralela introduzida por Arge, Goodrich, Nelson e Sitchinava em 2008 pode ser um modelo preciso.

Se você quer dizer "o melhor" modelo computacional para tornar sua vida mais complicada, pode usar a máquina de turing universal de dois estados e três símbolos da Wolfram.

PROS : nenhum, exceto a sensação de andar na linha tênue entre razão e loucura;

CONTRAS : toneladas ...

:-D (apenas uma piada, eu basicamente concordo com as respostas anteriores ...)

Em uma nota mais teórica: O artigo Modelos teóricos finais de nanocomputadores argumenta que o modelo de malha 3D reversível é o modelo físico ideal de computação, no sentido de que nenhum outro modelo físico poderia ser assintoticamente mais rápido. Considerações físicas como a velocidade da luz, o princípio de Landauer e o limite de Bekenstein são discutidas.

Para citar o resumo:

Descobrimos que, usando a tecnologia atual, uma máquina reversível contendo apenas algumas centenas de camadas de circuitos poderia superar qualquer máquina existente e que um computador reversível baseado em nanotecnologia precisaria apenas de alguns mícrons para superar qualquer tecnologia irreversível possível.

Argumentamos que uma implementação de silicone da malha 3D reversível pode ser valiosa hoje para acelerar certos cálculos científicos e de engenharia, e propomos que o modelo se torne um foco de estudos futuros na teoria dos algoritmos paralelos para uma ampla gama de problemas.