1. Exercícios Livro Algorithms, Dasgupta, Papadimitriou e Vazirani.
   • Cap. 5: 5.13, 5.14, 5.15;
     
     
   • Cap. 6: 6.2, 6.3, 6.4, 6.13, 6.17, 6.19.
   
   
2. Considere a multiplicação de n matrizes A₁, ..., A_n. Considere também que denota-se o produto das matrizes A_k.A_k+1..... A_q por A_k..q e que as dimensões das matrizes são dadas por d_k × d_k+1 para a matriz A_k. Assim, A_1..n terá dimensão d₁ × d_n+1.
   
   Aqui a multiplicação de pares consecutivos de matrizes A_k.A_k+1 é feita calculando

   ai,jk..k+1 =

   dk+1 å p=1

   ai,pk.ap,jk+1

   para todo par (i,j) que é elemento de A_k.A_k+1 e onde a_i,j^k representa o elemento (i,j) da matriz A_k.
   
   Observe que a multiplicação de 3 matrizes A₁, A₂ e A₃, pode ser feita de duas manieras: ((A₁.A₂). A₃) e (A₁.(A₂.A₃)). (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 ?
   
   
3. 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 d_t para a semana t, onde t=1,2,...,T. Além disso, ele possui s₀(£ C) unidades em estoque antes do início da primeira semana, e já negociou com os fornecedores os preços unitários p_t (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,s₀ = 3, d₁ = 7, d₂ = 4, d₃ = 15, d₄ = 10, d₅ = 7 e p₁ = 3, p₂ = 4, p₃ = 7, p₄ = 6, p₅ = 8. Informe quanto o comerciante deve comprar em cada semana e o seu custo total.
   
   
4. 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 p_ij e um consumo q_ij (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 q_ij = 1 e p_ij = 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 p₂₂ = 100 e mantendo os demais valores.
   
   
5. Sejam T = { t₁, ..., t_n } e P = { p₁, ..., p_k } duas sequências de caracteres on k £ n.
   
   
   1. Proponha um algoritmo linear para determinar se P é uma subsequência de T, isto é, se os elementos de P aparecem em T na mesma ordem que em P, mas não necessariamente consecutivos.
      
      
   2. Suponha que a resposta do item anterior é negativa. Proponha um algoritmo para encontrar a maior subsequência de P que está em T.
      
      
   3. Considere que para cada elemento de T é associado um custo positivo c_i, i=1,...,n. Proponha um algoritmo para encontrar a subsequência de P que é subsequência de T onde a soma dos custos dos elementos de T é maximizada.
      
      
   4. Analise a complexidade dos algoritmos propostos. Qual a complexidade menor possível de um algoritmo que resolve estes problemas ?
   
   
6. Sejam P₁, P₂ e P₃ três problemas tais que P₁ a_n P₂ a_n³logn P₃ (i.e., P₁ é redutível a P₂ em tempo linear e P₂ a P₃ em tempo n³ log n). Assuma a hipótese de que P₁ é W(n log n). Assuma também que você conhece um algoritmo O (n³) para resolver P₃. Discuta as afirmações abaixo.
   1. O que você pode dizer sobre a complexidade de resolução de P₂ ? Qual a complexidade do melhor algoritmo que você conhece para P₂ ?
   2. Todo algoritmo que resolve P₂ tem que gastar pelo menos tempo quadrático (P₂ é W(n²)).
   3. W(n log n) é um limite inferior para a complexidade de P₃.
   4. Todo algoritmo que resolve P₁ pode ser usado para resolver P₂.
   5. Todo algoritmo que resolve P₃ pode ser usado para resolver P₂.
   6. P₂ pode ser resolvido no pior caso em tempo O(n log n).
   
   
7. Defina as classes de problemas P, NP e NP-completo Relacione estas classes e dê um exemplo de problema para cada classe.
   
   
8. 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 P₁ Î P e P₂ Î NP-completo. Indique se cada afirmação abaixo é verdadeira, falsa ou se não se sabe.
   1. Conhece-se uma redução de P₁ para P₂ que toma tempo polinomial (O(n^k)).
   2. Se existe um algoritmo determinístico polinomial para a resolução de P₂ então podemos afirmar que P₁ Î NP-completo assim como P₂ Î P.
   3. P₂ é pelo menos tão difícil quanto 3-SAT.
   4. 3-SAT é pelo menos tão difícil quanto P₂.
   5. Existe uma redução de P₂ para P₁ que toma tempo polinomial.
   
   
   
   
   
   
   
   
9. Dado que você conhece um algoritmo determinístico polinomial para a resolução do problema (CMC) abaixo, USE ESTE CONHECIMENTO para provar que você também conhece um algoritmo determinístico polinomial para a resolução do problema (VMC) apresentado em seguida.
   
   (CMC) Dado um grafo orientado G=(V,A) com comprimentos positivos associados aos arcos (i,j) Î A, dois vértices i,j Î V e uma constante K. Pergunta-se se existe uma caminho do vértice i ao vértice j que possua comprimento menor ou igual à K.
   
   (VMC) Dado um grafo orientado G=(V,A), com comprimentos positivos associados aos arcos (i,j) Î A, e uma constante K. Pergunta-se se existe um par de vértices (i,j) para o qual exista um caminho de i a j e de j a i que tenha comprimento menor ou igual à K.
   
   
10. Prove que os problemas (de decisão) abaixo pertencem à NP.
    
    
    1. Árvore Geradora Mínima com restrição de Grau (AGG) - Dado um grafo não-orientado G=(V,E), pesos w_e Î 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={ m₁, m₂, ..., m_p} e um conjunto de tarefas T={ t₁, t₂, ...,t_q} cada uma com uma duração d_i Î Z, i=1,...,q onde d_i 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)
    
    
11. Sabe-se que o problema (MC), abaixo, pertence a NP-completo. Use este conhecimento para provar que (MS) 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 (MS) - 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).
    
    
12. Considere o problema abaixo:
    
    (MS): Dados um conjunto de máquinas M={ m₁, m₂, ..., m_p} e um conjunto de tarefas T={ t₁, t₂, ...,t_q} cada uma com uma duração d_i, i=1,...,q 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).
    
    Dado que este problema pertence a NP-completo responda:
    1. Quando temos um algoritmo polinomial determinístico para resolvê-lo ?
    2. Proponha um algoritmo para resolver este problema em tempo polinomial.
    3. Em que casos a solução obtida pelo seu algoritmo é correta ?
    4. Descreva um algoritmo que encontre sempre a resposta correta para este problema.
    
    
