Técnicas e Complexidade de Algoritmos: Guia Rápido

Algoritmos Gulosos (Gananciosos)

1. O que os Algoritmos Gulosos fazem?

   R: É uma técnica de algoritmos para resolver problemas de otimização, sempre realizando a escolha que parece ser a melhor no momento; fazendo uma escolha ótima local, na esperança de que esta escolha leve à solução ótima global.

2. Qual é a ideia do algoritmo para ele realizar a escolha da melhor opção?

   R: Quando é necessário fazer uma escolha durante o processo de otimização, escolher a opção que pareça ser a melhor no momento.

3. Qual é a desvantagem de utilizar o Algoritmo Guloso? Justifique sua resposta.

   R:

   • Nem sempre conduz a soluções ótimas globais.
   • Podem efetuar cálculos repetitivos.

4. Qual é o objetivo do exemplo da mochila? Explique com suas palavras.

   R: É preencher toda a mochila maximizando o valor total, e não a quantidade ou o peso.

5. Quando um Algoritmo Guloso não consegue resolver um problema de otimização, ele possui características que podem mostrar o problema do algoritmo. Quais são as características, e comente-as?

   R: As características são a Propriedade de Escolha Gulosa e a Subestrutura Ótima.

   • Subestrutura Ótima

     O que é preciso fazer é demonstrar que a combinação de uma escolha gulosa já realizada com uma solução ótima para o subproblema resulta em uma solução ótima para o problema original.

   • Propriedade de Escolha Gulosa

     Pela propriedade de escolha gulosa, uma solução globalmente ótima pode ser alcançada fazendo-se uma escolha localmente ótima (gulosa), isto é, aquela que parece ser a melhor naquele momento, desconsiderando-se resultados de subproblemas. É importante ressaltar a necessidade de se provar que realmente uma escolha gulosa em cada um dos passos irá levar a uma solução ótima global. O que normalmente se faz é examinar uma solução ótima global para algum subproblema e depois mostrar que ela pode ser modificada em uma solução gulosa. Isto irá resultar em um subproblema menor, mas similar.

NP-Completo

1. Qual problema pode ser resolvido em tempo real?

   (a) Algoritmos (b) NP-Completo (c) Tempo Polinomial (d) Técnicas Subconjunto (e) Nenhuma das alternativas

2. No problema de ciclo hamiltoniano, dado o grafo orientado G=(V,E). Qual certificado seria uma sequência de vértices [v]? Assinale a resposta certa.

   (a) <V1, V2, V3...V|V|> (b) <V3, V2, V3...V|V|> (c) <V1, V2, V4...V|V|> (d) <V1, V3, V2...V|V|> (e) Nenhuma das alternativas.

3. Os teóricos acreditam que os problemas NP-Completos são intratáveis. Explique por quê.

   R: Dada a ampla faixa de problemas NP-Completos que foram estudados até hoje sem qualquer progresso em direção a uma solução de tempo polinomial, seria verdadeiramente espantoso se todos eles pudessem ser resolvidos em tempo polinomial.

4. Complete com Otimização, sim ou não, decisão, difícil, fácil:

   O caráter NP-Completo não se aplica diretamente a problemas de Otimização, mas a problemas de decisão em que a resposta é simplesmente sim ou não. Se um problema de otimização é fácil, seu problema de decisão relacionado também é fácil. Se pudermos fornecer evidências de que um problema de decisão é difícil, também forneceremos evidências de que seu problema de otimização relacionado é difícil. Embora restrinja a atenção a problemas de decisão, a teoria de problemas NP-Completos frequentemente também tem implicações para problemas de otimização.

5. O que é um problema de tempo polinomial?

   R: É a relação que associa cada instância de um grafo e dois vértices com um caminho mais curto no grafo que conecta os dois vértices, tendo em vista que os caminhos mais curtos não são necessariamente únicos, uma dada instância de problemas pode ter mais de uma solução.

Divisão e Conquista

