Introdução

A cadeira é perfeitamente acompanhável recorrendo apenas às aulas teóricas (cujos slides podem ser encontrados na página da UC), notas do professor, coletânea de exercícios e a estes resumos. Contudo, e segundo o professor Fragoso, alunos que queiram aprofundar conhecimento podem (e devem) fazê-lo recorrendo a alguns livros indicados na bibliografia:

• Introduction to Algorithms, de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein (MIT Press)

• Algorithms, de S. Dasgupta, C. Papadimitriou e U. Vazirani, McGraw-Hill

Cálculo dos Números de Fibonacci

Um dos exemplos clássicos de algoritmos introdutórios é o cálculo de números de Fibonacci - por um lado por ser relativamente fácil de compreender, e por outro por ser igualmente fácil melhorá-lo (em relação à sua complexidade temporal).

Sabemos, claro, que para calcular o $n$-ésimo elemento da sequência de Fibonacci, temos:

Implementação 1 (Naïve)

A implementação naïve numa linguagem de programação (e.g C++, como abaixo), passaria por algo como:

int Fib(int n) {
  if (n <= 1) {
    return n;
  }
  return Fib(n - 1) + Fib(n - 2);
}

Esta implementação tem, contudo, um problema - apesar de ser fácil de escrever, é extremamente ineficiente, podendo calcular números mais do que uma vez. Este problema até pode não parecer fazer grande diferença ao calcular números de Fibonacci pequenos, mas quando se pretender calcular, por exemplo, $Fib(400)$, a tarefa tornar-se-á profundamente mais desagradável.

Abaixo podemos observar a árvore dos subproblemas de uma chamada $Fib(4)$, onde os dois filhos de um nó são as duas chamadas recursivas realizadas nesse nó. Podemos ver que, mesmo considerando um problema "pequeno", calculamos o mesmo valor várias vezes.

Podemos, para avaliar melhor a complexidade temporal desta solução, definir uma função $T(n)$ - uma função que, neste caso, corresponderá a "quanto tempo" (vulgo quantidade de operações) é necessário para calcular um dado $Fib(n)$.

Ora, olhando para o corpo da função, podemos admitir que:

O ramo de cima corresponde aos casos base - há um número constante, $c_0$, de operações a realizar caso estejamos na presença do caso base.
O ramo de baixo ocorre quando os casos base não se verifiquem - terá de ocorrer uma chamada recursiva a $Fib(n-1)$ e a $Fib(n-2)$ (tendo, portanto, de adicionar o "tempo" que essas 2 chamadas levarem), e temos também um número constante de operações requeridas (e.g if's, somas): $c_1$.
Temos que $c_0, c_1 \geq 2$.

Podemos, ainda, provar que $T(n) > fibo(n)$ (a função matemática, não a nossa implementação da mesma):

Podemos, ainda, referir que:

provado nas notas do professor (no fim desta página).

Implementação 2 (Memoization e Programação Dinâmica)

Ora, o nosso objetivo, para tornar o algoritmo mais eficiente, passará então por arranjar uma maneira de ir guardando os números já calculados, de modo a não ter de os calcular novamente. Uma das técnicas que nos pode ajudar a fazê-lo é a memoization.

Em C++, a aplicação da memoization ao cálculo de um número de Fibonacci passaria por qualquer coisa como:

int Fib(int n) {
  if (n <= 1) return n;
  else {
    std::vector<int> table = std::vector<int>(n + 1);
    table[0] = 0;
    table[1] = 1;
    return FibAux(n, table);
  }
}

int FibAux(int n, std::vector<int> &v) {
  if (n < v.size()) return v[n];

  int fibNum = FibAux(n - 1, table) + FibAux(n - 2, table);
  table[n] = fibNum;
  return fibNum;
}

Podemos ainda ter uma implementação em programação dinâmica normal, com a diferença de na memoization se passar necessariamente a tabela como argumento.

int Fib(int n) {
  if (n <= 1) {
    return n;
  }
  // vetor inicializado com n + 1 elementos -> de 0 a n
  std::vector<int> A(n + 1);
  A[0] = 0;
  A[1] = 1;
  for (int i = 2; i <= n; i++) {
    A[i] = A[i - 1] + A[i - 2];
  }
  return A[n];
}

Foi, então, inicializado um vetor de $n + 1$ elementos, onde os primeiros dois elementos correspondem aos casos base. A partir daí, podemos ir juntando novos valores ao vetor, partindo de valores previamente calculados, evitando cálculos desnecessários - aqui, cada número de Fibonacci é calculado apenas uma vez.

Em relação a esta implementação, temos:

O ramo de cima é igual ao da implementação anterior. O de baixo, contudo, é bastante diferente - não estamos dependentes de chamadas recursivas. Temos uma componente $c_1 \cdot n$, correspondente às operações realizadas durante o loop principal, e uma $c_2$ correspondente às outras operações da função, todas realizadas em tempo constante.

Esta implementação tem, ainda, um pormenor que pode ser melhorado - a complexidade no espaço é linear ($S(n) \in O(n)$), já que precisamos de criar um vetor com $n$ entradas. Podemos, no entanto, melhorar este aspeto.

Implementação 3 (Constantes Auxiliares)

O algoritmo seguinte é bastante semelhante ao anterior, recorrendo, no entanto, a constantes auxiliares temporárias ao invés de uma estrutura de dados adicional. Evita, na mesma, os cálculos repetidos desnecessários, mas sem o "incómodo" da complexidade no espaço ser linear - é $O(1)$.
Em C++, corresponderia a qualquer coisa como:

int Fib(int n) {
  if (n <= 1) {
    return n;
  }
  int prev = 0;
  int curr = 1;
  int temp;
  for (int i = 2; i <= n; i++) {
    temp = prev + curr;
    prev = curr;
    curr = temp;
  }
  return curr;
}

De realçar que a complexidade temporal continua igual à anterior, $T(n) \in O(n)$.

Invariante de um Loop

Resta, por fim, definir o invariante de um loop, noção que nos vai acompanhar durante o decorrer da cadeira.

Dito assim pode parecer estranho, por isso podemos olhar para o seguinte algoritmo:

int sumArray(std::vector<int> arr) {
  int sum = 0;
  for (int i = 0; i < arr.size(); i++) {
    sum += arr[i];
  }
  return sum;
}

Aqui, temos que, em qualquer momento do loop, a variável sum é dada por:

onde i é a variável do ciclo que vai sendo incrementada. Podemos verificar, a qualquer momento do loop, que sum corresponde, de facto, ao valor daquele somatório.

• Notas da Aula - Prof. José Fragoso