Construcao e Analise de Algoritmos - Prova 1 -------------------------------------------- 1) Considere o algoritmo abaixo que manipula os elementos de um conjunto A de numeros inteiros, e retorna dois subconjuntos de A: Algoritmo X (A) { 1. (B,C) := Dividir (A); 2. Se (B = {b} e C = {c}) // ou seja, B e C sao conj. unitarios { 3. Se (b < c) Retorna ({b},{c}); 4. Senao Retorna ({c},{b}); } 5. (B1,B2) := X(B); 6. (C1,C2) := X(C); 7. b1 := Max (B1); 8. b2 := Min (B2); 9. c1 := Max (C1); 10. c2 := Min (C2); 11. Se (b2 < c1) { 12. (D1,D2) := X (B2 uniao C1); 13. Retorna (B1 uniao D1, C2 uniao D2); } 14. Se (c2 < b1) { 15. (D1,D2) := X (B1 uniao C2); 16. Retorna (C1 uniao D1, B2 uniao D2); } 17. Retorna (B1 uniao C1, B2 uniao C2); } Notas: 1) A rotina Dividir(A) retorna dois subconjuntos disjuntos arbitrarios do conjunto A com o mesmo tamanho. 2) As rotina Max(A) ( Min(A) ) retorna o maior (menor) elemento do conjunto A. a) Simule a execucao do algoritmo X no conjunto {7,2,17,13,9,15,5,43} indicando o valor de retorno de cada chamada recursiva. b) Descreva sucintamente a funcionalidade do algoritmo X. c) Prove que o algoritmo X funciona corretamente. d) Analise a complexidade do algoritmo X. e) Nas linhas (7)-(10) o algoritmo encontra maximos e minimos de quatro subconjuntos. Se isto for feito de maneira ingenua, o tempo gasto nesta computacao e' Theta(n) (onde n e' o tamanho de cada subconjunto). Descreva como o algoritmo pode ser modificado de modo que os maximos e minimos possam ser obtidos em tempo O(1). f) A modificacao sugerida no item (e) altera a complexidade do algoritmo X? Justifique. g) Estime o numero de chamadas recursivas realizadas pelo algoritmo no melhor e pior caso. 2) Voce possui um lote com n laranjas e uma balanca. A operacao basica para realizar as tarefas abaixo consiste em colocar um certo numero de laranjas de cada lado da balanca e verificar qual o lado mais pesado. a) Suponha que possam existir laranjas podres no lote, e que uma laranja podre tenha peso menor do que uma laranja boa. a1) Descreva um procedimento para verificar se existe alguma laranja podre no lote que realize O(log n) pesagens. a2) Descreva um procedimento para encontrar todas as laranjas podres do lote. Estime o numero de pesagens realizadas pelo seu algoritmo no pior caso, em termos do numero K de laranjas podres. Seu procedimento deve executar um numero de pesagens assintoticamente menor do que n, quando k e' pequeno. b) Suponha agora que as laranjas possam ter todas pesos distintos. Indique se a proposicao a seguir e' verdadeira ou falsa, justificando a sua resposta. PROPOSICAO: Qualquer procedimento que ordena as laranjas de acordo com seu peso realiza Omega(n log n) pesagens. 3) Suponha que temos n programas p1,...,pn, que requerem o mesmo tempo de computacao (e.g., 15 min.), e devem ser executados em um unico processador. Cada programa pi possui um prazo maximo ti para terminar sua execucao. O problema consiste em determinar uma ordem para a execucao dos programas que minimize o numero de programas atrasados. Parte I: ------- a) Descreva um algoritmo para encontrar a ordem de execucao dos programas. b) Prove que o seu algoritmo encontra uma solucao otima para o problema. Parte II: -------- Suponha agora que cada programa pi esta associado a uma penalidade wi que e' paga se o programa termina sua execucao apos o prazo maximo. Nesta versao do problema, o objetivo e' minimizar a soma das penalidades sofridas pelos programas atrasados. c) Verifique se o algoritmo que voce descreveu no item (a) e' otimo para esta versao do problema. Caso ele seja otimo, apresente um prova deste fato e ignore os itens (d) e (e) a seguir. Caso contrario, apresente um contra-exemplo. d) Descreva um algoritmo para esta versao do problema. e) Prove que o seu algoritmo encontra uma solucao otima para esta versao do problema. 4) Um candidato ao governo do Ceara' tem uma serie de eventos publicos que deseja participar. Os eventos ocorrem ao longo de uma estrada, e se localizam em pontos multiplos de 50 kms (e.g., km 50, km 150, etc.). Os eventos comecam sempre em uma hora exata, nao existem dois eventos ocorrendo na mesma hora, mas pode ocorrer mais de um evento na mesma localizacao. Para que seu nome seja anunciado ao publico, o candidato deve estar presente no inicio do evento. Suponha que no inicio do dia o candidato esta no km 0 da estrada, e que ele viaja 'a velocidade de 50 km/h. O objetivo e' definir uma estrategia que faca com que seu nome seja anunciado no maior numero possivel de eventos. a) Apresente um contra-exemplo para as seguintes estrategias: a1) A cada passo, selecionar o evento que comeca mais cedo, e que possa ser alcancado a tempo. a2) A cada passo, selecionar o evento que seja compativel com o maior numero de outros eventos, e que possa ser alcancado a tempo. Nota: O evento i e' compativel com o evento j se, estando presente no inicio do evento i, e' possivel alcancar o evento j no momento do seu inicio. b) Neste item examinaremos a qualidade das solucoes obtidas pelas estrategias acima. Denote por S* uma solucao otima para o problema, e denote por S1 e S2 as solucoes encontradas pelas estrategias (a1) e (a2), respectivamente. b1) Mostre que, para todo k > 0, existe um problema em que |S*| > K |S1| (i.e., o numero de eventos na solucao otima e' k vezes maior do que o numero de eventos em S1). b2) Faca apenas um dos itens a seguir: b2.1) Apresente um exemplo em que |S*| >= 2 |S2|. b2.2) Apresente um exemplo em que |S*| >= 3 |S2|. b2.3) Mostre que, para todo k>0, existe problema em que |S*| > K |S2|. b3) Mostre que, se nao ocorrem dois eventos na mesma localizacao, entao |S*| <= 2 |S2|, em qualquer problema. c) Descreva um algoritmo que encontre uma solucao otima para este problema. 5) Considere os problemas a seguir: (I) Cortes de Tora Uma tora deve ser cortada em n pontos para produzir (n+1) pedacos de madeira. O custo para a realizacao de cada corte e' proporcional ao tamanho do pedaco que esta sendo cortado. Dados o comprimento L da tora e os pontos de corte c1,...,cn, o problema consiste em determinar uma ordem para a realizacao dos cortes que minimize o custo total. (II) Combinacao de Listas Dadas k listas ordenadas, o problema consiste em formar uma lista ordenada combinando as listas duas de cada vez. O objetivo e' minimizar o numero de comparacoes realizadas no processo. (III) Arvore Binaria (c/ nos externos) Otima Temos m registros indexados pelas chaves h1,...,hm (onde hi < hi+1, para i = 1,...,m-1) com os quais precisamos construir uma arvore binaria com nos externos (ver nota abaixo). Cada registro hi e' acessado mi vezes, e o custo de cada acesso a hi e' proporcional 'a sua altura na arvore. O problema consiste em construir uma arvore que minimize o custo total dos acessos. Nota: Uma arvore binaria com nos externos e' uma arvore binaria de busca em que os registros h1,...,hm sao armazenados nas folhas da arvore. Os valores dos nos internos sao arbitrarios, e sao apenas utilizados para navegar pela arvore e encontrar a folha correta em uma busca. a) O problema do corte de tora (I) e' logicamente equivalente a exatamente um dos outros problemas acima. Indique que problema e' este. Denote por (X) o problema indicado no item (a), e por (Y) o outro problema. b) Prove que o problema (I) e' logicamente equivalente ao problema (X) respondendo os itens a seguir: b1) Mostre como uma instancia Pi do problema (I) pode ser transformada em uma instancia Px do problema (X) b2) Mostre como transformar uma solucao Sx para o problema Px em uma solucao Si para o problema Pi. b3) Mostre que se Sx e' uma solucao otima para Px, entao Si e' uma solucao otima para Pi. c) Justifique porque o problema (I) nao e' logicamente equivalente ao problema (Y).