Apostila: Fundamentos Matemáticos para Computação

📘

👋 Introdução

Seja bem-vindo à disciplina Fundamentos Matemáticos para Computação (COM150), uma das pedras angulares do curso de Engenharia de Computação da UNIVESP. Aqui, mergulharemos no universo da matemática discreta, explorando conceitos que são essenciais para a compreensão e desenvolvimento de algoritmos, estruturas de dados e sistemas computacionais.

Ao longo das próximas semanas, abordaremos tópicos como lógica proposicional, técnicas de demonstração, relações e funções, sequências, e a fascinante teoria dos grafos. Cada capítulo será enriquecido com exemplos práticos, analogias criativas e reflexões instigantes, tornando o aprendizado mais acessível e agradável.

Prepare-se para uma jornada de descobertas matemáticas, onde cada conceito aprendido será uma ferramenta a mais no seu arsenal de programador e engenheiro de computação. Vamos juntos desvendar os segredos que tornam a computação uma ciência tão poderosa e transformadora!

📚 Sumário

Semana 1 – Introdução à Matemática Discreta e Lógica Proposicional
- Conceitos fundamentais da matemática discreta
- Introdução à lógica proposicional
- Operadores lógicos e tabelas verdade
- Exemplos e aplicações
- Reflexões e analogias
- Exercícios com gabarito
Semana 2 – Lógica de Predicados
- Predicados e quantificadores
- Negação de proposições com quantificadores
- Equivalências lógicas
- Aplicações em computação
- Exemplos práticos
- Exercícios com gabarito
Semana 3 – Técnicas de Demonstração
- Provas diretas e indiretas
- Prova por contraposição
- Prova por contradição
- Exemplos clássicos
- Dicas para elaboração de provas
- Exercícios com gabarito
Semana 4 – Indução Matemática
- Princípio da indução matemática
- Provas por indução simples e forte
- Aplicações em sequências e algoritmos
- Exemplos detalhados
- Reflexões sobre a importância da indução
- Exercícios com gabarito
Semana 5 – Relações e Funções
- Definição e propriedades de relações
- Tipos de relações: reflexiva, simétrica, transitiva
- Funções: injetoras, sobrejetoras e bijetoras
- Composição de funções
- Exemplos no contexto computacional
- Exercícios com gabarito
Semana 6 – Sequências e Recorrências
- Sequências aritméticas e geométricas
- Fórmulas de recorrência
- Solução de recorrências
- Aplicações em análise de algoritmos
- Exemplos ilustrativos
- Exercícios com gabarito
Semana 7 – Introdução à Teoria dos Grafos
- Conceitos básicos: vértices, arestas, grafos simples
- Representações de grafos: listas e matrizes
- Caminhos, ciclos e conectividade
- Aplicações em redes e algoritmos
- Exemplos práticos
- Exercícios com gabarito
Semana 8 – Revisão e Síntese dos Conteúdos
- Resumo dos principais tópicos abordados
- Mapas mentais e esquemas visuais
- Dicas para fixação do conteúdo
- Questões de revisão com gabarito
- Reflexões finais sobre a disciplina

Com todo prazer, meu caro! Vamos juntos desvendar os mistérios da Semana 1 – Introdução à Matemática Discreta e Lógica Proposicional com estilo, clareza e uma pitada de bom humor. Puxe a cadeira, ajeite os óculos imaginários e prepare-se para mergulhar no lado lógico da força.

Semana 1 – Introdução à Matemática Discreta e Lógica Proposicional

1. Conceitos Fundamentais da Matemática Discreta

Matemática Discreta é o estudo dos objetos contáveis e distintos. Diferente da matemática contínua (tipo cálculo, onde tudo escorre como mel), a discreta trabalha com aquilo que você pode contar com os dedos... ou com zeros e uns.

Ela é a matemática do “click”, não do “deslize”.

Usos?

Lógica de programação
Estruturas de dados
Criptografia
Redes
Algoritmos

Exemplo da vida real:
Pensar se um número é par ou ímpar (e agir de acordo). Sim ou não. Verdadeiro ou falso. Ligar ou desligar. Isso é discreto (e elegante).

2. Introdução à Lógica Proposicional

Lógica proposicional é a base para que máquinas e programadores possam "pensar" com clareza. Uma proposição é uma frase que pode ser verdadeira (V) ou falsa (F). Nada de “talvez” ou “depende”. Aqui, é preto no branco.

Exemplo:

“A terra é redonda.” → proposição (V)
“Passe-me a batata!” → não é proposição (não é algo que pode ser julgado V ou F)

