Lista 2

Prévia do material em texto

1 
 UNIVERSIDADE FEDERAL DE VIÇOSA 
 DEPARTAMENTO DE INFORMÁTICA 
 INF332 - Projeto e Análise de Algoritmos 
 Prof. José Elias C. Arroyo 
 
Lista de Exercícios 2 
Data de entrega: 10 de novembro de 2014 
 
1. Seja um array de n elementos (números). Deseja-se determinar o elemento que aparece o maior 
número de vezes no array. Caso todos os elementos do array são diferentes, a solução é o primeiro 
elemento que aparece uma vez. 
a) Escreva um algoritmo de força bruta para determinar uma solução do problema. Calcule a 
complexidade do algoritmo. 
b) Escreva um algoritmo de complexidade O(nlogn). 
 
2. Seja um array com n-1 elementos inteiros que estão na faixa 1 a n. Não existem elementos 
repetidos. No array um dos elementos está faltando. 
a) Escreva um algoritmo de força bruta para encontrar o elemento que está faltando no array. 
Calcule a complexidade do algoritmo. Exemplo, para n = 8: A = [4, 2, 7, 6, 3, 8, 1]. O 
elemento que está faltando é 5. 
b) Escreva um algoritmo de complexidade O(nlogn). 
c) Escreva um algoritmo de complexidade O(n). 
 
3. Dados dois arrays com n elementos (números) ordenados. Deseja-se determinar a mediana da 
união dos dois arrays (ou seja a mediana dos 2n elementos). 
Exemplo: Para A = [2, 3, 5, 6, 10] e B = [1, 7, 10, 13, 15] a mediana é (6+7)/2 = 6,5. 
a) Escreva um algoritmo de força bruta para resolver o problema. Calcule a complexidade do 
algoritmo. 
b) Escreva um algoritmo baseado na técnica Divisão e Conquista (D&C) para encontrar a solução 
do problema. Calcule a complexidade do algoritmo. 
 
4. Seja um conjunto M contendo n moedas (n>1), sendo que (n-1) são idênticas (válidas) e uma é 
falsa. Suponha que as moedas válidas pesam 1g e a falsa pesa 0,5g. O problema consiste em 
detectar a moeda falsa no conjunto M. Escreva três algoritmos diferentes baseadas, 
respectivamente, nas técnicas de Força Bruta, Indução, e D&C. Apresente a complexidade dos 
algoritmos. 
 
5. Escreva um algoritmo recursivo baseado na técnica de Indução para a ordenação por inserção de 
um array de n números reais. Calcule a complexidade do algoritmo. 
 
6. Problema da subsequência crescente máxima (ou mais longa): Seja uma sequencia de n números 
a = [a1, a2, ..., an]. Uma subsequencia de a é qualquer subconjunto s = [ai1, ai2, ..., aik] de números 
tomados em ordem, ou seja, 1 ≤ i1 < i2< ...<ik ≤ n. A subsequencia s é crescente se ai1< ai2< ... < 
aik, e é máxima se tem o maior número de elementos. 
Exemplo: para a = [5, 2, 8, 6, 3, 6, 9, 7], s = [5, 6, 9] é uma sequencia crescente com 3 
elementos. s = [2, 3, 6, 9] e s = [2, 3, 6, 7] são sequencias crescentes com 4 elementos. 
a) Escreva um algoritmo de força bruta para resolver o problema. Qual é complexidade do 
seu algoritmo? 
b) Escreva um algoritmo baseado em D&C para resolver o problema. Qual é complexidade 
do seu algoritmo? 
 
 2 
 
7. Seja um conjunto {p1, p2, ..., pn} de n (n ≥ 2) pontos no plano R2 (pi = (xi, yi)). Aplicando a técnica 
de D&C, escreva um algoritmo para determinar o par de pontos mais próximos (os dois pontos de 
menor distância euclidiana). Obs. Se o conjunto tiver n ≤ 3 pontos, os dois pontos mais próximos 
podem ser obtidos pelo método de foça bruta. Calcule a complexidade do algoritmo. 
 
