Construcao e Analise de Algoritmos - Prova 2 -------------------------------------------- 1) Suponha que a secretaria de saude publica tenha coletado n amostras de agua a1,...,an em diferentes pontos da cidade, e precisa determinar quais delas estao contaminadas. Uma solucao ingenua para este problema consiste em testar cada uma das amostras individualmente. Entretanto, esta nao e' uma solucao eficiente se o numero de amostras contaminadas e' pequeno. Neste caso, o numero de testes pode ser reduzido realizando testes coletivos. Em um teste coletivo diversas amostras sao testadas simultaneamente, misturando pequenas porcoes de agua de cada amostra. O resultado de um teste coletivo e' positivo se e somente se pelo menos uma das amostras esta' contaminada. a) Descreva um algoritmo eficiente para identificar as amostras de agua contaminadas. b) Estime o numero de testes realizados pelo seu algoritmo, em termos de n e m, onde m e' o numero de amostras contaminadas. c) Para que valores de m o seu algoritmo realiza menos testes do que a solucao ingenua. 2) Suponha que voce pegou n livros emprestado na biblioteca para estudar para as provas finais, mas ainda nao leu nenhum deles. Os livros deveriam ter sido devolvidos ontem, e a biblioteca cobra um taxa de R$ 1,00 por dia de atraso de cada livro. Para cada livro j voce planeja que precisara' de tj dias para estudar o seu conteudo. Assuma que apenas um livro e' utilizado de cada vez, e que ele e' imediatamente devolvido quando nao e' mais necessario. a) Descreva um algoritmo guloso para determinar a ordem em que os livros devem ser estudados, de modo a minimizar o total de taxas pago `a biblioteca. b) Neste item, construiremos uma prova para a otimalidade do algoritmo G1. b.1) Mostre que existe uma solucao otima para o problema que utiliza uma caixa com o mesmo conteudo da primeira caixa utilizada por G1. A seguir, aplicamos um argumento indutivo. b.2) Prove a tese para o caso base, e defina uma hipotese indutiva. b.3) Utilize a hipotese indutiva do item anterior para provar que o algoritmo encontra uma solucao otima para o problema. b.4) Indique em que ponto da sua prova foi necessario utilizar o resultado do item (a2.1). 3) Considere um vetor A[1..n] representando uma sequencia de numeros reais positivos: . O problema consiste em dividir a sequencia em particoes A1,...,Ak, onde cada particao Ai e' uma subsequencia do tipo A[i,j], ou seja, cada Ai e' uma subsequencia contigua de A. A ideia e' que as particoes sejam aproximadamente equilibradas, de modo que nao exista uma particao com varios elementos grandes e outra apenas com elementos pequenos. Por exemplo, se a sequencia A e' dada por A = < 8, 10, 5, 17, 150 > entao uma particao como A1 = < 8, 10 > A2 = < 5, 17 > A3 = < 150 > e' certamente mais equilibrada do que A1 = < 8 > A2 = < 10, 5 > A3 = < 17, 150 > Esta ideia e' formalizada pela definicao de que uma particao e' equilibrada se ela minimiza a expressao: Soma_i Prod_{aj em Ai} aj ou seja, a soma para todas as particoes do produto dos seus elementos. Por exemplo, para a primeira particao acima a expressao tem valor 80 + 85 + 150 = 315, enquanto que para a segunda particao a expressao assume valor 8 + 50 + 2550 = 2608. a) Mostre que, se todos os elementos de A sao maiores do que 1, entao a unica solucao otima e' aquela que coloca apenas um elemento em cada particao. b) Apresente um contra-exemplo mostrando que a afirmacao do item (a) nao e' verdadeira quando existem elementos menores do que 1 na sequencia A. c) Descreva um algoritmo que encontre uma particao otima para este problema. (Dica: utilize a tecnica de programacao dinamica.) d) Determine a complexidade do seu algoritmo. 4) Suponha que voce esta organizando um torneio de tenis com duplas mistas (ou seja, cada time e' formado por um homem e uma mulher). Os times devem ser formados a partir de um grupo com n homens e n mulheres. Cada homem possui um indice de desempenho denotado por hi, e cada mulher possui um indice de desempenho denotatado por mi. O indice de um time formado pelo homem hi e pela mulher mj e' calculado atraves da expressao: T = (hi + mj) / 2 A ideia e' formar times equilibrados para que o torneio seja interessante. Com este objetivo, determinou-se que os times sao adequados se o valor da expressao abaixo e' o menor possivel: max_k Tk - min_k Tk onde Tk denota o indice de desempenho do k-esimo time. Ou seja, a diferenca entre os indices do melhor time e do pior time deve ser a minima possivel. a) Descreva um algoritmo guloso para encontrar uma solucao otima para este problema. b) Siga o roteiro apresentado no problema (2) da primeira parte da prova, e prove que o seu algoritmo realmente encontra uma solucao otima. 5) Considere um vetor A[1..n] de numeros inteiros. Um segmento do vetor A e' qualquer subconjunto de elementos da forma A[i..j]. O peso de um segmento e' definido como a soma de seus elementos. O problema consiste em encontrar um segmento de A com peso maximo. Por exemplo, se o vetor A e': A = [ 10 ; 0,8 ; -3 ; 14 ; -7 ; 17 ; 71 ; -67 ] entao o segmento A[1..8] tem peso 35,8, e o segmento A[3..5] tem peso 4. O segmento de peso maximo neste caso e' A[1..7], que tem peso 102,8. a) Descreva um algoritmo ingenuo para este problema que execute em tempo O(n^2). b) Apresente um algoritmo que execute em tempo O(n) para encontrar o segmento da forma A[1..j] com peso maximo. c) Apresente um algoritmo baseado na tecnica de divisao e conquista para resolver o problema original. d) Determine a complexidade do seu algoritmo. *e) Apresente um algoritmo para este problema que execute em tempo O(n). 6) Considere uma regiao atravessada por um rio, e suponha que as cidades A1, ..., An estao em uma margem do rio, enquanto que as cidades B1, ..., Bn se encontram na outra margem do rio A1 A2 A3 . . . An ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ B1 B2 B3 . . . Bn Os moradores desta regiao desejam construir pontes conectando as cidades que satisfacam `as seguintes condicoes: a) duas pontes nao podem se cruzar. b) deve existir pelo menos uma ponte conectando cada cidade ao outro lado do rio. Para cada par de cidades Ai, Bj o custo de construcao de uma ponte entre as duas cidades e' denotado por cij. O problema consiste em construir um conjunto de pontes que satisfacam as condicoes (a) e (b) e que possua custo total minimo. Exemplo: 3 cidades de cada lado, e matriz de custos dada por B1 B2 B3 --------------- A1 | 5 11 15 | | | A2 | 3 10 9 | , ou seja o custo de uma ponte entre | | A1 e B3 e' de 15, e o custo de uma A3 | 8 4 5 | ponte entre A3 e B2 e' de 4. --------------- Possiveis solucoes: A1 A2 A3 A1 A2 A3 | | | | / /| 5| 10| 5| e 5| 3/ 4/ |5 | | | | / / | B1 B2 B3 B1 B2 B3 custo total: 20 custo total: 17 a) Estime o numero de solucoes validas para este problema, e verifique que a alternativa de inspecionar todas elas e selecionar a melhor nao e' viavel. b) Proponha um algoritmo guloso para este problema e verifique se ele encontra uma solucao otima para o problema. c) Fazer algoritmo de programacao dinamica para encontrar uma solucao otima para o problema. d) Determine a complexidade do seu algoritmo.