3. Operadores Lógicos e Tabelas Verdade

Aqui é onde começa a mágica. Os operadores lógicos funcionam como conectivos que unem proposições.

Operador	Símbolo	Nome	Exemplo
E	∧	Conjunção	A ∧ B
OU	∨	Disjunção	A ∨ B
NÃO	¬	Negação	¬A
SE...ENTÃO	→	Condicional	A → B
SE E SOMENTE SE	↔	Bicondicional	A ↔ B

Tabelas verdade básicas:

Conjunção (E / ∧): Só é verdadeira se ambos forem verdadeiros.

A B A ∧ B

V V V

V F F

F V F

F F F
Disjunção (OU / ∨): É verdadeira se pelo menos um for verdadeiro.

A B A ∨ B

V V V

V F V

F V V

F F F
Negação (NÃO / ¬): Inverte o valor lógico.

A ¬A

V F

F V

A	B	A ∧ B
V	V	V
V	F	F
F	V	F
F	F	F

A	B	A ∨ B
V	V	V
V	F	V
F	V	V
F	F	F

A	¬A
V	F
F	V

4. Exemplos e Aplicações

Exemplo 1:
Se “Hoje é segunda” (A) e “Tenho aula” (B), então:

A ∧ B → “Hoje é segunda E tenho aula.”
¬B → “Não tenho aula.”

Aplicação prática:
Ao programar um botão de login:

if (usuarioValido && senhaCorreta) {
   permitirAcesso();
}

Aqui temos um clássico A ∧ B.

5. Reflexões e Analogias

Analogia com casais:

A ∧ B = Os dois querem sair? Só saem juntos se ambos quiserem.
A ∨ B = Basta um querer, e já estão de pé!
¬A = Se um diz “não quero”, significa que está fora do rolê.

Reflexão:
A lógica é o alicerce da computação. Assim como um castelo precisa de uma fundação sólida, um programa precisa de uma lógica bem construída.

6. Exercícios com Gabarito

1. Qual das sentenças a seguir é uma proposição?
A) Feche a porta!
B) Que lindo o céu!
C) A Terra gira em torno do Sol.
D) Você viu aquilo?

2. Dado A = “Choveu” e B = “Levei guarda-chuva”, o que representa ¬A ∧ B?
A) Choveu e levei guarda-chuva
B) Não choveu e levei guarda-chuva
C) Não choveu e não levei guarda-chuva
D) Choveu ou levei guarda-chuva

3. Complete a tabela verdade da disjunção A ∨ B. Se A = F e B = V, o resultado é:
A) V
B) F
C) Indeterminado
D) V e F ao mesmo tempo

4. Se A = V e B = F, o valor de A → B é:
A) V
B) F
C) Não existe
D) Igual a B

5. Qual operador lógico representa o “E”?
A) ∨
B) →
C) ∧
D) ¬

Gabarito

Semana 2 – Lógica de Predicados

1. Predicados e Quantificadores

Na lógica proposicional, vimos frases com valor fixo (V ou F). Agora, com lógica de predicados, colocamos variáveis na jogada. É como dizer: "X tem tal propriedade."

Predicado: é uma função que vira proposição quando você atribui um valor.
Ex: P(x) = “x é maior que 5” → P(7) = verdadeiro

Quantificadores são os comandantes que dizem para quem essa regra vale:

Universal (∀) → “Para todo” ou “Para cada”
Ex: ∀x P(x) → “Todo x satisfaz P(x)”
Existencial (∃) → “Existe pelo menos um”
Ex: ∃x P(x) → “Existe algum x que satisfaz P(x)”

Exemplo prático:

“Todo estudante é curioso” → ∀x (Estudante(x) → Curioso(x))
“Algum estudante gosta de lógica” → ∃x (Estudante(x) ∧ GostaDeLógica(x))

2. Negação de Proposições com Quantificadores

Ah, o doce prazer de negar coisas...

Negar um quantificador é trocar seu tipo e negar o predicado:

¬(∀x P(x)) ≡ ∃x ¬P(x) → “Nem todo x satisfaz P(x)”
¬(∃x P(x)) ≡ ∀x ¬P(x) → “Nenhum x satisfaz P(x)”

Exemplo:

“Nem todo aluno passou.” = ¬(∀x Passou(x)) = ∃x ¬Passou(x)
“Nenhum aluno colou.” = ¬(∃x Colou(x)) = ∀x ¬Colou(x)

É como inverter a plaquinha da lógica: “Aberto” vira “Fechado”.

