Inserindo elementos em uma sequência ordenada

Neste post, vamos descrever indutivamente um algoritmo para inserir um elemento em uma sequência ordenada. Utilizaremos a linguagem Haskell, e em posts posteriores apresentaremos implementações em Python e Scala.

Descrição indutiva:

• Caso Base: Inserir um elemento em uma sequência vazia é trivial.
• Hipótese de Indução: Vamos assumir que sabemos como inserir um elemento em uma sequência com n-1 elementos.
• Caso Geral: Simples, basta verificar se o elemento que desejamos inserir é maior ou menor que o primeiro elemento da lista, caso seja maior, entregamos o elemento e o restante da lista para a hipótese de indução, caso seja menor que o primeiro elemento, basta colocá-lo no início da lista ordenada.

A implementação em Haskell segue exatamente a descrição indutiva apresentada acima.

• Implementação em Haskell

insert :: [Int] -> Int -> [Int]
insert [] a = [a]
insert (x:xs) a 
  | (a < x)   = a:(x:xs)
  | otherwise = x:(insert xs a)

Como podemos perceber, utilizar uma linguagem funcional ajuda no processo de abstração e resolução dos problemas. Inductioncode disponibilizará em breve um editorial que fará um comparativo entre os paradigmas funcional e imperativo.

Prova Indutiva: $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n}^2 = F{\tiny n} \times F{\tiny n+1}$

A sequência 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .... é conhecida como série de Fibonacci e foi definida formalmente aqui. Os números de Fibonacci possuem várias propriedades interessantes, agora vamos apresentar uma delas, provando por indução que

                                                           $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n}^2 = F{\tiny n} \times F{\tiny n+1}$

A prova é por indução em n:

• Caso Base: Para n = 1, $F{\tiny 1}^2 = F{\tiny 1} \times F{\tiny 2}$.
• Hipótese de Indução: Vamos assumir que $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n-1}^2 = F{\tiny n-1} \times F{\tiny n}$.
• Caso Geral: No passo indutivo, basta adicionarmos o valor de $F{\tiny n}^2$ a soma dos primeiros n-1 elementos que definimos na hipótese de indução, ou seja

                                                     $F{\tiny n} \times F{\tiny n+1} = \overbrace{\underbrace{(F{\tiny n-1} \times F{\tiny n})}_\text{Hipótese de Indução} + F{\tiny n}^2}^{Caso Geral}$

                                                    $F{\tiny n} \times F{\tiny n+1} = F{\tiny n} \times (F{\tiny n-1} + F{\tiny n})$

                         {Por definição, sabemos que $F{\tiny n} = F{\tiny n-1} + F{\tiny n-2}$, logo $F{\tiny n-1} + F{\tiny n} = F{\tiny n+1}$}

                                                   $F{\tiny n} \times F{\tiny n+1} = F{\tiny n} \times F{\tiny n+1}$      C.Q.D.

Torres de Hanói: Computando o número de movimentações

Em posts anteriores, apresentamos a descrição indutiva para o problema das Torres de Hanói e provamos que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$, onde n é o número de discos. Agora, vamos usar a descrição indutiva já discutida para calcular o número de movimentações necessárias, mas com um detalhe, o número de movimentações será calculado no momento em que as movimentações forem feitas. Nosso objetivo é apresentar o significado de "fortalecimento da hipótese de indução".

Fortalecer uma hipótese, significa assumir que ela realiza algo a mais quando comparada à hipótese original. Ou seja, além de assumirmos que a proposição P(n-1) é válida, também assumiremos uma condição C(n-1) e em seguida estenderemos nossa solução para P(n) e C(n).

Para um pleno entendimento do tema tratado aqui, não deixem de ler os posts:

• Torres de Hanói: O número mínimo de movimentações é $2^n-1$.
• Torres de Hanói.

Siga o Inductioncode no Twitter: Seguir @inductioncode

Descrição indutiva:

• Caso Base: para n = 0, temos que o número de movimentações é 0.
• Hipótese de Indução: vamos assumir que sabemos como mover n-1 discos, e como condição extra vamos assumir que o número de movimentações está armazenado em uma variável que chamaremos de numMoves.
• Caso Geral: No passo indutivo, vamos estender a solução para o caso geral. Para isso, após realizar uma movimentação, basta incrementar a variável numMoves.

A implementação que apresentaremos em Java, segue exatamente a ideia apresentada acima.

• Implementação em Java

public static int numMoves = 0;
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);
    numMoves++;
    hanoi(n - 1, C, B, A);
  }
}

Em breve, falaremos mais sobre o fortalecimento da hipótese de indução. Aguardem.
@inductioncode

