lista-exercicios-nocoes-complexidade-algoritmos-ordenacao

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: 2ª Lista de Exercícios
Formiga, MG, 18 de junho 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 17/07/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) Um pesquisador tem a sua disposição 2 algoritmos para resolver um determinado problema. Um algoritmo possui
complexidade O(n2) e outro possui complexidade O(n3). Esse pesquisador escolheu o algoritmo com complexidade
O(n3). Cite 3 motivos que poderiam ter motivado essa escolha.
2) Explique o objetivo da operação de partição utilizada pelo algoritmo de ordenação quicksort. Ilustre sua explicação
particionando um vetor A com os seguintes elementos: 13, 19, 9, 5, 12, 8, 7, 4, 2, 6, 11. Mostre a configuração do
vetor após cada troca de elementos. A escolha do pivô é arbitrária, portanto fica a seu critério como selecioná-lo.
Explicite na sua resposta como selecionou o valor do pivô.
3) A sequência (32, 27, 17, 6, 13, 8, 14, 4, 11, 5, 12) é um heap máximo? Justifique sua resposta.
4) Um ponto crucial no algoritmo de ordenação quicksort é a escolha do pivô. Cite e explique duas abordagens para
escolha do pivô que tornam improváveis a ocorrência do pior caso desse algoritmo.
5) Explique de forma sucinta os algoritmos de ordenação selection sort e insertion sort. Complemente sua explicação
mostrando os passos executados por esses algoritmos para ordenar de forma ascendente os seguintes elementos: 161,
41, 101, 141, 71, 16, 32.
6) [ZIV- Exercício 4.17-Modificado] Considere a necessidade de ordenar de forma ascendente os elementos de
vetores com 100, 600, 2.000, 30.000, 100.000, 300.000 e 100.000.000 elementos. Para todos os vetores é necessário
realizar a ordenação no menor tempo possível. Discuta qual(is) algoritmo(s) de ordenação você usaria para cada
tamanho de vetor. Considere que o conteúdo dos vetores foi gerado aleatoriamente.
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: 2ª Lista de Exercícios
Formiga, MG, 18 de junho de 2014
7) Um algoritmo de ordenação muito estudado é o quicksort. Na literatura especializada é comum encontrar várias
propostas de otimização aplicadas a esse algoritmo. Combinar o quicksort e o insertion sort é uma das sugestões mais
promissoras, melhorando o desempenho em até 25%. Considerando tais informações, responda:
a) Descreva como combinar esses dois algoritmos
b) Justifique a melhoria de desempenho obtida com essa proposta
8) Considere o algoritmo de ordenação heapsort. Explique-o de forma sucinta. Inclua na sua explicação a
complexidade do algoritmo e em quais situações sua aplicação/adoção é indicada.
9) [ZIV- Exercício 4.7-Modificado] Descreva como reorganizar os elementos de um vetor A contendo
números inteiros de forma que todos os números negativos precedam os não-negativos. A solução proposta
deve ser in place e ter complexidade O(n). Dica: trecho de um dos algoritmos de ordenação estudado em
sala de aula pode ser modificado para conseguir tal organização com complexidade O(n).
10) [ZIV- Exercício 4.1-Modificado] Considerando que existe a 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 você escolheria diante das seguintes situações:
a) restrições de estabilidade (isto é, a ordenação original dos elementos com chave idêntica precisa ser
mantida)
b) restrições 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)
c) os elementos do arquivo estão bem próximos da ordem final
d) os elementos do arquivo são muito grandes se comparados ao tamanho das chaves
11) [ZIV- Exercício 4.2] Invente um vetor exemplo para demonstrar que o método de ordenação por seleção
é instável.
12) Cite e explique um algoritmo de ordenação por distribuição.
13) Cite e explique um algoritmo de ordenação parcial.
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: 2ª Lista de Exercícios
Formiga, MG, 18 de junho de 2014
14) [ZIV- Exercício 4.13-Modificado] Considere a ordem lexicográfica e o algoritmo de ordenação
quicksort. Responda o que se pede:
a) Mostre como o vetor A B A B A B A é particionado quando se escolhe o elemento do meio como pivô?
b) Mostre as etapas de funcionamento do algoritmo quicksort para ordenar as chaves Q U I C K S O R T.
Considere que o pivô escolhido é o elemento do meio.
c) Mostre as etapas de funcionamento do algoritmo quicksort para ordenar as chaves Q U I C K S O R T.
Considere que o pivô escolhido é o primeiro elemento.
d) Mostre as etapas de funcionamento do algoritmo quicksort para ordenar as chaves Q U I C K S O R T.
Considere que o pivô escolhido é o último elemento
15) Escreva um algoritmo para ordenar uma sequencia de exatamente três elementos. Faça com que seu
algoritmo seja o mais eficiente possível.
16) Joãozinho é aluno de ciência da computação. Certo dia ele procurou seu professor de algoritmos e
estruturas de dados e lhe contou a seguinte novidade: “passei essa noite acordado e inventei um novo
algoritmo de ordenação que executa no pior caso O(n) comparações”. Se você fosse o professor do
Joãozinho lhe daria os parabéns ou mandaria ele de volta a prancheta? Justifique sua resposta.
17) Uma versão do método de ordenação bubble sort é chamada ordenação coqueteleira. Tal como o método
bubble sort, esse algoritmo perfaz um total de n - 1 passadas no vetor. Entretanto, os passos alternantes são
feitos em direção opostas. Por exemplo, durante a primeira passada o maior item vai para o fim do vetor e
durante a segunda passada o menor item vai pro inicio do vetor.
a) Faça, na linguagem de programação Pascal, um programa que implemente o método de ordenação
coqueteleira
b) Calcule a complexidade assintótica do pior, melhor e do caso médio do método de ordenação coqueteleira
18) Mostre como ordenar n inteiros no intervalo [1,n2] em tempo linear O(n). Seu algoritmo é in-place?
Justifique sua resposta.
19) Prove, usando a definição da notação Big O, que 2n2 - 3n = O(n2).
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: 2ª Lista de Exercícios
Formiga, MG, 18 de junho de 2014
20) 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 10 faça
soma <- soma + 1;
b) soma1 <- 0;
 para i de 1 até n faça
para j de 1 ate k faça //onde k é uma constante
soma1<- soma1 + 1;
c) soma <- 0;
 para i de 1 até n faça
para j de 1 ate n faça
soma <- soma + 1;
 para k de 1 até n faça
algum comando executado em O(1);
d) soma <- 0;
 i ← n;
 enquanto i > 0 faça
 inicio
soma <- soma + 1;
i <- i div 2; // div representa divisão inteira
 fim
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.