PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2008.1
7 de junho de 2008
Horário: 2as-feiras e 4as-feiras de 9 às 11 horas
ANÁLISE DE ALGORITMOS (INF 1721)
3a Lista de Exercícios
  1. Exercícios Livro Algorithms, Dasgupta, Papadimitriou e Vazirani.
  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 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 ?

  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 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.

This document was translated from LATEX by HEVEA.