Demonstração por Indução Matemática

Princípio da Indução Finita

• O princípio da indução finita é uma técnica utilizada para provar que uma proposição é verdadeira para todos os inteiros naturais.
• A prova por indução matemática segue dois passos: passo base e passo indutivo.

Passo Base

• O passo base consiste em mostrar que a proposição é verdadeira para o menor caso possível (geralmente n = 0 ou n = 1).
• Exemplo: Provar que P(n) = 1 + 2 + 3 + … + n = n(n+2)/2, para n = 0.

Passo Indutivo

• O passo indutivo consiste em supor que a proposição é verdadeira para algum inteiro k e mostrar que ela é verdadeira para k + 1.
• Exemplo: Suponha que P(k) = 1 + 2 + 3 + … + k = k(k+2)/2, para algum inteiro k ≥ 1. Mostrar que P(k+1) é verdadeira.

Exemplos de Provas por Indução

• Provar que P(n) = 1 + 2 + 3 + … + n = n(n+2)/2, para todos inteiros n ≥ 0.
• Provar que P(n) = 12 + 22 + 32 + … + n2 = n(n+1)(2n+1)/6, para todos inteiros n ≥ 1.
• Provar que P(n) = 1 + 2 + 3 + … + n = n(n+1)/2, para todos inteiros n ≥ 1.

Observações

• É importante usar obrigatoriamente o predicado/proposição P(k) na prova por indução matemática.
• A soma da P(k+1) pode ser decomposta em partes menores, utilizando a hipótese indutiva.

Introdução ao Algoritmo

• Um algoritmo é um conjunto de instruções executáveis para resolver um problema
• São as ideias por detrás dos programas
• O problema é a motivação para o algoritmo
• Geralmente existem vários algoritmos para um mesmo problema

Análise de Algoritmo

• Análise do Melhor Caso: T(n) = avaliação ingênua de um algoritmo que é rápido para algumas entradas
• Análise Caso Médio: T(n) = tempo médio do algoritmo para todos as entradas de tamanho n
• Análise do Pior Caso: T(n) = tempo máximo do algoritmo para uma entrada qualquer de tamanho n

Eficiência de Algoritmos

• A eficiência de um algoritmo depende do tamanho do problema
• Assume-se que “n” é o tamanho do problema
• Calcula-se o número de operações/instruções que serão realizadas sobre os n elementos

Complexidade de Algoritmos

• A complexidade de um algoritmo é quantas instruções são necessárias para obter a solução de uma instância do problema
• A eficiência de um algoritmo é importante para saber se ele é rápido o suficiente para resolver um problema

Análise Assintótica

• A análise assintótica é o estudo do comportamento de algoritmos para entradas arbitrariamente grandes
• É usada para comparar funções e analisar o crescimento de algoritmos
• É importante para saber se um algoritmo é eficiente para um problema grande

Comportamento Assintótico

• O comportamento assintótico é o estudo do comportamento de uma função quando n tende ao infinito
• É importante descartar termos constantes e manter apenas os que crescem mais rápido
• O termo de maior expoente domina o comportamento da função