3. Equivalências Lógicas

A lógica ama reciclagem: certas expressões podem ser trocadas sem alterar o sentido.

Algumas equivalências úteis:

Contrapositiva: (P → Q) ≡ (¬Q → ¬P)
De Morgan (versão quantificadores):
¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)

Exemplo em português:

“Se chove, eu levo guarda-chuva” → “Se não levei guarda-chuva, então não choveu”

4. Aplicações em Computação

A lógica de predicados é o Google da programação: faz perguntas e procura verdade.

Onde se aplica?

Sistemas especialistas e IA:
Ex: ∀x (Humano(x) → Mortal(x)) — obrigado, Aristóteles!
Bancos de dados:
SELECT * FROM Alunos WHERE idade > 18
(Isso é ∃x (Aluno(x) ∧ Idade(x) > 18))
Verificação formal de algoritmos:
Provar que “para toda entrada válida, o algoritmo retorna o resultado correto”.

5. Exemplos Práticos

Exemplo 1:
Considere o predicado:
P(x): “x é um número primo maior que 10”

∃x P(x): Existe um número primo maior que 10 (VERDADEIRO)
∀x P(x): Todo número é um primo maior que 10 (FALSO)
¬∀x P(x): Nem todo número é um primo maior que 10 (VERDADEIRO)

Exemplo 2 (programação):

def todos_maiores_que_10(lista):
    return all(x > 10 for x in lista)

Traduzido: ∀x ∈ lista (x > 10)

6. Exercícios com Gabarito

1. Qual é a forma correta da negação de “Todos os alunos passaram”?
A) Todos os alunos não passaram
B) Nenhum aluno passou
C) Existe pelo menos um aluno que não passou
D) Todos os alunos reprovaram

2. Qual quantificador usamos para dizer “Existe alguém que ama lógica”?
A) ∀
B) →
C) ∃
D) ¬

3. A proposição ∀x (Estudante(x) → Inteligente(x)) é equivalente a:
A) Todo estudante é burro
B) Se x é estudante, então x é inteligente
C) Nenhum estudante é inteligente
D) Existe um estudante inteligente

4. A contrapositiva de (P → Q) é:
A) Q → P
B) ¬P → ¬Q
C) ¬Q → ¬P
D) ¬P ∨ Q

5. ¬(∃x P(x)) é logicamente equivalente a:
A) ∀x ¬P(x)
B) ∃x ¬P(x)
C) ¬∀x P(x)
D) ∀x P(x)

Gabarito

Semana 3 – Técnicas de Demonstração

1. Provas Diretas e Indiretas

Uma demonstração é uma sequência de argumentos lógicos que mostra, sem deixar dúvida, que uma proposição é verdadeira. É como fazer uma receita exata que leva ao bolo da verdade — sem fermento de achismo.

Prova Direta

Começamos com o que sabemos (hipóteses) e usamos regras lógicas para chegar à conclusão.

Exemplo:
Provar: Se n é par, então n² é par.
Prova:

n é par → n = 2k
n² = (2k)² = 4k² = 2(2k²) → múltiplo de 2 → é par.

Simples, direto, sem curvas.

2. Prova por Contraposição

Ao invés de provar “Se P então Q” diretamente, provamos o equivalente lógico “Se não Q então não P”.

Exemplo:
Provar: “Se n² é ímpar, então n é ímpar.”
Contrapositiva: “Se n é par, então n² é par.”
Já provamos isso antes! Logo, a afirmação original também é verdadeira.

Dica ninja: se a proposição direta for difícil, tente a contrapositiva. Às vezes, o caminho oposto é mais limpo (e com menos dragões).

3. Prova por Contradição

Assumimos que a afirmação não é verdadeira e mostramos que isso leva a um absurdo lógico (tipo dizer que 2 = 3). É como mostrar que um caminho não pode ser seguido porque ele termina num penhasco lógico.

Exemplo clássico:
Provar que √2 não é racional.
Suponha o contrário: √2 = a/b, onde a e b são inteiros primos entre si.
→ √2 = a/b → 2 = a²/b² → a² = 2b²
→ a² é par → a é par → a = 2k → a² = 4k² → 2b² = 4k² → b² = 2k² → b é par
→ Contradição: a e b não podem ser ambos pares (não são primos entre si).
Logo: √2 é irracional.

4. Exemplos Clássicos

Todo número natural par maior que 2 pode ser escrito como a soma de dois primos. (Hipótese de Goldbach – ainda sem prova geral!)
Se n² é par, então n é par.
Não existe o maior número primo.
- Suponha que existe. Multiplique todos e some 1 → novo número primo → contradição!

