Construcao e Analise de Algoritmos - Prova 3 -------------------------------------------- 1) Parte A) Problema do Vendedor de Bananas -------- Um vendedor de bananas pode trabalhar na cidade de Aracati ou na cidade de Barbalha a cada dia. Sabe-se que Um dia de trabalho na cidade A (B) gera um rendimento de Ra (Rb) reais, e o custo da viagem entre A e B e' de V reais. Suponha que o vendedor se encontra na cidade B, que Rb < Ra, e que ele planeja trabalhar exatamente k dias. Determine uma estrategia otima para o vendedor. Justifique. Nota: Uma estrategia deve determinar em que cidade o vendedor trabalha a cada dia, e tem como recompensa a soma dos rendimentos de cada dia menos o custo total das viagens. A estrategia pode depender dos valores de Ra, Rb, V e k. Uma estrategia e' otima se ela gera a maior recompensa possivel. - - - - - - - - - - - - - - - - - - - - - - - - Parte B) Problema do Teste de Chips -------- Suponha que temos n chips de computador, e que alguns deles podem estar defeituosos. O problema consiste em identificar os chips que funcionam corretamente realizando testes com pares de chips. Um teste com os chips A e B consiste em utilizar o chip A para testar o chip B, e, em seguida, utilizar o chip B para testar o chip A. Se um chip funciona corretamente, entao ele sempre indica de maneira correta se o chip testado esta' defeituoso ou nao. Por outro lado, um chip defeituoso pode indicar qualquer coisa como resultado de um teste. (Nota: Dois chips defeituosos podem indicar resultados diferentes ao testar o mesmo chip.) a) Suponha que a maioria dos chips funciona corretamente (i.e., menos do que n/2 chips sao defeituosos) a1) Faca um algoritmo para encontrar um chip que funciona corretamente. a2) Utilize o resultado do item anterior para construir um algoritmo que encontra todos os chips bons. a3) Estime o numero de testes realizados pelo seu algoritmo, no pior caso. 2) Porcas e Parafusos Considere uma caixa com n pares de porcas e parafusos, mas suponha que as 2n pecas estao separadas e espalhadas pela caixa. Os tamanhos dos parafusos sao muito parecidos, e, portanto, uma comparacao entre dois parafusos (ou duas porcas) nao permite decidir qual deles e' o menor. A unica maneira de obter alguma informacao e' atraves de comparacoes entre parafusos e porcas (por exemplo, tentando encaixar a porca no parafuso). Neste caso, e' possivel verificar se o parafuso e a porca formam um par, ou se o parafuso e' maior ou menor do que a porca. O problema consiste em encontrar para cada parafuso a porca com que ele forma um par. a) Apresente um algoritmo para encontrar o menor par de parafuso e porca utilizando apenas 2n - 2 comparacoes. b) Um algoritmo ingenuo para este problema consiste em comparar cada parafuso com todas as porcas ate' encontrar o seu par. E' facil ver que, no pior caso, este algoritmo realiza Theta(n^2) comparacoes. Argumente que este algoritmo tambem realiza Theta(n^2) comparacoes no caso medio. c) Apresente um algoritmo para este problema que executa O(n log n) comparacoes no caso medio. Justifique. - - - - - - - - - - - - - - - - - - - - - - - - - - 3) Problema da Soma Alternada Considere uma sequencia S = < s1, s2, ..., sn > de inteiros positivos, e seja A = < si1, si2, ..., sik > uma subsequencia de S. Definimos a soma alternada da subsequencia A como: Soma_j (-1)^{j+1} sij O problema consiste em encontrar uma subsequencia de S com soma alternada maxima possivel. Exemplos: 1) S = < 4, 9, 2, 4, 1, 3, 7 > solucao otima: < 9, 2, 4, 1, 7 > 2) S = < 7, 6, 5, 4, 3, 2, 1 > solucao otima: < 7 > a) Prove que se S e' uma sequencia monotona (i.e., S e' crescente ou decrescente), entao a solucao otima contem apenas um elemento. b) Este problema pode ser resolvido por um problema de Divisao e Conquista. Justifique. c) Desenvolva um algoritmo de programacao dinamica para o problema, seguindo os passos abaixo. c1) Analise a estrutura de uma solucao otima para o problema. c2) Apresente o algoritmo de programacao dinamica baseado na analise do item (c1). Nota: Descreva a ideia do algoritmo em um paragrafo. c3) Determine a complexidade do seu algoritmo. c4) Simule a execucao do seu algoritmo no primeiro exemplo acima. 4) Problema com Caixas Suponha que voce possui um conjunto de caixas { C1, C2, ..., Cn }, e que cada caixa Ci e' definida por 3 dimensoes: di1, di2 e di3. (Nota: dependendo da posicao da caixa, as dimensoes podem ser interpretadas como a altura, largura e comprimento da caixa, mas as caixas podem ser colocadas em qualquer posicao.) Uma caixa A pode ser colocada dentro da caixa B se a caixa A pode ser posicionada de modo que as dimensoes de A sejam (estritamente) menores do que as dimensoes correspondentes de B. Formalmente, A pode ser colocada dentro de B se existe uma permutacao S de <1, 2, 3> tal que db_i > da_S(i), para i = 1, 2 e 3. a) Mostre que a relacao "pode ser colocada dentro de" e' transitiva. b) Apresente um algoritmo que, dadas duas caixas A e B, determine, de maneira eficiente, se A pode ser colocada dentro de B. c) Faca um algoritmo para encontrar a maior sequencia de caixas < Ci1, Ci2, ..., Cik > de caixas tal que, para j = 2, ..., k, a caixa Cij pode ser colocada dentro da caixa Ci_{j-1}. 5) Problema da Discagem Telefonica (ou, problema da telefonista preguicosa, mas inteligente). Considere uma telefonista que realiza um grande numero de chamadas telefonicas todos os dias. Para reduzir o seu esforco, ela decide desenvolver um algoritmo para fazer as chamadas movendo os seus dedos o minimo possivel. Mais precisamente, cada numero de telefone possui n digitos, e a chamada e' feita utilizando apenas 2 dedos (por exemplo, os dedos indicadores das maos direita e esquerda). No inicio da chamada, os deods se encontram nas posicoes * e # do teclado. Suponha que o esforco para mover um dedo de um botao para o outro e' proporcional `a distancia entre os botoes. a) Considere o algoritmo guloso para este problema que consiste em mover o dedo que esta mais perto do proximo botao a ser apertado. Apresente um contra-exemplo mostrando que este algoritmo nao encontra sempre uma solucao otima. (Ou seja, apresente um numero de telefone em que o algoritmo guloso realiza uma certa quantidade de movimento, e mostre como o mesmo numero pode ser chamada movendo menos os dedos.) b) Desenvolva um algoritmo para este problema baseado na tecnica de programacao dinamica, seguindo os passos abaixo: b1) Analise a estrutura de uma solucao otima para o problema, e mostre como o problema pode ser dividido a partir desta observacao. b2) Apresente o algoritmo de programacao dinamica baseado na analise do item (b1). Nota: Descreva sucintamente a ideia do algoritmo em um paragrafo. b3) Determine a complexidade do seu algoritmo. 6) Problemas NP-completos Considere os problemas a seguir: * Problema 1: ---------- / colecao {A1, A2, A3, ..., Am} de subconjuntos de um Entrada: | conjunto finito S. | \ numero inteiro k > 0 Problema: Existem k subconjuntos na colecao cuja uniao seja igual ao conjunto S? * Problema 2: ---------- / colecao {A1, A2, A3, ..., Am} de subconjuntos de um Entrada: | conjunto finito S. | \ numero inteiro k > 0 Problema: Existem k subconjuntos na colecao que formam uma particao para o conjunto S? Nota: Lembre-se que uma particao (A1, A2, ..., Ak) para um conjunto S e' uma colecao de subconjuntos "disjuntos" cuja uniao e' igual ao conjunto S. A seguir, provaremos que o seguinte resultado: TEOREMA: O Problema 2 e' NP-completo. PROVA: a1) Mostre que o Problema 2 pertence `a classe NP. A seguir, apresentamos a reducao de uma versao simplificada do Problema 1 (que e' NP-completo) para o Problema 2. Suponha que temos uma colecao de subconjuntos do conjunto S, com no maximo 3 elementos cada um, e um numero inteiro k > 0. Exemplo: S = { 8, 3, 5, 9, 14, 7, 11, 4 } colecao de subconjuntos : < {8,9,11} ; {4,3,8} ; {5,9} ; {3,11,4} ; {7, 14} > Queremos determinar se existem k subconjuntos na colecao cuja uniao e' igual ao conjunto S. No exemplo acima, se tomamos k = 3 entao nao e' dificil verificar que a resposta para o problema e' NAO. Entretanto, se tomamos k = 4, entao temos a seguinte solucao < {8,9,11} ; {5,9} ; {3,11,4} ; {7, 14} > que comprova que a resposta para o problema e' SIM. A reducao do Problema 1 para o problema 2 e' feita da seguinte maneira. Simplesmente expandimos a colecao adicionando todos os subconjuntos de um subconjunto que ja' esteja na colecao, e tomamos o mesmo numero inteiro k. a2) Para completar a prova do teorema, basta mostrar que: a2.1) Esta reducao pode ser calculada em tempo polinomial. a2.2) Existe uma particao de S formada por k subconjuntos da colecao expandida se e somente se existem k subconjuntos na colecao original cuja soma e' igual ao conjunto S.