MAC5711  Análise de Algoritmos

Tarefa 1

Correndo contra o relógio

I make mistakes. I always have, and I probably always will. But I like
to think that I learn something, every time I go astray.

D.E. Knuth
"Literate Programming"

Para irmos aquecendo os motores. Esta primeira tarefa é um exercício simples, tipicamente dado aos alunos do primeiro ano de cursos de Ciência da Computação.

Problema do Segmento de Soma Máxima

Escreva um programa que resolva o seguinte problema: dada uma seqüência de n números inteiros x0 x1,..., xn-1, encontre índices l,r, com l <= r, tais que a soma
xl + xl+1 +...+ xr
seja máxima. Por exemplo, dada a seqüência

1, -3, 6, -4, 2, -5, 1, 8, -4, 2, 3, -1, 2, -3, 1, 3, -5, 3 , -3, 4,

seu programa deve devolver os índices 6 e 15, pois o segmento

1, 8, -4, 2, 3, -1, 2, -3, 1, 3

tem soma igual a 1+8-4+2+3-1+2-3+1+3 = 12, que é máxima.
[Hmmmmm, é máxima mesmo?!?]

Correndo contra o relógio

Para tornar o desafio de fazer seu programa mais interessante, será fornecido a você um programa executável que, além de resolver o problema acima, imprime o tempo gasto (em segundos).

Você pode, em C, cronometrar o tempo de execução do seu programa da seguinte maneira: 


   clock_t t0, tf;
   double tempo_gasto;

   ...
   /* Leitura de dados */
   ...
   t0 = clock();
   ...
   /* ache um segmento de soma máxima */
   ...
   tf = clock();
   tempo_gasto = ( (double) (tf - t0) ) / CLOCKS_PER_SEC;
   ...
   printf("Tempo gasto: %lf s\n", tempo_gasto);

O tipo clock_t e a constante CLOCKS_PER_SEC já estão definidos na biblioteca time.h.

Desse modo, você pode comparar o desempenho do seu programa com o que vamos fornecer. A eficiência do seu programa NÃO será levada em conta na nota. Apesar disto, tente fazer algo além do trivial.

Entrada e saída

O seu programa deve ler a seqüência de números a partir de um arquivo cujo nome é fornecido pelo usuário através da linha de comando. O arquivo é binário, e na primeira posição contém o número de elementos da seqüência e depois a seqüência propriamente dita:

n x0 x1 x2 x3 x4 ... xn-3 xn-2 xn-1.

Consertei os links para gera.c e para os arquivos de dados.

A propósito, devido as diferentes arquiteturas de memória das máquinas.

Para gerar os dados você pode usar o programa gera.c, mas sugiro que antes você teste seu programa com arquivos textos de seqüências pequenas de números.

O programa deve aceitar valores de n entre 1 e 10000000 (10 milhões ... arquivos de 40Mb ... é pouco ? é muito ?). Para a leitura de arquivos binários você pode usar as funções fopen e fread disponíveis na biblioteca de funções do C (veja a utilização dessas funções no programa gera.c e no exemplo abaixo).

Como saída, seu programa deve imprimir:

  1. o número de elementos lidos, isto é, o tamanho da seqüência;
  2. o início e o final de um segmento de soma máxima que seu programa encontrou;
  3. a soma dos elementos do segmento de soma máxima encontrado;

Esqueleto do programa

Com a leitura e cronometragem de tempo o seu programa pode ser algo do tipo: 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>


/*#define MAX 10000000 */


int 
main(int argc, char *argv[])
{
  FILE *fp;
  /* int sequencia[MAX], n=0; É melhor fazer como está abaixo */
  int *sequencbia;
  int n;
  int l, r, soma;
  clock_t start, end;
  double elapsed;


  if (argc < 2) 
    {
      fprintf(stdout," \n%s: este programa recebe uma"
              " sequencia de n numeros" 
	      " inteiros\n"
	      "   x[1], x[2], x[3], ... , x[n-1], x[n],\n"
	      " e devolve l e r tais que a soma\n"
	      "   x[l] + x[l+1] + ... + x[r-1] + x[r]\n"
	      " seja maxima.\n\n"
	      " Uso: segmax .\n\n"
	      " O arquivo deve ser binario e ter formato\n"
	      "   n x[1] x[2] ... x[n-1] x[n]\n"
	      " onde n >= 1.\n\n",  argv[0]);
      return -1;
    }

  if (!(fp = fopen(argv[1],"rb"))) 
    {
      fprintf(stderr,"%s: erro na abertura do"
                     " arquivo %s.\n", argv[0], argv[1]);
      return -2;
    }

  /* leitura do tamanho da sequencia */
  if (!(fread(&n, sizeof(int), 1, fp))) 
    {
      fprintf(stderr,"%s: erro na leitura do"
                     " arquivo %s.\n", argv[0], argv[1]);
      return -3;
    }

  if (n <= 0) 
    {
      fprintf(stderr,"%s: valor de n nao permitido.\n", argv[0]);
      return -4;
    }

  /* aloca um vetor de n posicoes */
  if ((sequencia = (int *) malloc(n * sizeof(int))) == NULL)
    {
      fprintf(stderr,"%s: espaco insuficiente.\n", argv[0]);
      return -5;
    }
      
  /* leitura de sequencia */
  if (fread(sequencia, sizeof(int), n, fp) < n) 
    {
      fprintf(stderr,"%s: arquivo %s nao esta"
                     " completo.\n", argv[0], argv[1]);
      return -6;
    }
  fclose(fp);
  
  
  start = clock();

  /* ENCONTRAR O SEGMENTO DE SOMA MAXIMA */
  [...]  
    
  end = clock();
  elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
  
  fprintf(stdout," O arquivo de entrada \"%s\" contem %d numeros.\n"
	  " Foi encontrada uma subsequencia de soma maxima com\n"
	  " Inicio: %d\n"
	  "  Final: %d\n"
	  "   Soma: %d\n"
	  "  Tempo: %f s\n\n", argv[1], n, l, r, soma, elapsed);
  
  return 0;
}

Exemplos de execução do programa

A saída do programa, tendo como entrada o arquivo de dados seq1.dat, pode ser algo como 
jaca:/home/mac/coelho> segmax seq1.dat
 O arquivo de entrada "seq1.dat" contem 100 numeros.
 Foi encontrada uma subsequencia de soma maxima com
 Inicio: 30
  Final: 56
   Soma: 3916
  Tempo: 0.000000 s
e com o arquivo seq2.dat pode ser algo como 
kama:/home/mac/coelho> segmax seq2.dat
 O arquivo de entrada "seq2.dat" contem 10000000 numeros.
 Foi encontrada uma subsequencia de soma maxima com
 Inicio: 7050879
  Final: 8425274
   Soma: 1717434
  Tempo: 0.100000 s (nao incluido tempo com leitura)
Teste seu programa com os arquivos de dados seq1.dat e seq2.dat. Mas antes teste com arquivos menores (arquivos textos de preferência).

Executável do programa

O programa segmax resolve o problema acima. Compare os resultados obtidos com o resultado do segmax.

Entrega, prazos e observações