5. Dicas para Elaboração de Provas

Leia a proposição como se fosse um contrato: o que se pede?
Identifique hipóteses e conclusão.
Provas diretas: use definições e propriedades conhecidas.
Contraposição: útil quando a conclusão for negativa.
Contradição: ótima para afirmações do tipo “não existe”, “é impossível”.
Use linguagem clara. Matemática é um idioma — escreva bem!

Lembre-se: Não existe “chute técnico” em demonstração. Existe lógica e paciência!

6. Exercícios com Gabarito

1. Qual técnica está sendo usada?
Provar que √5 é irracional assumindo que √5 = a/b, depois mostrando contradição.
A) Prova direta
B) Prova por contraposição
C) Prova por contradição
D) Prova experimental

2. O que é contrapositiva de: “Se João estuda, então João passa”?
A) Se João não estuda, então João não passa
B) Se João não passa, então João não estuda
C) Se João passa, então João estuda
D) Se João não passa, então João não estuda

3. Complete: “Prova por contradição parte da ____ da afirmação original.”
A) conclusão
B) negação
C) contrapositiva
D) hipótese

4. Provar que todo número par pode ser escrito como 2k, onde k é inteiro, é exemplo de:
A) Prova por contradição
B) Prova direta
C) Prova por contraexemplo
D) Indução matemática

5. A prova de que não há número primo maior usando multiplicação de todos os anteriores + 1 é exemplo de:
A) Prova direta
B) Prova por indução
C) Prova por contraposição
D) Prova por contradição

Gabarito

Semana 4 – Indução Matemática

1. Princípio da Indução Matemática

A indução matemática é como empurrar uma fileira infinita de dominós:

Se você derruba o primeiro (caso base),
E garante que cada um derruba o próximo (passo indutivo),
Toda a fileira cairá — mesmo que ela vá até o infinito e além!

Forma geral:

Para provar que uma propriedade P(n) vale para todo n ∈ ℕ:

Base: Prove que P(1) (ou P(0), dependendo do caso) é verdadeira.
Passo indutivo: Suponha que P(k) é verdadeira (hipótese de indução)
→ Prove que P(k+1) também é verdadeira.

2. Provas por Indução Simples e Forte

Indução Simples

Usamos apenas a suposição de que P(k) é verdadeira para provar P(k+1).

Exemplo clássico:

Provar que:
1 + 2 + 3 + ... + n = n(n+1)/2

Base (n = 1):
1 = 1(1+1)/2 → 1 = 1 ✔️

Hipótese (n = k):
1 + 2 + ... + k = k(k+1)/2

Mostrar (n = k+1):
1 + 2 + ... + k + (k+1) = ?

Usando a hipótese:
[k(k+1)/2] + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 ✔️

Indução Forte

Usa a suposição de que P(j) é verdadeira para todo j ≤ k, para provar P(k+1).

Útil quando: o valor de P(k+1) depende de vários casos anteriores.

Exemplo:

Definir sequência de Fibonacci:
F(0) = 0, F(1) = 1, F(n) = F(n–1) + F(n–2)

Provar que F(n) < 2ⁿ, para todo n ≥ 1

3. Aplicações em Sequências e Algoritmos

A indução é o "martelo de Thor" das provas sobre:

Fórmulas de somatórios (ex: somas de progressões)
Sequências definidas por recorrência (Fibonacci, torres de Hanoi)
Corretude de algoritmos recursivos
Análise de complexidade (ex: provar que mergesort é O(n log n))

Exemplo em computação:

def soma_n(n):
    if n == 1:
        return 1
    return n + soma_n(n-1)

Usamos indução para provar que soma_n(n) = n(n+1)/2.

4. Exemplos Detalhados

Exemplo 1:

Provar que 2ⁿ ≥ n + 1 para todo n ≥ 1.

Base: n = 1 → 2¹ = 2 ≥ 2 ✔️

Hipótese: Suponha 2ᵏ ≥ k + 1

Mostrar: 2ᵏ⁺¹ ≥ k + 2
→ 2ᵏ⁺¹ = 2 × 2ᵏ ≥ 2 × (k + 1)
→ 2(k + 1) ≥ k + 2
→ 2k + 2 ≥ k + 2
→ k ≥ 0 ✔️ (válido para k ≥ 1)

Exemplo 2 (indução forte):

Provar que qualquer número natural ≥ 2 pode ser escrito como produto de primos.

Base: 2 = 2 (primo) ✔️

