MO417 - Questão para a prova oral
Número: 049
Enunciado:
A seguinte aplicação não pode ser eficientemente implementada
com cada uma das operações básicas implementadas em tempo
no máximo proporcional a log n, com um (ou mais de um) heap
binomial:
- Um escalonador de processos de prioridade fixa em vários
processadores que precisa lidar com o fato de que às vezes um
processador pode falhar e ser removido do sistema, e sua fila terá
que ser unida à fila de algum outro processador pré-especificado.
- Um algoritmo de ordenação que precisa selecionar, a cada
momento, o menor elemento do vetor original para colocar no
começo, bem como remover elementos já usados.
- Uma aplicação matemática que precisa calcular mínimo, máximo e
união de conjuntos rapidamente.
- Uma aplicação matemática que precisa calcular mínimo e
interseção de conjuntos rapidamente.
- NDA
Autor(a): Alexandre Tachard Passos