quinta-feira, 28 de junho de 2012

Torres de Hanói

Agora, vamos resolver indutivamente o problema das Torres de Hanói. Muita gente conhece o jogo, mas não sabe como resolvê-lo computacionalmente. As regras são as seguintes:
  1. Devemos mover um disco de cada vez.
  2. Um disco maior não pode ser colocado sobre um disco menor.
Usando indução, a solução computacional para o problema é quase trivial.
Idéia indutiva:
  • Caso Base: para zero disco, o problema já está resolvido.
  • Hipótese de Indução: vamos supor que o problema pode ser resolvido para n - 1 elementos. Esse truque libera o disco da base (maior disco).
  • Caso Geral: basta invocar a hipótese de indução para mover os n- 1 discos e liberar o disco maior, e em seguida, invocamos a H.I. novamente para mover os n - 1 discos para o destino.
Para esclarecer, vamos analisar um exemplo:

Situação inicial: todos os discos estão em A.


Hipótese de indução 1: vamos supor que os n - 1 discos iniciais serão movidos para o pino C.


Caso trivial: agora ficou fácil mover o disco maior para o destino, ou seja, para o pino B.

Hipótese de indução 2: agora vamos supor que os n - 1 discos que estão em C serão movidos para B.


E assim, chegamos a solução do problema!!!

As implementações decorrem da idéia apresentada acima.
  • Implementação em Python
def hanoi(n, A, B, C):
  if n > 0:
    hanoi(n - 1, A, C, B)
    print "Mova o disco " + str(n) + " de " + A + " para " + B
    hanoi(n - 1, C, B, A)
  • Implementação em Java
static void hanoi(int n, char A, char B, char C) {
  if (n > 0) {
    hanoi(n - 1, A, C, B);
    System.out.println("Mova o disco " + n + " de " + A + " para " + B);
    hanoi(n - 1, C, B, A);
  }
}

Complexidade do algoritmo: vamos derivar a relação de recorrência T(n) = 2T(n - 1) + 1.

$T(n) = 2T(n - 1) + 1$
$T(n) = 2(2T(n - 2) + 1) + 1$
$T(n) = 4T(n - 2) + 2 + 1$
$T(n) = 4(2T(n - 3) + 1) + 2 + 1$
$T(n) = 8T(n - 3) + 4 + 2 + 1$
$...$
$T(n) = 2^n + 2^{n - 1} + 2^{n - 2} + ... + 2^2 + 2^1 + 2^0$
$T(n) = 2^n - 1$
$T(n) = O(2^n)$

Podemos concluir que a complexidade do algoritmo é limitada pela função exponencial. Na prática, se o número de discos for muito grande, a obtenção de uma solução torna-se inviável.

terça-feira, 26 de junho de 2012

Altura de Árvores Binárias: uma abordagem indutiva

Agora vamos criar um algoritmo que nos diz a altura de uma árvore binária. A altura de uma árvore binária pode ser definida como:
  • Comprimento do maior caminho que vai da raiz até um nó folha. Onde o comprimento de um caminho é determinado pelo número de arestas que ele possui.
A árvore abaixo possui altura 3.


Para construir nosso algoritmo vamos mais uma vez recorrer a abordagem indutiva.
Idéia indutiva
  • Caso Base: a altura de uma árvore vazia, ou com apenas um nó, é igual a zero.
  • Hipótese de Indução: podemos assumir que já temos as alturas das subárvores esquerda e direita.
  • Caso Geral: a altura da árvore será a maior dentre as alturas encontradas pela hipótese de indução mais 1.

A implementação a seguir decorre da idéia indutiva apresentada acima.

  • Implementação em Python
def height(tree):
  if tree.left == tree.right: return 0   # arvore vazia
  if height(tree.left) > height(tree.right): return height(tree.left) + 1
  return height(tree.right) + 1

  • Implementação em C++
int height(ARVORE *t){
  if(t == NULL || t->esq == t->dir)
    return 0;
  else
    return max(height(t->esq), height(t->dir)) + 1;
}

domingo, 24 de junho de 2012

Palavras Palíndromas


Um palíndromo é uma palavra que pode ser lida tanto da esquerda para a direita como da direta para a esquerda. Por exemplo:

"A man, a plan, a canal, Panama!"
"Anotaram a data da maratona."

Vamos agora dar uma definição indutiva para o problema:
Idéia indutiva
  • Caso Base: uma palavra com 1 caractere é um palíndromo.
  • Hipótese de indução: vamos supor que a palavra sem o primeiro e o último caractere é um palíndromo.
  • Caso Geral: Se o primeiro e o último caractere forem iguais e a hipótese de indução for verdadeira, então a palavra é um palíndromo.
