PAA_ListaAv2_Gab (2)

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL DO PIAUÍ 
CENTRO DE EDUCAÇÃO ABERTA E A DISTÂNCIA 
CURSO DE SISTEMAS DE INFORMAÇÃO 
PROJETO E ANÁLISE DE ALGORITMOS 
 
2ª LISTA DE EXERCÍCIOS DE PROJETO E ANÁLISE DE ALGORITMOS 
 
1. Quanto tempo (em números de operações) é gasto para executar o seguinte algoritmo? 
Para i  1 até n – 1, faça n – 1 vezes 
 Para k  1 até n, faça n x (n-1) vezes 
 S[i, k]  S[i, k] - S[i, k] * S[i, i] / S[i, i] 4n x (n-1) vezes 
 T(n) = n – 1 + n² - n + 4n² - 4n = 5n² - 4n - 1 
2. Determine o tempo consumido na execução do algoritmo abaixo: 
S  0; 1 vez, O(1) 
Para i  1 até n, faça n vezes, O(n) 
 S  S + A[i] 2n vezes, O(n) 
 m  S/n 2n vezes, O(n) 
 k  1 n vezes, O(n) 
Para i  2 até n, faça n vezes, O(n) 
 Se (A[i] – m)/2 < (A[k] – m)/2, então n log n vezes, O(n log n) 
 k  i n log n vezes, O(n log n) 
retorne k. 1 vez, O(1) 
3. Explique as etapas do método dividir-para-conquistar. 
O algoritmo tem 3 etapas: Divisão, Conquista e Combinação. A etapa de divisão, o 
algoritmo divide recursivamente um problema em subproblemas. A etapa de 
conquista é quando o algoritmo resolve os subproblemas encontrando as soluções e a 
etapa de combinando é quando o algoritmo combina todas as soluções dos 
subproblemas para encontrar uma única solução do problema inicial. Exemplos: os 
algoritmos de ordenação mergesort, quicksort,... 
 
4. Determinar uma parentização ótima para o produto de matrizes cuja sequência de 
dimensões é [5, 10, 3, 12, 5, 50, 6]. 
 
 
 
 
M1 = 5 x 10, M2 = 10 x 3, M3 = 3 x 12, M4 = 12 x 5, M5 = 5 x 50 e M6 = 50 x 6 
M1 x M2 = 5 x 10 x 3 = 150 operações 
M3 x M4 = 3 x 12 x 5 = 180 operações 
M5 x M6 = 5 x 50 x 6 = 1500 operações 
(M3 x M4) x (M5 x M6) = 3 x 5 x 6 = 90 operações 
(M1 x M2) x ((M3 x M4) x (M5 x M6)) = 5 x 3 x 6 = 90 operações 
150 + 180 + 1500 + 90 + 90 = 2010 operações 
 
5. O método guloso sempre fornece uma solução ótima? Justifique sua resposta através 
de um exemplo. 
Nem sempre o método guloso fornece uma solução ótima, por exemplo, no problema 
do troco, quando se tem as moedas de 50 centavos, 25 centavos, 10 centavos e 1 
centavo e se quer devolver um troco de 30 centavos com a menor quantidade de 
moedas, pelo método guloso, ele vai escolher primeiro 1 moeda de 25 centavos e 
depois 5 moedas de 1 centavo, dando um total de 6 moedas mas a solução ótima 
seria 3 moedas de 10 centavos. 
 
6. Explique o método guloso. 
Método Guloso é a estratégia usada por algoritmos que consiste na escolha da 
melhor solução em determinado instante. Ele faz uma escolha ótima localmente 
esperando que esta escolha leve a uma solução ótima global. É muito utilizado para 
resolver problemas de otimização. Exemplos de algoritmos: Problema do troco, 
Problema da árvore geradora mínima... 
 
7. Explique o método “programação dinâmica”. 
Programação Dinâmica resolve problemas combinando as soluções dos 
subproblemas, é aplicável quando os subproblemas não são independentes, havendo 
assim a necessidade de uma tabela para armazenamento dos resultados a serem 
compartilhados e evitar cálculos repetidos. A programação dinâmica pode ser 
dividida em quatro passos: Caracterização da estrutura de uma solução ótima; 
Definir recursivamente o valor de uma solução ótima; Cálculo do valor de uma 
solução ótima e Construção de uma solução ótima a partir da informação computada. 
Exemplos de algoritmos: Multiplicação de diversas matrizes, o problema da 
mochila... 
 
 
 
 
8. Modificar o algoritmo de Dijkstra implementando a lista de prioridade com o uso de 
“heap”. Determinar a complexidade desse algoritmo. É melhor do que o algoritmo 
apresentado na apostila? (pesquisar no livro do Cormen ou na internet) 
Pesquisar na internet 
9. Julgue as seguintes assertivas como verdadeira (V) ou falsa (F), justifique ou dê um 
contraexemplo: 
a) (V) Existem problemas NP que não estão na classe NP-Completo. Os problemas 
P, eles são verificáveis em tempo polinomial, então eles são NP mas não NP-
Completo. 
b) (V) A classe NP-Completo contém todos os problemas NP-Difíceis. 
c) (V) Se houver uma solução polinomial para o problema SAT, então P = NP. 
Porque todos os problemas NP-Completos são redutíveis a SAT em tempo 
polinomial. 
d) (F) NP-Completo é classe dos problemas computacionais para os quais não existe 
um algoritmo polinomial. Essa é a classe de problemas intratáveis mas que existe 
algoritmo polinomial para reduzir um problema a outro. 
e) (F) Se um problema A, NP-difícil, é redutível polinomialmente a outro B, então 
B também será NP-difícil. Um problema A é NP-Difícil se todos os problemas 
NP-Difíceis podem ser reduzidos em tempo polinomial a A. 
f) (V) As soluções dos problemas NP são implementáveis, havendo várias técnicas 
para isso, como algoritmo exponencial, probabilístico e de aproximação. 
 
 
 
Bom Trabalho!