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:
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:
- T vale para n = 1.
- Para todo n > 1, se T vale para n - 1, então T vale para n.
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.
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/
Nenhum comentário:
Postar um comentário