Prova indutiva: n! > $2^n$ para n $\geq$ 4

Provaremos agora a desigualdade n! > $2^n$ para n $\geq$ 4. Mostraremos que a função fatorial cresce mais rápido que a função exponencial.

A prova é por indução em n:

• Caso Base: Para n = 4, temos que $4! > 2^4$.
• Hipótese de Indução: Vamos supor que $(n-1)! > 2^{n-1}$.
• Caso Geral: Agora basta utilizar o resultado obtido na hipótese de indução e estender a solução para o caso geral, assim temos que

                               $2*(n-1)! > 2*2^{n-1}$

                       $2*(n-1)! > 2^n$  

         {como 2*(n-1)! é menor que n!, para n = 4, podemos substituí-lo por n! e mantemos a desigualdade}

                   $n! > 2^n$   C.Q.D.

Descrição Indutiva: Busca Binária recursiva em Java

Neste post, vamos descrever indutivamente e discutir a complexidade da busca binária. Como veremos,    a busca binária é mais eficiente que a busca sequencial discutida no post Descrição indutiva: Busca sequencial recursiva em Java. No entanto, para que possamos aplicar a busca binária em um vetor (lista) é necessário que ele esteja ordenado.

Descrição Indutiva:

• Caso Base: Para um vetor com apenas um elemento, basta verificar se o elemento procurado é o elemento armazenado no vetor.
• Hipótese de Indução: Vamos assumir que a hipótese de indução sabe procurar o elemento desejado em um vetor com $\frac{n}{2}$ elementos.
• Caso Geral: Vamos procurar um elemento K no vetor. Para compor o caso geral, vamos dividir o vetor ao meio e verificar se o elemento central é maior ou menor que K. Caso o elemento central seja menor que K, então K poderá ser encontrado na segunda parte do vetor, caso contrário, o elemento K poderá ser encontrado na primeira parte do vetor.

A implementação em Java (ou em sua linguagem predileta) segue exatamente a descrição indutiva do problema.

• Implementação em Java

public class BinarySearch {

  public static int binarySearch(int vet[], int value, int left, int rigth) {
    int middle;
    if (left <= rigth) {
      middle = left + (rigth - left) / 2;
      if (vet[middle] == value)
      return middle;
    else if (vet[middle] > value)
      return binarySearch(vet, value, left, middle - 1);
    else
      return binarySearch(vet, value, middle + 1, rigth);
    }
    return -1;
}
  public static void main(String[] args) {
    int vet[] = { 1, 3, 4, 6, 78, 90 };
    System.out.println(binarySearch(vet, 3, 0, 5));
  }
}

Complexidade
A busca binária é muito eficiente, pois a cada passo descarta a metade do espaço de busca. A relação de recorrência que expressa a complexidade do algoritmo é: $T(n) = T(\frac{n}{2}) + 1$. Resolvendo a recorrência temos que a busca binária é O(log n).


Gostou da publicação? Sim? Então curta nossa fan page no Facebook e acompanhe nossas postagens.

@inductioncode

Exponenciação Rápida: Descrição indutiva e implementação em Java

Neste post, apresentaremos uma implementação eficiente para o problema da exponenciação. Faremos a descrição indutiva do problema e em seguida implementaremos uma solução em Java. No  post anterior (ver post), utilizamos a indução fraca, agora vamos usar a indução forte para descrever o mesmo problema. Para revisar os conceitos básicos referentes ao uso da indução matemática na construção de algoritmos, veja o post: Indução Matemática - Visão Geral.

Matematicamente, temos o seguinte:

                                                                  $a^n = (a^{\frac{n}{2}})^2$     , se n for par
                                                                  $a^n = a * a^{n-1}$ , se n for ímpar

Descrição indutiva:

• Caso Base: Para n = 0, temos que $a^0 = 1$.
• Hipótese de Indução: Vamos assumir que temos o valor de $a^{\frac{n}{2}}$.
• Caso Geral: Simples, basta elevar ao quadrado o resultado encontrado na hipótese de indução.

A implementação em Java (ou sua linguagem predileta) segue exatamente a descrição indutiva do problema.

• Implementação em Java:

public class Potenciacao {

  public static int fastExp(int base, int exp) {
    if (exp == 0)
      return 1;
    else if (exp % 2 == 0)
      return (int) Math.pow(fastExp(base, exp / 2), 2);
    else
      return (int) (Math.pow(fastExp(base, exp - 1), 2) * base);
  }

  public static void main(String[] args) {
    System.out.println(fastExp(2, 3));
  }
}

Complexidade

