Exercicios Resolvidos - Análise de Algoritmos
4 pág.

Exercicios Resolvidos - Análise de Algoritmos


DisciplinaAnálise de Algoritmos191 materiais713 seguidores
Pré-visualização2 páginas
Análise e Projeto de Algoritmos - LISTA DE EXERCÍCIOS DE REVISÃO PARA P2
1) Quais os dois principais conceitos relacionados a Programação Dinâmica?
A programação dinâmica é uma junção de dois conceitos chave, a recursão e a memoização.
Recursão é a chamada de um método por ele mesmo e a memoização são tabelas.
2) Nem todo problema pode ou deve ser resolvido utilizando Programação Dinâmica. Quais os
requisitos necessários para que valha a pena considerar essa abordagem?
A programação dinâmica normalmente é utilizada em problemas de otimização (custo
máximo/mínimo), porém nem sempre irá fazer sentido usá-la é necessário que hajam subproblemas
sobrepostos e uma subestrutura ótima.
3) Considere o problema de calcular a sequência de Fibonacci para um valor de entrada N.
a. Como seria a implementação recursiva desse algoritmo?
def fibo(n):
    if n <= 1:
        return n
    else:
        return fibo(n­1) + fibo(n­2)
b. Descreva o grafo de chamadas do algoritmo recursivo para N=4.
 fibo(4)
 / \
 fibo(3) fibo(2)
 / \ / \
 fibo(2) fibo(1) fibo(1) fibo(0)
 / \
 fibo(1) fibo(0)
c. Explique se você consideraria implementar esse algoritmo com
Programação Dinâmica e por quê.
Sim, a implementação da programação dinâmica para a sequência de Fibonacci é válida pois a
chamada do método repete várias vezes (alguns valores são recalculados). A complexidade
computacional sem PD é O(2n) e utilizando PD passa a ser O(n).
4) Repita os passos da questão 3 para o problema de calcular o Fatorial de um valor de entrada N.
a. 
def fat(n):
    if n <= 1:
        return 1
    else:
        return fat(n­1)
b. 
fat(4)
 |
fat(3)
 |
fat(2)
 |
