Centro Federal de Educação Tecnológica de Minas Gerais
Programa de Pós-Graduação em Modelagem Matemática e
Computacional
Disciplina: Algoritmos e Estruturas de Dados
Professor: Flávio Cardeal
Lista de Exercı́cios 1 - 20/08/2015 - 15 pontos
Data de entrega: 29/09/2015
1. Dê o conceito de: (a) algoritmo; (b) tipo de dados; (c) tipo abstrato de dados.
2. O custo de utilização de um algoritmo pode ser medido de várias maneiras. Descreva
as principais técnicas, apontando suas eventuais vantagens e desvantagens.
3. O que significa dizer que uma função g(n) é O(f (n))?
4. Indique se as afirmativas abaixo são verdadeiras ou falsas e justifique a sua resposta
utilizando a definição de dominação assintótica em cada caso.
(a) 22n = O(3n )
(b) 2n+1 = o(3n )
(c) f (n) = O(u(n)) e g(n) = O(v(n)) ⇒ f (n) + g(n) = O(u(n) + v(n))
(d) f (n) = O(u(n)) e g(n) = O(v(n)) ⇒ f (n) − g(n) = O(u(n) − v(n))
5. Prove que f (n) = 12 + 22 + ... + n2 é igual a n3 /3 + O(n2 ).
6. Apresente um algoritmo para obter o maior e o segundo maior elemento de um
conjunto. Apresente também uma análise do algoritmo. Você acha o seu algoritmo
eficiente? Por quê? Procure comprovar suas respostas.
7. Implemente em Linguagem C os três algoritmos apresentados nos Programas 1.3,
1.4 e 2.8 do livro texto, para obter o máximo e o mı́nimo de um conjunto contendo n
elementos. Execute os algoritmos para valores suficientemente grandes de n, gerando
casos de teste para o melhor caso, pior caso e caso esperado. Meça o tempo de
execução para cada algoritmo dos três casos acima. Comente os resultados obtidos.
8. Avalie as somas:
P
(a) ni=1 ai
P
(b) ni=1 1i
P
(c) ni=1 log i
P
1
(d) n−1
i=1 i(i+1)
1
9. Resolva as seguintes equações de recorrência:
T (n) = T (n − 1) + c, c constante, n > 1
(a)
T (1) = 0
T (n) = 2T (n/4) + n, para n > 1
(b)
T (1) = 27
T (n) = xT (n/2) + yn, para n > 1
(c)
T (1) = 1
10. Apresente a complexidade de tempo para as funções abaixo:
(a)
void Funcao(int *a)
{
int i, j, k;
for (i=1; i < 3; i++)
for (j=i; j < n+1; j++)
for (k=i; k < j+1; k++)
*a = *a + i + j + k;
}
(b)
void Pesquisa(int n)
{
if (n > 1)
{
Inspecione n*n*n elementos;
Pesquisa(2n/3);
}
}
(c)
int Funcao(int n)
{
if (n == 0)
return(1);
else
return(Funcao(n-1)+Funcao(n-1));
}
2
(d)
void Funcao(int n)
{
if (n > 1)
{
Divide n em 3 partes iguais n1, n2, n3
com custo de n*n passos;
Funcao(n1);
Funcao(n2);
Funcao(n3);
}
}
11. Prove por indução que as seguintes propriedades são verdadeiras:
i2
h
n(n+1)
3
3
3
3
, para todo n ∈ N
(a) 1 + 2 + 3 + ... + n =
2
(b) 1 + 2n ≤ 3n , para todo n ∈ N
(c) n! > 2n , para todo n ≥ 4
12. Seja a definição recursiva para a multiplicação de dois números naturais a e b:
a ∗ b = a, se b = 1
a ∗ b = a ∗ (b − 1) + a, se b > 1
Construa dois algoritmos, um recursivo e um iterativo, para a multiplicação de dois
números naturais. Implemente-os em Linguagem C. Apresente a complexidade de
tempo para as funções implementadas.
13. Determine o que faz a função recursiva a seguir. Mostre seu raciocı́nio.
int Recursiva(int n) {
int x;
if n <= 0
x = 1;
else
x = Recursiva(n-1) + Recursiva(n-1);
return x;
}
14. Construa um algoritmo recursivo para encontrar o maior elemento das entradas
A[1], A[2], ..., A[n] de um arranjo A. O procedimento deve dividir o arranjo em duas
partes de tamanhos aproximadamente iguais. Derive uma relação de recorrência
para a função de complexidade f , onde f (n) é definida como o número de comparações entre os elementos de A e n pode ser considerado como uma potência de
2. Resolva a equação de recorrência.
3
15. Pesquise e relate de maneira didática três exemplos de problemas onde são comumente aplicados algoritmos de tentativa e erro.
16. Seja P um conjunto de pontos definidos a partir das coordenadas cartesianas em
um plano. Apresente um algoritmo baseado em divisão e conquista para encontrar
o par de pontos mais próximos.
17. Sejam n objetos a serem ordenados de acordo co as seguintes relações: < e =. Por
exemplo, com 3 objetos existem 13 ordenações possı́veis.
a=b=c
a=c<b
c<a=b
a=b<c
b<a=c
c<a<b
a<b=c
b<a<c
c<b<a
a<b<c
b<c<a
a<c<b
b=c<a
.
Apresente um algoritmo baseado em programação dinâmica que possa calcular, como
função de n, o número de diferentes ordenações possı́veis.
18. Considere a implementação de listas lineares utilizando apontadores e com célula
cabeça. Considere que um dos campos do TipoItem é uma chave: TipoChave.
Escreva uma função em C, cujo cabeçalho segue abaixo:
int EstaNaLista(TipoChave Ch, TipoLista *Lista);
que retorna 1 se Ch estiver na lista e retorna 0 se Ch não estiver na lista. Considere
que não há ocorrências de chaves repetidas na lista. Determine a complexidade do
seu algoritmo.
19. Um problema que pode surgir na manipulação de listas lineares simples é o de voltar
atrás na lista, ou seja, percorrê-la no sentido inverso ao dos apontadores. A solução
geralmente adotada é a incorporação à célula de um apontador para o seu antecessor.
Listas deste tipo são chamadas de duplamente encadeadas. A Figura 1 mostra
uma lista deste tipo com estrutura circular e a presença de uma célula cabeça.
Figura 1: Lista circular duplamente encadeada.
a) Declare os tipos necessários para a manipulação da lista.
b) Escreva uma função em C para retirar da lista a célula apontada por p:
4
void Retira(Apontador p, TipoLista *Lista);
20. Considere uma expressão matemática que inclui vários parênteses aninhados como,
por exemplo:
7 - ((X * ((X + Y) / (J - 3)) + Y) / (4 - 2.5))
Para se assegurar que os parênteses estão aninhados corretamente, precisa-se verificar que:
- existe um número de parênteses à direita igual ao número de parênteses à
esquerda;
- todo parêntese à direita é precedido por um parêntese correspondente à esquerda.
Considere que cada parêntese à esquerda abre um escopo, enquanto cada parêntese
à direita fecha um escopo. Sendo assim, duas condições devem ser satisfeitas, de
forma que o uso de parênteses em uma equação seja feito corretamente:
1. o número de parênteses à esquerda menos o número de parênteses à direita
da expressão deve ser zero. Isso significa que nenhum escopo foi deixado aberto.
2. o número de parênteses à esquerda menos o número de parênteses à direita
em cada ponto da expressão é positivo. Isso significa que nenhum parêntese à direita
é encontrado para o qual um correspondente parêntese à esquerda não tenha sido
aberto previamente. Por exemplo, observe abaixo o número de parênteses à esquerda
menos o número de parênteses à direita em cada ponto da expressão:
7 - ( ( X * ( ( X + Y ) / ( J - 3 ) ) + Y ) / ( 4 - 2.5 ) )
0 0 1 2 2 2 3 4 4 4 4 3 3 4 4 4 4 3 2 2 2 1 1 2 2 2 2 1 0
Uma pilha pode ser utilizada para averiguar se o uso de parênteses em uma equação
está correto. Sempre que um escopo é aberto, um parêntese à esquerda é empilhado
na pilha. Por outro lado, sempre que um escopo é fechado, a pilha é examinada.
Se a pilha estiver vazia, o finalizador de escopo (parêntese à direita) não possui um
correspondente parêntese à esquerda e, portanto, a string é inválida. Se, porém, a
pilha não estiver vazia, deve-se desempilhar a pilha e verificar se o item desempilhado corresponde ao finalizador de escopo. Se ocorrer uma correspondência correta,
continua-se o processo, caso contrário, a string é inválida. Quando se alcançar o
final da string, a pilha deve estar vazia. Caso contrário, um ou mais escopos foram
abertos e não fechados posteriormente, sendo a string inválida. Escreva e implemente um algoritmo em C para averiguar se o uso de parênteses em uma equação
está correto ou não.
5
21. Uma fila com prioridades é uma estrutura de dados na qual a ordem intrı́nseca dos
elementos determina os resultados das suas operações básicas. Pesquise na literatura
sobre este tipo de estrutura de dados, defina seus principais tipos e onde as mesmas
são usualmente aplicadas. Escreva uma função em C responsável por implementar
a operação Desenfileira em tal fila.
22. Dado que existe necessidade de ordenar arquivos de tamanhos diversos, podendo
também variar o tamanho dos registros de um arquivo para outro, apresente uma
discussão sobre quais algoritmos de ordenação (Seleção, Inserção, Shellsort e Quicksort) você escolheria diante das diversas situações possı́veis. Que observações adicionais você apresentaria caso haja restrições de estabilidade ou de intolerância para
o pior caso (isto é, a aplicação exige um algoritmo eficiente, mas não permite que
ele eventualmente demore muito tempo para executar)?
23. Invente um vetor-exemplo de entrada para demonstrar que ordenação por Seleção
é um método instável. Mostre os passos da execução do algoritmo até que a estabilidade seja violada. Note que quanto menor for o vetor que você inventar, mais
rápido você vai resolver a questão.
24. Para os seguintes algoritmos de ordenação interna: Inserção, Seleção, Shellsort e
Quicksort:
a) Determine experimentalmente o número esperado de (i) comparações e (ii)
movimento-de-registros para cada um dos quatro métodos de ordenação. Utilize a
função PermutacaoRandomica abaixo para obter uma permutação randômica dos
valores de um vetor A de n elementos. Utilize arquivos de diferentes tamanhos com
chaves geradas randomicamente. Repita cada experimento algumas vezes e obtenha
a média para cada medida de complexidade. Dê sua interpretação dos dados obtidos,
comparando-os com resultados analı́ticos.
b) Uma opção, para o caso do uso de máquinas que permitem medir o tempo
de execução de um programa, é considerar os mesmos algoritmos propostos e determinar experimentalmente o tempo de execução de cada um dos quatro métodos
de ordenação indicados. Use um gerador de números aletórios para gerar arquivos
de tamanhos 500, 2.000 e 10.000 registros. Para cada tamanho de arquivo utilize
dois tamanhos de registros, a saber: um registro contendo apenas a chave e outro
registro de tamanho 11 vezes o tamanho da chave (isto é, a chave acompanhada
de outros componentes cujo tamanho seja equivalente a dez chaves). Repita cada
experimento algumas vezes e obtenha a média dos tempos de execução. Dê a sua
interpretação dos dados obtidos.
6
#include <stdlib.h> #include <sys/time.h> typedef long Vetor[20];
Vetor A; int n, i;
double rand0a1() {
/* Dividir pelo maior inteiro */
double resultado= (double) rand()/ RAND_MAX;
if (resultado>1.0) resultado= 1.0;
return resultado;
}
void Permut(Vetor A, int n) {
/* Obtem permutacao randomica dos numeros entre 1 e n */
int i, j, b;
for (i = n; i >= 1; i--)
{
j = (long)(i * rand0a1() + 1);
b = A[i-1];
A[i-1] = A[j-1];
A[j-1] = b;
}
}
int main(int argc, char *argv[]) {
struct timeval semente;
gettimeofday(&semente,NULL);
/* utilizar o tempo como semente para a funcao srand() */
srand((int)(semente.tv_sec + 1000000*semente.tv_usec));
n = 10;
for (i = 1; i <= n; i++)
A[i-1] = i;
Permut(A, n);
for (i = 1; i <= n; i++)
printf("%d ", A[i-1]);
putchar(’\n’);
return 0;
}
7