Tarefa 1 - PAA

Prévia do material em texto

UNIVERSIDADE FEDERAL DO PARÁ 
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS PROGRAMA 
DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO 
 
Disciplina: - PPGCC0107 - Projeto e Análise de Algoritmos 
Professor: Lídio Mauro Lima de Campos 
Data de Entrega: 09/11/2021 
 
LISTA DE EXERCÍCIOS 1 -Referente ao Capítulo 1 – Análise de Algoritmos e Problemas - 
Princípios e Exemplos e Capítulo 2- Crescimento de Funções - Ordens Assintóticas 
1)(2.0 pts) Implementar os algoritmos maxmin1, maxmin2 , maxmin3 e maxmin4 apresentados 
na primeira unidade e que possuem a funcionalidade de encontrar o maior e o menor elemento 
de um arranjo de n elementos. Faça uma análise comparativa entre os algoritmos, considerando 
o número de comparações como medida de complexidade. Para o algoritmo maxmin4, a 
implementação deve ser recursiva. 
2)(0.5pts)Um método de ordenação “Big-Ohh” tem complexidade O(n log n) emprega 1 
milissegundo (10-3s) para ordenar 1000 itens de dados. Assumindo que o tempo para 
ordenar n itens é diretamente proporcional a n log n, isto é, T(n)=c.n log n , obtenha uma 
fórmula para T(n) , dado o tempo T(N) para ordenar N itens, e estime quanto tempo levará 
para ordenar 1.000.000 itens. 
 
3)(0.75pt)Sabendo-se que um determinado computador executa 10M (106 ) 
instruções/segundo, construir a Tabela 1 (que descreve os tamanhos limites de problemas 
resolvíveis por algoritmos de diferentes Complexidades, coluna 1) , visando obter qual o tempo 
para ordenar um vetor de 106 elem? 
 
 
 
4)(0.75pt)Estimar o tamanho máximo de um problema resolvível em uma máquina 10(dez) 
vezes mais rápida, considerando as complexidades apresentadas na coluna 1 da Tabela 2, 
tomando por base o tamanho máximo de problema resolvível na máquina mais lenta (segunda 
coluna da Tabela 2). 
 
Tabela 1 - Complexidade do Algoritmo x Tempo de Execução 
 
UNIVERSIDADE FEDERAL DO PARÁ 
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS PROGRAMA 
DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO 
 
Disciplina: - PPGCC0107 - Projeto e Análise de Algoritmos 
Professor: Lídio Mauro Lima de Campos 
Data de Entrega: 09/11/2021 
 
 
Tabela 2 - Complexidade do Problema x Tamanho Máximo do Problema Resolvível 
 
 
 
 
 
5)(0.25pts)Usando notação assintótica, descreva a complexidade no tempo do algoritmo abaixo. 
Ele recebe dois vetores A e V de tamanhos n e w, respectivamente. 
TESTE (A, V, n, w) 
1. para i = 1 até n faça 
2. para j = 1 até w faça 
3. V[j] = A[i] + 2 
4. max = V[1] 
5. para j = 2 até w faça 
6. se max < V[j] então max = V[j] 
6)(0.25pts) Observe as funções representadas no gráfico abaixo. 
 
Assinale a afirmativa correta sobre o crescimento assintótico dessas funções. 
(a) f(n) = O(h(n)) e f(n) = w(g(n)). 
(b) g(n) = Ω(f(n)) e f(n) = Θ(h(n)). 
(c) g(n) = O(f(n)) e g(n) = Ω(h(n)). 
(d) h(n) = w(g(n)) e g(n) = Θ(f(n)). 
(e) h(n) = Ω(f(n)) e h(n) = O(g(n)). 
 
UNIVERSIDADE FEDERAL DO PARÁ 
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS PROGRAMA 
DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO 
 
Disciplina: - PPGCC0107 - Projeto e Análise de Algoritmos 
Professor: Lídio Mauro Lima de Campos 
Data de Entrega: 09/11/2021 
 
7) (1pt) Assumindo que cada expressão representa o tempo de processamento de um algoritmo 
para resolver um problema de tamanho n. Selecione o termo dominante e especifique a 
complexidade no pior caso. 
 
8)(1pt)Indique se as afirmativas a seguir são verdadeiras ou falsas, justifique as suas 
respostas, para cada resposta dada V ou F. 
a)100n está em O(n2 ) 
b)5n+3=O(n) 
c)log n está em O(n) 
d)g(n)=2n2+3n+4 e f(n)=n2 , g(n)=0(f(n)) 
e) 22n = O(2n ) 
 
9)(1pt) Sejam f, g e h funções reais positivas da variável inteira n, análise as 
alternativas abaixo como verdadeiras ou falsas (justificando cada resposta, para V ou 
F) de acordo com os conceitos de notações assintóticas. 
 
a)A notação Θ exprime o fato de que duas funções possuem a mesma ordem de grandeza 
assintótica. 
b)por exemplo se f=3n3 + 20n2 + 5 , g=3 log n + 5 , h=n2 , então f é O(n3), g é O(log n), h é 
O(n). 
 
c)ℎ = √ =Ω(lg n) 
 
d)Podemos dizer que f=x2 é O(x!) , mas não o contrário 
 
 
UNIVERSIDADE FEDERAL DO PARÁ 
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS PROGRAMA 
DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO 
 
Disciplina: - PPGCC0107 - Projeto e Análise de Algoritmos 
Professor: Lídio Mauro Lima de Campos 
Data de Entrega: 09/11/2021 
 
e) Podemos dizer que f=5log2(n) é O(n), e o contrário também. 
 
10)(1pt) As afirmativas abaixo são verdadeiras ou falsas? Justifique cada resposta. 
 
a) 2n2 + 1000 =Ω(n2). 
 
b) 2 = O(2 ) 
 
c) Podemos dizer que n2 é (2n), mas não o contrário. 
 
d) Sejam f (n) = n2 + 2n + 1 e g(n) = n2. f(n)= Θ(g(n)?. 
 
e) Assim como a notação O é útil para descrever limites superiores assintóticos, a notação Ω é 
empregada para limites inferiores assintóticos. 
 
11)(0.5pt)Suponha que dois algoritmos, A e B, resolvem um mesmo problema. Suponha que o 
tamanho das instancias do problema é medido por um parâmetro n. Em quais dos seguintes 
casos podemos afirmar que A é mais rápido que B? 
 
Caso 1: A consome tempo O(log(n)) no pior caso e B consome tempo O(n3) no pior caso. 
 
Caso 2: A consome O(n2log(n)) unidades de tempo no pior caso e B consome O(n2) 
unidades de tempo no pior caso. 
 
Caso 3: No pior caso, A consome O(n) unidades de tempo e B consome O(nlog(n)) unidades de 
tempo. 
 
12)(1pt) mostrar que: 
 a)6n3 ≠ Θ(n2)