13. Sabe-se que o problema (CH), abaixo, pertence a NP-completo. Use este conhecimento para provar que (AGG) também pertence a NP-completo.
    
    Caminho Hamiltoniano (CH) - Dado um grafo não-orientado G=(V,A). Pergunta-se se este grafo G possui um caminho Hamiltoniano (isto é um caminho que começa em algum vértice, e passa exatamente uma vez em cada vértice do grafo, terminando em algum outro vértice qualquer).
    
    Árvore Geradora com restrição de Grau (AGG) - Dado um grafo não-orientado G=(V,A) e uma constante K.
    
    Pergunta-se se este grafo G possui uma árvore geradora (uma árvore que conecta todos os vértices do grafo) cujo grau (na árvore) em nenhum dos vértices seja superior a K.
    
    (Dica: Siga os passos para provar que um problema é NP-completo. Prove que (AGG) pertence a NP e em seguida use (CH) para mostrar que todos os problemas em NP se transformam em (AGG). Na transformação você deve mostrar que a resposta sim para o problema (CH) acontece se e somente se acontece a resposta sim na instância obtida pela transformação do problema (AGG). Não esqueça de explicitar as complexidades dos algoritmos de verificação e de transformação).
    
    
14. Seja G=(V,E) um grafo não-orientado. Considere a seguinte função que leva um subconjunto S de V em um valor real: f(S) = |S| - 2 |E(S)|, onde E(S) é o conjunto das arestas de G=(V,E) que tem as duas extremidades em S. Podemos agora enunciar o problema: Conjunto Independente Máximo (MAXSS) - Dado um grafo não-orientado G=(V,E). Encontrar S^* tal que " S Í V,
    f(S^*) ³ f(S), onde f(S) = |S| - 2 |E(S)|.
    
    Algoritmo Constroi I
    • Passo 0: Inicialização
      
      S ¬ Ø
      
      
    • Passo 1: Iteração
      • Para v=1 até |V| e v Î V - S faça
        • Se f(S È { v }) > f(S) entao
          
          S ¬ S È { v };
        
        
    
    Algoritmo Constroi II
    • Passo 0: Inicialização
      
      S ¬ Ø
      
      
    • Passo 1: Iteração
      • mingrau = |V|; v_min = -1
      • Para v=1 até |V| e v Î V - S faça
        • Se grau( v ) < mingrau entao
          
          mingrau = grau(v); v_min = v ;
        
        
      
      
    • Passo 2: Atualização
      • Se v_min ¹ -1 e f(S È { v_min }) > f(S) entao
        
        S ¬ S È { v_min}; Volte ao Passo 1;
      
      
    
    
    1. Escreva um algoritmo que enumere todos os subconjuntos S de V e encontre S^*. Analise sua complexidade.
    2. Escreva um algoritmo que enumere todos os subconjuntos S de V que não possuem arestas ligando dois dos seus elementos, e encontre S^*. Analise sua complexidade.
    3. Analise a complexidade do algoritmos I e II acima.
    4. Aplique os 4 algoritmos acima no grafo G=(V,E) onde V={ 1, 2, 3, 4, 5, 6, 7, 8 } e E={ (1,2), (1,3), (1,4), (2,4), (2,5), (2,7), (3,4), (3,6), (4,6), (4,8), (5,6), (5,7) }.
    5. Explicite no algoritmo I o cálculo do valor da função f(S). Descreva as estruturas de dados utilizadas e analise a complexidade do algoritmo resultante. Repita a análise para o algoritmo II.
    6. Seria interessante o algoritmo I gerar soluções tomando decisões aleatorizadas ? Como isso seria feito ? E para o algoritmo II ?
    7. O que é busca local ? Proponha um algoritmo de busca local para melhorar a solução S obtida pelos algoritmos I e II. Analise sua complexidade e aplique nas soluções obtidas para o grafo acima.
    8. Compare as soluções obtidas pelos algoritmos enumerativos e os algoritmos I e II.
    
    
