Construcao e Analise de Algoritmos - Prova 3 -------------------------------------------- 1) Um problema de interesse teorico consiste em encontrar um algoritmo de ordenacao cujo numero exato de comparacoes e' o menor possivel. A analise apresentada em sala de aula mostrou que este numero deve ser pelo menos igual a Teto( log n! ). A seguir apresentaremos um algoritmo bastante simples, desenvolvido por Ford e Johnson, que se aproxima deste limite inferior. Este algoritmo foi desevolvido em 1959, e ate bem pouco tempo era o melhor algoritmo conhecido para ordenacao (considerando apenas o numero de comparacoes) Algoritmo FJA { 1. Dividir elementos em n/2 pares 2. Ordenar o subconjunto formado pelos maiores elementos de cada par. Este passo produz uma lista ordenada . Denote por bi o elemento que formava par com ai no passo 1. 3. Inserir os elementos b1,...,bn/2 na lista ordenada, utilizando busca binaria para localizar a posicao de insercao. } A eficiencia do algoritmo depende fundamentalmente de como o passo (3) e' implementado. Nos itens a seguir consideraremos diversas possibilidade. a) Suponha que os elementos sao inseridos na ordem bn/2, ..., b2, b1. Neste caso, a insercao de bn/2 requer log(n/2) comparacoes, pois ele e' inserido na lista , e existem exatamente n/2 lugares onde ele pode ser inserido. Note que o elemento b_{n/2 - 1} tambem requer log(n/2) comparacoes pois, no pior caso, o elemento bn/2 e' inserido 'a esquerda de a_{n/2 - 1}, e portant b_{n/2 - 1} tambem e' inserido em uma lista com n/2 - 1 elementos. De fato, a insercao de todos os elementos requer log(n/2) comparacoes (no pior caso), e o numero de comparacoes que o algoritmo realiza no passo (3) e' exatamente n/2 * log (n/2). a1) Apresente a equacao de recorrencia que descreve o numero de comparacoes realizadas pelo algoritmo FJA com esta implementacao. (Nao se esqueca de considerar os tres passos do algoritmo) a2) Desenvolva a equacao pelo metodo iterativo, e mostre que seu resultado e' dado pela expressao: T(n) = 1 + n*log(n) * Soma_{j=1 ate log(n)-1} 1/2^j - n * Soma_{j=1 ate log(n)-1} (j-1)/2^j Resolvendo os somatorios e cancelando alguns termos, obtem-se T(n) = n*log(n) - n + 1 b) Suponha agora que a insercao dos elementos e' realizada na ordem b1,...,bn/2. Neste caso, os primeiros elementos sao inseridos em listas pequenas, exigindo poucas comparacoes. Por outro lado, a insercao dos ultimos elementos ocorre em listas com pelo menos n/2 elementos, o que requer (log n) comparacoes. Prove que o numero de comparacoes realizado no passo (3) do algoritmo utilizando esta implementacao e' dado pela expressao: Soma_{j=1 ate log(n)-1} (j+1) * 2^(j-1) Surpreendentemente o resultado deste somatorio e' n/2 * log (n/2). Portanto, esta implemetacao realiza o mesmo numero de comparacoes que a implementacao do item (a). c) Para reduzir o numero de comparacoes no passo (3) combinaremos as ideias acima. Note que, segundo a ordem do item (b), b1 requer 0 comparacoes b2 requer 2 comparacoes b3 requer 3 comparacoes (pois e' inserido em uma lista com 4 elementos) Entretanto, se invertemos a ordem de insercao de b2 e b3, entao b1 requer 0 comparacoes b3 requer 2 comparacoes b2 requer 2 comparacoes pois temos uma situacao similar ao que ocorre no item (a), onde b3 e b2 sao ambos inseridos em listas com ate 3 elementos. c1) Verifique que o mesmo fenomeno ocorre na insercao de {b4,b5,b6,b7}, e indique quantas comparacoes sao economizadas, com relacao ao item (b), inserindo os elementos em uma ordem adequada. c2) Descreva um algoritmo que utilize esta ideia para a insercao de todos os elementos bi's. c3) Calcule o numero de comparacoes realizadas no passo (3) utilizando o seu algoritmo. 2) Considere os seguintes problemas de otimizacao e seus respectivos algoritmos: Problema 1: Temos n aparelhos de radio r1,...,rn. Cada radio ri opera em uma faixa definida pela frequencia minima li e a frequencia maxima hi. Um radio ri sofre interferencia de outro radio rj se: [li,hi] inter [lj,hj] <> vazio. O problema consiste em selecionar o maior numero possivel de radios tal que dois radios selecionados nao tenham interferencia. Algoritmo A1 { R := {r1, r2,..., rn}; S := vazio; Enquanto (R nao e' vazio) { Selecione rj em R que tenha interferencia com o menor numero de de radios em R; S := S uniao {rj}; Remover de R todos os radios que tenham interferencia com rj. } Retornar (S); } Problema 2: Temos n caixas c1,...,cn. Cada caixa ci e' utilizada ki vezes e possui peso pi. (Se i <> j podemos ter ki <> kj e pi <> pj) As caixas devem ser organizadas em uma pilha . O esforco realizado para utilizar a caixa cij nesta pilha e' definido por Eij = kij * Soma_{t=j ate n} pit ou seja, o numero de vezes que a caixa e' utilizada multiplicado pela soma do seu peso com os pesos das caixas que estao acima dela na pilha. O custo da solucao e' dado por Max {Ei1, Ei2, ..., Ein} ou seja, o esforco maximo entre todas as caixas na pilha: O problema consiste em encontrar uma solucao para o problema que tenha custo minimo. Algoritmo A2 { Organizar as caixas em ordem crescente de acordo com o numero de vezes ki que elas sao utilizadas. } Apenas um dos algoritmos acima encontra uma solucao otima para o seu problema. Determine o algoritmo otimo, apresente uma prova de sua otimalidade, e de um contra-exemplo para o outro algoritmo. 3) Pilha de Blocos Coloridos Suponha que voce possui n blocos b1, b2,..., bn, onde cada bloco bi possui as seguintes caracteristicas: - cor ci (preta ou branca) - altura ai - peso pi Descreva algoritmos para os problemas a seguir. Para cada algoritmo voce deve apresentar: 1) Descricao sucinta do algoritmo 2) Pseudo-codigo com detalhes (i.e., condicoes de parada, construcao da solucao, manipulacao de tabelas, etc.) 3) Analise de complexidade 4) Prova de correcao (ou seja, provar que o algoritmo encontra solucao otima) a) Formar uma pilha com a maior altura possivel utilizando k blocos, satisfazendo as seguintes condicoes: i) Nao existem 3 blocos consecutivos da mesma cor. ii) Para cada par bij e bi(j+i) de blocos consecutivo na pilha, peso(bij) < peso(bij) b) Formar uma pilha com a maior altura possivel utilizando qualquer numero de blocos, satifazendo as condicoes (i) e (ii) acima, e a condicoao adicional iii) A cor do primeiro bloco na pilha deve ser igual a cor do ultimo bloco na pilha. 4) Considere os problemas a seguir: A) Conjunto Dominante Dado um grafo G e um inteiro k, determinar se existe algum subconjunto de vetices com tamanho k tal que, para todo vertice v de G: i) v esta' em D; ou ii) v e' adjacente a algum vertice em D. B) Cobertura de Vertices Dado um grafo G e um inteiro k, determinar se existe algum subconjunto C de vertices com tamanho k tal que, para toda aresta (u,v) de G, temos que u esta' em C ou v esta' em C. C) Hitting Set Dada uma colecao {S1,S2,...,Sn}, onde cada Si e´um subconjunto de T, e um inteiro k, determine se existe algum subconjunto H de T com k elementos tal que (H inter Si) >= 1, para todo i. a) Neste item provaremos que o problema do conjunto dominante e' NP-completo. a1) Prove que Conj-Domin esta' na classe NP. Para completar a prova, mostraremos que Cob-Vert <~ Conj-Domin. Nota: A expressao A <~ B significa que "A pode ser reduzido a B". Seja uma instancia do problema da cobertura de vertices. Construimos um grafo G' adicionando novos vertices e arestas ao grafo G. Especificamente, para cada aresta (v,w) de G, adicione o vertice vw e as arestas (v,vw) e (w,vw). O grafo obtido e' denotado por G'. a2) Prove a seguinte proposicaor: PROPOSICAO: G' possui um conjunto dominante de tamanho k se e somente se G possui uma cobertura de vertices de tamamho k. b) Neste item voce deve provar que o problema Hitting-Set e' NP-completo. b1) Mostre que Hitting-Set esta' na classe NP. b2) Utilize um dos problemas descritos acima para provar que Hittng-Set e' NP-completo.