A solução apresentada acima é mais eficiente que a solução utilizada no post anterior. A relação de recorrência $T(n) = T(\frac{n}{2}) + 1$ mostra que o algoritmo possui complexidade O(log n).

@inductioncode

Particionando dados: implementação em Haskell

Em uma postagem anterior, que pode ser vista aqui, abordamos indutivamente a construção de um algoritmo que realiza a separação de dados em um vetor. Agora apresentamos uma implementação em Haskell para solucionar o mesmo problema. 

Por se tratar de uma linguagem funcional, Haskell possibilita uma implementação clara e enxuta na maioria dos casos.

Vamos a descrição indutiva do problema:

• Caso Base: Uma lista vazia está particionada em pares e ímpares por definição.
• Hipótese de Indução: Vamos assumir que uma lista com n-1 elementos já está particionada em pares e ímpares.
• Caso Geral: Basta verificar a paridade do elemento que ficou de fora, se ele for par então basta colocá-lo no início da lista com n-1 elementos obtida por hipótese de indução, caso contrário ele será colocado no final da lista obtida por hipótese de indução.

E mais uma vez derivaremos o algoritmo a partir da descrição indutiva. A boa notícia é que o algoritmo decorre imediatamente da descrição indutiva e podemos chegar até ele sem esforço. A seguir apresentamos a solução para a descrição indutiva implementada em Haskell.

• Implementação em Haskell

partition :: [Int] -> [Int]
partition [] = []
partition (x:xs)
  | x `mod` 2 == 0 = x : (partition xs)
  | otherwise      = (partition xs) ++ [x]

Complexidade do algoritmo:

Apesar de simples, a implementação apresentada em Haskell não é eficiente. Em nosso editorial, discutiremos uma implementação mais eficiente também em Haskell.

@inductioncode

Exponenciação: Descrição indutiva e implementação em Java

Neste post, vamos descrever indutivamente um algoritmo que realiza a exponenciação. Em seguida, apresentaremos uma implementação em Java. Matematicamente, para calcular a exponencial $a^n$, fazemos:

                                                                   $\underbrace{a * a * a * ... * a * a}_\text{n termos} = a^n$

Descrição indutiva:

• Caso Base: Para n = 0, temos que $a^0 = 1$.
• Hipótese de Indução: Vamos assumir que a hipótese de indução sabe como calcular $a^{n-1}$.
• Caso Geral: Trivial, basta pegar a resposta que a hipótese de indução nos deu e multiplicar por a. E assim teremos:                                                                   $\underbrace{\overbrace{(a^{n-1})}^\text{Hipótese de Indução}*a}_\text{Caso Geral} = a^n$.

A implementação em Java segue exatamente a descrição indutiva apresentada acima.

• Implementação em Java

public class Potenciacao {
  public static int slowExp(int a, int n) {
    if (n == 0)
      return 1;
    else
      return slowExp(a, n - 1) * a;
  }

  public static void main(String[] args) {
    System.out.println(slowExp(2, 3));
  }
}

Complexidade
A implementação acima possui complexidade linear. Ou seja, T(n) = T(n-1) + O(1),onde n é o expoente da potência. Podemos fazer melhor?

@inductioncode

Participe da nossa enquete

Participe da nossa enquete e diga qual linguagem de programação você quer ver aqui no Inductioncode. Faremos uma série especial de posts com implementações na linguagem escolhida.

Seguir @inductioncode

Prova Indutiva: $2^n$ > $n^2$, para n $\geq$ 5

Continuando nossa série de posts sobre provas por indução, vamos mostrar que: $2^n$ > $n^2$, para n $\geq$ 5.

Prova por indução em n:

• Caso Base: Para n = 5, $2^5 > 5^2$.
• Hipótese de Indução: Vamos assumir que a inequação é valida para n-1, ou seja, $2^{n-1} > (n-1)^2$.
• Caso Geral: Agora vamos utilizar a hipótese de indução e estender a solução, esta etapa também é conhecida como "passo indutivo".

                                                  $2 * 2^{n-1} > 2*(n-1)^2$     {multiplicando ambos os lados por 2}
                                                  $2^n > 2(n^2 - 2n + 1)$
                                                  $2^n > n^2 + n^2 - 4n + 2$    {como $-4n > -n^2$, vamos subtituí-lo por $n^2$}
                                                  $2^n > n^2 + n^2 - n^2 + 2$     {substituindo $n^2 + n^2 - n^2 + 2$ por $n^2 + n^2 - n^2$}
                                                  $2^n > n^2 + n^2 - n^2$
                                                  $2^n > n^2$                               C.Q.D.