1. Marque verdadeiro (V) ou falso (F):

   • (V) A abordagem de divisão e conquista propõe dividir o problema em vários subproblemas.
   • (F) Divisão e conquista é uma técnica tipicamente aplicada a problemas de otimização em que pode haver várias soluções possíveis.
   • (F) A divisão e conquista nem sempre encontra a solução ótima, mas faz sempre a melhor escolha momentânea.

2. Cite dois problemas que podem ser resolvidos pelo método da Divisão e Conquista.

   R: Torre de Hanói e Merge Sort.

3. Fale em poucas palavras sobre Divisão e Conquista e Combinação.

   R: Consiste em dividir um problema maior em problemas menores até que o problema possa ser resolvido diretamente.

4. Como resolver um problema com o método da Divisão e Conquista?

   R: Tendo um problema, faz-se a sua divisão recursivamente quantas vezes for possível até se chegar a um único resultado.

5. Qual a opção não representa uma das fases de nível da recursão sobre Divisão e Conquista?

   (a) Dividir o problema em um determinado número de problemas. (b) Conquistar os subproblemas, resolvendo-os recursivamente. (c) Combinar as soluções dadas aos subproblemas, a fim de formar a solução para o problema original. (d) Conquistar subproblemas não os resolvendo recursivamente.

Programação Dinâmica

1. Marque V ou F:

   • (V) Técnica algorítmica, normalmente é usada em problemas de otimização.
   • (V) Baseada em guardar o resultado de subproblemas em vez de recalcular.
   • (F) O algoritmo tem complexidade exponencial, quando a soma dos tamanhos dos subproblemas é O(n).
   • (F) Quando um subproblema é resolvido, a resposta é armazenada em uma tabela, e quando há outro subproblema o mesmo é recalculado.
   • (V) A técnica sistematicamente considera todas as possíveis decisões e sempre seleciona a ótima.

2. O que é Programação Dinâmica? Dê exemplos.

   R: Técnica de resolução de problemas relacionados com otimização de algoritmos, resultando em geral em algoritmos mais eficientes que os mais diretos. Exemplo: Sequência de Fibonacci.

3. Como resolver um problema usando Programação Dinâmica?

   R: Como num jogo da velha, se escolher uma [jogada] que dê um bom resultado, mas sem guardar as contas, testaríamos muitas vezes as mesmas jogadas. Com Programação Dinâmica, podemos memorizar todos os resultados. Se executarmos o algoritmo apenas uma vez, já teremos todos os resultados. Sem memorização, além de calcular várias vezes as mesmas jogadas, teríamos que executar o algoritmo a cada jogada.

4. Fale sobre a Técnica de Fibonacci.

   R: Consiste em uma sequência de inteiros tal que os primeiros dois elementos são 0 e 1, respectivamente. Posteriormente, cada elemento na sequência é definido como a soma dos dois imediatamente anteriores.

Problemas de Otimização

1. Marque V ou F:

   • (V) Aquele onde se procura determinar os valores extremos de uma função.
   • (V) Encontra a melhor solução de um conjunto de soluções para um problema.
   • (F) Procura encontrar a solução mais demorada para o problema, nem sempre a melhor.
   • (V) Devem ser utilizadas quando não existe uma solução simples e diretamente calculável para o problema.

2. Defina Otimização Global e Otimização Local.

   R:

   • Otimização Global: Procura pela melhor solução de um conjunto de todas as soluções possíveis.
   • Otimização Local: Encontra a melhor solução dentro de um possível conjunto de soluções.

3. Os modelos de programação linear são implementados por meio da elaboração de sistemas lineares constituídos de:

   (a) Um conjunto de equações e inequações. (b) Um conjunto de caracteres especiais. (c) Um conjunto de variáveis. (d) Um conjunto de algoritmos.

4. Otimização combinatória de uma situação em que no problema é necessário se preencher com objetos de diferentes pesos e valores.

   (a) Problema da Torre de Hanói. (b) Problema da Mochila. (c) Problema do Ciclo Hamiltoniano. (d) Problema de cobertura de vértices.

5. Em um algoritmo criptografado de chave pública, quem pode decifrar sua chave?

   (a) O servidor de chaves públicas/privadas. (b) Sua chave privada correspondente. (c) A própria chave pública. (d) Não é necessário decifrar.