8. Considere o problema de ordenação onde os vetores a serem ordenados, de tamanho n > 0, 
possuem ⌊n/2⌋ valores iguais a um número real x e ⌈n/2⌉ valores iguais a um outro número real y. 
Considere que os números reais x e y são conhecidos e fixos (dados de entrada), porém estão 
distribuídos aleatoriamente no vetor a ser ordenado. Responda as seguintes questões e justifique 
sua resposta: 
a) No pior caso, o Quicksort será o algoritmo mais eficiente para este problema, com tempo 
O(nlog2n) ? 
b) O algoritmo de ordenação por inserção sempre opera no melhor caso com tempo O(n)? 
c) O melhor algoritmo para este problema tem tempo O(n)? Caso sim, escreva o algoritmo. 
 
9. Escreva um algoritmo baseado na técnica D&C para determinar o número de níveis de uma 
árvore binária (se a árvore é vazia o número de níveis é zero). Determine a complexidade 
de tempo do seu algoritmo. 
 
10. Considere o problema da busca de uma chave x num vetor V com n elementos não 
ordenados (V[0..n-1]). O algoritmo da busca binária é baseada na técnica D&C. 
a) Escreva o algoritmo da busca binária baseado na técnica D&C. Determine a 
complexidade do algoritmo. 
b) Rescreva o algoritmo da busca binária para o problema da busca de uma chave x num 
vetor V ordenado e determine a complexidade do algoritmo. 
 
11. Seja x um número real e S = {x1, x2, ...., xn} uma lista de n números reais. 
a) Escreva um algoritmo de força bruta para determinar se a soma de dois elementos de S é igual 
a x. Calcule a complexidade do seu algoritmo. 
b) Escreva um algoritmo de complexidade O(nlog2n) para o mesmo problema. Mostre que a 
complexidade é O(nlog2n). 
 
12. Dada uma sequência S = {x1, x2, ...., xn} de n números. A multiplicidade de um elemento x de S é 
definida como sendo o número de vezes que este elemento ocorre na sequência. Além disso, um 
número z é dito a maioria da sequência se a sua multiplicidade é maior do que n/2. 
a) Escreva um algoritmo de força bruta que determina o número que é a maioria da sequência 
(se ele existir). Determine a complexidade do algoritmo. 
b) Escreva um algoritmo de complexidade O(nlog2n) para determinar a maioria da sequência. 
c) É possível projetar um algoritmo de complexidade Θ(n)? Caso sim escreva o algoritmo. 
 
13. Problema do troco: Seja d = {d1, d2,..., dn} um conjunto de n valores distintos (moedas) 
correspondentes a uma unidade monetária. Suponha que existe uma quantidade ilimitada de cada 
moeda para serem usadas. O problema do troco consiste em formar uma quantidade X utilizando o 
menor número de moedas. 
a) Escreva um algoritmo de força bruta para resolver o problema; 
b) Escreva um algoritmo baseado em uma estratégia gulosa para resolver este problema. 
Qual é complexidade do seu algoritmo? 
c) Seja d = { R$ 0,01; R$0,05; R$0,10; R$0,25; R$0,50; R$1,00; R$2,00; R$5,00; R$10,00; 
R$20,00; R$50,00; R$100,00} as moedas da unidade monetária brasileira. Utilizando seu 
 3 
algoritmo, determine as soluções para X = 49,78, X = 995,39 e X = 3149,32. Seu 
algoritmo gera a melhor solução possível? Caso não, apresente um contraexemplo. 
 
14. Apagando e Ganhando: Seja um número x de n dígitos, então devem ser apagados k dígitos 
desse número de tal forma que os números que restarem forme um número que equivale a 
um prêmio em dinheiro que você ganharia. Quais seriam os k dígitos a serem apagados para 
obter o maior prêmio? 
Exemplo: x = 671930, k = 3. Uma solução seria apagar 6, 1 e 0 obtendo 793. 
Escreva um algoritmo guloso de tempo O(n) para resolver o problema. 
 
15. Considere um conjunto H = {(starti , endi) : 1 ≤	
 i ≤ n} de n horários de aula. Estes horários 
correspondem a disciplinas que devem ser oferecidas em um dia da semana. A disciplina i 
demanda de uma sala de aula no horário (starti , endi). Deseja-se determinar o menor numero de 
salas de aula para atender todas as disciplinas. Escreva um algoritmo guloso para resolver o 
problema. 
 
