lista-exercicios-nocoes-complexidade-tad

Prévia do material em texto

Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Algoritmos e Estruturas de Dados I
Professor: Mário Luiz Rodrigues Oliveira
Atividade: 1ª Lista de Exercícios
Formiga, MG, 29 de maio de 2014
OBSERVAÇÕES:
1. Esta lista de exercícios poderá ser resolvida em grupo de no máximo 2 pessoas.
2. Caso você ache que falta algum detalhe nas especificações, você deverá fazer as suposições que
julgar necessárias e escrevê-las com as suas respostas. Pode acontecer também de algum enunciado
conter dados e/ou especificações supérfluas para a solução de alguma pergunta específica. Utilize sua
capacidade de julgamento para separar o supérfluo do necessário.
3. A data final para entrega desta lista de exercícios é o dia 10/06/2014, via portal meu.ifmg.edu.br.
4. Listas plagiadas serão desconsideradas, sendo atribuída nota 0 (zero) a todos os envolvidos.
5. O valor dessa lista de exercícios é 2 pontos.
EXERCÍCIOS
1) Para cada uma das afirmações abaixo, justifique formalmente (usando definições, manipulações
algébricas e implicações) se for verdade ou dê um contraexemplo se for falso.
a) 2 n + 1 = O (2n)
b) 2 n + a = O (2n)
c) 3n = O (n)
d) 2n2 - n = O(n2)
e) log8 n = O(log2 n)
f) Se f(n) = O (u(n)) e g(n) = O (v(n)), então f(n) - g(n) = O (u(n)) - O (v(n))
g) Se f(n) = O (g(n)) e g(n) = O (h(n)), então f(n) = O (h(n))
h) Se f(n) = O (h(n)) e g(n) = O (h(n)), então f(n) = g(n)
i) Se f(n) = O (u(n)) e g(n) = O (v(n)), então f(n) + g(n) = O (u(n)) + O (v(n))
j) Se f(n) = 3n2 - n + 4, então f(n) = O (n2 )
k) Se f(n) = 17, então f(n) = O (1)
As questões das letras a, f, i foram retiradas do livro do Nívio Ziviani [ZIV].
2) Demonstre as seguintes propriedades da notação Big O.
a) f(n) = O (f(n))
b) c * O (f(n)) = O (f(n)), onde c é uma constante
c) O (f(n)) + O (f(n)) = O (f(n))
d) O (f(n)) * O (g(n)) = O (f(n) * g(n))
e) f (n) * O(g(n)) = O (f(n) * g(n))
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Algoritmos e Estruturas de Dados I
Professor: Mário Luiz Rodrigues Oliveira
Atividade: 1ª Lista de Exercícios
Formiga, MG, 29 de maio de 2014
3) Faça um algoritmo que verifique se os elementos de um vetor estão ordenados de forma ascendente. Qual
a complexidade de pior, melhor e caso médio do seu algoritmo? Justifique suas respostas.
4) [ZIV- Exercício 1.3] O que significa dizer que um algoritmo executa em tempo proporcional a n?
5) [ZIV- Exercício 1.4] Explique a diferença entre O(1) e O(2).
6) [ZIV- Exercício 1.1-Modificado] Dê o conceito de:
a) algoritmo;
b) tipos de dados;
c) tipo abstrato de dados;
d) estrutura de dados;
e) linguagem de programação;
f) programa.
7) Calcule a complexidade assintótica dos códigos abaixo: Justifique suas respostas
a) soma <- 0;
 para i de 1 até n faça
para j de 1 ate n faça
soma <- soma + 1;
b) soma1 <- 0;
 para i de 1 até n faça
