31

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

A afirmação do professor será provada equivocada seguindo a seguinte demonstração:

• Suponha que é o heap do Fibonacci. Será criado um algoritmo para esse heap de forma que é composta por apenas uma árvore com n-1 nós começando com um vazio. Depois disso será adicionado mais um nó a essa cadeia.

• Criar um Fibonacci heap com a altura de uma de suas raizes chave R, R tal que é o valor da nó da raiz.

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Abaixo se encontra o pseudo-código necessário para criar o heap de Fibonacci, sendo que está assumindo que n é maior que 2:

Linear-heap()

Linear-heap()

Insert()

Insert()

Deletemin()

Decreasekey(b,)

Deletemin()

Retorna

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Considerando o seguinte caso base:

• A hipótese é correta para já que o heap contém uma árvore com a corrente linear de n nós.

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Vamos utilizar o seguinte processo indutivo:

• Suponha que a demonstração abaixo é verdadeira para . Agora para o pseudo código cria uma corrente linear contendo nós. Depois disso dois novos filhos e são adicionados ao nó raiz da árvore.

• O filho que possui possui uma chave que é menos do que a chave mínima.

• O filho que possui possui uma chave que é menos do que a chave mínima.

• Por último é adicionado ao nó R de forma que o nó chave é menor que a mínima chave. Quando esse nó R é deletado então a corrente remanescente de k nós irá possuir e .

• Já que o grau dos nós e é zero então esses nós são adicionados. Agora a corrente possui dois elementos que foram obtidos de forma que se torna raiz com o grau 1.

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Portanto, ter uma corrente de altura 2 e a outra corrente com altura são combinadas. Sendo assim, removendo os nós irá dar uma corrente linear com n nós. Então, podemos concluir que um Fibonacci heap contendo uma árvore com uma corrente linear de n nós pode ser criada com a sequência de operações de Fibonacci-heap, provando que a afirmação do professor está errada.

Navegar por capítulo

O passo a passo dos exercícios mais difíceis

R$ 29,90 /mêsCancele quando quiser, sem multa

E mais

  • check Videoaulas objetivas
  • check Resumos por tópicos
  • check Salve para ver depois
  • check Disciplinas ilimitadas
  • check Filtros exclusivos de busca