24

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

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.201

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.

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.