Exercicio-1

Prévia do material em texto

Lista de Exercícios de Análise de Algoritmos
Antonio Ramos de Carvalho Júnior
1 Exercícios
1. Descreva um problema real que pode ser solucionado por meio de algoritmos de de ordenação e
apresente uma solução para o mesmo, justificando a sua escolha.
2. Quais parâmetros podem ser utilizados como medidas de eficiência para a solução de um deter-
minado problema. Discorra sobre as vantagens e em quais cenários existem uma limitação para
tais parâmetros.
3. Mostre um problema real no qual apenas a melhor solução servirá. Em seguida, apresente um
problema em que baste uma solução que seja ”aproximadamente” a melhor. (Cormen, Thomas
H., 1.1-5 pg 7)
4. Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n2 funciona mais
rápido que um algoritmo cujo tempo de execução é 2n na mesma máquina? (Cormen, Thomas
H., 1.2-3 pg 9)
5. Para cada uma função f(n) e cada tempo t na tabela a seguir, determine o maior tamanho n
de um problema que pode ser resolvido no tempo t, supondo-se que o algoritmo para resolver o
problema demore f(n) microsegundos. Dica: Utilize suas habilidades em desenvolvimento para
uma solução mais rápida e precisa =D. (Cormen, Thomas H., 1-1 pg 9)
1 segundo 1 minuto 1 hora 1 dia 1 mês 1 ano 1 século
lgn√
n
n
nlgn
n2
n3
2n
n!
6. Usando a figura abaixo como modelo, ilustre a operação de INSERTION-SORT no arranjo A =<
31, 41, 59, 26, 41, 58 >. (Cormen, Thomas H., 2.1-1 pg 15)
7. Considere um arranjo A com n elementos, faça um pseudocódigo para buscar um elemento x
neste arranjo considerando que:
(a) o arranjo A não possui nenhuma ordem;
(b) o arranjo A está em ordem crescente;
1
(c) o arranjo A está em ordem decrescente.
8. Qual a ordem aplicada a um determinado arranjo pelo algoritmo ORDENA (crescente ou de-
crescente)? Qual a mudança necessária no mesmo para que ele faça a odenação em sentido
contrário?
1: procedure ORDENA
2: for j ← 2 to n do
3: chave← A[j]
4: j ← j − 1
5: while i > 0 e A[i] > chave do
6: A[i+ j]← A[i]
7: i← i− 1
8: A[i+ j]← chaves
9. Discorra sobre a análise de algoritmos, qual sua importância, que fatores devem ser observados
e qual a maneira de definir que um algoritmo é X melhor que outro algoritmo Y .
10. Expresse as funções f(n) abaixo em termos da notação Θ:
(a) 10n2 + 5n− n3
(b) n+ 10k2
(c) n3/100 + 100n2 − 100n+ 3
(d) n10 + 2n
11. Considere a ordenação de n números armazenados no arranjo A, localizando primeiro o menor
elemento de A e permutando esse elemento com o elemento contido em A[1]. Em seguida, encontre
o segundo menor elemento de A e o troque pelo elemento A[2]. Continue dessa maneira para os
primeiros n − 1 elementos de A. Escreva o pseudocódigo para esse algoritmo, conhecido como
ordenação por seleção. Que loop invariante esse algoritmo mantém? por que ele só precisa ser
executado para os primeiros n−1 elementos e não para todos os n elementos? Forneça os tempos
de execução do melhor caso e do pior caso da ordenação por seleção em notação Θ. (Cormen,
Thomas H., 2.2-2 pg 20)
12. Reescreva o procedimento abaixo de modo que ele não utilize sentinelas e, em vez disso, se
interrompa depois que o arranjo L ou R tiver todos os seus elementos copiados de volta para A,
e então copie o restante do outro arranjo de volta em A.
2
13. Ilustre a operação de ordenação por intercalação para o arranjo A =< 3, 41, 52, 26, 38, 57, 9, 49 >.
14. Uma abordagem empregada em projetos de algoritmos é a de dividir e conquistar, explique quais
são os requistos para que um algoritmo seja divisível. Escolha um exemplo de algoritmo divisível
apresente um pseudocódigo que solucione-o utilizando uma abordagem sem divisão e conquista
e outra com divisão e conquista.
15. Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique a sua resposta: (Ziviani,
Nivio. Questão 7, pg 30) e (Cormen, Thomas H., 3-4 pg 47)
(a) (2n+1) = Ω(2n)
(b) (22n) = Ω(2n)
(c) max(f(n), g(n)) = Θ(f(n) + g(n)) sendo f(n) e g(n) duas funções assintoticamente não
negativas.
(d) (n+ a)b = Θ(nb) para quaisquer constantes a e b, onde b > 0
(e) f(n) + g(n) = Θ(min(f(n), g(n))
16. Suponha um algoritmo A e um algoritmo B, com funções de complexidade de tempo a(n) =
n2 − n + 549 e b(n) = 49n + 49, respectivamente. Determine quais valores de n pertencentes
ao conjunto dos números naturais para os quais A leva menos tempo para executar do que B.
(Ziviani, Nivio. Questão 9, pg 30)
17. Forneça limites assintóticos superiores e inferiores para T (n) em cada uma das recorrências a
seguir. Suponha que T (n) seja constante para n ≤ 2. Torne seus limites tão restritos quanto
possível e justifique sua resposta.
DICA 1: Você pode utilizar as definições assintóticas para justificar sua resposta.
DICA 2: Sempre que for difícil encontrar o comportamento da recorrência, você pode utilizar
mecanismos matemáticos para obter uma recorrência mais simples, assim como já foi demonstrado
em sala de aula.
(a) T (n) = 2T (n/2) + n3
(b) T (n) = T (9n/10) + n
(c) T (n) = 2T (n/2) + n3
(d) T (n) = T (
√
n) + 1
18. Use o método mestre para fornecer limites assintóticos restritos para as recorrências a seguir:
(Cormen, Thomas H., .43-1 pg 60)
(a) T (n) = 4T (n/2) + n
(b) T (n) = 4T (n/2) + n2
(c) T (n) = 4T (n/2) + n3
19. O tempo de execução de um algoritmo A é descrito pela recorrência T (n) = 7T (n/2) + n2. Um
algoritmo concorrente A′ tem um tempo de execução T ′(n) = aT ′(n/4) + n2. Qual é o maior
valor inteiro para a tal que A′ seja assintoticamente mais rápido que A? (Cormen, Thomas H.,
4.3-2 pg 61)
20. Resolva os somatórios abaixo:
3
(a)
∑50
i=0(3 + i)
(b)
∑10
k=0(5 + 4k)
(c)
∑n
i=0 ai
(d)
∑n
i=0 a
i
(e)
∑n
i=0
∑i
j=0 a
21. Forneça os limites assintóticos para os algoritmos abaixo:
(a) 1: procedure ORDENA
2: for j ← 2 to n do
3: chave← A[j]
4: j ← j − 1
5: while i > 0 e A[i] > chave do
6: A[i+ j]← A[i]
7: i← i− 1
8: A[i+ j]← chaves
(b) 1: procedure FAT(n)
2: if n > 1 then
3: return n ∗ FAT (n− 1);
4: else
5: return 1;
(c) 1: procedure MULTIPLICA(A, B)
2: for i← 0 to M do
3: for i← 0 to M do
4: for k ← 0 to M do
5: C[i][j] = C[i][j] + (A[i][k] ∗B[k][i]);
2 Referências
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Algoritmos Teoria e
Prática, Tradução da 2a edição americana, Editora Campus, 2002.
Ziviani, Nivio. Projeto de Algoritmos. 2a edição revisada e ampliada Editora Thomson, 2004.
4
3 Propriedades Somatórios
1.
∑n
i=m αf(i) = α
∑n
i=m f(i)
2.
∑n
i=m[f(i)± g(i)] =
∑n
i=m f(i)±
∑n
i=m g(i)
3.
∑m
i=m f(i) = f(m)
4.
∑n
i=a f(i) =
∑p
i=a f(i) +
∑n
i=p+1 f(i)
5.
∑n
i=m f(i) =
∑n+p
i=m+p f(i− p)
6.
∑n
i=m f(i) =
∑−m
i=−n f(−i)
7.
∑n
i=m[f(i+ 1)− f(i)] = f(n+ 1)− f(m)
8.
∑n
i=m
∑l
j=k f(i)g(j) =
∑n
i=m f(i)
∑l
j=k g(j)
9. |∑ni=m f(i)| ≤∑ni=m |f(i)|
4 Links para auxiliar
1. Propriedades de Logarítmos: <http://www.infoescola.com/matematica/logaritmo/>
2. Propriedades de Equações Exponenciais: <http://www.infoescola.com/matematica/equacao-exponencial/>
5