Hipótese forte: Todo número entre 2 e k pode ser escrito como produto de primos.

Mostrar: k + 1 também pode
→ Se k+1 é primo, já está provado
→ Se não é primo, então k+1 = a × b com 2 ≤ a, b ≤ k
→ Pela hipótese, a e b são produtos de primos → então k+1 também é ✔️

5. Reflexões sobre a Importância da Indução

A indução permite provar propriedades infinitas com um número finito de passos.
É a alma da recursividade formal.
Ela é tão poderosa que, sem ela, não provaríamos nem que 1 + 2 + 3 + ... + n funciona.

Analogias úteis:

Indução é como subir uma escada infinita: se você consegue subir o primeiro degrau e cada degrau leva ao próximo, você pode subir para sempre.
Ou como um dominó bem montado: empurra o primeiro e... tcha-ran!

6. Exercícios com Gabarito

1. Qual é o primeiro passo de uma prova por indução?
A) Passo indutivo
B) Suposição da verdade
C) Provar para n = 1 (ou 0)
D) Substituir n por k+1

2. A indução forte é usada quando:
A) O caso base é muito difícil
B) A fórmula envolve somas
C) P(k+1) depende de vários casos anteriores
D) Não temos como provar nada

3. Complete: "Na indução simples, assumimos que P(k) é verdadeira para provar que..."
A) P(n) é verdadeira
B) P(k+1) é verdadeira
C) P(k–1) é falsa
D) Nada pode ser provado

4. Qual técnica é usada para provar propriedades de algoritmos recursivos?
A) Tentativa e erro
B) Indução matemática
C) Contraposição
D) Análise combinatória

5. O que prova a seguinte cadeia? 1 + 2 + ... + n = n(n+1)/2
A) É falsa
B) Só vale para n ≤ 10
C) Foi inventada por Gauss
D) Pode ser provada por indução

Gabarito

Semana 5 – Relações e Funções

1. Definição e Propriedades de Relações

Em matemática discreta, uma relação é basicamente um conjunto de pares ordenados.
Sejam dois conjuntos A e B, uma relação R de A em B é um subconjunto do produto cartesiano A × B.

Exemplo:
A = {1, 2, 3}, B = {a, b}
R = {(1, a), (2, b)} é uma relação de A em B.

Tradução computacional: relações são como tabelas de correspondência, tipo chave-valor.

2. Tipos de Relações

Uma relação R em um conjunto A (ou seja, R: A × A) pode ter propriedades especiais:

Reflexiva

Todo elemento se relaciona com ele mesmo:
(∀a ∈ A) → (a, a) ∈ R

Exemplo: R = {(1,1), (2,2), (3,3), (1,2), (2,3)}
→ Reflexiva se todos (a,a) estiverem no conjunto.

Simétrica

Se (a,b) ∈ R então (b,a) ∈ R

Exemplo: Se (2,3) está na relação, (3,2) também precisa estar.

Transitiva

Se (a,b) ∈ R e (b,c) ∈ R, então (a,c) ∈ R

Exemplo: Se (1,2) ∈ R e (2,3) ∈ R → (1,3) deve estar também.

Dica Mnemônica:

Reflexiva → "Se olha no espelho"
Simétrica → "Retribui o cumprimento"
Transitiva → "Passa o recado adiante"

3. Funções: Injetoras, Sobrejetoras, Bijetoras

Uma função é uma relação especial onde cada elemento do domínio se relaciona com exatamente UM elemento do contradomínio.

Injetora (1 a 1)

Elementos diferentes do domínio vão para elementos diferentes do contradomínio.
Exemplo: f(x) = 2x

Sobrejetora (cobridora)

Todo elemento do contradomínio é atingido por algum valor do domínio.

Bijetora (1 a 1 e sobrejetora)

Cada elemento do domínio casa com um e apenas um elemento do contradomínio, e todos são "casados".
É a função perfeita: não sobra nem falta ninguém.

4. Composição de Funções

Dada f: A → B e g: B → C, a composição g∘f é:
(g∘f)(x) = g(f(x))

Analogia:
É como enviar uma carta ao setor A que redireciona ao setor B, e depois ao setor C.
Ou seja, uma função que passa por várias “estações”.

5. Exemplos no Contexto Computacional

Relações como estruturas de grafos (arestas entre nós)
Funções como métodos de transformação de dados
Composição de funções em pipelines de dados ou funções encadeadas
Relações reflexivas/simétricas/transitivas no design de bancos de dados relacionais
Injetoras/sobrejetoras: úteis para entender hashing, mapas, e criptografia

