lista-exercicios-complexidade-ordenacao-listas-fila-pilha

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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
INSTRUÇÕES:
1. Estas listas de exercícios podem ser resolvidas em grupo de até 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. O prazo final para entrega desta atividade é até as 23:59:00 do dia 31/08/2014 via portal
acadêmico acessado pela URL:https://meu.ifmg.edu.br/.
4. Listas plagiadas serão desconsideradas, sendo atribuída nota 0 (zero) a todos os envolvidos.
5. O valor dessas listas de exercícios é 4 pontos.
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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
EXERCÍCIOS
1) Suponha que estamos estudando o desempenho de um algoritmo em função do tamanho n das instâncias
de um problema. Considere as seguintes afirmações:
1. o consumo de tempo do algoritmo é O(n²) no pior caso;
2. o consumo de tempo do algoritmo é O(n²) para toda instância do problema.
Qual a diferença entre as afirmações 1 e 2?
2) Escreva, na linguagem de programação Pascal, um programa que implemente o algoritmo descrito no
desafio 3.
3) A pilha é uma estrutura de dados linear no qual as operações de inserção e remoção são efetuadas sempre
num mesmo extremo denominado topo da pilha. É possível implementar um Tipo Abstrato de Dados (TAD)
que representa a estrutura de dados pilha através de um vetor. Também é possível implementar duas pilhas
num mesmo vetor. Considerando tais afirmações, responda: como implementar de maneira eficiente duas
pilhas num mesmo vetor? Justifique sua resposta.
4) Considere uma lista duplamente encadeada (ligada) de números inteiros.
a) Mostre como definir, na linguagem de programação Pascal, o tipo de dado lista duplamente encadeada de
números inteiros
b) Escreva funções/procedimentos na linguagem de programação Pascal para:
1. inserir um elemento no final da lista
2. inverter a lista de forma que o primeiro elemento se torne o último e assim por diante
3. remover o último elemento da lista
4. remover o menor elemento da lista
5. remover o maior elemento da lista
6. calcular e retornar o comprimento da lista
7. calcular e retornar a soma dos elementos da lista
8. remover um elemento qualquer da lista. O elemento a ser removido é passado como parâmetro da
função/procedimento
Daniel
Daniel
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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
5) Considere uma lista circular encadeada (ligada) de números reais.
a) Mostre como definir, na linguagem de programação Pascal, o tipo de dado lista circular encadeada
(ligada) de números reais
b) Escreva funções/procedimentos na linguagem de programação Pascal para:
1. remover o menor elemento da lista
2. calcular e retornar o comprimento da lista
3. calcular e retornar a soma dos elementos da lista
4. remover um elemento qualquer da lista. O elemento a ser removido é passado como parâmetro da
função/procedimento
6) A estrutura de dados fila segue o procolo First-In First-Out (FIFO) e pode basicamente ser implementada
de duas maneiras: através de vetores ou através de listas encadeadas. Na implementação usando vetores
pode ser conveniente considerar o vetor de forma circular. Justifique essa escolha.
7) Considere um vetor V e a necessidade de verificar se existem elementos repetidos nesse vetor. Como
você procederia para cumprir tal tarefa?
a) Escreva, em Pascal-like, uma função/procedimento que implemente sua ideia. 
b) Qual a complexidade (pior caso) da sua implementação?
c) Se sua resposta à alternativa b foi maior que O(n * log n), proponha uma implementação de forma a obter
uma complexidade O(n * log n).
8) Analise os códigos abaixo e calcule a complexidade assintótica em cada caso usando a notação Big O.
Considere o pior caso.
a) soma <- 0;
 para i de 1 até n faça
para j de 1 até n/2 faça
soma <- soma + 1;
Daniel
Daniel
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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
b) soma <- 0;
 para i de 1 até n/3 faça
inicio
j <- 1;
enquanto (j <= n)faça
inicio
soma <- soma + 1;
 j <- j + 6;
fim
fim
c) soma <- 0;
 para i de 1 até n-5 faça
 inicio
para j de 1 até n/3 faça
inicio
k <- 1;
enquanto (k <= n)faça
inicio
soma <- soma + 1;
 k <- k * 2;
fim
fim
 fim
d) soma <- 0;
 para i de 1 até n faça
para j de 1 até i faça
para k de 1 até 25 faça
soma <- soma + 1;
Daniel
Daniel
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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
e) soma <- 0;
para i de 1 até n faça
inicio
y <- 1/i; // divisão em ponto flutuante
x <- i;
enquanto(x > 0)faça
inicio
soma <- soma + 1;
 x <- x-y;
fim
fim
f) soma <- 0;
 para i de 1 até n faça
para j de 1 até i faça
para k de 1 até n faça
soma <- soma + 1;
g) soma <- 0;
 para i de 1 até n-2 faça
 inicio
para j de 1 até 5 faça
inicio
k <- n;
enquanto (k >= 1)faça
inicio
soma <- soma + 1;
 k <- k div 2; // div representa divisão inteira
fim
fim
 fim
