Dicas Linux

Bom pessoal, a partir de agora também darei aqui no blog algumas dicas de programação que serão úteis para quem usa alguma distribuição baseada no Unix como Debian, Ubuntu e outros.

Quick-Sort: Uma abordagem indutiva.

Neste post, vamos fazer uma análise indutiva do método de ordenação que na prática é o mais rápido. O quick-sort demostra a eficiência do paradigma "dividir e conquistar".

O primeiro passo do quick-sort é escolher aleatoriamente um elemento x que será chamado de pivô. Em seguida, o vetor será particionado de forma que os elementos a esquerda do pivô sejam menores que ele, e os elementos a direita sejam maiores ou iguais a ele. A Figura 1 apresenta uma partição cujo pivô é 4.

Figura 1. Vetor particionado

Descrição indutiva da "partição": Para construir o nosso algoritmo vamos utilizar a abordagem indutiva, detalhando o caso base, a hipótese de indução e o caso geral..

Idéia indutiva:

• Caso Base: o vetor possui apenas 1 elemento, então ele já está particionado!
• Hipótese de Indução: vamos supor que o problema da partição já está resolvido para n - 1 elementos e que sabemos onde termina a lista de elementos menores que o pivô.
• Caso Geral: é quase trivial, pois basta verificar se o último elemento do vetor é menor ou maior que o pivô. Caso o último elemento seja menor que o pivô, então basta colocá-lo no final da lista de elementos menores que o pivô.

Implementação da partição: Seguindo o esquema indutivo apresentado, podemos implementar um método de forma simples. Nessa implementação, o pivô escolhido é o primeiro elemento do vetor.

• Implementação em C++:

int partition(int X[], int left, int right) {
    int pivot = X[left];
    int i = left;

    for (int j = left; j <= right; j++)
        if (X[j] < pivot)
            swap(X, j, ++i);
    swap(X, left, i);
    return i;
}

Após a execução do método "partition", apenas o pivô estará na posição correta. Precisamos ordenar os elementos que estão à esquerda e à direita do pivô. No entanto, podemos assumir que a hipótese de indução fará esse trabalho, como podemos ver na Figura 2.

Figura 2.

Idéia indutiva:

• Caso Base: um vetor com 1 elemento já está ordenado.
• Hipótese de Indução: após a execução do método "partition", vamos assumir que a hipótese de indução sabe como ordenar todos os elemento que estão à esquerda e à direita do pivô.
• Caso Geral: simplesmente já temos o vetor ordenado!

Na Figura 3, apresentamos o resultado final, um vetor ordenado!

Figura 3. Vetor ordenado.

A seguir, apresentamos a implementação completa do Quick-Sort.

• Implementação em Haskell: por se tratar de uma linguagem funcional, Haskell permite que o programador implemente uma solução enxuta, sem se preocupar com detalhes.

quickSort :: [Int] -> [Int]
quickSort [] = []
quickSort [x] = [x]
quickSort (x:xs) = quickSort menores ++ [x] ++ quickSort maiores
  where
    menores = [p | p <- xs, p <= x]
    maiores = [p | p <- xs, p > x]

• Implementação em C++

void quickSort(int A[], int left, int right){
    if(left < right){
        int middle = partition(A, left, right);
        quickSort(A, left, middle - 1);
        quickSort(A, middle + 1, right);
    }
}

• Implementação em Python

def quickSort(lista):
  if lista == []:
    return []
  else:
    pivot = lista[0]
    menores = [x for x in lista[1::] if x < pivot]
    maiores = [x for x in lista[1::] if x >= pivot]
    return quickSort(menores) + [pivot] + quickSort(maiores)

Complexidade do Quick-Sort: A complexidade do algoritmo depende da escolha do pivô, caso o pivô escolhido divida o vetor em duas partes com tamanhos iguais ou similares, a sua complexidade será O(n log n).

Caso os elementos do vetor já estejam ordenados, a complexidade do Quick-Sort no pior caso será descrita pela recorrência $T(n) = T(n - 1) + O(n) = O(n^2)$. Na prática, como o pior caso raramente acontece, a literatura reconhece que o Quick-Sort é o melhor algoritmo de ordenação, e por isso ele é utilizado em uma grande variedade de aplicações.

Particionando em pares e ímpares

Agora, vamos utilizar indução para resolver um problema fácil, que com indução ficou mais fácil ainda.

Problema:

• Dada uma sequência de n valores inteiros, rearranjar os elementos de forma que os valores pares apareçam antes dos ímpares.

Idéia indutiva:

• Caso Base: uma lista com 1 elemento já está particionada em pares e ímpares.
• Hipótese de Indução: podemos assumir que o problema já foi resolvido para n-1 elementos, e que sabemos onde termina a lista de pares.
• Caso Geral: basta verificar se o último elemento é par ou ímpar, se ele for par basta inseri-lo no final da lista de pares, caso contrário, não fazemos nada.  

Agora, vamos ilustrar o problema com um exemplo:

• Situação inicial: Um vetor com valores pares e ímpares misturados.

• Hipótese de indução: agora vamos "imaginar" que o problema já foi resolvido para os primeiros n - 1 elementos, e que sabemos onde termina a lista de pares.

• Caso Geral: Pronto! Agora ficou muito fácil, podemos perceber que o último elemento é par, então vamos incrementar o final da lista de pares e trocar o último  elemento da lista de pares com o último elemento do vetor.

• E assim chegamos a solução do problema.

O algoritmo segue exatamente a idéia apresentada acima. Vamos assumir que o problema já foi resolvido para os primeiros n - 1 elementos, e dentro do loop só escreveremos código para trocar o último elemento do vetor (caso ele seja par) com o último elemento da lista de pares. E não podemos esquecer do caso base!

• Implementação em C++ (versão iterativa)

fimPares = -1; // caso base
for(int i = 0; i < tamVetor; i++)
  if(vetor[i] % 2 == 0){  // passo indutivo
    fimPares++;
    troca(vetor[i], vetor[fimPares]);
  }

Complexidade do algoritmo: A relação de recorrência da nossa solução é T(n) = T(n - 1) + 1, ou seja, o tempo gasto pela hipótese de indução para separar os n - 1 elementos mais o tempo gasto para colocar o último elemento no final da lista de pares. Derivando T(n) temos:

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

Logo, concluímos que o nossa solução tem complexidade linear.

Por que usar indução?

Em seu artigo, intitulado "Using induction to design algorithms",  Udi Manber faz uma analogia entre a prova de teoremas matemáticos e a construção de algoritmos usando indução. E diz que embora esses dois processos sirvam para alcançar resultados diferentes, eles são muito similares. Além disso, Manber deixa claro que a indução não serve apenas para construir algoritmos recursivos, pois támbem podemos construir algoritmos iterativos pensando de forma indutiva.

"Although induction suggests implementation by recursion, this is not necessarily the case. (Indeed, we call this approach inductive rather than recursive to deemphasize recursive implementations.) In many cases, iterative implementation is just as easy, even if the algorithm was designed with induction in mind; iteration is also generally more efficient." Udi Manber

Então pessoal, não deixem de conferir as nossas postagens, e fiquem atentos ao trio: caso base, hipótese de indução e caso geral.

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.