6. Exercícios com Gabarito

1. Qual propriedade está presente se para todo (a,b) em R, o par (b,a) também está?
A) Reflexiva
B) Simétrica
C) Transitiva
D) Bijetora

2. Uma função f: A → B é sobrejetora se:
A) Cada b ∈ B tem um a ∈ A tal que f(a) = b
B) Cada a ∈ A tem um b ∈ B tal que f(a) ≠ b
C) f(a) = a
D) Nenhum valor é repetido

3. Qual exemplo representa uma função injetora?
A) f(x) = x²
B) f(x) = x + 1
C) f(x) = 0
D) f(x) = sen(x)

4. Qual é a composição de f(x) = x + 2 e g(x) = 3x? (g∘f)(x)
A) 3x + 2
B) x + 6
C) 3(x + 2) = 3x + 6
D) x² + 2

5. Se uma relação é reflexiva, simétrica e transitiva, ela é:
A) Aleatória
B) Equivalência
C) Identidade
D) Binária

Gabarito

Semana 6 – Sequências e Recorrências

1. Sequências Aritméticas e Geométricas

Sequência é uma lista ordenada de elementos, geralmente números.

Sequência Aritmética (PA)

Diferença constante entre termos consecutivos.

Fórmula geral:
aₙ = a₁ + (n - 1)·r
Onde:

a₁: primeiro termo
r: razão da PA
n: posição do termo

Exemplo: 3, 6, 9, 12, ... (razão r = 3)

Sequência Geométrica (PG)

Cada termo é obtido multiplicando o anterior por uma constante (a razão).

Fórmula geral:
aₙ = a₁·qⁿ⁻¹
Onde:

q: razão da PG

Exemplo: 2, 4, 8, 16, ... (razão q = 2)

2. Fórmulas de Recorrência

Uma recorrência é como um quebra-cabeça onde cada peça depende das anteriores.

Definição:
Uma equação que define um termo a partir de um ou mais termos anteriores.

Exemplos clássicos:

Fibonacci: F(n) = F(n−1) + F(n−2), com F(0) = 0, F(1) = 1
Torre de Hanoi: T(n) = 2·T(n−1) + 1
Busca binária (análise de tempo): T(n) = T(n/2) + 1

3. Solução de Recorrências

Resolver uma recorrência = encontrar uma fórmula fechada (sem depender de termos anteriores).

Método 1: Expansão Iterativa

Vai “abrindo” a fórmula até notar um padrão.

Exemplo: T(n) = T(n−1) + 2, T(1) = 1
T(2) = T(1) + 2 = 3
T(3) = T(2) + 2 = 5
T(4) = 7 → T(n) = 2n - 1

Método 2: Fórmulas conhecidas

Algumas sequências famosas já têm solução (como Fibonacci ou PG).

Método 3: Substituição e indução

Você "chuta" a fórmula e prova que ela funciona por indução matemática.

4. Aplicações em Análise de Algoritmos

A análise do tempo de execução de algoritmos, especialmente os recursivos, frequentemente envolve recorrência.

Exemplos:

Merge Sort: T(n) = 2·T(n/2) + n
→ Solução: T(n) = O(n log n)
Busca binária: T(n) = T(n/2) + 1
→ Solução: T(n) = O(log n)
Problemas de dividir para conquistar sempre geram equações de recorrência.

Analogia: Resolver uma recorrência em algoritmo é como descobrir “quanto tempo leva o herói para atravessar todas as fases do jogo, se cada fase depende das anteriores”.

5. Exemplos Ilustrativos

Exemplo 1:

Encontre a fórmula geral da sequência:
aₙ = aₙ₋₁ + 3, com a₁ = 2

Solução por expansão:
a₂ = 2 + 3 = 5
a₃ = 5 + 3 = 8
a₄ = 8 + 3 = 11
→ aₙ = 2 + 3(n−1) = 3n - 1

Exemplo 2 (Análise de Algoritmo):

Dado: T(n) = 2·T(n/2) + n, com T(1) = 1
Vamos resolver por substituição:

T(n) = 2·T(n/2) + n
= 2[2·T(n/4) + n/2] + n
= 4·T(n/4) + 2n
= 8·T(n/8) + 3n
...
= 2^k·T(n/2^k) + kn
Quando n/2^k = 1 → k = log₂n
→ T(n) = n·T(1) + n·log₂n = O(n log n)

6. Exercícios com Gabarito

1. Qual é o 10º termo da PA: 2, 5, 8, ...?
A) 29
B) 30
C) 31
D) 32

