1. 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.
   
   
2. 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
   
   
3. Prove por indução e dê o algoritmo recursivo que resulta da sua prova.
   
   Teorema: Todos os vértices de uma qualquer árvore podem ser coloridos (sem ter vértices adjacentes com uma mesma cor) com duas cores. Uma árvore é um grafo não orientado G=(V,E) sem ciclos, conexo, e onde |E|=|V|-1.
   
   Dicas: use indução simples nos vértices e observe que qualquer árvore pode ser construída a partir de um vértice sozinho, com a inserção sucessiva de um vértice conectado a uma aresta.
   
   Você deve escrever o algoritmo para colorir uma árvore qualquer com duas cores.
   
   
4. Seja G=(V,E) um grafo orientado e acíclico, então existe uma renumeração dos seus vértices tal que todos os vértices que podem ser atingidos a partir de um vértice v, v Î V, estão renumerados com valores superiores a v.
   
   Prove por indução o teorema abaixo e dê o algoritmo recursivo que resulta da sua prova.
   
   Teorema: Todo grafo conexo e acíclico possui pelo menos um vértice com grau de entrada (número de arcos que chegam em um vértice) igual a ZERO.
   
   Dicas: use indução simples nos vértices. Utilize n=2 como caso base e mostre que o teorema vale para esta caso por exaustão.
   
   Você deve escrever um algoritmo que encontre uma renumeração dos vértices que satisfaça a propriedade descrita no início da questão. A entrada do algoritmo é um grafo, i.e. um conjunto de vértices e um conjunto de arcos. A saída é a renumeração dos vértices, i.e. por exemplo: os vértices 1, 2, 3, 4 e 5 devem ser renumerados como 2, 4, 1, 5, 3.
   
   
5. Seja G=(V,E) um grafo não-orientado. Deseja-se decidir se G é um grafo bi-partido ou não.
   
   Um grafo é bi-partido se existe uma partição de V, V₁ e V₂ (V₁ Ç V₂ = Ø , V₁ È V₂ = V) tal que " (u,v)Î E, tem-se que u Î V₁ e v Î V₂ ou vice-versa. Isto é, não existe aresta entre vértices de V₁ ou V₂.
   
   Caso G seja bi-partido, deseja-se obter a partição V₁ e V₂ de V.
   
   Elabore o caso base e a hipótese indutiva para a prova, por indução, de que sabe-se encontrar um tal conjunto. Descreva o algoritmo resultante de sua prova.
   
   
6. Logo após uma operação de sucesso dois ladrões decidem se separar. Entretanto, o resultado da operação foi um conjunto de objetos indivisíveis (de alta liquidez) cujos valores de mercado são bem estabelecidos e conhecidos pelos ladrões (de alto nível, é claro), o que dificulta a partilha. O problema dos ladrões é dividir entre eles o conjunto de objetos roubados de modo que a diferença entre o valor total que cada um vai ficar seja a menor possível. Sabendo que são n objetos e que seus valores são v₁, v₂, ..., v_n, responda aos itens abaixo.
   
   
   1. Utilizando indução matemática (com reforço de hipótese), mostre como pode-se construir uma divisão dos objetos que tenha diferença de valor a menor possível.
   2. Descreva, de forma compacta, o algoritmo resultante.
   3. Mostre como o seu algoritmo funciona caso sejam 5 objetos com os seguintes valores: v₁ = 5, v₂ = 4, v₃ = 7, v₄ = 3, v₅ = 17.
   4. 
      Dica: Reforce a hipótese de modo que as divisões dos objetos sejam conhecidas para cada valor total atribuído a cada ladrão.
      
      
      Suponha que antes de chegar ao local da partilha os ladrões tiveram que carregar os objetos. Assuma que os pesos dos objetos são p₁, p₂, ..., p_n e que os ladrões possuem juntos uma mochila que resiste ao peso máximo de P.
   5. Utilize indução matemática (com reforço de hipótese) para projetar um algoritmo que encontra o maior valor total, em objetos, que os ladrões podem carregar na mochila (represente por V(k) este valor para os objetos 1,2,...,k; reforce a hipótese assumindo que este valor pode ser calculado, dado que o peso total dos objetos na mochila é exatamente q, para todos os pesos possíveis; represente por V(k,q) este valor).
   6. Mostre como o seu algoritmo funciona caso sejam 5 objetos com os valores: v₁ = 5, v₂ = 4, v₃ = 7, v₄ = 3, v₅ = 10 e os respectivos pesos p₁ = 5, p₂ = 3, p₃ = 6, p₄ = 4, p₅ = 7 onde o peso máximo suportado pela mochila é 9.
   7. Como você resolveria esse problema se os ladrões tivessem duas mochilas ?
   
   
7. Sejam duas sequências de inteiros distintos T = { t₁, ..., t_n } e Q = { q₁, ..., q_m }.
   
   
   1. Utilize indução matemática (com reforço de hipótese) para propor um algoritmo que obtenha a maior subsequência (não necessariamente consecutiva) comum às duas sequências (T e Q).
      1. Qual é o reforço de hipótese utilizado ?
      2. Explique a recursão resultante (i.e., o algoritmo):
         custo(i,j) = max { custo(i-1,j), custo(i,j-1), custo(i-1, j-1) + d }
         onde d vale 1 se t_i = q_j e 0 caso contrário.
      3. Qual o valor dos custos: custo(0,0), custo(i,0) para i=1,...,n e custo(0,j) para j=1,...,m ?
      
      
   2. Considere que para cada par de elementos de T e Q, t_i e q_j é associado um custo positivo c_ij, i=1,...,n, j=1,...,m. Proponha um algoritmo para encontrar a subsequência comum onde a soma dos custos dos elementos é maximizada.
      1. O que muda na recursão resultante ? Apresente a nova recursão resultante.
      
      
   3. Mostre como os algoritmos obtidos acima funcionam nas sequências:
      3, 7, 9, 2, 3, 6, 2, 8
      e
      3, 5, 8, 7, 9, 2, 3, 6, 7
      Execute o algoritmo do item (b) com os custos c_ij=i + j.
   
   
8. 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 vértice 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).
      
      Represente a árvore determinando para cada vértice o seu vértice pai (p(v) é o pai de v).
      
      
   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.
   
   
9. Considere o seguinte jogo: Dada um sequência de n (n é par) cartas enfileiradas com valores positivos e inteiros v₁, v₂, ..., v_n abertos (conhecidos). Dois jogadores J1 e J2 alternam a vez de jogar. Uma jogada consiste em pegar uma carta de uma das pontas (a carta 1 ou a n no início, a 2 ou a n se o primeiro a jogar pegou a carta 1, ou 1 ou a n-1 se ele pegou a carta n). Vence aquele cuja soma dos valores das cartas que pegou for maior.
   1. Apresente uma sequência de cartas onde o primeiro jogador não pegar o maior valor possível se ele escolhe a carta de maior valor na primeira jogada. (Ou seja, mostre que a estratégia gulosa não funciona para este problema.)
   2. Proponha um algoritmo que calcule a estratégia ótima para o primeiro jogador. Uma estratégia ótima é a informação necessária para que o jogador 1 determine cada uma das suas jogadas de modo a obter, no final, o maior valor possível.

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