35

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

Thomas CormenIBSN: 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

Cancele quando quiser, sem multa

Aproveite também

  • check Exercícios passo a passo
  • check Resumos por tópicos
  • check Disciplinas ilimitadas
  • check Ferramentas para otimizar seu tempo