16. Considere um serviço de atendimento ao cliente na qual n clientes estão numa fila. Suponha que 
cada cliente i requer um tempo ti (em minutos) para ser atendido (esse tempo é conhecido). 
Supondo que o funcionamento do serviço de atendimento inicia às 0:00h. De que maneira os 
clientes devem ser organizados na fila de tal maneira que o tempo total de espera de todos os 
clientes seja mínimo? O tempo de espera de um cliente i é S + ti, onde S é a soma dos tempos de 
atendimento dos clientes que foram previamente atendidos. Escrevaum algoritmo para resolver o 
problema. 
 
17. Suponha que temos n programas de computador {1,...,n} que resolvem problemas diferentes. 
Existe só uma máquina para executar os programas. Uma tarefa i demora ai horas para ser 
executado na máquina. Após a execução dos programas devem ser entregues os resultados dos 
mesmos. Seja pi o prazo para entregar o resultado do programa i. Este prazo é dado em horas e é 
contabilizado a partir do início da execução do primeiro programa. Se a execução de uma tarefa i 
finaliza após do prazo de entrega é produzido um atraso definido por: ci – pi, onde ci é o instante 
de finalização do programa i. Se ci – pi < 0 o atraso da tarefa será 0. Assumir um escalonamento 
não preemptivo, ou seja, os programas devem ser executados um por vez. O objetivo do problema 
é determinar o escalonamento dos programas (ordem de processamento) de tal maneira que seja 
produzido o menor atraso total (em horas). 
Considere o seguinte exemplo numérico: n = 5 programas, os tempos de execução e prazos 
são: a1 = 8, a2 = 15, a3 = 5, a4 = 9, a5 = 10; p1 = 7, p2 = 25, p3 = 20, p4 = 35, p5 = 27. 
Um possível escalonamento é executar os programas na seguinte ordem 1, 2, 3, 4, 5 (programa 1, 
programa 2, programa 3, programa 4, programa 5). Note que a execução do programa 1 terminará 
após de 8 horas (do inicio de funcionamento da máquina), e o resultado desse programa é para 
entregar no prazo de 7 horas. O programa 1 terá um atraso de 1h. A execução do programa 2 
finalizará depois de 23h, ou seja, não tem atraso, pois p2 = 25. As tarefas 3, 4 e 5 possuem atrasos 
de 8h, 2h e 22h, respectivamente. O atraso total produzido será: 0+0+8+2+22 = 32h. 
a) Escreva um algoritmo baseado numa estratégia gulosa para resolver o problema. 
b) Usando a estratégia gulosa, qual seria a solução do exemplo numérico apresentado acima? O 
atraso total obtido é o menor possível? Caso não, apresente um contraexemplo. 
c) Como seria um algoritmo de força bruta para obter a melhor solução do problema? 
 
18. Seja {B1, ..., Bn} um conjunto de n caixas todas com um mesmo peso p. Cada caixa Bi possui um 
custo ci. Escreva um algoritmo que dado um valor K, determina um subconjunto de caixas cujo 
peso é menor ou igual a K e tal que o custo total é máximo. 
 
 4 
19. Solitaire é um jogo num tabuleiro n×n para um único jogador. Cada campo do tabuleiro possui 
um número inteiro. O jogador começa escolhendo alguma posição do tabuleiro. Depois ele pode 
repetidamente mover uma posição para a direita ou uma posição para baixo. O jogo termina 
quando a próxima posição cai fora do tabuleiro (a ultima posição soma 0). O valor do jogo é igual 
à soma dos números visitados (incluindo a posição inicial). O objetivo é encontrar o jogo de maior 
valor. 
Por exemplo, no tabuleiro 
3 1 -4 1 
5 -1 9 2 
6 5 -3 -5 
-8 -9 -7 2 
começando da posição (2,3) com 9, indo para baixo, e depois para direita, baixo, direita ( ou 
baixo) obtêm-se uma solução com valor: 9 – 3 – 5 + 2 + 0 = 3. 
a) Escreva um algoritmo de força bruta para determinar o jogo de maior valor. Determine a 
complexidade do algoritmo. 
b) Escreva um algoritmo baseado numa estratégia gulosa. Determine a complexidade do 
algoritmo. Seu algoritmo determina a melhor solução?