Construcao e Analise de Algoritmos - Prova 2 -------------------------------------------- 1) Suponha que voce possui uma rotina X(.) com a seguinte funcionalidade. Se fornecemos como entrada um conjunto de inteiros A = {a1,a2,...,an} e um numero inteiro k, a rotina responde "SIM" ou "NAO", indicando se existe algum subconjunto de A cuja soma dos elementos e' exatamente k. a) Descreva um algoritmo que utilize a rotina X(.) para encontrar um subconjunto de A com soma de elememtos exatamente k. b) Suponha que a rotina X(.) executa em tempo O(f(n)). Determine a complexidade do seu algoritimo. Justifique. c) Descreva um algoritmo que implementa a fucionalidade da rotina X(.). Seu algoritmo deve executar em tempo polinominal em n. Justifique a sua resposta (ou seja, analise a complexidade do seu algaritmo). 2) Temos um conjunto de arquivos {a1,...,an} que devem ser armazenados em uma fita magnetica em determinada ordem. Em seguinda sao realizadas consultas na fita por alguma informacao armazenada nos arquivos. O processo de consulta consiste em examinar o conteudo dos arquivos na ordem em que eles aparecem na fita, sendo que o tempo necessario para examinar um arquivo e' proporcional ao seu tamanho. O exame de um arquivo ai encontra alguma informacao relevante para a consulta com probabilidade pi, e neste caso a consulta e' encerrada. Caso contrario, o arquivo seguinte na fita magnetica e' examinado, e o processo continua ate' que alguma informacao seja encontrada ou todos os arquivos sejam examinados. O objetivo do problema e' encontrar uma ordem para o armazenamento dos arquivos na fita que minimize o tempo medio para a execucao de uma consulta. O tempo medio de uma consulta e' dado por Soma_j P(consuta se encerrar no j-esimo arquivo) * ( Tempo de uma consulta que se encerra no j-esimo arquivo ) onde a probabilidade da consulta se encerrar no j-esimo arquivo e' dada por: / pj * Prod_{k=1,...,j-1} (1 - pk) , se j < n | \ Prod_{k=1,...,n-1} (1 - pk) , se j = n a) Faca um algoritmo para determinar uma ordem para o armazenamento dos arquivos na fita. b) Prove que seu algoritmo encontra uma solucao otima. 3) Dizemos que a sequencia de caracteres A e' uma supersequencia de B se B e' uma subsequencia de A. Se duas sequencias B e C sao ambas subsequencias de A, entao dizemos que A e' uma supersequencia comum de B e C. Por exemplo, PINDAMONHANGABA e' uma supersequencia comum de MANGABA e PAMONHA Neste problema, estamos interessados em encontrar a supersequencia comum mais curta de duas sequencias B e C. a) Neste item exploramos a relacao que existe entre a supersequencia comum mais curta e a subsequencia comum mais longa de B e C. Considere, B = C = X : subsequencia comum mais longa de B e C Y : supersequencia comum mais curta de B e C a1) Prove que |Y| = |B| + |C| - |X|. Nota: |A| denota o tamanho da sequencia A. a2) Suponha que voce possui uma rotina SC+L(.) que encontra uma subsequencia comum mais longa de B e C. Descreva um algoritmo que utiliza esta rotina para encontrar uma supersequencia comum mais curta de B e C. a3) Determine a complexidade do seu algoritmo, supondo que a rotina SC+L(.) executa em tempo O(f(n)). Justifique. b) Neste item vamos construir diretamente um algoritmo para o problema da supersequencia comum mais curta. b1) O problema pode ser resolvido por uma estrategia simples de divisao em subproblemas? Especificamente, a solucao para o problema (B = ; C = ) pode ser obtida pela concatenacao de solucoes otimas para os subproblemas ( B1 = ; C1 = ) e ( B2 = ; C2 = )? Justifique sua resposta apresentando uma prova em caso positivo, ou um contra-exemplo em caso negativo. b2) Mostre como o problema pode ser dividido em dois subproblemas independentes, utilizando alguma informacao sobre a solucao, de modo que a concatenacao das solucoes dos subproblemas forneca uma solucao otima para o problema. Justifique sua resposta. b3) Apresente um algoritmo que encontre uma solucao otima para o problema da supersequencia comum mais curta. (Sugestao: utilize as ideias do item (b2)). Voce deve: * Mostrar as condicoes de parada do seu algoritmo (caso ele seja recursivo) * Calcular a solucao do problema (e nao apenas o seu tamanho) * Mostrar explicitamente a manipulacao da tabela para armazenar resultados de chamadas anteriores (caso voce use uma). b4) Determine a complexidade do seu algoritmo. 4) Na primeira prova da CANA havia um problema que pedia para provar a equivalencia entre o problema dos cortes de tora e o problema da arvore binaria de busca com nos externos. Para evidenciar esta equivalencia, o problema dos cortes da tora em pedacos menores como um problema em que temos que colar os diversos pedacos de madeira para obter a tora original. Neste caso o custo de cada colagem e' dado pela soma dos tamanhos dos pedacos que estao sendo colados. Observe agora que qualquer solucao para este problema pode ser representada por uma arvore binaria em que cada folha corresponde a um dos pedacos de madeira do problema, e os nos internos correspondem 'as colagens que sao realizadas. Por exemplo, se temos 3 pedacos de madeira c1,c2 e c3 com tamanhos 10, 7 e 18, respectivamente, entao a arvore * / \ c1 * / \ c2 c3 corresponde 'a solucao em que os pedacos c2 e c3 sao coladas primeiro, e em seguido o pedaco obtido e' colado ao pedaco c1. O custo da solucao e' dado pela soma dos custos das colagens que, no exemplo acima, e' igual a: (7+18) + ([7+18]+10) = 60. Entretanto, note que o custo da solucao tambem pode ser calculada da seguinte maneira. Se um pedaco de madeira participa de 3 colagens, entao ele contribui para o custo total da solucao com 3 vezes o seu tamanho. Como o numero de colagens de um pedaco e' dado pela sua altura na arvore temos que o custo total de uma solucao e' Soma_i tamanho(ci) * altura(ci) Mas note que esta e' exatamente a expressao de custo do problema da arvore binaria com externos onde o numero de acessos mi e' substituido pelo tamanho do pedaco ci. A equivalencia logica e' completa pois os pedacos de madeira devem ser colados na ordem correta para forma a tora original, e na arvore binaria de busca os registro menores devem aparecer 'a esquerda dos registros maiores. (Este e' justamente o ponto em que a equivalencia entre o problema da tora e o problema das listas falha.) a) Considere a versao modificada do problema dos cortes de tora em que a cada passo sao realizados dois cortes simultaneos, mas o custo dessa operacao continua igual ao tamanho do pedaco que esta sendo cortado. Apresente uma versao do problema da arvore de busca que seja logicamente equivalente a problema. Justifique sua resposta. b) Apresente uma versao do problema de cortes de tora que seja logicamente equivalente ao problema da arvore binaria de busca tradicional, em que os registros tambem sao armazenados em nos internos da arvore. Questao Extra (para entrega em 01/02/06, quarta-feira) ------------- Considere o seguinte algoritmo que poderia ser utilizado, por exemplo, por uma agencia de casamentos pela Internet para formar casais. Existem n homens e n mulheres. Cada homem classifica as mulheres em ordem, de acordo com a sua preferencia. As mulheres fazem o mesmo com relacao aos homens. No inicio de cada iteracao do algoritmo, cada homem faz uma proposta para a mulher de sua preferencia, dentre aquelas que ainda nao o rejeitaram. Em seguida, cada mulher examina as propostas que recebeu e rejeita todas com a excecao daquela do homem de sua preferencia (entre aqueles que fizeram propostas nesta iteracao). Note que um homem pode fazer diversas propostas 'a mesma mulher, se ele for o seu preferido em iteracoes sucessivas, mas em seguida ser rejeitado, caso a mulher receba uma proposta de um homem que lhe pareca mais interessante. O algoritmo termina quando cada mulher recebe exatamente uma proposta em determinada iteracao. a) Este algoritmo sempre termina? Caso positivo, apresente uma prova; caso negativo, apresente um exemplo. b) Caso sua resposta ao item (a) tenha sido positiva, apresente um limite superior para o numero de iteracoes que o algoritmo executa, em termos de n. c) Uma atribuicao de casais e' dita estavel se nao existe um homem hi e uma mulher mj tal que: 1) hi prefere mj do que a mulher com quem ele esta. 2) mj prefere hi do que o homem com quem ela esta. Prove que este algoritmo encontra uma atribuicao de casais estavel.