Disciplina_ Análise e Projeto de Algoritmos

Prévia do material em texto

Disciplina: Análise e Projeto de Algoritmos
Professora: Alexandra Zimpeck
Lista de Exercícios
Algoritmos Gulosos
1) Dê uma definição formal para grafos e ilustre conceitos da vida real modelados
por essa estrutura.
Um grafo qualquer é representado por G = (V,E) composta por dois conjuntos:
V→ É um conjunto finito chamado de conjuntos de vértices do grafo G.
E → É uma relação binária em V onde é chamado de conjunto de arestas de G.
Exemplos da vida real:
Transporte aéreo.(V = Cidades, E = Vôo entre duas cidades).
Grade escolar.(V=Professor e disciplina, E=disciplina lecionada pelo professor).
2) Existem dois algoritmos de busca em grafos que são bastante diferentes na sua
aplicação: busca em largura e busca em profundidade. Qual a diferença entre
eles? Qual a complexidade assintótica de cada um deles? Quais as vantagens e
desvantagens destes algoritmos de busca?
Busca em largura: O método consiste em, a partir de um vértice de origem s,
“descobrir” todos os vértices do grafo uniformemente em relação a sua distância de s.
Busca em profundidade:O método consiste em, a partir de um vértice de origem s,
“descobrir” todos os vértices do grafo explorando cada caminho o mais profundamente possível.
A diferença consiste na forma de como é feita a busca.
--------------------------------------------------------------------------------------------------------------
3) Mostre um grafo orientado com arestas negativas para o qual o algoritmo de
Dijkstra não funciona corretamente.
Ele não funciona normalmente pois tem um ciclo negativo(peso negativo em geral).
4) Explique por que o problema da mochila booleana não pode ser resolvido por
um algoritmo guloso.
Levando em consideração a relação entre o problema da mochila fracionária e a booleana,
o problema da mochila booleana não pode ser resolvido pois a estratégia do algoritmo guloso é de
levar o máximo possível do item com maior valor por quilo primeiro e isto não irá apresentar uma
solução ótima para o problema da mochila booleana pois na mochila booleana não se pode
fracionar o valor carregado e sim levar o item inteiro.
5) Aprendemos que os algoritmos de árvore geradora mínima são capazes de gerar
subgrafos em que todos os vértices estão conectados usando o menor custo
total de arestas.
a) Quais os algoritmos que geram as árvores geradoras mínimas? Qual a
diferença entre eles? Qual a complexidade assintótica de cada um deles?
Algoritmo de Prim e Algoritmo de Kruskal a diferença entre eles está no método de definir
uma aresta segura:
● O algoritmo de Prim define sua aresta segura utilizando-se de um corte(S, V-S) que
respeite algum subconjunto(A) de uma MST em um grafo conexo(G=V, E) com uma função
de peso definida em E, sendo que se o par (u,v) é a aresta mais leve cruzando(S,V-S) a
aresta segura é decidida pelo seu menor peso w em E.
● O algoritmo de Kruskal define sua aresta segura a partir de um componente conexo(C=Vc,
Ve) na floresta G=(V,A) se o par (u,v) é a aresta mais leve conectando C a algum outro
componente de Ga então o par (u,v) é uma aresta segura.
O tempo de complexidade desses algoritmos é O(E lg V).
b) Dê aplicações práticas destes algoritmos.
Projeto de redes de computadores e de comunicação. computação móvel.
6) Se utilizarmos Heaps de Fibonacci no algoritmo de Prim, ele passar a ter uma
complexidade assintótica de O(E + V lg V). Dito isso, qual implementação (Kruskal
ou Prim com Heap de Fibonacci) é a mais recomendada para grafos esparsos? E
para grafos densos?
Denso = Prim
Disparço = Fibonacci
-------------------------------------------------------------------------------------
7) Considere o problema: Dado um grupo de cidades em uma região que está nos
estágios iniciais de planejamento e seus administradores estão decidindo onde
colocar escolas. Há apenas duas restrições: cada escola deve ser em uma cidade
e ninguém deve viajar mais que 50 km para alcançar uma delas. Você recomenda
o uso da estratégia gulosa para o problema? Justifique.
Não pois para o uso da técnica gulosa sempre se espera um ponto inicial, já nesse modelo o
objetivo deve ser no máximo 50 km entre as escolas ou seja os pontos estão diversificados.
conjunto de vértices
8) Aplique o algoritmo de Prim e Kruskal para o grafo abaixo
??????
9) Aplique o algoritmo de Djikstra no grafo abaixo considerando o vértice A como ponto de
partida. Mostre as tabelas d (distância) e π(pai) resultantes no final da execução
????????????
10) Diferencie a estratégia gulosa e a estratégia de programação dinâmica no que tange à
otimicidade e aos requisitos de memória.
Algoritmos Gulosos Programação dinâmica
Estratégia top-down Estratégia bottom-up
Escolhe a alternativa mais promissora no
momento
Explora todas as alternativas de maneira
eficiente
Nunca se arrependem de uma decisão já
tomada
A cada decisão podem se arrepender de
decisões anteriores
São rápidos São um tanto lentos
Não tem prova de correção simples Possuem prova de correção simples
Algoritmos de Ordenação
11) Diferencie o modo de implementação dos algoritmos Counting Sort, Radix Sort e Bucket
Sort. Quando cada um deles é mais indicado?
● Counting Sort: Para cada elemento x, determinar quantos elementos são menores que x e
usar essa informação para colocar x diretamente em sua posição correta no vetor de
saída. Indicado para números inteiros e é um algoritmo estável.
● Radix Sort: Ordena os elementos de um arranjo através da ordenação do valor dos seus
dígitos separadamente partindo do menos significativo para o mais significativo partindo
sempre da primeira coluna n colunas.
● Bucket Sort: Elementos do arranjo de entrada são gerados uniformemente e
independentemente dentro do intervalo [0,1) subdividindo esse intervalo em n
subintervalos, ou baldes, de tamanhos iguais, e então distribuir os n elementos de entrada
entre os baldes. Mais indicado em números com ponto flutuante sendo um algoritmo
estável.
12) Simule a execução do algoritmo Couting Sort usando como entrada o vetor
A = (7,1,3,1,2,4,5,7,2,4,3).
a) Através da sua simulação, mostre que este algoritmo é estável
Ele é estável pois ele ta na mesma ordem inicial
--------------------------------
b) Suponha que o laço for da linha 10 do Couting Sort é substituído por:
for j=1 to n do Mostre se este algoritmo ainda funciona. Se sim, ele ainda
continua estável?
13) Descreva como você modificaria o RadixSort para ordenar cadeias de caracteres com
tamanhos diferentes. Por exemplo, a chave “carrega” deve estar antes de “carregamento” e
depois de “borboleta”.
------------------------------
14) Ilustre a execução do Bucket Sort considerando a entrada: 0.79, 0.13, 0.16, 0.64, 0.39,
0.20, 0.89, 0.53, 0.71, 0.42. 15) Explique por que o tempo de execução do pior caso para o
Bucket Sort é O(n2). Qual é a alteração no algoritmo que preserva seu tempo de execução
linear do caso médio e torna seu tempo de execução do pior caso igual a O(n lg n)?
---------------------------------------------------
Programação Dinâmica
16) Nem todo problema pode ou deve ser resolvido utilizando a programação dinâmica.
Quais os requisitos necessários para que valha a pena considerar essa abordagem?
Os requisitos são: Subestrutura ótima, Subproblemas sobrepostos.
17) Quais são os quatro passos fundamentais para a solução de problemas utilizando a
programação dinâmica? Qual o único passo que pode ser omitido?
Os passos são:
1)Caracterizar a estrutura de solução ótima.
2)Recursivamente definir esse valor
3)Computar o valor de baixo para cima.
4)Construir uma solução ótima a partir da informação computada.
O único passo que poder ser omitido é o passo 4 pode ser omitido se apenas o valor de uma
solução ótima é necessária.
18) Considere o problema de calcular a sequência de Fibonacci para um valor de entrada n,
e responda:
a) Como seria a implementação recursiva desse algoritmo?
def fibonacci(n):
if n <= 1:
return n
else: return fibonacci(n-1) + fibonacci(n-2)
for i in range(4):
print(fibonacci(i), '\n')
b) Descreva o grafo de chamadas do algoritmo recursivo paran=4
c) Explique se você consideraria implementar esse algoritmo com programação dinâmica e
justifique.
--------------------------------
19) Repita os passos da questão 18 para o problema de calcular o fatorial de um valor de
entrada n.
a) s
def fatorial(n):
if n == 0 or n == 1:
return 1
else:
return n * fatorial(n-1)
print(fatorial(3))
b)
c)
20) Explique como funciona a técnica de relaxamento, quais algoritmos a utilizam e quando
ela deve ser aplicada.
O processo de relaxar uma aresta (u,v) consiste em testar se podemos melhorar o
caminho mais curto para v encontrado até agora pela passagem através de u e, neste caso,
atualizar d[v] e π[v].
Algoritmos de Dijkstra e Bellman-Ford
21) Um navio pode carregar 4 toneladas. A tabela a seguir fornece o peso unitário wi em
toneladas e o valor unitário vi para cada item i.
Como o navio deve ser carregado para maximizar o retorno total?
47 + 14 = 61
22) Execute o algoritmo do problema do corte das hastes para uma haste de comprimento
5, considerando a tabela de preços abaixo
Qual o desdobramento em pedaços que maximiza a receita? Lembre-se de que podemos
concluir que a melhor opção é não cortar
Valor = 16 pode ser pela combinação (2 comprimento 1) e 1 de comprimento 3.
23) Suponha que você é dono de um mercado e precisa dar 35 centavos de troco a um
cliente. Considere que as moedas disponíveis no seu estabelecimento são de 1, 7 e 10
centavos. Mostre a solução utilizando a estratégica gulosa e também a programação
dinâmica. Qual das técnicas apresentou o melhor resultado? Justifique sua resposta.
● Estratégia gulosa : 10 - 10 - 10 - 1 - 1 - 1 - 1 - 1 = 35
● Programação Dinâmica : 7 - 7 - 7 -7 -7 = 35
A técnica de programação dinâmica pois ela verifica todos os valores possíveis para utilizar como
troco portanto ela usa menos moedas enquanto a estratégia gulosa sempre utiliza o maior valor
primeiro.
24) Mostre com um exemplo que uma parentização completa de uma expressão de n
elementos tem exatamente n-1 pares de parênteses
Um produto de matrizes é totalmente parentizado se for uma única matriz ou produto de
duas matrizes também expressos entre parênteses.
25) Execute o algoritmo de Bellman-Ford no grafo abaixo considerando o nodo 0, em
vermelho, como ponto de partida. Deixe explícito a ordem de exploração das arestas deste
grafo.
possui um ciclo (perguntar para a prof)
gráfico e a lista!!!
26) Como a memoization pode nos ajudar a economizar espaço em memória e evitar a
sobreposição de subproblemas?
Memoization utiliza na sua estratégia uma solução top-down essa técnica evita que
subproblemas que nunca serão usados sejam resolvidos caso seja utilizado este subproblema
então é buscado em uma tabela. Essa estratégia auxilia economizando tempo de execução e
memória, pois os cálculos já estão salvos na tabela e não precisará ser feito novamente.
Classes de Problemas
27) O algoritmo de programação dinâmica para o problema da mochila booleana é um
algoritmo de tempo polinomial? Justifique sua resposta.
O algoritmo possui tempo pois o tempo no melhor caso provado matematicamente é
polinomial.
28) O que é um problema tratável, intratável, computável e não-computável? Como estas
quatro definições estão relacionadas?
● Problema tratável: tem solução em tempo polinomial(boa situação).
● Problema intratável: ele tem solução em tempo exponencial (situação ruim)
● Computável: Todos os problemas resolvidos em tempo exponencial ou polinomial.
● Não-computável: Problemas que não admitem algoritmos para todos os casos de
entrada.
Como demonstrado os problemas tratáveis e intratáveis são computáveis os que não se
encaixam como tratável e intratável são não-computáveis.
29) O que significa dizer que um problema está fechado? É melhor termos um problema
fechado como tratável ou intratável?
Significa que tanto o limite superior como o limite inferior tem seu tempo de execução
iguais, o melhor é ter um problema fechado tratável pois representa a melhor situação e seu
tempo é polinomial.
30) Diferencie as classes P, NP e NP-Completo. Use um diagrama para representar esses
conjuntos de problemas.
● NP: É a classe de todos os problemas de busca, o conjunto cuja solução é
verificada em tempo polinomial.
● P: Conjunto de problemas que podem ser resolvidas em tempo polinomial para
qualquer instância.
● NPC: É classificado como o conjunto de problemas é tanto NP como NP-Difícil.
32) Explique o que é redução no contexto de classes de problemas e qual a utilidade dessa
estratégia para o estudo de problemas NP-Completo.
entende-se que se alguém encontrar uma solução polinomial para um problema NP-
Completo, então todos os problemas em NP também tem uma solução em tempo polinomial.
Logo, P = NP.
33) Defina o problema SAT e explique por que ele é NP-Completo. O que significa dizer que
uma fórmula booleana está na 3CNF?
O problema SAT determina se as variáveis de uma dada função booleana podem ser
atribuídas de forma que faça a função ser verdadeira.
Significa que uma fórmula booleana é satisfazível quando as cláusulas tem no máximo três
literais, ou seja, três produtos de uma soma conhecido com o 3SAT também.
Literais→ (x1^x2)...
34) Encontre um conjunto de valores booleanos (0 ou 1) para x1, x2, x3 e x4 de modo que a
fórmula (x1 v ¬x3 v x4) ^ (¬x2 v x3 v ¬x4) seja verdadeira, isto é, retorne o valor 1
x1 = 1, x2 = 0, x3 = 1, x4 =1
= (x1 v ¬x3 v x4) ^ (¬x2 v x3 v ¬x4)
= (1 v 0 v 1) ^ (1 v 1 v 0)
= (1) ^(1)
= 1
35) Explique o que diz o Teorema de Cook-Levin. Por que ele é relevante para a Ciência da
Computação?
O SAT foi o primeiro problema na história da computação a ser provado como
NP-Completo.
Foi provado que todo o problema em NP pode ser reduzido a SAT em
tempo polinomial.
Algoritmos de Aproximação
36) Qual a motivação para o surgimento dos algoritmos de aproximação? O que significa
dizer que estes algoritmos heurísticos contam com a sorte ou com o azar?
A motivação foi lidar com problemas intratáveis já que não é possível encontrar uma
solução polinomial para todos esses problemas, um meio termo para isso foi uma aproximação.
A questão da sorte ou azar é na parte é que inicialmente temos que chutar um valor para
começar a heurística e o mesmo pode ficar preso num máximo global e consequentemente não
achar o melhor resultado.
37) Como é calculada a medida de desempenho de um algoritmo de aproximação? Como a
modalidade de maximização e de minimização impacta no cálculo de desempenho de um
algoritmo de aproximação?
O seu desempenho é calculado na diferença ou na razão entre a solução ótima e a
solução produzida entre o algoritmo de aproximação.
Sendo:
● p(n) = Razão de aproximação.
● n = Instância de tamanho n
O impacto das modalidades no cálculo de desempenho:
● Maximização : 0 < C < C*, e a razão C*/C, dá o fator pelo qual o custo de uma solução
ótima é maior do que o custo da solução aproximada.
● Minimização : 0 < C* < C, e a razão C/C*, dá o fator pelo qual o custo de uma solução
aproximada é maior do que o custo da solução ótima.
38) Em que são baseadas as heurísticas dos algoritmos de aproximação?
● São probabilísticos.
● Determinísticos.
39) Você acha que todos os problemas NP-Completo admitem um algoritmo de
aproximação? Justifique sua resposta.
Sim mas a questão é se o algoritmo de aproximação tende a ser mais rápido e espera-se
que o tempo seja totalmente polinomial, aumentando com um fator constante com o aumento de ε.
40) Cite e explique três problemas que possuem solução através de um algoritmo de
aproximação.
Problema 1: Cobertura dos Vértices:
Um subconjunto V’ ⊆ V tal que, se (u,v) é uma aresta de um grafo, então u ∈ V’, v
∈ V’ ou ambos. Recebemos de entrada um grafo não dirigido e não ponderado e de saída
um subconjunto de vértices V’ ⊆ V que toca todas as arestas.
Solução:
É baseado em emparelhamento então é necessário a geração de
emparelhamentos maximais e seja S um conjunto que contenha ambas as
extremidades de cada aresta em um emparelhamento maximal M. Sendo: S→
Cobertura dos vérticese a cobertura S tem 2 | M | vértices
Problema 2 Caixeiro viajante:
Como visitar N cidades, iniciando e terminando em uma delas, com menor custo
possível?
Solução:
Adotando o princípio de desigualdade triangular e respeitando a distância
Euclidiana, ou seja, analisando sempre o menor caminho entre dois pontos. A
distância entre vértices é definida pela distância Euclidiana e o algoritmo baseia-se
no cálculo da árvore geradora mínima do grafo e na visitação dos vértices da
árvore em pré-ordem
Problema 3: Cobertura dos conjuntos:
Utilizado na modelação de muitos problemas de alocação de recursos.
Solução:
Utilizando heurística gulosa simples com uma razão de aproximação
logarítmica. Este método guloso funciona escolhendo, em cada fase, o conjunto S
que cobre o maior número de elementos não cobertos (decidindo empates
aleatoriamente).