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.194

Passo 1 de 7keyboard_arrow_downkeyboard_arrow_up

A prova é uma indução direta em relação ao número de operação, com a utilização das implementações de MAKE-SET, UNION e FIND-SET.

Passo 2 de 7keyboard_arrow_downkeyboard_arrow_up

São os seguintes os pseudo-código para as operações MAKE-SET, UNION e FIND-SET. Primeiramente descreveremos as operações.

Temos que o posto está chamando o valor do limite de x. Sempre que MAKE-SET cria um conjunto unitário, o posto da árvore é ajustado para zero.

Passo 3 de 7keyboard_arrow_downkeyboard_arrow_up

A operação UNION que armazena no primeiro conjunto os elementos de ambos conjuntos. Como pode ser vista:

Onde a operação LINK é :

Já a operação FIND-SET:

Passo 4 de 7keyboard_arrow_downkeyboard_arrow_up

Agora, aplicando indução no número de operações e considerando o número de operações n. Separaremos em três situações distintas n = 1, n = k e n = k+1

Quando n = 1:

Quando MAKE-FIRST é chamada em x, ela cria uma árvore com um único elemento x como raiz e conjunto com o posto zero. Similarmente, quando MAKE-FIRST é chamada em y, é criado uma árvore com um único elemento y como raiz e conjunto com o posto zero. Quando a única operação UNION é aplicada sobre esses dois caminhos. O resultado é uma nova árvore com x ou y com de raiz. Depois a árvore contém x e y, apenas. Se x é a raiz da nova árvore, então o posto de x é 1 e o posto de y é 0. Semelhantemente, se y é a raiz da nova árvore, então o posto e y é 1 e o posto de x é 0.

Passo 5 de 7keyboard_arrow_downkeyboard_arrow_up

Para n = k, quando k são executadas em k nós, o nó raiz que resulta da árvore tem o posto k -1 e o nó remanescente tem o posto menos que k -1;

Passo 6 de 7keyboard_arrow_downkeyboard_arrow_up

Quando n = k+1. Assumimos que depois de k operações, o lema é verdadeiro. Agora, isso é necessário para mostrar que dada a arvore, isso também é verdadeiro para k+1 operações.

Da hipótese indutiva, depois de k operações sobre k elemento, a árvore é obtida e a raiz (yk) tem o posto no máximo k-1.

Agora consideramos a árvore que contenha apenas um nó (xk). Aplicando mais uma operação UNION. O procedimento LINK seria o nó xk e o pai de ou ao contrário. Isso é, o posto de kx vira k ou o posto de incrementado por 1.

Passo 7 de 7keyboard_arrow_downkeyboard_arrow_up

Logo, fica evidente que o posto da raiz é modificado por cada operação e o posto dos nós restantes é menor que o posto da raiz.

Portanto, o valor de varia monotomicamente com o tempo.

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.