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

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 é:

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.