Resolvido: Algoritmos - Teoria e Prática - 3ª Ed. 2012 | Cap 21 Ex 1P
50
Algoritmos - Teoria e Prática - 3ª Ed. 2012

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

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 11keyboard_arrow_downkeyboard_arrow_up

Para encontrar uma solução para o problema do mínimo off-line é preciso considerar a lógica do algoritmo dado no enunciado.

Passo 2 de 11keyboard_arrow_downkeyboard_arrow_up

a.

Para preencher os valores extraídos é preciso considerar a sequência inserida: “”.

Passo 3 de 11keyboard_arrow_downkeyboard_arrow_up

Considerando a lógica do algoritmo, obtém-se:

Passo 4 de 11keyboard_arrow_downkeyboard_arrow_up

Portanto, os valores extraídos são:

Passo 5 de 11keyboard_arrow_downkeyboard_arrow_up

b.

Para provar que o resultado está correto, será utilizada a técnica da negação da tese (demonstração por contraposição). Considera-se que o valor extraído (incorreto) é e o valor correto é . Assim, para que a tese esteja errada existe a possibilidade de ser maior ou menor do que .

Passo 6 de 11keyboard_arrow_downkeyboard_arrow_up

Analisando inicialmente a possibilidade de , nota-se que, para que ela fosse verdadeira, deveria estar contido em com , mas não é possível que ele esteja em . Assim, essa possibilidade é falsa.

Passo 7 de 11keyboard_arrow_downkeyboard_arrow_up

Analisando a possibilidade de , seria necessário que tivesse sido extraído para , mas estaria vazio, de forma que não seja possível encontrar no valor extraído de sem ter o valor extraído de . Assim, essa possibilidade também é falsa.

Passo 8 de 11keyboard_arrow_downkeyboard_arrow_up

Portanto, como nenhuma das possibilidades é possível, a tese inicial de que o arranjo extraído é falso é negada, e o arranjo extraído é, então, correto.

Passo 9 de 11keyboard_arrow_downkeyboard_arrow_up

c.

A implementação pode ser feita através de conjuntos disjuntos dinâmicos, utilizando as funções:

Passo 10 de 11keyboard_arrow_downkeyboard_arrow_up

Analisando o tempo de execução, consideram-se as operações:

Passo 11 de 11keyboard_arrow_downkeyboard_arrow_up

Portanto, o tempo de implementação máximo é:

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Assine o PremiumCancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com 5.000 livros, escolha 5 por mês
  • check Videoaulas exclusivas
  • check Resumos por tópicos