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.

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;
}

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;
}

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); 
}

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)

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)$. 

Caminhamento indutivo em Árvores Binárias

Neste post vamos construir indutivamente algoritmos que realizam os caminhamentos "pré-ordem", "em-ordem" e "pós-ordem" em árvores binárias. Tais algoritmos são similares, diferindo apenas na ordem em que as chamadas recursivas, que são representantes diretas da hipótese de indução, aparecem.

• Pré-Ordem: visita a raiz, em seguida a subárvore da esquerda e a subárvore da direita.
• Em-Ordem: visita a subárvore da esquerda, e em seguida a raiz e a subárvore da direita.
• Pós-Ordem: vista a subárvore da esquerda, e em seguida a subárvore da direita e a raiz.

O resultado dos caminhamentos aplicados a árvore acima são os seguintes:

• Pré-Ordem: A | B | D | E | C | F | G
• Em-Ordem: D | B | E | A | F | C | G
• Pós-Ordem: D | E | B | F | G | C | A

Agora vamos derivar o nosso algoritmo indutivamente.

Idéia indutiva

• Caso base: é trivial, pois não fazemos caminhamento em árvores binárias vazias.
• Hipótese de Indução: podemos assumir que já temos os caminhamentos das subárvores esquerda e direita.
• Caso Geral: Usando as respostas dadas pela hipótese de indução, basta definir quem será impresso/visitado primeiro. Seguindo o esquema dos três tipos de caminhamento apresentados acima.

As implementações são imediatas, pois já sabemos "o que fazer". A partir de agora nos preocuparemos com os detalhes de implementação.

Caminhamento pré-ordem

• Implementação em C++

void preOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     cout << t->info << ' ';
     preOrdem(t->esq);
     preOrdem(t->dir);
  }
}

Caminhamento em-ordem

• Implementação em C++

void emOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     emOrdem(t->esq);
     cout << t->info << ' ';
     emOrdem(t->dir);
  }
}

Caminhamento pós-ordem

• Implementação em C++

void posOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     posOrdem(t->esq);
     posOrdem(t->dir);
     cout << t->info << ' ';
  }
}

Definição indutiva de Listas

Conhecer a definição indutiva de uma estrutura de dados, facilita a implementação dos algoritmos que à manipulam. Uma lista pode ser definida como sendo

• uma lista vazia (caso base).
• ou uma lista L do tipo <T>, concatenada com um elemento a do mesmo tipo.

Podemos perceber a indução facilmente quando analisamos a concatenação L::a, que segundo a definição, nos diz que se L for uma lista, então L::a também será.

Agora vamos usar a mesma idéia para construir alguns programas que manipulam listas em Haskell.

• Soma dos elementos de uma lista

somaList :: [Int] -> Int
somaList [] = 0
somaList (x:xs) = x + somaList xs  -- Hipótese de indução: somaList xs

• Inversão de uma lista

reverse :: [Int] -> [Int]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]   -- Hipótese de indução: reverse xs

• Seleção do menor valor em uma lista

menor :: [Int] -> Int
menor [x] = x
menor (x:xs)
    | x <= (menor xs) = x
    | otherwise = (menor xs)   -- Hipótese de indução: menor xs

• Tamanho de uma lista

length :: [Int] -> Int
length [] = 0
length (x:xs) = 1 + length xs  -- Hipótese de indução: length xs

Nas implementações acima, podemos perceber que a utilização da hipótese de indução facilitou a construção dos algoritmos, pois nós assumimos que o problema já estava resolvido para listas com n - 1 elementos e simplesmente estendemos a solução para uma lista com n elementos.

É importante lembrar que a indução é uma ferramenta que facilita a construção dos algoritmos e não depende da linguagem ou do paradigma de programação específico que será utilizado. A implementação a seguir foi alcançada através da indução e foi escrita na linguagem C.

• Tamanho de uma string

int length(char *s)
{
 if(!*s)
      return 0;  
   else
      return 1 + length(++a); // Hipótese de indução: length(++a)
}

Indução Matemática - Visão Geral