2. A fórmula geral da PG 3, 6, 12, 24... é:
A) aₙ = 3n
B) aₙ = 3·2ⁿ
C) aₙ = 3·2ⁿ⁻¹
D) aₙ = 6·n

3. A recorrência T(n) = T(n−1) + 2, com T(1) = 3, tem solução:
A) T(n) = 2n
B) T(n) = 2n + 1
C) T(n) = 2n + 2
D) T(n) = 2n + 1

4. O tempo de execução do Merge Sort é descrito por qual equação de recorrência?
A) T(n) = T(n−1) + 1
B) T(n) = 2T(n/2) + n
C) T(n) = T(n/2) + 1
D) T(n) = n²

5. O que representa uma fórmula de recorrência em algoritmos?
A) O espaço necessário
B) O número de variáveis
C) O tempo de execução com base em subproblemas
D) O número de linhas de código

Gabarito

Semana 7 – Introdução à Teoria dos Grafos

1. Conceitos Básicos: Vértices, Arestas, Grafos Simples

Um grafo é uma estrutura composta por vértices (ou nós) e arestas (ou ligações). Ele pode ser usado para modelar relacionamentos entre objetos.

Vértice (nó): ponto de conexão (ex: uma cidade, uma pessoa, uma página da web).
Aresta (ligação): conexão entre dois vértices (ex: estrada, amizade, link).

Grafo simples:

Não tem laços (aresta que liga um vértice a ele mesmo)
Não tem múltiplas arestas entre o mesmo par de vértices

2. Representações de Grafos: Listas e Matrizes

Existem formas diferentes de representar grafos em programas de computador. As mais comuns são:

Matriz de Adjacência

Uma tabela n×n (n = número de vértices)
Valor 1 indica que há uma aresta entre os vértices i e j, 0 indica ausência.

Exemplo (3 vértices):

Esse grafo liga o 0 com o 1, o 1 com o 2.

Lista de Adjacência

Para cada vértice, temos uma lista de seus vizinhos.

Exemplo:

0 → [1]  
1 → [0, 2]  
2 → [1]

Comparação:

Matriz: rápida consulta, mas gasta mais memória
Lista: eficiente em grafos esparsos (com poucas conexões)

3. Caminhos, Ciclos e Conectividade

Caminho

Sequência de vértices em que cada par consecutivo está conectado por uma aresta.

Exemplo: 0 → 1 → 2

Ciclo

Caminho que começa e termina no mesmo vértice, sem repetir arestas ou vértices (exceto o inicial/final).

Exemplo: 0 → 1 → 2 → 0

Grafo Conexo

Todos os vértices estão conectados, direta ou indiretamente.

Grafo desconexo: existem “ilhas”, ou seja, vértices isolados do resto.

4. Aplicações em Redes e Algoritmos

Grafos não são apenas para nerds da matemática — eles estão por toda parte:

Redes sociais: pessoas como vértices, amizades como arestas
Mapas e GPS: cidades como vértices, estradas como arestas
Navegadores: páginas web como vértices, hyperlinks como arestas
Algoritmos de busca: como o Dijkstra (caminho mais curto) ou DFS/BFS (buscas em profundidade/largura)

Analogia esperta:
Pense no grafo como um “mapa de conexões sociais”. Cada vértice é um amigo, cada aresta uma fofoca que os liga. O grafo te mostra quem sabe de quem, e por onde a fofoca (ou dado) pode chegar mais rápido!

5. Exemplos Práticos

Exemplo 1 – Representação

Dado o grafo com conexões:
A — B, B — C, C — A
Lista de adjacência:

A → [B, C]  
B → [A, C]  
C → [B, A]

Matriz de adjacência:

   A B C
A [0 1 1]  
B [1 0 1]  
C [1 1 0]

Exemplo 2 – Conectividade

Se um grafo tem vértices A, B, C, D onde apenas A — B e C — D, então o grafo não é conexo, pois há duas “ilhas”.

6. Exercícios com Gabarito

1. Qual é o nome da estrutura que contém um conjunto de vértices conectados por arestas?
A) Pilha
B) Fila
C) Grafo
D) Lista

2. Um grafo simples não possui:
A) Vértices
B) Laços ou arestas múltiplas
C) Arestas
D) Caminhos

3. Em qual representação de grafo cada vértice tem uma lista com seus vizinhos?
A) Matriz de adjacência
B) Lista de adjacência
C) Tabela hash
D) Árvore binária

