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.
quarta-feira, 4 de setembro de 2013
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
$=\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:
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.
= $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:
$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,
- 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
$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
Assinar:
Postagens (Atom)