Neste post, apresentamos a prova por indução de uma inequação. É interessante observar que a prova de inequações é um pouco diferente da prova de equações, pois ao trabalharmos com desigualdades podemos realizar algumas substituições que não seriam permitidas em equações com operador de igualdade.

Descrição indutiva: Busca sequencial recursiva em Java

Neste post, vamos implementar em Java e descrever indutivamente um algoritmo que realiza a busca sequencial em um vetor. Apresentaremos uma implementação recursiva, em outro post trataremos da implementação iterativa.

Descrição indutiva:

• Caso Base: Trivial, não fazemos busca em listas vazias.
• Hipótese de Indução: Vamos supor que a hipótese de indução busca um valor em uma lista com n-1 elementos.
• Caso Geral: Simples, verificamos se o último elemento é o valor procurado, se não for entregamos os n-1 primeiros elementos para a hipótese de indução que se encarrega de fazer a busca no resto da lista.

Agora, apresentaremos uma implementação que decorre da descrição indutiva apresentada acima.

• Implementação em Java:

public class LinearSearch {

 public static int linearSearch(int vet[], int n, int value) {

  if (n >= 0) {
   if (vet[n] == value)
    return n;
   else
    return linearSearch(vet, n - 1, value);
  }
  return -1;
 }

 public static void main(String[] args) {

  int vet[] = { 10, 2, 43, 14, 25, 6, 37 };
  int value = 14;
  int index = linearSearch(vet, 6, value);

  if (index == -1)
   System.out.println("Elemento não encontrado");
  else
   System.out.println("O índice do elemento " + value + " é: " + index);
 }
}

Complexidade do algoritmo/implementação:

