Construcao e Analise de Algoritmos - Teste 9
--------------------------------------------

   Considere um vetor A[1..n] representando uma sequencia de 
  numeros reais positivos: <a1, a2, ..., an>. 

   O problema consiste em dividir a sequencia em particoes A1,...,Ak,
  onde cada particao Ai e' uma subsequencia do tipo A[i,j], ou seja,
  cada Ai e' uma subsequencia contigua de A.

   A ideia e' que as particoes sejam aproximadamente equilibradas, de modo 
  que nao exista uma particao com varios elementos grandes e outra apenas 
  com elementos pequenos. Por exemplo, se a sequencia A e' dada por  

             A = < 8, 10, 5, 17, 150 > 

  entao a particao  A1=<8,10>  A2=<5,17>  A3 = <150>
  e' mais equilibrada que  A1=<8>  A2=<10,5>  A3=<17,150>

   Esta ideia e' formalizada pela definicao de que uma particao 
  e' equilibrada se ela minimiza a expressao:

           Soma_i   Prod_{aj em Ai} aj

  ou seja, a soma para todas as particoes do produto dos seus
  elementos. 

   Por exemplo, para a primeira particao acima a expressao tem
  valor 80 + 85 + 150 = 315, enquanto que para a segunda particao
  a expressao assume valor 8 + 50 + 2550 = 2608.

  a) Mostre que, se todos os elementos de A sao maiores do que 1, entao a 
    unica solucao otima e' aquela que coloca apenas um elemento em cada 
    particao.

  b) Apresente um contra-exemplo mostrando que a afirmacao do item (a) nao 
    e' verdadeira quando existem elementos menores do que 1 na sequencia A.

  c) Descreva um algoritmo que encontre uma particao otima para 
    este problema.

  d) Determine a complexidade do seu algoritmo.

   Considere agora a definicao que requer que uma particao 
  equilibrada minimize a expressao:

           Max_i   Prod_{aj em Ai} aj

  ou seja, o maximo entre todas as particoes do produto dos seus
  elementos. 

  Repita os itens (c) e (d) acima, e faca o item a seguir.

  e) Escolha apenas uma das alternativas abaixo e repita o
    exercicio do item (c).

    e1) Suponha que a sequencia A deve ser dividida em exatamente k particoes.

    e2) Suponha que o algoritmo deve encontrar uma particao que 
       minimize a expressao   

           K*C  +  Max_i   Prod_{aj em Ai} aj

       onde K e' o numero de particoes utilizadas e C e' o custo
       de cada particao.

        A ideia neste caso, e' incluir um custo adicional por
       particao de modo que o numero total de particoes seja reduzido.