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 nn-ésimo elemento da sequência de Fibonacci, temos:

Fib(n)={0 se n=01 se n=1Fib(n1)+Fib(n2) caso contraˊrioFib(n)=\begin{cases} 0 &\text{ se } n = 0 \\ 1 &\text{ se } n = 1 \\ Fib(n-1) + Fib(n-2) &\text{ caso contrário} \end{cases}

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)Fib(400), a tarefa tornar-se-á profundamente mais desagradável.

Abaixo podemos observar a árvore dos subproblemas de uma chamada Fib(4)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)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)Fib(n).

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

T(n)={c0se x==0 ou x==1T(n1)+T(n2)+c1caso contraˊrioT(n)=\begin{cases} c_0 &\text{se } x == 0 \text{ ou } x == 1 \\ T(n - 1) + T(n - 2) + c_1 &\text{caso contrário} \end{cases}

O ramo de cima corresponde aos casos base - há um número constante, c0c_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(n1)Fib(n-1) e a Fib(n2)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): c1c_1.
Temos que c0,c12c_0, c_1 \geq 2.

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

Prova por indução forte

(Já agora, a diferença entre as induções simples e forte).

Casos Base:

  • n=0:T(0)>fibo(0)c0>0n = 0: \quad T(0) > fibo(0) \leftrightarrow c_0 > 0 - acontece sempre, já que c0>=2c_0 >= 2.
  • n=1:T(1)>fibo(1)c0>1n = 1: \quad T(1) > fibo(1) \leftrightarrow c_0 > 1 - acontece sempre, pela mesma razão.

Caso indutivo:

  • A provar: T(n+1)>fibo(n+1)T(n+1) > fibo(n+1)
  • Assumimos: 0kn,T(k)fibo(k)\forall_{0 \leq k \leq n}, T(k) \geq fibo(k), a nossa hipótese de indução.
  • Prova:
    T(n+1)=T(n)+T(n1)+c1, pela definic¸a˜o de T(n)T(n+1)>fibo(n)+fibo(n1)+c1, pela hipoˊtese de induc¸a˜oT(n+1)=fibo(n+1)+c1, pela definic¸a˜o de fibo(n)T(n+1)>fibo(n+1), jaˊ que c12\begin{split} &T(n + 1) = T(n) + T(n - 1) + c_1 \text{, pela definição de }T(n) \\ &T(n + 1) > fibo(n) + fibo(n - 1) + c_1 \text{, pela hipótese de indução} \\ &T(n + 1) = fibo(n + 1) + c_1 \text{, pela definição de }fibo(n) \\ &T(n + 1) > fibo(n + 1) \text{, já que }c_1 \geq 2 \end{split}

Fica, então, provado que T(n)>fibo(n)T(n) > fibo(n).

Podemos, ainda, referir que:

n11 fibo(n)(32)n\forall_{n \geq 11} \text{ } fibo(n) \geq \left(\frac{3}{2}\right)^n

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.

Memoization

Técnica que garante que um método não calcula os mesmos valores mais do que uma vez, guardando os valores já calculados numa estrutura de dados (por ex. um mapa, um vetor, etc), funcionando como uma cache.

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+1n + 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:

T(n)={c0se x1c1n+c2caso contraˊrioT(n)=\begin{cases} c_0 &\text{se } x \leq 1\\ c_1 \cdot n + c_2 &\text{caso contrário} \end{cases}

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 c1nc_1 \cdot n, correspondente às operações realizadas durante o loop principal, e uma c2c_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)O(n)S(n) \in O(n)), já que precisamos de criar um vetor com nn 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)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)O(n)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.

Invariante de um Loop

Corresponde a uma propriedade que o algoritmo mantém durante todo o loop. Colapsa no final do loop.

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:

sum=k=0i1arr[k]\operatorname{sum} = \sum^{i - 1}_{k = 0}\operatorname{arr} [k]

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.