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) Considere um conjunto com n livros, onde cada livro i possui peso pi < 1 kg. Os livros devem ser armazenados em caixas. Cada caixa pode receber ate' dois livros, e suporta um peso maximo de 1 kg. O problema consiste em armazenar todos os livros utilizando o menor numero de caixas possivel. a) Considere o seguinte algoritmo guloso para este problema: Algoritmo G1 { Enquanto houver livro sem caixa { lMax := livro com maior peso; lmim := livro com menor peso; Se (lMax + lmin <= 1 kg) Colocar lMax e lmin em uma nova caixa; Senao Colocar apenas lMax em uma nova caixa; } } a1) Descreva como o algoritmo G1 pode ser implementado de modo que execute em tempo O(n log n). a2) Neste item, construiremos uma prova para a otimalidade do algoritmo G1. a2.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. a2.2) Prove a tese para o caso base, e defina uma hipotese indutiva. a2.3) Utilize a hipotese indutiva do item anterior para provar que o algoritmo encontra uma solucao otima para o problema. a2.4) Indique em que ponto da sua prova foi necessario utilizar o resultado do item (a2.1). b) Considere este outro algoritmo guloso para o mesmo problema: Algoritmo G2 { Enquanto existir livro sem caixa { Selecionar um subconjunto com ate' 2 livros e peso total maximo (mas <= 1kg), e colocar em uma nova caixa. } } Este algoritmo encontra uma solucao otima para o problema? Apresente um argumento informal para justificar sua resposta. c) Considere agora a versao do problema em que cada caixa pode armazenar ate' 3 livros. Suponha que o algoritmo G2 e' modificado para considerar subconjuntos com ate' 3 livros. Apresente um contra-exemplo mostrando que este algoritmo nao encontra (necessariamente) uma solucao otima para o problema. 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: Max_i Prod_{aj em Ai} aj ou seja, o maximo entre todas as particoes do produto dos seus elementos. Por exemplo, para a primeira particao acima a expressao tem valor 150, enquanto que para a segunda particao a expressao assume valor 17 * 150 = 2550. a) Mostre que, se todos os elementos de A sao maiores do que 1, entao a solucao que coloca apenas um elemento em cada particao e' otima. 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. e) Escolha apenas uma das alternativas abaixo e repita o exercicio do item (c). e1) Suponha que a sequencia A deve ser dividida em exatamente k particoes. e2) Suponha que o algoritmo deve encontrar uma particao que minimize a expressao K*C + Max_i Prod_{aj em Ai} aj onde K e' o numero de particoes utilizadas e C e' o custo de cada particao. A ideia neste caso, e' incluir um custo adicional por particao de modo que o numero total de particoes seja reduzido. 4) Nesta questao consideramos o problema de armazenamento de dados em um sistema heterogeneo de memoria. O sistema e' composto por m dispositivos de memoria d1,...,dm distintos. Cada dispositivo dj pode armazenar ate' hj arquivos (independentemente dos seus tamanhos), e possui taxa de acesso de tj bytes por milisegundo. Temos k arquivos a1,...,ak para armazenar no sistema, onde cada arquivo ai possui tamanho si bytes, e probabilidade de acesso pi. O objetivo e' encontrar uma configuracao para o armazenamento dos arquivos que minimize o tempo medio de acesso, definido pela expressao Soma_i pi * Ti onde Ti e' o tempo de acesso ao arquivo ai, que depende do seu tamanho e das caracteristicas do dispositivo em que ele e' armazenado. a) Proponha um algoritmo guloso para encontrar uma solucao para este problema. b) Siga o roteiro apresentado no problema (2) da primeira parte da prova, e prove que o seu algoritmo encontra uma solucao otima. Considere agora a versao mais realista deste problema em que removemos a suposicao de que cada dispositivo dj pode armazenar ate' hj arquivos, nao importanto o tamanho dos arquivos, e introduzimos a restricao de que o dispositivo dj tem capacidade maxima igual a Cj bytes. c) Descreva um algoritmo guloso para o caso particular do problema em que todos os arquivos possuem o mesmo tamanho. d) Apresente um contra-exemplo mostrando que o algoritmo do item (c) nao encontra uma solucao otima para o caso geral (i.e., quando os arquivos possuem tamanho diferente). e) Descreva um algoritmo guloso para o caso particular do problema em que todos os arquivos possuem a mesma probabilidade de acesso. f) Apresente um contra-exemplo mostrando que o algoritmo do item (e) nao encontra uma solucao otima para o caso geral (i.e., quando os arquivos possuem probabilidades de acesso diferentes). g) Discuta possiveis ideias para a elaboracao de um algoritmo que encontra uma solucao otima para o caso geral do problema. 5) 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 dos dois lados do rio, e possuem um orcamento de valor C para realizar este projeto. A unica restricao estabelecida e' que duas pontes nao podem se cruzar. Para cada para de cidades Ai, Bj o custo de construcao de uma ponte entre as duas cidades e' denotado por cij. O problema consiste em construir o maior numero de pontes, de modo que o custo total de construcao nao exceda o valor do orcamento. Exemplo: 3 cidades de cada lado, orcamento C = 20 custos: B1 B2 B3 --------------- A1 | 5 11 2 | | | por exemplo, o custo de uma ponte A2 | 3 10 9 | entre A1 e B3 e' 15, e o custo de | | uma ponte entre A3 e B2 e' 4. A3 | 8 4 5 | --------------- Possiveis solucoes: A1 A2 A3 A1 A2 A3 | | | | / /| 5| 10| 5| 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. (Nota: Voce pode incluir solucoes que excedam o valor do orcamento na sua estimativa.) 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. 6) Os missionarios Abraao e Benjamin devem percorrer um conjunto de cidades C = < c1, c2, c3, ..., cn >, na ordem estabelecida por esta sequencia. Entretanto, para reduzir o esforco, eles decidem particionar as cidades em Ca = < ca1, ca2, ..., cak > Cb = < cb1, cb2, ..., cbl > onde Ca e Cb sao subsequencias da sequencia original C, e toda cidade de C aparece em exatamente uma das duas subsequencias. Desta maneira, o missionario A so' percorre as cidades em Ca, enquanto que o missionario B percorre apenas as cidades em Cb (nas ordens estabelecidas pelas subsequencias). a) Indique se e' possivel que uma escolha infeliz da particao (Ca,Cb) faca com que algum dos missionarios percorra uma distancia maior do que a que ele percorreria caso as cidades nao fossem particionadas? Justifique a sua resposta. Alem de particionar as cidades, os missionarios resolvem fazer isto de modo que a soma das distancias percorridas por eles seja a menor possivel. Formalmente, denotando por D(ci,cj) a distancia entre as cidades ci e cj, o problema consiste em encontrar uma particao (Ca,Cb) que minimize a expressao: Soma_i D(cai, ca(i+1)) + Soma_j D(cbj, cb(j+1)) b) Faca um algoritmo que encontre uma particao otima das cidades. (Dica: Utilize a tecnica de programacao dinamica.)