PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2006.1
20 de junho de 2006
Horário: 2as-feiras e 4as-feiras de 19 às 21 horas
PROJETO E ANÁLISE DE ALGORITMOS (INF 1309)
3a Lista de Exercícios
  1. 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 ?

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

  3. Sejam T = { t1, ..., tn } e P = { p1, ..., pk } 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 ci, 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 ?


This document was translated from LATEX by HEVEA.