1. 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. Mostre que esse algoritmo pode ser obtido por indução matemática e explique qual o reforço da hipótese indutiva que permite provar o passo indutivo que leva ao algoritmo.
   
   
2. Considere o problema de encontrar a sub-árvore de uma árvore enraizada no vértice r cujo peso é máximo. A sub-árvore também deverá ser enraizada em r. O problema é definido da seguinte forma: dada uma árvore (é um grafo não-orientado, é claro) T=(V,E), um 'vertice raiz r Î V e pesos w_v associados aos vértices de V, determinar uma árvore T^*=(V^*, E^*), contida em T onde r Î V^* e a soma å_{v Î V^*} w_v é máxima. A árvore vazia vale zero(0) e, naturalmente, os valores dos pesos podem ser positivos ou negativos. Responda:
   1. Use reforço de hipótese para propor um algoritmo que obtenha uma sub-árvore de peso máximo (nesse caso, o reforço é supor que conhece-se a sub-árvore de peso máximo com raiz em cada um dos vértices filhos, e indução prova que se é verdade para os filhos então é verdade para os pais).
   2. Execute o seu algoritmo sobre a seguinte instância: r=1, V={1,..., 12}, E={ (1,2), (1,3), (2,4), (2,5), (2,6), (3,7), (3,8), (5,9), (5,10), (8,11), (8,12)}, w₁ = -2, w₂ = -1, w₃ = -1, w₄ = 4, w₅ = -6, w₆ = -1, w₇ = -1, w₈ = 1, w₉ = 2, w₁₀ = 3, w₁₁ = -2 e w₁₂ = 3.
   
   
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. Explique que reforço da hipótese indutiva deve ser utilizado para se obter um algoritmo eficiente para este cálculo.
   3. Mostre como fica a prova do passo indutivo e sua relação com o algoritmo proposto.
   4. 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. Seja uma sequência de n inteiros distintos T = { t₁, ..., t_n }.
   
   
   1. Utilize indução matemática (com reforço de hipótese) para propor um algoritmo que obenha a maior subsequência crescente (não necessariamente consecutiva).
      
      
   2. Mostre como os algoritmos obtidos acima funcionam na sequência:
      3, 17, 9, 12, 35, 6, 27, 8, 21, 26, 23, 11, 19, 13, 15

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