fat(1)
c.
Não, a implementação da programação dinâmica para calcular o fatorial não é válida pois a
chamada do método não repete nenhuma vez (os valores são calculados apenas uma vez).
5) Cite dois problemas clássicos resolvíveis com Programação Dinâmica. Descreva brevemente cada
problema.
Problema da mochila:
É um problema de otimização combinatória. O nome dá-se devido ao modelo de uma situação
em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é
que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.
Problema do caixeiro viajante:
O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor
distância, começando em uma cidade qualquer, entre várias, visitando cada cidade precisamente uma
vez e regressando à cidade inicial. O problema pertence à categoria NP-Completo que o remete para
um campo de complexidade exponencial, isto é, o esforço computacional necessário para a sua
resolução cresce exponencialmente com o tamanho do problema, ou seja não há uma solução eficiente.
6) Algoritmos gulosos se baseiam na premissa de que a solução local para cada iteração da solução é
suficiente para determinar uma solução global satisfatória. Nesse contexto, defina mínimo/máximo
local e global.
Máximo/mínimo local é o maior/menor ponto em um determinado espaço percorrido pelo
algoritmo. Máximo/mínimo global é o maior/menor ponto geral de todos os pontos do problema (tendo
o algoritmo passado por ele ou não).
7) A estratégia gulosa consiste em escolher uma de diversas possibilidades, adicioná-la como parte da
solução, e repetir esse processo para as possibilidades restantes. Qual seria sua escolha de estratégia
gulosa para os seguintes casos? (pode ser uma descrição textual da estratégia)
a. Dados um conjunto de N itens e dois vetores P e C, representando respectivamente o peso e o custo
de cada item. Seu objetivo é calcular o lucro máximo para um dado peso W.
A NP-dificuldade do problema do caminho mais longo sem peso pode ser demonstrado por
meio de uma redução do problema do caminho Hamiltoniano: um grafo G tem um caminho
hamiltoniano se e somente se o seu caminho mais longo tem um comprimento n - 1, onde n é o número
de vértices em G. Se o problema do caminho mais longo pode ser resolvido em tempo polinomial, que
pode ser utilizado para resolver este problema de decisão, por descoberta de um caminho mais longo e,
em seguida, comparando a sua extensão para o número k então, o problema do caminho mais longo é
NP-difícil.
Björklund, Husfeldt & Khanna escrevem que o problema do caminho mais longo em gráficos
sem direções não ponderadas. O melhor algoritmo de aproximação de tempo polinomial conhecido
para este caso alcança apenas uma relação de aproximação. A técnica de codificação de cor pode ser
usada para encontrar caminhos de comprimentos logarítmicos, se é que existem, o que dá uma relação
de aproximação de apenas O(n/log n).
b. Dado um valor N, que representa o troco de uma transação, e um vetor V com os valores de moedas
disponíveis em uma dada moeda. Sua tarefa é reduzir ao máximo o número de moedas necessárias para
o troco.
Para um valor de troco N, e com um estoque infinito de cada uma das M moedas de diferentes
valores m1, m2, \u2026, mM, quais e quantas moedas você deve entregar ao cliente de modo que o total de
moedas seja o mínimo possível? Uma solução Gulosa, pela sua definição, consiste em fazer a melhor
escolha no estado atual. Temos um valor N, e quando escolhemos uma moeda m para subtrair de N,
desejamos que N fique o mais próximo possível de 0. Se ele ficar igual a 0, por exemplo, terminamos.
c. Dado um conjunto de vértices V e arestas E de um grafo totalmente conectado. Cada aresta possui
um peso W associado. Seu objetivo é computar o custo mínimo necessário para conectar todos os
vértices do grafo.
O problema consiste em encontrar um Caminho ou um Ciclo Hamiltoniano; O análogo
problema da decisão é para testar se um Caminho ou Ciclo Hamiltoniano existe. Um ciclo
Hamiltoniano, circuito Hamiltoniano, passeio em vértices ou grafo ciclo é um ciclo que visita cada
vértice exatamente uma vez (exceto o vértice que é tanto o início quanto o fim, e portanto é visitado
duas vezes).
O algoritmo divide o grafo em componentes que podem ser resolvidos separadamente. Também,
um algoritmo de programação dinâmica de Bellman, Held e Karp pode ser usado para resolver o
problema no tempo O(n2*2n). Neste método, um determina, para cada conjunto S de vértices e cada
vértice v em S, se existe um caminho que cobre exatamente os vértices em S e termina em v. Para cada
escolha de S e V, existe um caminho para (S, v) se e somente se v tem um vizinho w de tal forma que
existe um caminho para (S \u2212 v,w), que pode ser pesquisado a partir de informações já computadas no
programa dinâmico
8) Diferencie Algoritmos Gulosos e Programação Dinâmica no que tange à otimicidade e aos requisitos
de memória de cada abordagem.
Guloso nem sempre tem uma solução ótima, já o PD sempre retorna uma solução ótima. Nos
requisitos de memória PD usa muito mais porque tem tabelas e gulosos não.
9) Cite dois problemas clássicos resolvíveis com Estratégia Gulosa. Descreva brevemente cada
problema.
Mochila Fracionaria: 
Qualquer subconjunto que satisfaça esta restrição é chamado de solução viável. Então o que
queremos é uma solução viável que maximize ou minimize uma dada função objetivo. No Método
Guloso construímos um algoritmo que trabalha em estágios, considerando uma entrada por vez. Em
cada estágio é tomada uma decisão considerando se uma entrada particular é uma solução ótima. Isto é
feito considerando as entradas em uma ordem determinada por um processo de seleção, que é baseado
em alguma medida de otimização que pode ou não ser a função objetivo. Na maioria das vezes, porém,
essas medidas de otimização resultarão