Modelo transdicotômico - Transdichotomous model
Na teoria da complexidade computacional , e mais especificamente na análise de algoritmos com dados inteiros , o modelo transdicotômico é uma variação da máquina de acesso aleatório na qual o tamanho da palavra da máquina é considerado compatível com o tamanho do problema. O modelo foi proposto por Michael Fredman e Dan Willard , que escolheram seu nome "porque a dicotomia entre o modelo da máquina e o tamanho do problema é cruzada de maneira razoável".
Em um problema como a classificação de inteiros em que há n inteiros a serem classificados, o modelo transdicotômico assume que cada número inteiro pode ser armazenado em uma única palavra da memória do computador, que as operações em palavras únicas levam um tempo constante por operação e que o número de bits que podem ser armazenados em uma única palavra é pelo menos log 2 n . O objetivo da análise de complexidade neste modelo é encontrar limites de tempo que dependem apenas de n e não do tamanho real dos valores de entrada ou das palavras de máquina. Na modelagem de computação inteira, é necessário assumir que as palavras de máquina são limitadas em tamanho, porque os modelos com precisão ilimitada são excessivamente poderosos (capazes de resolver problemas PSPACE-completos em tempo polinomial). O modelo transdicotômico faz uma suposição mínima desse tipo: que há algum limite e que o limite é grande o suficiente para permitir a indexação de acesso aleatório nos dados de entrada.
Além de sua aplicação à ordenação de inteiros, o modelo transdicotômico também tem sido aplicado ao projeto de filas de prioridade e a problemas em geometria computacional e algoritmos de grafos .
Veja também
Referências