Agora vamos de fato ao que interessa, neste post darei uma visão geral da indução matemática. É com base no que apresentarei aqui que faremos todas as nossas análises nos próximos posts.

Indução Matemática

Poderosa técnica de prova, usada largamente na matemática para provar a corretude de teoremas. Na Ciência da Computação é utilizada para provar a corretude de algoritmos, além de ser uma super ferramenta que auxilia a construção de algoritmos e a descrição indutiva de estruturas de dados.

Esquema para a prova de um teorema
Seja T um teorema que queremos provar. Suponha que T inclui um parâmetro n cujo valor pode ser qualquer número natural. Ao invés de provarmos que T vale para todos os valores de n, nós provaremos as seguintes condições:

1. T vale para n = 1.
2. Para todo n > 1, se T vale para n - 1, então T vale para n.

A condição 1 é fácil de provar. Basta verificar a validade de T para valores pequenos de n, geralmente verificamos para n = 0 ou n = 1.

Provar a condição 2 é mais fácil que provar o teorema diretamente, então nós podemos supor que T vale para n - 1. Esta suposição é chamada de Hipótese de Indução (e será muito usada em nossas explicações aqui no blog).

O esquema acima decorre do Princípio da Indução que é enunciado da seguinte forma:

•  Se a asserção P, com parâmetro n, é verdade para n = 1, e se, para todo n > 1, a verdade de P para n - 1 implica na verdade de P para n, então P é verdade para todos os números naturais.

Teorema 1: A soma dos n primeiros números naturais é S(n) = n(n + 1)/2.
A prova é por indução em n.
Caso Base: Vamos verificar a validade do teorema para n = 1.
                   S(1) = 1(1+1)/2
                           = 1

Hipótese de Indução: Vamos assumir que o teorema vale para a soma de n - 1 números.
                   S(n - 1) = (n - 1)(n - 1 + 1)/2
                                = (n - 1)(n)/2

Agora no passo indutivo vamos extender a solução, mostrando que o teorema vale para n. É importante lembrar que a utilização da hipótese de indução neste passo é obrigatória.
                  S(n) = S(n - 1) + n
                         = n (n + 1) / 2

Agora já podemos derivar o nosso primeiro algoritmo usando indução:

#include <iostream>

using namespace std;

int soma(int n)
{
  if(n == 1) // caso base
    return n;
  else
    return soma(n - 1) + n; //passo indutivo, vejam a hipótese de indução "soma(n - 1)"
}

int main()
{
  int n;
  cin >> n;
  cout << soma(n) << endl;
  return 0;
}

O programa acima possui complexidade O(n), no entanto, é possível fazer melhor. A aplicação direta da fórmula resolve o problema em tempo O(1), ou seja, gastando apenas algumas operações constantes. No entanto, o objetivo do exemplo nesta introdução foi mostrar a relação direta que existe entre a indução e a construção de algoritmos.

Um problema de dificuldade razoável do Spoj é o Cards. Vale a pena tentar o/

http://www.spoj.pl/problems/CRDS/

Qual o objetivo do InductionCode?

Bom pessoal, este é o meu primeiro post aqui no InductionCode. Criei este blog para compartilhar, com todos os entusiastas na área de TI, um pouco da boa experiência que estou tendo com a construção de algoritmos usando como base a Indução Matemática. O curioso é que esse tipo de abordagem é raro nos cursos de Ciência da Computação, principalmente no Brasil. No entanto, tive a "sorte" de conhecer essa maneira fantástica de construir algoritmos no meu curso, mas especificamente na matéria Projeto e Análise de Algoritmos (Paa).

Já faz algum tempo que eu tento e me esforço ao máximo para pensar sobre algoritmos usando indução. E fazendo isso, percebi que os ganhos são enormes, pois consegui de fato entender o funcionamento de várias estruturas de dados e algoritmos sem ter que decorá-los. É claro que ainda há muito o que aprender, mas penso que este é o caminho. 

Me esforçarei ao máximo para fazer uma postagem por semana, e em cada post eu trarei alguma descrição utilizando indução, pode ser um algoritmo ou uma estrutura de dados.

Att.