quarta-feira, 4 de setembro de 2013

[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.

terça-feira, 3 de setembro de 2013

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.

segunda-feira, 2 de setembro de 2013

[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

domingo, 1 de setembro de 2013

[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