Usando indução não é difícil encontrar uma relação de recorrência que expresse o tempo de execução do algoritmo acima. O raciocínio é simples, basta imaginar que o tempo total do algoritmo é o tempo que gastamos para verificar se o último elemento é o procurado, mais o tempo que a hipótese de indução gastou para procurar nos n-1 elementos restantes, ou seja, T(n) = T(n-1) + O(1). Resolvendo a recorrência, temos

                                                                  T(n) = T(n-1) + O(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 + 1

                                                                  ...

                                                                  T(n) = T(0) + 1 + 1 + 1 + ... + 1

                                                                  T(n) = O(n)

Analisando a relação de recorrência, podemos perceber que a busca sequencial possui complexidade linear, o algoritmo visita cada elemento apenas uma vez.

Como sempre, utilizamos a Indução Matemática para descrever nossos problemas. Para o iniciante que não está acostumado com esta abordagem, pode parecer confuso no início, mas nada que a prática não resolva.

Seguir @inductioncode

[EDITORIAL 4] Teoria dos Grafos

Em breve, Inductioncode apresentará uma série de postagens sobre teoria dos grafos. Além da prova indutiva de alguns teoremas, descreveremos indutivamente algoritmos bastante conhecidos, como as buscas em largura e profundidade.

@inductioncode

Prova Indutiva: Soma de uma série geométrica

Neste post, apresentaremos a prova por indução da fórmula que calcula a soma dos termos de uma progressão geométrica. 

                                                $\sum\limits_{i=0}^n r^i = \frac{r^{n + 1} - 1}{r - 1}$

A prova é por indução em n:

• Caso Base: Para n = 0 temos, $\sum\limits_{i=0}^0 r^i = \frac{r ^ {0 + 1} - 1}{r - 1} = 1$.
• Hipótese de Indução: Vamos assumir que a fórmula é válida para n-1. Logo, temos $\sum\limits_{i=0}^{n-1}r^i = \frac{r ^ {n -1 + 1} - 1}{r - 1}= \frac{r ^{n} - 1}{r - 1}$.
• Caso Geral: Para compor o caso geral, vamos somar o elemento r^n a soma dos n-1 elementos da P.G. encontrada na hipótese de indução, temos

                                                                  $\sum\limits_{i=0}^n r^i=( \sum\limits_{i=0}^{n-1} r^i ) + r^n$

                                                                            $=\frac{r ^{n} - 1}{r - 1} + r^n$

                                                                            $=\frac{r ^{n} - 1 + (r-1)r^n}{r - 1}$

                                                                            $=\frac{r ^{n} - 1 + r^{n+1} - r^n}{r - 1}$
                                                                 
                                                                            $=\frac{r ^{n+1} - 1}{r - 1}$             C.Q.D.

Descrição indutiva: Fibonacci implementado em Java

Em 1202 Leonardo Pisano criou uma série de números conhecida como sequência de Fibonacci. Cada elemento na sequência é a soma dos dois elementos imediatamente anteriores:

                                              0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Formalmente, os elementos da sequência são definidos como:

• F(0) = 0; 
• F(1) = 1; 
• Fn = F(n-1) + F(n-2);

Descrição indutiva:

• Caso Base: Por definição, F(0) = 0 e F(1) = 1.
• Hipótese de Indução: Vamos assumir que já conhecemos os valores de F(n-2) e F(n-1).
• Caso Geral: Basta combinar os valores encontrados por hipótese de indução e somá-los para obter o resultado final fazendo F(n) = F(n-1) + F(n-2).

O algoritmo decorre imediatamente da descrição indutiva apresentada acima.

• Implementação em Java

public class Fibonacci {

 public static int fibRec(int n) {
  if (n <= 1)
   return n;
  else
   return fibRec(n - 1) + fibRec(n - 2);
 }
 // test
 public static void main(String[] args) {
  System.out.println(fibRec(11));

 }
}

Complexidade

Apesar de termos um algoritmo de fácil implementação e enxuto, a versão recursiva para os números de Fibonacci apresentada acima é extremamente ineficiente, sua complexidade é exponencial. Em uma outra postagem traremos uma implementação iterativa e mais eficiente.

@inductioncode

Torres de Hanói: O número mínimo de movimentações é $2^n$-1

Continuando a série de posts sobre torres de Hanói e indução, vamos provar que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$.

A prova é por indução em n:

• Caso Base: Para n = 0, temos $2^0-1 = 0$.
• Hipótese de Indução: Vamos supor que para mover n-1 discos entre quaisquer 2 pinos sejam necessárias $2^{n-1}-1$ movimentações.
• Caso Geral: Para compor o caso geral teremos que considerar o custo para mover n-1 discos para um pino auxiliar ($2^{n-1}-1$ movimentações), o custo para mover 1 disco para o pino final (1 movimentação) e o custo para mover os n-1 discos do pino auxiliar para o pino final ($2^{n-1}-1$ movimentações), ou seja

                                                      Nº de movimentações =  $\underbrace{(2^{n-1}-1) + (2^{n-1}-1)}_\text{Hipótese de Indução} + 1$
                                                                                                     
                                                                                    = $2(2^{n-1}-1) + 1$

                                                                                    = $(2^n -2) + 1$

                                                                                    = $2^n -1$     C.Q.D.

[EDITORIAL 3] Reverse e Append: Uma combinação ineficiente

O Inductioncode trará amanhã uma análise sobre o uso da função append (++) na implementação da função reverse, como mostrada abaixo:

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Vamos discutir a complexidade dessa solução e apresentar uma outra implementação assintoticamente mais eficiente.

@inductioncode

Prova Indutiva: 2 + 5 + 8 + ... + 3n-1 = $\frac{n(3n + 1)}{2}$

Neste post, apresentaremos a prova indutiva de que a soma 2 + 5 + 8 + ... + 3n-1 vale $\frac{n(3n + 1)}{2}$.

                                   $S{\tiny n} = 2 + 5 + 8 + ... + 3n-1 = \frac{n(3n + 1)}{2}$

A prova é por indução em n:

• Caso Base: Para n = 1, temos que $\frac{1(3\times1 + 1)}{2} = 2$.

• Hipótese de Indução: Vamos assumir que a fórmula vale para n-1, ou seja,

                                     $S{\tiny n-1} =\frac{(n-1)(3(n-1) + 1)}{2} = \frac{3n^2 - 5n + 2}{2}$.

• Caso Geral: Vamos estender a solução adicionando o elemento (3n-1) a soma dos n-1 primeiros elementos que assumimos ser verdadeira na hipótese de indução, logo

                                                              $S{\tiny n} = S{\tiny n-1} + (3n-1)$

                                                              $S{\tiny n} = \frac{3n^2 - 5n + 2}{2}+ (3n-1)$

                                                              $S{\tiny n} = \frac{3n^2 - 5n + 2 + 6n - 2}{2}$

                                                              $S{\tiny n} = \frac{3n^2 + n}{2}$

                                                              {Colocando n em evidência}
                                                              $S{\tiny n} = \frac{n(3n + 1)}{2}$   C.Q.D.

@inductioncode

[EDITORIAL 2] Implementações em várias linguagens contemplam vários paradigmas.

A utilização de linguagens de programação imperativas facilitam ou dificultam a programação usando indução? Por que ao utilizar uma linguagem imperativa temos que ficar atentos a tantos detalhes de implementação? Por que o paradigma funcional nos permite construir programas mais enxutos?

Inductioncode responderá a essas e outras perguntas em um post esclarecedor. Faremos um paralelo entre os paradigmas imperativo e funcional.

@inductioncode