15. Seja o Problema do Caixeiro Viajante(TSP):
    
    (TSP): Dado um grafo completo G=(V, E), custos c(i,j) ³ 0 associadas às arestas (i,j) em E. Deseja-se encontrar uma sequência de visitação dos vértices de G iniciando e terminando em um mesmo vértice (1), e passando exatamente uma vez por todos os demais vértices onde a soma dos custos das arestas usadas na visitação seja mínima.
    
    Seja Z^* o custo de uma visitação de custo mínimo.
    
    
    1. O custo da árvore geradora de G é maior, menor ou igual a Z^* ?
    2. Dado que um conjunto de arestas E1 tem que ser todo usado na visitação e que um conjunto de arestas E0 não pode ser usado, sugira uma forma de estimar o menor custo que essa visitação pode ter.
    3. O custo da visitação 1 ® 2 ® ... ® n ® 1 é maior, menor ou igual a Z^* ?
    
    
16. Seja o Problema da Árvore Geradora com Restrições de Capacidade:
    
    (CAP-MST): Dado um grafo G=(V È { r }, E), custos c(i,j) ³ 0 associadas às arestas (i,j) em E, demandas q(v) associados aos vértices v em V, e uma capacidade Q. Deseja-se encontrar uma árvore geradora de G, cujas sub-árvores enraizadas no vértice r possuam a soma das demandas dos seus vértices inferiores ou iguais à Q, cujo custo total de suas arestas seja mínimo. Considere a seguinte estrutura de dados para representar uma solução:
    
    
    • Un vetor com n=|V| posições que indica em que árvore o vértice v está. Isto é, A[v]=k significa que o vértice v está na árvore k.
    
    
    1. Escreva um algoritmo para determinar se uma solução representada por um vetor A é viável. Analise sua complexidade.
    2. Escreva um algoritmo para determinar o valor da solução representada por A. Analise a sua complexidade.
    3. Considere que um vértice pode pertencer à n árvores diferentes, logo A[v] Î {1, ..., n } para v=1, ..., n. Supondo que uma vizinhança de uma solução arbitrária A é definida como todas as soluções em que somente um vértice troca de árvore, investigar a vizinhança de A é equivalente à avaliar o valor da solução representada por A onde modifica-se somente o valor do elemento A[v] onde este assume os valores k=1, ..., n, k ¹ v, para v=1, ..., n.
       1. Qual é a complexidade do algoritmo para encontrar a solução vizinha de menor valor, caso seja calculada o valor da solução de casa solução vizinha ?
       2. Esta complexidade pode ser reduzida ? No caso afirmativo, proponha um algoritmo com complexidade menor.

This document was translated from L^AT_EX by H^EV^EA.