PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Horário: 3as-feiras de 13 às 16 horas - Sala 154L
28 de junho de 2009
Período: 2009.1
PROJETO E ANÁLISE DE ALGORITMOS (INF 2926)

4a Lista de Exercícios

  1. Sejam P1, P2 e P3 três problemas tais que P1 an P2 an3logn P3 (i.e., P1 é redutível a P2 em tempo linear e P2 a P3 em tempo n3 log n). Assuma a hipótese de que P1 é W(n log n). Assuma também que você conhece um algoritmo O (n3) para resolver P3. Discuta as afirmaoeabaixo.
    1. O que você pode dizer sobre a complexidade de resolução de P2 ? Qual a complexidade do melhor algoritmo que você conhece para P2 ?
    2. Todo algoritmo que resolve P2 tem que gastar pelo menos tempo quadrático (P2 é W(n2)).
    3. W(n log n) é um limite inferior para a complexidade de P3.
    4. P2 pode ser resolvido no pior caso em tempo O(n log n).

  2. Sejam P1 e P2 dois problemas tais que P1 a2n P2. Assuma a hipótese de que P1 Î NP-completo. Assuma também que você conhece um algoritmo O (n3) para resolver P2. Discuta as afirmações abaixo.
    1. P2 Î NP-completo.
    2. P1 tem algoritmo polinomial para a sua resolução.
    3. Somente algoritmos de complexidade exponencial resolvem P1.
    4. Somente algoritmos de complexidade exponencial resolvem P2.

  3. Defina as classes de problemas P, NP e NP-completo Relacione estas classes e dê um exemplo de problema para cada classe.

  4. Seja P o conjunto dos problemas para os quais existem algoritmos determinísticos polinomias para a sua resolução . Seja NP o conjunto dos problemas para os quais existem algoritmos não-determinísticos polinomias para a sua resolução . Naturalmente P está contido em NP. Considere os problemas P1 Î P e P2 Î NP-completo. Indique se cada afirmação abaixo é verdadeira, falsa ou se não se sabe.
    1. Conhece-se uma redução de P1 para P2 que toma tempo polinomial (O(nk)).
    2. Se existe um algoritmo determinístico polinomial para a resolução de P2 então podemos afirmar que P1 Î NP-completo assim como P2 Î P.
    3. P2 é pelo menos tão difícil quanto 3-SAT.
    4. 3-SAT é pelo menos tão difícil quanto P2.
    5. Conhece-se uma redução de P2 para P1 que toma tempo polinomial.

  5. Sabe-se que o problema (MC), abaixo, pertence a NP-completo. Use este conhecimento para provar que (MSS) também pertence a NP-completo.

    Clique-Máximo (MC) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um clique (isto é um sub-grafo completo) de cardinalidade maior ou igual à K.

    Estável-Máximo (MSS) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um conjunto de vértices independentes (isto é, um conjunto de vértices onde não existe aresta entre nenhum par do conjunto) de cardinalidade maior ou igual à K.

    (Dica: Siga os passos para provar que um problema é NP-completo. A redução pedida aqui é muito, mas muito simples. Leia com cuidado e desenhe exemplos dos problemas).

  6. Prove que os problemas abaixo pertencem à NP. Em seguida, apresente uma relaxação (aceitável, a melhor que você pode conseguir) e calculável em tempo polinomial para as versões de otimização de cada um deles.

    1. Árvore Geradora Mínima com restrição de Grau (AGG) - Dado um grafo não-orientado G=(V,E), pesos we Î E e constantes K e C.

      Pergunta-se se este grafo G possui uma árvore geradora cujo grau em nenhum dos vértices seja superior a K e cuja soma dos pesos das arestas nesta árvore seja no máximo C.

      (minimize C)

    2. Clique-Máximo (MC) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um clique (isto é um sub-grafo completo) de cardinalidade maior ou igual à K.

      (maximize K)

    3. (MS): Dados um conjunto de máquinas M={ m1, m2, ..., mp} e um conjunto de tarefas T={ t1, t2, ...,tq} cada uma com uma duração di Î Z, i=1,...,q onde di associada e uma constante K. Considerando-se que as tarefas podem ser atribuídas à qualquer máquina indistintamente. Pergunta-se se existe uma atribuição das tarefas às p máquinas tal que o instante em que a última tarefa é terminada é menor ou igual que K (Isto é, a duração total é inferior ou igual a K).

      (minimize K)

  7. Considere a multiplicação de n matrizes A1, ..., An. Considere também que denota-se o produto das matrizes Ak.Ak+1..... Aq por Ak..q e que as dimensões das matrizes são dadas por dk × dk+1 para a matriz Ak. Assim, A1..n terá dimensão d1 × dn+1.

    Aqui a multiplicação de pares consecutivos de matrizes Ak.Ak+1 é feita calculando
    ai,jk..k+1 =
    dk+1
    å
    p=1
    ai,pk.ap,jk+1
    para todo par (i,j) que é elemento de Ak.Ak+1 e onde ai,jk representa o elemento (i,j) da matriz Ak.

    Observe que a multiplicação de 3 matrizes A1, A2 e A3, pode ser feita de duas manieras: ((A1.A2). A3) e (A1.(A2.A3)). (De quantas maneiras pode-se obter o produto de n matrizes ?)

    Observe também que para cada maneira de se multiplicar n matrizes pode-se ter que realizar um número diferente de multiplicações. Quantas são ?

    Apresente um algoritmo para determinar a maneira de se multiplicar as n matrizes que utiliza o menor número de multiplicações. Analise a complexidade do algoritmo proposto. A complexidade é polinomial ? Qual a complexidade menor possível que um algoritmo que resolve este problema pode ter ?

  8. Um comerciante possui um armazém que utiliza para suprir seus clientes de um único produto. O seu armazém pode guardar até C unidades do produto. Para as próximas T semanas o comerciante TEM que atender às demandas dos seus clientes que somam dt para a semana t, onde t=1,2,...,T. Além disso, ele possui s0(£ C) unidades em estoque antes do início da primeira semana, e já negociou com os fornecedores os preços unitários pt (t=1,2,...,T). Ele deseja planejar o atendimento dos seus clientes de modo a gastar o mínimo possível com a compra do produto.

    Ajude ao comerciante a definir a sua estratégia ótima de compra do produto nas semanas t=1,..., T.
    1. Apresente o algoritmo que obtém a estratégia de compra de menor custo e atende às demandas dos seus clientes.
    2. Analise a complexidade do algoritmo proposto. A complexidade é polinomial ? Qual a complexidade menor possível que um algoritmo que resolve este problema pode ter ?
    3. Execute o seu algoritmo sobre a seguinte instância: C=12, T=5,s0 = 3, d1 = 7, d2 = 4, d3 = 15, d4 = 10, d5 = 7 e p1 = 3, p2 = 4, p3 = 7, p4 = 6, p5 = 8. Informe quanto o comerciante deve comprar em cada semana e o seu custo total.

  9. Considere um tabuleiro de xadrez e um rei que está inicialmente na posição (1,1) (as posições do tabuleiro são representadas por (i,j) onde 1 £ i £ 8 e 1 £ j £ 8). Para cada posição do tabuleiro estão associados um prêmio pij e um consumo qij (o prêmio pode ser em USD(!!) e o consumo em litros de gasolina, por exemplo). Os prêmios e os consumos assumem somente valores positivos. O rei tem inicialmente Q unidades para consumir e pode passar quantas vezes quiser em cada posição do tabuleiro e a cada vez receber o prêmio e, naturalmente, consumir os seus recursos. Ao final (do passeio) o rei tem que estar de volta na posição (1,1).
    1. Proponha um algoritmo para determinar o caminho que o rei deve fazer para obter o maior total possível em prêmios.

      (Dica: Suponha que você conhece a solução que obtém o maior total em prêmios dado que o rei está em cada uma das posições do tabuleiro e para cada consumo possível. Escreva agora o teorema do passo indutivo reforçando a hipótese indutiva. A prova por indução matemática (simples) de que você sabe resolver o problema do rei leva ao algoritmo).

    2. Analise a complexidade do algoritmo proposto. A complexidade é polinomial ? Qual a complexidade menor possível que um algoritmo que resolve este problema pode ter ? Qual a complexidade deste problema ?

    3. Suponha que Q = 7 e que qij = 1 e pij = 2*i + 3*j para todo (i,j). Determine o caminho em que o rei acumula o maior total possível de prêmios. Repita o cálculo modificando apenas p22 = 100 e mantendo os demais valores.

  10. Considere que um ladrão possui um caminhão (:-)) cuja capacidade de peso é P e de volume é V. Este ladrão está assaltando um almoxarifado de um museu que contém n objetos. Em visita anterior, o ladrão levantou para cada objeto j o seu preço fj, o seu peso pj e o seu volume vj (para j=1,...,n). Para escolher os objetos que é capaz de colocar no seu caminhão que maximizam o valor total do furto, o ladrão utilizou um algoritmo de programação dinâmica que utiliza a seguinte recursão:
    F(j,p,v) = max { F(j-1, p, v), F(j-1, p-pj, v - vj) + fj }
    1. Explique como esta recursão é utilizada pelo ladrão para obter o furto ótimo. Explique o que representa F(j,p,v), como é obtida e para que valores de j, p e v a cada iteração (o faz um iteração e como é a sua inicialização).
    2. Qual é a complexidade do algoritmo resultante ?
    3. Aplique este algoritmo na seguinte instância de furto: P=3, V=6, n=3, f1=4, p1=2, v1=2, f2=5, p2=2, v2=2, f3=3, p3=1 e v3=2.

  11. Considere o seguinte jogo: Dada um sequência de n (n é par) cartas enfileiradas com valores positivos e inteiros v1, v2, ..., vn abertos (conhecidos). Dois jogadores J1 e J2 alternam a vez de jogar. Uma jogada consiste em pegar uma carta de uma das pontas (a carta 1 ou a n no início, a 2 ou a n se o primeiro a jogar pegou a carta 1, ou 1 ou a n-1 se ele pegou a carta n). Vence aquele cuja soma dos valores das cartas que pegou for maior.
    1. Apresente uma sequência de cartas onde o primeiro jogador não pegar o maior valor possível se ele escolhe a carta de maior valor na primeira jogada. (Ou seja, mostre que a estratégia gulosa não funciona para este problema.)
    2. Proponha um algoritmo que calcule a estratégia ótima para o primeiro jogador. Este algoritmo deve executar em O(n2). Uma estratégia ótima é a informação necessária para que o jogador 1 determine cada uma das suas jogadas em O(1) de modo que obtenha no final o maior valor possível.

This document was translated from LATEX by HEVEA.