Centro Federal de Educação Tecnológica de Minas Gerais
Programa de Pós-Graduação em Modelagem Matemática e
Computacional
Disciplina: Algoritmos e Estruturas de Dados
Professor: Flávio Cardeal
Lista de Exercı́cios 1 - 20/08/2015 - 15 pontos
Data de entrega: 29/09/2015
1. Dê o conceito de: (a) algoritmo; (b) tipo de dados; (c) tipo abstrato de dados.
2. O custo de utilização de um algoritmo pode ser medido de várias maneiras. Descreva
as principais técnicas, apontando suas eventuais vantagens e desvantagens.
3. O que significa dizer que uma função g(n) é O(f (n))?
4. Indique se as afirmativas abaixo são verdadeiras ou falsas e justifique a sua resposta
utilizando a definição de dominação assintó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 é igual a n3 /3 + O(n2 ).
6. Apresente um algoritmo para obter o maior e o segundo maior elemento de um
conjunto. Apresente também uma análise do algoritmo. Você acha o seu algoritmo
eficiente? Por quê? Procure comprovar suas respostas.
7. Implemente em Linguagem C os três algoritmos apresentados nos Programas 1.3,
1.4 e 2.8 do livro texto, para obter o má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. Meça o tempo de
execução para cada algoritmo dos trê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 equações de recorrê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 funçõ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 indução que as seguintes propriedades sã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 definição recursiva para a multiplicação de dois nú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 multiplicação de dois
números naturais. Implemente-os em Linguagem C. Apresente a complexidade de
tempo para as funções implementadas.
13. Determine o que faz a funçã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 relação de recorrência
para a função de complexidade f , onde f (n) é definida como o número de comparações entre os elementos de A e n pode ser considerado como uma potência de
2. Resolva a equação de recorrência.
3
15. Pesquise e relate de maneira didática três exemplos de problemas onde sã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 divisão e conquista para encontrar
o par de pontos mais próximos.
17. Sejam n objetos a serem ordenados de acordo co as seguintes relações: < e =. Por
exemplo, com 3 objetos existem 13 ordenaçõ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 programação dinâmica que possa calcular, como
função de n, o número de diferentes ordenações possı́veis.
18. Considere a implementação de listas lineares utilizando apontadores e com célula
cabeça. Considere que um dos campos do TipoItem é uma chave: TipoChave.
Escreva uma função em C, cujo cabeçalho segue abaixo:
int EstaNaLista(TipoChave Ch, TipoLista *Lista);
que retorna 1 se Ch estiver na lista e retorna 0 se Ch não estiver na lista. Considere
que não há ocorrências de chaves repetidas na lista. Determine a complexidade do
seu algoritmo.
19. Um problema que pode surgir na manipulação de listas lineares simples é o de voltar
atrás na lista, ou seja, percorrê-la no sentido inverso ao dos apontadores. A solução
geralmente adotada é a incorporação à célula de um apontador para o seu antecessor.
Listas deste tipo são chamadas de duplamente encadeadas. A Figura 1 mostra
uma lista deste tipo com estrutura circular e a presença de uma célula cabeça.
Figura 1: Lista circular duplamente encadeada.
a) Declare os tipos necessários para a manipulação da lista.
b) Escreva uma função em C para retirar da lista a célula apontada por p:
4
void Retira(Apontador p, TipoLista *Lista);
20. Considere uma expressão matemática que inclui vários parênteses aninhados como,
por exemplo:
7 - ((X * ((X + Y) / (J - 3)) + Y) / (4 - 2.5))
Para se assegurar que os parênteses estão aninhados corretamente, precisa-se verificar que:
- existe um número de parênteses à direita igual ao número de parênteses à
esquerda;
- todo parêntese à direita é precedido por um parêntese correspondente à esquerda.
Considere que cada parêntese à esquerda abre um escopo, enquanto cada parêntese
à direita fecha um escopo. Sendo assim, duas condições devem ser satisfeitas, de
forma que o uso de parênteses em uma equação seja feito corretamente:
1. o número de parênteses à esquerda menos o número de parênteses à direita
da expressão deve ser zero. Isso significa que nenhum escopo foi deixado aberto.
2. o número de parênteses à esquerda menos o número de parênteses à direita
em cada ponto da expressão é positivo. Isso significa que nenhum parêntese à direita
é encontrado para o qual um correspondente parêntese à esquerda não tenha sido
aberto previamente. Por exemplo, observe abaixo o número de parênteses à esquerda
menos o número de parênteses à direita em cada ponto da expressã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 parênteses em uma equação
está correto. Sempre que um escopo é aberto, um parêntese à esquerda é empilhado
na pilha. Por outro lado, sempre que um escopo é fechado, a pilha é examinada.
Se a pilha estiver vazia, o finalizador de escopo (parêntese à direita) não possui um
correspondente parêntese à esquerda e, portanto, a string é inválida. Se, porém, a
pilha não estiver vazia, deve-se desempilhar a pilha e verificar se o item desempilhado corresponde ao finalizador de escopo. Se ocorrer uma correspondência correta,
continua-se o processo, caso contrário, a string é inválida. Quando se alcançar o
final da string, a pilha deve estar vazia. Caso contrário, um ou mais escopos foram
abertos e não fechados posteriormente, sendo a string inválida. Escreva e implemente um algoritmo em C para averiguar se o uso de parênteses em uma equação
está correto ou não.
5
21. Uma fila com prioridades é uma estrutura de dados na qual a ordem intrı́nseca dos
elementos determina os resultados das suas operações básicas. Pesquise na literatura
sobre este tipo de estrutura de dados, defina seus principais tipos e onde as mesmas
são usualmente aplicadas. Escreva uma função em C responsável por implementar
a operação Desenfileira em tal fila.
22. Dado que existe necessidade de ordenar arquivos de tamanhos diversos, podendo
também variar o tamanho dos registros de um arquivo para outro, apresente uma
discussão sobre quais algoritmos de ordenação (Seleção, Inserção, Shellsort e Quicksort) você escolheria diante das diversas situações possı́veis. Que observações adicionais você apresentaria caso haja restrições de estabilidade ou de intolerância para
o pior caso (isto é, a aplicação exige um algoritmo eficiente, mas não permite que
ele eventualmente demore muito tempo para executar)?
23. Invente um vetor-exemplo de entrada para demonstrar que ordenação por Seleção
é um método instável. Mostre os passos da execução do algoritmo até que a estabilidade seja violada. Note que quanto menor for o vetor que você inventar, mais
rápido você vai resolver a questão.
24. Para os seguintes algoritmos de ordenação interna: Inserção, Seleção, Shellsort e
Quicksort:
a) Determine experimentalmente o número esperado de (i) comparações e (ii)
movimento-de-registros para cada um dos quatro métodos de ordenação. Utilize a
função PermutacaoRandomica abaixo para obter uma permutação randô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 média para cada medida de complexidade. Dê sua interpretação dos dados obtidos,
comparando-os com resultados analı́ticos.
b) Uma opção, para o caso do uso de máquinas que permitem medir o tempo
de execução de um programa, é considerar os mesmos algoritmos propostos e determinar experimentalmente o tempo de execução de cada um dos quatro métodos
de ordenação indicados. Use um gerador de números aletó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 é, a chave acompanhada
de outros componentes cujo tamanho seja equivalente a dez chaves). Repita cada
experimento algumas vezes e obtenha a média dos tempos de execução. Dê a sua
interpretaçã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