Construcao e Analise de Algoritmos - Prova 1 -------------------------------------------- 1) Neste problema analisamos o tempo de execucao do algoritmo Merge-Sort sob diversos aspectos. Algoritmo M-S (i,j) { Se (i >= j) Retorna; M-S (i, (i+j-1)/2); M-S ((i+j+1)/2, j); Combina(i,j); } A) Nesta primeira parte estamos interessados no numero exato de comparacoes e chamadas recursivas realizadas pelo algoritmo M-S. As comparacoes sao realizadas no interior da rotina Combina, que foi omitida por falta de espaço. a1) Determine o numero exato de comparacoes realizadas para combinar duas listas com k elementos cada, no pior caso. a2) Utilize o resultado do item (a1) para determinar o numero exato de comparacoes realizadas pelo algoritmo M-S para ordernar um vetor com n elementos, no pior caso. a3) Apresente um vetor com 8 elementos para o qual o algoritmo M-S realiza o numero maximo de comparacoes. a4) Determine o numero exato de vezes que a rotina M-S e' chamada para ordenar um vetor com n elementos. Voce deve considerar a chamada inicial e todas as chamadas recursivas. Nota: Nos items (a1)-(a4) voce pode assumir que n = 2^h, onde h e' um numero inteiro positivo. B) Nesta parte, consideramos a complexidade do algoritmo M-S. Denote por C(n) e R(n) o numero de comparacoes e chamadas recursivas realizadas por M-S para ordernar um vetor com n elementos. Para cada proposicao a seguir, indique se ela e' verdadeira ou falsa, justificando a sua resposta. i) A complexidade do algoritmo M-S e' Theta(C(n) + R(n)). ii) Sabendo que uma chamada recursiva leva muito mais tempo do que uma comparacao, podemos concluir que complexidade O(C(n)). C) Nesta parte, analisamos o tempo de execucao de M-S em um computador com multiplos processadores. A versao paralela do algoritmo, que denotamos por PM-S, divide o vetor em duas partes, e encarrega processadores distintos de ordenar as duas metades. c1) Analise o tempo de execucao do algoritmo PM-S em uma maquina com n processadores. c2) Repita o exercicio anterior supondo que a maquina possui apenas k processadores. Nota: Nos itens (c1) e (c2) voce pode assumir que n = 2^s e k = 2^t, onde s e t sao numeros inteiros positivos, e s > t. 2) A) Considere uma lista ordernada de numeros inteiros arbitrarios S = {s1, s2, ..., sn}, onde todos os elementos sao distintos. O problema consiste em determinar se existe algum indice i tal que si = i. a1) Descreva um algoritmo para este problema que execute em tempo O(log n). a2) Mostre que qualquer algoritmo baseado em comparacoes para este problema executa em tempo Omega(log n). B) Para cada um dos casos a seguir verifique se a estimativa de pior caso do tempo de execucao dos procedimentos e' pessimista. Mais especificamente, para cada procedimento voce deve estimar o tempo de execucao f(n) no pior caso, o tempo medio de execucao g(n), e verificar se g(n) = o(f(n)) (i.e., g(n) assintoticamente menor do que f(n)). b1) Busca linear em um vetor nao-ordenado. b2) Busca binaria em um vetor ordenado. 3) Considere uma lista L = {v1, v2, ..., vn} de vetores em R^2. Ou seja, os elementos sao da forma vi = (xi,yi). Sabe-se que o angulo theta entre dois vetores vi e vj satisfaz cos(theta) = ----------- |vi| * |vj| onde denota o produto interno de vi e vj, e |vi| denota o modulo do vetor vi. Dois vetores vi e vj sao ditos ortogonais se o angulo theta entre eles e' igual a 90 graus, ou, equivalentemente, se cos(theta) = 0. a) Descreva algoritmos para os seguintes problemas que executem em tempo o(n^2) (i.e., assintoticamente menor do que n^2). a1) Encontrar o par de vetores em L com menor angulo entre si. a2) Determinar se existe algum par de vetores ortogonais em L. b) O seu algoritmo pode ser aplicado a uma lista de vetores em R^3? Justifique. 4) Considere uma sequencia de numeros A = (a1, a2, ..., an). Uma subsequencia S de A e' dita densa se: para todo elemento ai de A existe j tal que I) aj esta em S; II) |i - j| <= 1. Nota: Informalmente, uma subsequencia S e' densa em A se qualquer elemento ai de A ou esta' em S ou possui um vizinho em S. O custo de uma subsequencia S de A e' definido como a soma dos elementos em S. Um subsequencia densa S* de A e' dita otima se custo(S*) <= custo(S) , p/ toda subseq. densa S de A Exemplo: A = (-1, 9, -14, 3, 27, -19, 35) Neste caso, (-1,9,27,35) e (9,3,-19) sao subsequencias densas de A, mas (9,-19,35) nao e'. Os custos das subsequencias densas acima sao 70 e -7, respectivamente, e o custo da sequencia nao-densa e' de -45. A subsequencia densa otima para este problema e' (-1,-14,-19). a) Faca um algoritmo para encontrar uma subsequencia densa em A que possua custo minimo. b) Qual a complexidade do seu algoritmo? Justifique. 5) Suponha que temos n pessoas com alturas [p1, ..., pn], e n pares de esquis com alturas [e1, ..., en]. O problema consiste em associar um par de esquis a cada pessoa de modo a minimizar a media das diferenças entre a altura de cada pessoa e a altura do esqui associado a ela. Por exemplo, a solucao que associa, para todo i, a pessoa pi ao par de esquis ei tem custo: 1 --- * Soma_i |pi - ei| n A seguir apresentamos dois algoritmos para este problema: Alg X: A cada passo, encontrar a pessoa pi e o par de esquis ej com a menor diferenca de altura entre si, e associar ej a pi. Alg Y: Associar o menor par de esquis `a menor pessoa, associar o segundo menor par de esquis `a segunda menor pessoa, e assim por diante. Apenas um dos algoritmos acima encontra uma solucao otima para o problema. Indique qual e' o algoritmo otimo, prove a sua otimalidade, e apresente um contra-exemplo para o outro algoritmo. 6) Considere um grafo nao-orientado G = (V,A) e suponha que, com a excecao de um vertice arbitrario u, todos os vertices possuem uma cor que pode ser verde ou vermelha. Estamos interessados em encontrar todos os vertices vertices vermelhos que podem ser alcancados a partir de u sem passar por nenhum vertice verde. a) Apresente um algoritmo que resolva este problema. b) Qual a complexidade do seu algoritmo? c) Apresente um argumento para mostrar que o seu algoritmo funciona corretamente. d) Modifique o seu algoritmo (ou apresente um algoritmo diferente) para encontrar os vertices vermelhos que podem ser alcancados a partir de u passando por ate k vertices verdes. (Nota: O valor de k e' um parametro que e' passado ao algoritmo). Problema Extra: (p/ entregar durante a aula de segunda-feira (23/05)) -------------- Suponha que o chip XK-950 esta' em fase de desenvolvimento, e se deseja determinar a voltagem maxima que ele suporta. Ou seja, existe um valor inteiro u, desconhecido, tal que se aplicarmos qualquer voltagem v maior do que u ao chip ele e' queimado e nao pode mais ser utilizado; mas se aplicarmos uma voltagem v < u, entao o chip funciona normalmente e pode ser usado novamente. O problema consiste em determinar o valor de u realizando o menor numero de testes e danificando o menor numero de chips. a) Argumente que existe apenas uma estrategia correta para descobrir o valor de u utilizando um unico chip, e que ela realiza u+1 testes. b) Descreva uma estrategia que utiliza apenas 2 chips e realiza o(n) testes (i.e., uma quantidade assintoticamente menor do que n testes). c) Descreva uma estrategia para este problema que utiliza k chips e minimiza o numero de testes. d) Considere a seguinte estrategia para o problema: Algoritmo { y := 0; x := 1; inc := 1; Repetir { Enquanto (Testa_Chip(x) = OK) { y := x; x := x + inc; inc := 2 * inc; } Se (x = y + 1) Retorna (y); Senao { x := y + 1; inc := 1; } } } d1) Simule o algoritmo supondo que u = 100, apresentando a sequencia de testes que e' realizada. d2) Estime o numero de chips utilizados pelo algoritmo. d3) Estime o numero de testes realizados pelo algoritmo. Nota: As respostas para os itens (d2) e (d3) devem ser funcoes em termos da voltagem maxima u.