Fundamentos Matemáticos para Computação: Recorrências

1) Indução Forte (Indução Completa)

A indução forte amplia a hipótese de indução da indução fraca, exigindo que, para provar P(n) para todo n ≥ n0, você demonstre:

• P(n0) verdadeira;
• Para qualquer k ≥ n0, se P(r) vale para todo r entre n0 e k, então P(k+1) também vale.

Em geral, a hipótese ii é mais poderosa que a da indução fraca.

Exemplo: Provemos que, para todo n ≥ 2, n é primo ou n é o produto de primos.

• P(2) é verdadeira (2 é primo).
• Suponha que, para todo 2 ≤ r ≤ k, P(r) seja verdadeira. Se k+1 for primo, então P(k+1) é verdadeira. Caso contrário, k+1 = a·b com 2 ≤ a,b ≤ k; pela hipótese de indução, cada um é primo ou produto de primos, logo k+1 também é produto de primos.

2) Algoritmos Recursivos e Indução Forte

Algoritmos recursivos resolvem problemas complexos por meio de chamadas repetidas a si próprio, com estruturas condicionais simples (se, então, senão).

Exemplo em pseudocódigo para T(n):

\nT(1) = 1
T(n) = T(n-1) + 3, para n ≥ 2

3) Solução de Recorrências lineares de primeira ordem

Uma recorrência linear de primeira ordem com coeficiente constante tem formato S(n) = c · S(n-1) + g(n). A solução fechada é:

S(n) = c^(n-1) · S(1) + Σ_{i=2}^{n} c^(n-i) · g(i)

Exemplo: T(1) = 1; T(n) = T(n-1) + 3 (logo c = 1, g(n) = 3). Então, T(n) = 1 + (n-1)·3 = 3n − 2.

4) Operações Matriciais e Matrizes Booleanas

Matrizes são tabelas numéricas, com aplicações em grafos (matriz de adjacência). Matrizes booleanas utilizam operações distintas:

• Conjunção (AND): A ∧ B = [a_{ij} ∧ b_{ij}]
• Disjunção (OR): A ∨ B = [a_{ij} ∨ b_{ij}]

Exemplos com A e B 3x3 apresentados no material.

Exemplo de grafo não orientado com matriz de adjacência 4x4.

5) Observações e dicas

• Somatórios são convenções para facilitar a escrita de somas repetidas.
• Em grafos não orientados, a matriz de adjacência é simétrica.

Resumo dos tópicos (2)

Abaixo, uma síntese prática de cada tópico apresentado:

• Indução Forte: base P(n0) e passo usando P(r) para n0 ≤ r ≤ k ⇒ P(k+1).
• Recorrências lineares: transformar recurrences em expressão fechada com c^(n-1) S(1) + Σ c^(n-i) g(i).
• Matrizes: estruturas de dados, com A^T = A para simetria; matrizes booleanas com ∧ e ∨ para operações lógicas.
• Exemplos-chave: T(n) = T(n-1) + 3 → T(n) = 3n − 2; decomposição de n ≥ 2 em primos ou produtos.

Questões sobre o assunto