problema dinâmicas (algoritmos) - Dynamic problem (algorithms)

Problemas dinâmicos em teoria da complexidade computacional são problemas enunciados em termos dos dados de entrada em mudança. Na forma mais geral um problema nesta categoria é normalmente referida como segue:

• Dada uma classe de objectos de entrada, encontrar algoritmos eficientes e estruturas de dados para responder a uma determinada consulta sobre um conjunto de entrada de objectos de cada vez que os dados de entrada for modificada, isto é, são inseridos ou eliminados objectos.

Problemas desta classe têm as seguintes medidas de complexidade:

• Espaço  - a quantidade de espaço de memória necessário para armazenar a estrutura de dados;
• Tempo de inicialização  - tempo necessário para a construção inicial da estrutura de dados;
• Tempo de inserção  - tempo necessário para a actualização da estrutura de dados quando mais um elemento de entrada é adicionado;
• Tempo de eliminação  - tempo necessário para a actualização da estrutura de dados, quando um elemento de entrada é suprimido;
• Consultar tempo  - tempo necessário para responder a uma consulta;
• Outras operações específicas para o problema em questão

O conjunto global de cálculos para um problema dinâmico é chamado de algoritmo dinâmico .

Muitos problemas algorítmicos expressos em termos de dados de entrada fixa (chamados problemas estáticos neste contexto e resolvidos por algoritmos estáticos ) têm versões dinâmicas significativas.

Casos especiais

Algoritmos incrementais , ou algoritmos de linha , são algoritmos em que são permitidos apenas adições de elementos, possivelmente a partir da entrada de dados vazio / trivial.

Algoritmos decrementais são algoritmos em que são permitidos somente deleções de elementos, a começar com uma inicialização de uma estrutura de dados completo.

Se ambas as adições e exclusões são permitidas, o algoritmo é às vezes chamado totalmente dinâmico .

Exemplos

elemento minimal

problema estática 

Para um conjunto de números de N encontrar a um mimo.

O problema pode ser resolvido em O (n).

problema dinâmica 

Para um conjunto inicial de N números, manter dinamicamente a máxima quando uma inserção ou deleção são permitidos.

Uma solução conhecida para este problema é usar uma árvore de busca binária de auto-equilíbrio . Leva espaço S (N), podem ser inicialmente construído em tempo O (N log N) e fornece tempos de inserção, deleção e de consulta em O (log N).

A fila de prioridade problema de manutenção

É uma versão simplificada do problema dinâmico, onde se requer para excluir somente o elemento minimal. Esta versão pode fazer com estruturas de dados mais simples.

gráficos

Dado um gráfico, manter os seus parâmetros, tais como a conectividade, grau máximo, os caminhos mais curtos, etc, quando a inserção e deleção de suas bordas são permitidos.

Veja também

• dinamização
• conectividade dinâmica

Referências