E mais uma vez, se seguirmos a idéia indutiva, o algoritmo surge de forma imediata!

  • Implementação em Haskell
palindromo :: String -> Bool
palindromo [] = True
palindromo [a] = True
palindromo (x:xs) = (x == last xs) && (palindromo elem)
    where
        newlen = (length xs) – 1
        elem = take newlen xs

  • Implementação em C++ (versão iterativa)
bool palindromo(int n, char s[]){

    int i = 0, j = n - 1;
    while(i < j){
         if(s[i] != s[j])
             return false;
         i++;
         j--;
    }
    return true;
}

quinta-feira, 21 de junho de 2012

Definição indutiva de Árvores Binárias

Saber manipular uma estrutura de dados corretamente é imprescindível para qualquer programador. E com árvores binárias não pode ser diferente, principalmente quando nos deparamos com problemas cuja natureza exige uma  estrutura de dados não linear e que permita uma hierarquização dos dados que serão manipulados.
Indutivamente, podemos definir uma árvore binária T como sendo:
  • Uma árvore vazia, ou
  • Um nó especial r, chamado raiz de T, com duas subárvores Te e Td. Onde Te e Td são as subárvores esquerda e direita respectivamente.

Podemos tirar proveito da definição acima na hora de construir algoritmos que manipulam árvores. Para isso, basta assumir que o problema que desejamos resolver, já está resolvido para as subárvores esquerda e direita. Por exemplo, vamos supor que desejamos somar os valores armazenados em todos os vértices de uma árvore binária. Usando indução, a solução é a seguinte:
  • Caso Base: a soma dos nós de uma árvore vazia é zero.
  • Hipótese de Indução: assumimos que já temos a soma de todos os valores armazenados nas subárvores esquerda e direita.
  • Caso Geral: é quase trivial, pois simplesmente somamos o valor armazenado na raiz com os valores que por hipótese de indução são as somas das subárvores esquerda e direita.
A implementação decorre "diretamente" do esquema apresentado acima:

  • Implementação em C++
int somaNos(ARVORE t)
{
  if(t == NULL)
    return 0;
  else
    return t->info + somaNos(t->esq) + somaNos(t->dir); 
}

quarta-feira, 20 de junho de 2012

Insertion-Sort: Uma descrição Indutiva

Agora vamos fazer uma descrição indutiva do algoritmo Insertion-Sort. É importante lembrar que este tipo de abordagem é um pouco diferente dos métodos convencionais que muitos livros utilizam. No entanto, de forma simples e clara resolveremos o problema de ordenação.

Idéia indutiva:
  • Caso Base: é trivial, pois uma lista com apenas um elemento já está ordenada.
  • Hipótese de Indução: vamos assumir que a lista com n- 1 elementos já está ordenada.
  • Caso Geral: agora, basta inserir o último elemento na sequência que, por hipótese de indução, já está ordenada.
Antes de derivar o algoritmo vamos visualizar um exemplo.

Situação inicial: Vetor desordenado


Agora vamos trabalhar com os primeiros n - 1 elementos


Vamos assumir que os n - 1 elementos já estão ordenados


Agora, só precisamos inserir o último elemento na sequência ordenada


E vamos mais uma vez, construir o nosso algoritmo seguindo a idéia indutiva apresentada acima.

  • Implementação em Python (versão recursiva)
def ins_sort_rec(seq, i):
 if i==0: return
 ins_sort_rec(seq, i-1)
 j = i
 while j > 0 and seq[j-1] > seq[j]:
  seq[j-1], seq[j] = seq[j], seq[j-1]
  j -= 1
  • Implementação em Java (versão interativa)
static void insertionSort(int vet[]){
  int i, aux;
  for(int j = 1; j < vet.length; j++){
    i = j - 1;
    aux = vet[j];
    while(i > -1 && vet[i] > aux){
      vet[i+1] = vet[i];
      i--;
    }
    vet[i + 1] = aux;
  }
}

Complexidade do algoritmo
A relação de recorrência que expressa a complexidade de tempo do insertion-sort é: T(n) = T(n - 1) + n.
Essa relação nos diz que o tempo do insertion-sort é igual ao tempo que a hipótese de indução gasta para ordenar os n - 1 elementos, mais o tempo gasto para inserir um elemento na sequência ordenada.
Resolvendo a recorrência temos:

T(n) = T(n - 1) + n
T(n) = T(n - 2) + (n -1) + n
T(n) = T(n - 3) + (n - 2) + (n - 1) + n
...
T(n) = T(1) + 2 + 3 + 4 + 5 + ... + (n - 1) + n
T(n) = n(n + 1)/2
T(n) = O($n^2$)

