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 o problema de Fluxo Máximo e os algoritmos Edmonds-Karp e Push-Relabel. Execute estes algoritmos nas instâncias abaixo:
   1. Fluxo do vértice s para o vértice t. Conjunto de vértices V={ s, 1, 2, ..., n, t } e conjunto de arcos E= { (s,1, (n+1)*k), (1,2, n*k), ..., (i,i+1, (n-i+1)*k), ..., (n-1,n, 2*k), (n,t,k) } onde (i,j,c) no conjunto corresponde ao arco (i,j) com capacidade c; Resolva para n=2 e n=3. Qual a complexidade desses algoritmos para este tipo de grafo em função de n ? Mostre que não depende de k.
      
      
   2. Fluxo do vértice s para o vértice t. Conjunto de vértices V={ s, 1, 2, ..., n, t } e conjunto de arcos E= { (s,1, k), (s,2, k), ..., (s,i, k), ..., (s,n, k), (1,t,k), (2,t,k), ..., (i,t, k), ..., (n, t, k) } onde (i,j,c) no conjunto corresponde ao arco (i,j) com capacidade c; Resolva para n=2 e n=3. Qual a complexidade desses algoritmos para este tipo de grafo em função de n ? Mostre que não depende de k.
   
   
3. 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 ?
   
   
4. 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.

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