para j de 1 ate i faça
soma1 <- soma1 + 1;
c)para i de 1 até n faça
para j de 1 ate n faça
a[i][j] <- b[i][j] + c[i][j];
d) para i de 1 até n faça
para j de 1 ate n faça
para k de 1 ate j faça
alguma instrução executa com complexidade O(1)
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Algoritmos e Estruturas de Dados I
Professor: Mário Luiz Rodrigues Oliveira
Atividade: 1ª Lista de Exercícios
Formiga, MG, 29 de maio de 2014
8) [CLRS- Exercício 2.2-4] Como podemos modificar praticamente qualquer algoritmo para ter um bom
tempo de execução no melhor caso? Você acha que analisar um algoritmo pelo seu melhor caso é uma boa
escolha? Justifique sua resposta.
9) Por muitas vezes damos atenção apenas à análise do pior caso dos algoritmos. Explique o porquê.
10) [CLRS- Exercício 1.2-3] Qual é o menor valor de n tal que um algoritmo A cujo tempo de execução é
100 n² é mais rápido que um algoritmo B com tempo de execução igual a 2n numa mesma máquina?
11) Suponha um algoritmo com complexidade O(n*lg n) para todas as instâncias do problema. Considere
que para N = 10.000.000, o tempo necessário para executar o programa equivalente a este algoritmo é de 8
segundos. Assuma que exista memória suficiente para executá-lo quando N = 1.000.000.000. Qual o tempo
de execução desse programa para N = 1.000.000.000? Dê sua resposta em segundos e em horas. Obs: lg
representa o logaritmo na base 2.
12) A tabela abaixo apresenta trechos de programas e suas respectivas análises de eficiência. São mostradas
duas análises: uma simples usando a notação Big O e outra detalhada contando todas as operações
executadas. Estas análises consideram uma unidade de tempo para qualquer tipo de operação. Verifique se os
resultados indicados estão corretos. Justifique suas respostas.
x <- a + b para i de 1 até n faça
 x <- a + b
para i de 1 até n faça
 para j de 1 até n faça
 x <- a + b
Simples: O(1) Simples: O(n) Simples: O(n2)
Detalhada: f(n) = 2 Detalhada: f(n) = 5*n + 2 Detalhada: f(n) = 5*n2 + 5*n+ 2
13) Uma métrica possível para avaliar algoritmos é a métrica empírica. Ela consiste em escolher um critério
de análise e um conjunto de entradas variadas. Após tais decisões implementa-se o algoritmo numa
linguagem de programação. Finalmente executa-se o programa com as entradas e faz-se uma análise dos
resultados. Esse procedimento pode ser utilizado para comparar dois ou mais programas. Critique essa
métrica.
14) Considere que existam dois algoritmos, denominados A e B, para resolver um determinado problema. O
algoritmo A exige 108*n operações e o algoritmo B exige 10*n2.
a) Calcule a complexidade assintótica de cada um desses algoritmos
b) Pode-se afirmar que o algoritmo A é sempre melhor que o algoritmo B?
15) [ZIV- Exercício 1.5] Qual algoritmo você prefere: um algoritmo que requer n5 passos ou um que requer
2n passos. Justifique sua resposta.
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Algoritmos e Estruturas de Dados I
Professor: Mário Luiz Rodrigues Oliveira
Atividade: 1ª Lista de Exercícios
Formiga, MG, 29 de maio de 2014
16) [ZIV- Exercício 1.2] O que significa dizer que g(n) é O (f(n)).
17) Considere o problema de percorrer um vetor não ordenado para encontrar um determinado elemento.
Calcule a complexidade assintótica do caso médio nas seguintes condições:
a) o elemento procurado encontra-se no vetor e a probabilidade de encontrá-lo em quaisquer posição do
vetor é a mesma e igual 1/n;
b) o elemento procurado encontra-se no vetor e a probabilidade de encontrá-lo na primeira posição do vetor
é ½, a probabilidade de encontrá-lo na segunda posição é ¼ e a probabilidade de encontrá-lo em quaisquer
das outras posições é a mesma e igual a 1/(4n-8);
c) o elemento procurado encontra-se no vetor em 50% das vezes e a probabilidade de encontrá-lo em
quaisquer posições vetor é a mesma e igual 1/n;
18) Defina um Tipo Abstrato de Dados (TAD) que represente números complexos. Implemente, na
linguagem de programação Pascal, um módulo que representa o TAD números complexos e faça um
pequeno programa para testar sua implementação.
19) Defina um Tipo Abstrato de Dados (TAD) que represente pontos2D. Implemente, na linguagem de
programação Pascal, um módulo que representa o TAD pontos2D e faça um pequeno programa para testar
sua implementação.
20) Defina um Tipo Abstrato de Dados (TAD) que represente pontos3D. Implemente, na linguagem de
programação Pascal, um módulo que representa o TAD pontos3D e faça um pequeno programa para testar
sua implementação.
Bibliografia:
[ZIV] ZIVIANI, Nivio. Projeto de Algoritmos – Com implementação em Pascal e C. 3ª edição revista e
ampliada.São Paulo: Cengage Learning, 2011.
[CLRS] CORMEN, T. et al. Algoritmos: Teoria e Prática. Editora Campus, 2002.