Ou seja, a complexidade de tempo do insertion-sort é limitada pela função quadrática.

De quantos bits eu preciso?

Neste post, vamos criar um algoritmo que nos diz o número de bits que são necessários para representar um dado valor inteiro. Por exemplo, na linguagem C++ o tipo de dado long int permite armazenar valores com até 31 bits além do bit de sinal. Ou seja a declaração abaixo nos permite armazenar inteiros que vão de −2147483648 a 2147483647.

long int a = 2174483647;

O algoritmo que vamos criar é semelhante a função sizeof(var) que retorna o tamanho de uma variável em bytes, no entanto nosso código retornará o tamanho mínimo em bits que é necessário para representar um valor.

A abordagem é mais uma vez "indutiva". O esquema que criaremos é semelhante ao apresentado no post que discutimos a conversão de um valor decimal para binário.

Projeto indutivo:

  • Caso base: Se o valor que será convertido for igual a 0 ou 1, então o problema está automaticamente resolvido, ou seja, precisamos de apenas 1 bit.
  • Hipótese de indução: Nós podemos assumir que já sabemos quantos são os n - 1 bits que são necessários para a nossa representação binária. Essa é a etapa mais interessante e criativa no processo indutivo =D.
  • Caso geral: Agora basta estender a solução adicionando 1 a resposta que a hipótese de indução nos deu. E assim obteremos a quantidade total de bits que são necessários para representar o valor desejado.

Agora é só escrever o código, a linguagem de programação que será utilizada é o que menos interessa. No entanto, saber "o que" deve ser feito é um pré-requisito básico para irmos a etapa seguinte, ou seja, a etapa do "como fazer". A linguagem Haskell é ótima para esse tipo de demostração, pois é puramente funcional/indutiva, e aproxima o "o que fazer" do "como fazer".

  • Implementação em Haskell
numberBits :: Int -> Int
numberBits 0 = 1
numberBits 1 = 1
numberBits n = 1 + numberBits(n `div` 2)

terça-feira, 19 de junho de 2012

Conversão de decimal para binário usando Indução

Novamente a abordagem é indutiva. O algoritmo implementará o método clássico e simples de conversão.
Idéa indutiva:
  • Caso base: Se o valor que será convertido for igual a 0 ou 1, então o problema está automaticamente resolvido.
  • Hipótese de indução: Nós podemos assumir que já temos os n - 1 bits que compõem a representação binária. Pode até parecer uma suposição absurda, mas é dessa forma que a indução trabalha =D.
  • Caso geral: Agora basta estender a solução adicionando o último bit ao final da resposta que a hipótese de indução nos deu. E assim como acontece na prova de um teorema, a utilização da hipótese de indução no passo indutivo é obrigatória.
A seguir, apresentamos algumas implementações que seguem "exatamente" a idéia mostrada acima. Notem a presença do caso base e da hipótese de indução "dec2bin(n / 2)" em todas elas.
  • Implementação em Haskell 
dec2bin :: Int -> String
dec2bin 0 = "0"
dec2bin 1 = "1"
dec2bin n = dec2bin(n `div` 2) ++ show(n `mod` 2)
  • Implementação em Python
def dec2bin(n):
  if n < 2:
    print (n),
  else:
    dec2bin(n / 2)
    print (n % 2),
  • Implementação em Java
public static void dec2bin(int n) {
    if (n < 2) {
        System.out.println(n);
    } else {
        dec2bin(n / 2);
        System.out.println(n % 2);
    }
}
  • Implementação em JavaScript
function dec2bin(a)
{
   if(a < 2)
     return a;
   else
     return dec2bin(Math.floor(a / 2)) + “” + (a % 2);
}
  • Implementação em C++
void dec2bin(int n){
   if(n < 2)
      cout << n;
   else {
      dec2bin(n / 2);
      cout << (n % 2);
   }
}
O tempo de execução do algoritmo apresentado aqui é expresso pela relação de recorrência T(n) = T(n/2) + 1.
Fazendo n = $2^k$, temos

$T(n) = T(2^{k-1}) + 1$
$T(n) = T(2^{k-2}) + 1 + 1$
$T(n) = T(2^{k-3}) + 1 + 1 + 1$
$T(n) = T(2^{k-4}) + 1 + 1 + 1 + 1$
....
$T(n) = T(2^0) + 1 + 1 + 1 + 1 + 1 + 1 +  ...  + 1 + 1$
$T(n) = k$

Como $n = 2^k$, temos que $log  n = log  2^k$ e $log  n = k$, então a complexidade do método é limitada assintoticamente pela função logarítmica. Ou seja, $T(n) = O(log  n)$.