4. O que é um ciclo em um grafo?
A) Um caminho que se repete indefinidamente
B) Um conjunto de vértices isolados
C) Um caminho que começa e termina no mesmo vértice
D) Um grafo sem arestas

5. O grafo é conexo quando:
A) Todos os vértices estão em componentes separados
B) Há pelo menos um laço
C) Existe um caminho entre todo par de vértices
D) Nenhuma aresta é usada duas vezes

Gabarito

Semana 8 – Revisão e Síntese dos Conteúdos

1. Resumo dos Principais Tópicos Abordados

Semana 1 – Lógica Proposicional

Proposições simples e compostas
Operadores lógicos: ¬, ∧, ∨, →, ↔
Tabelas verdade e equivalências
Aplicações no raciocínio lógico de algoritmos

Semana 2 – Lógica de Predicados

Predicados e variáveis
Quantificadores: ∀ (para todo), ∃ (existe)
Negação de proposições quantificadas
Tradução de linguagens naturais para a formal

Semana 3 – Técnicas de Demonstração

Provas diretas e indiretas
Prova por contraposição e contradição
Demonstrações como “debates formais” da matemática
Argumentação lógica aplicada à computação

Semana 4 – Indução Matemática

Princípio da indução
Indução simples: base + passo
Indução forte
Uso em algoritmos recursivos

Semana 5 – Relações e Funções

Relações: reflexivas, simétricas, transitivas
Funções: injetoras, sobrejetoras, bijetoras
Composição e propriedades
Aplicações em estruturas de dados

Semana 6 – Sequências e Recorrências

Sequências aritméticas e geométricas
Fórmulas de recorrência
Resolução de recorrências por substituição
Aplicação em análise de algoritmos (ex: mergesort)

Semana 7 – Teoria dos Grafos

Vértices, arestas, grafos simples
Representações: lista e matriz de adjacência
Caminhos, ciclos, conectividade
Aplicações em redes, rotas, algoritmos (BFS, DFS)

2. Mapas Mentais e Esquemas Visuais

(Representação simplificada — sugiro desenhar em papel ou usar apps como XMind ou FreeMind)

                          [Fundamentos Matemáticos]
                                  |
  -------------------------------------------------------------------
 |           |            |             |           |           |         |
Lógica   Provas   Indução   Funções   Sequências   Grafos   Predicados

Dica mnemônica para lembrar a ordem:
“LógiProInFunSeGraPre”
(leia como um nome estranho de um elfo de RPG — vai ajudar a lembrar!)

3. Dicas para Fixação do Conteúdo

Use cartões de memória (flashcards): ótimo para lógica e definições
Pratique com papel e caneta! O músculo da mente se exercita escrevendo
Tente ensinar alguém: se consegue explicar, é porque entendeu
Refaça exercícios antigos, mas troque os valores dos exemplos
Transforme as provas em desafios de raciocínio lógico

4. Questões de Revisão com Gabarito

1. Qual operador lógico representa a negação?
A) ∧
B) ∨
C) →
D) ¬

2. O quantificador “∀x P(x)” significa:
A) Existe um x tal que P(x) é verdadeiro
B) Para todo x, P(x) é verdadeiro
C) Para algum x, P(x) é falso
D) P(x) é verdadeiro se e somente se x é ímpar

3. Qual método de prova é usado ao assumir o contrário do que se quer provar?
A) Prova direta
B) Indução
C) Contraposição
D) Contradição

4. O que caracteriza uma função bijetora?
A) Nem injetora, nem sobrejetora
B) Apenas injetora
C) Tanto injetora quanto sobrejetora
D) Nenhuma das anteriores

5. A sequência: 2, 4, 6, 8,... é exemplo de:
A) Sequência geométrica
B) Sequência caótica
C) Sequência aritmética
D) Fórmula de recorrência

6. Um grafo é conexo quando:
A) Todos os vértices têm laços
B) Existe ao menos um ciclo
C) Todos os vértices estão ligados (direta ou indiretamente)
D) Nenhuma aresta é duplicada

Gabarito

5. Reflexões Finais sobre a Disciplina

A matemática discreta é a língua mãe da computação. Ela pode parecer rigorosa, mas na verdade é como uma boa música: cheia de ritmo, estrutura e lógica interna. Cada tópico aprendido aqui é como uma engrenagem num relógio digital — essencial para que o tempo da computação funcione sem travar.

Lembre-se: não existe algoritmo sem lógica, nem estrutura sem matemática.

Continue estudando com curiosidade, humor e aquele café esperto ao lado. Porque aprender pode (e deve) ser divertido, mesmo com um pouco de lógica no caminho.