Daniel
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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
h) ordenado <- falso;
enquanto (ordenado = falso)faça
inicio
v <- sorteia-ordem(v); //considere cada execução em O(n)
x <- 1;
enquanto (( x < tamanho) E (v[x] <= v[x+1]))faça
inicio
x <- x + 1;
 fim
se x = tamanho então
inicio
ordenado <- verdadeiro;
fim
fim
Dica: Use o conceito de somatório para resolver a questão 8.
QUESTÕES DESAFIO
As questões abaixo, numeradas desafio1, desafio2, desafio3, desafio4 e desafio5, são questões desafio.
Essas questões objetivam estimular a curiosidade e o raciocínio em busca de soluções elegantes, corretas,
eficientes e que envolvam o conhecimento adquirido em diversas disciplinas. Nessas questões são
especialmente importantes os conhecimentos das seguintes disciplinas: matemática discreta, estatística e
algoritmos e estruturas de dados. O critério de correção das questões desafio é booleano, ou seja, será
atribuída nota máxima a cada desafio resolvido inteira e totalmente correto e não será atribuída nota alguma
para soluções parcialmente corretas ou incorretas. A cada desafio com solução totalmente correta será
atribuído 1 ponto. Para confirmar a nota obtida nas questões desafio, o aluno deverá fazer uma apresentaçãooral para o professor e explicar correta e adequadamente suas soluções. A nota obtida nas questões desafios
será acrescida à nota da primeira prova.
Desafio1) Escreva, em Pascal-like, como encontrar o segundo menor elemento de um vetor V com n
elementos com no máximo n + log n - 2 comparações.
Daniel
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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
Desafio2) Considere uma lista simplesmente encadeada (ligada) e admita o desejo de inserir um novo
elemento antes do nó apontado pela variável do tipo apontador (ponteiro) p. Na sala de aula vimos um
algoritmo O(n) que resolve tal problema. Mostre como resolver esse problema em O(1).
Desafio3) A copa do mundo de futebol 2014 foi realizada no Brasil. Preencher o álbum de figurinhas da
copa do mundo pode ser uma atividade divertida. Fuleco é aluno do curso de Ciência da Computação do
IFMG - Campus Formiga e gostaria de participar dessa brincadeira preenchendo o seu álbum. Entretanto, ele
estava sem tempo para comprar (e muito menos trocar) figurinhas. Aproveitando seus conhecimentos
adquiridos nas disciplinas de programação e de algoritmos e estruturas de dados, ele criou um programa
baseado no seguinte algoritmo (em Pascal-like) para comprar as figurinhas na internet de maneira aleatória.
1. preencher-album (n)
2. inicio
3. album := vetor-vazio (n);
4. preenchido := 0;
5. enquanto preenchido < n faça
6. inicio
7. figurinha := comprar-figurinha();
8. se album[figurinha] = vazio então
9. inicio
10. album[figurinha] := colado;
11. preenchido := preenchido + 1;
12. fim
13. fim
14. retorna album;
15. fim
Calcule a complexidade assintótica do caso médio do algoritmo preencher-album. Considere n o tamanho
do álbum e que a função comprar-figurinha() executa em tempo constante.
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: 4ª e 5ª Listas de Exercícios
Formiga, MG, 20 de agosto de 2014
Desafio4) Dados um vetor de números naturais V e um número natural C, descreva como encontrar dois
números A e B pertencentes ao vetor V, tais que A + B = C. Escreva, em Pascal-like, um algoritmo que
implemente sua ideia. Como saída seu algoritmo deve indicar os índices do vetor que contém os números A
e B. Se não existirem números A e B que satisfaçam a condição A + B = C retorne -1. A complexidade do
seu algoritmo deve ser O(n * log n) no pior caso.
Desafio5) Um jogo de azar muito famoso no Brasil é o Bingo. Numa versão desse jogo, os jogadores
possuem cartelas nas quais há 25 números dispostos na forma de matriz (tabular). Nas cartelas podem existir
números no intervalo [1,75]. Há um globo no qual são colocadas bolas numeradas de 1 a 75. Uma bola é
sorteada por vez e é anunciado o número sorteado. O(s) jogador(es) devem verificar se na sua cartela há o
número sorteado. Se sim devem marcá-lo. É declarado vencedor o jogador que primeiro marcar todos os
números de sua cartela. Considerando que:
1. o jogo encerra-se quando o primeiro jogador completar sua cartela;
2. sempre há um vencedor no jogo;
3. cada jogador possui apenas uma cartela, e
4. o sorteio é equiprovável
 
Calcule o número médio de sorteios realizados nessa versão de Bingo.
Bibliografia:
BONACIN, Rodrigo. Lista Exercícios2 - Complexidade de Algoritmos. Mestrado em Ciência da
Computação. Faculdade Campo Limpo Paulista, 2014.
CORMEN, T. et al. Algoritmos: Teoria e Prática. 3ª edição. Rio de Janeiro: Elsevier, 2012.
ZIVIANI, Nívio. Projeto de Algoritmos: com implementação em Pascal e C. 3ª edição revista e ampliada.
São Paulo: Cengage Learning, 2011.
WIRTH, N.; Algoritmos e Estruturas de Dados. Rio de Janeiro: Editora LTC, 2009.