Teorema de Bayes: Probabilidade Condicional

Teorema de Bayes

• O Teorema de Bayes descreve a probabilidade de um evento com base no conhecimento prévio de condições relacionadas.
• A fórmula do Teorema de Bayes é: $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$
  • $P(A|B)$: Probabilidade a posteriori de A, dado que B é verdadeiro.
  • $P(B|A)$: Probabilidade de B, dado que A é verdadeiro.
  • $P(A)$: Probabilidade a priori de A.
  • $P(B)$: Probabilidade a priori de B.

Dedução do Teorema

• A probabilidade condicional de um evento A, dado que B ocorreu, é $P(A|B) = \frac{P(A\cap B)}{P(B)}$, onde $P(B) \neq 0$.
• A probabilidade conjunta pode ser expressa como $P(A\cap B) = P(A|B)P(B)$ ou $P(A\cap B) = P(B|A)P(A)$.
• Igualando e reorganizando essas expressões resulta no Teorema de Bayes.

Exemplo Prático

• Fábrica A produz 60% das lâmpadas com 5% de defeito, enquanto a fábrica B produz 40% com 10% de defeito.
• Se uma lâmpada defeituosa é selecionada, a probabilidade de ter vindo da fábrica A ($P(A|D)$) é calculada usando o Teorema de Bayes.
• $P(A) = 0.60$, $P(B) = 0.40$, $P(D|A) = 0.05$, $P(D|B) = 0.10$.
• A probabilidade total de uma lâmpada ser defeituosa é $P(D) = P(D|A)P(A) + P(D|B)P(B) = 0.07$.
• A probabilidade de que a lâmpada defeituosa tenha vindo da fábrica A é $P(A|D) = \frac{(0.05)(0.60)}{0.07} \approx 0.4286$.

Algoritmos de Busca

• Algoritmos de busca podem ser não informados (cegos) ou informados (heurísticos).

Busca Não Informada

• Não usam conhecimento específico do problema.
• Busca em Largura (BFS)
  • Explora nós por nível, usando uma fila.
  • Completa e ótima se o custo do passo for 1.
  • Complexidade: Tempo e Espaço $O(b^d)$.
• Busca em Profundidade (DFS)
  • Explora o caminho mais profundo, usando uma pilha.
  • Não é completa e não é ótima.
  • Complexidade: Tempo $O(b^m)$, Espaço $O(bm)$.
• Busca de Custo Uniforme
  • Expande o nó de menor custo, usando uma fila de prioridade.
  • Completa e ótima se o custo do passo for maior que 0.
  • Complexidade: Espaço e tempo $O(b^{C/\epsilon})$.
• Busca em Profundidade Limitada
  • DFS com limite de profundidade $l$.
  • Não é completa e não é ótima.
  • Complexidade: Tempo $O(b^l)$, Espaço $O(bl)$.
• Busca de Aprofundamento Iterativo (IDS)
  • DFS com profundidade limitada, aumentando o limite a cada iteração.
  • Completa e ótima se o custo do passo for 1.
  • Complexidade: Tempo $O(b^d)$, Espaço $O(bd)$.

Busca Informada (Heurística)

• Usa função heurística $h(n)$ para estimar o custo do caminho de $n$ até o objetivo.
• Busca Gananciosa (Gulosa)
  • Expande o nó mais próximo do objetivo (menor $h(n)$).
  • Não é completa e não é ótima.
  • Complexidade: Tempo e Espaço $O(b^m)$.
• Busca A*
  • Combina o custo do caminho $g(n)$ com a estimativa $h(n)$: $f(n) = g(n) + h(n)$.
  • Completa e ótima se $h(n)$ for admissível.
  • Complexidade exponencial no pior caso.
• Heurísticas Admissíveis
  • Nunca superestimam o custo real para chegar ao objetivo.
  • Exemplo: Distância em linha reta.
• Heurísticas Consistentes
  • $h(n) \leq c(n, a, n') + h(n')$.
  • Se $h(n)$ é consistente, então é admissível.
• Dominância
  • Se $h_1(n) \geq h_2(n)$ para todos os $n$, $h_1$ domina $h_2$.

Otimização

• Algoritmos Genéticos
  • Evoluem soluções candidatas usando seleção, cruzamento e mutação.
  • Adequado para problemas complexos.
• Algoritmo Hill-Climbing (Subida da Encosta)
  • Melhora iterativamente a solução movendo-se para a solução vizinha de maior valor.
  • Pode ficar preso em máximos locais.
• Simulated Annealing (Têmpera Simulada)
  • Aceita movimentos piores com probabilidade decrescente para escapar de máximos locais.

Problemas de Satisfação de Restrições (CSP)

• Atribuir valores a variáveis para satisfazer restrições.
• Backtracking Search
  • Atribui valores recursivamente, retrocedendo se uma restrição é violada.
• Heurísticas para CSP
  • MRV (Minimum Remaining Values): Variável com menos valores possíveis.
  • LCV (Least Constraining Value): Valor que menos restringe os vizinhos.
• Inferência
  • Reduz o espaço de busca eliminando valores inconsistentes.
  • Node Consistency: Remove valores que violam restrições unárias.
  • Arc Consistency: Remove valores de X que não têm suporte em Y para $X \rightarrow Y$.

Teoria dos Jogos

• Jogo de Soma Zero
  • Ganho de um jogador é a perda do outro.
• Estratégia Dominante
  • Sempre a melhor escolha, independentemente do oponente.
• Equilíbrio de Nash
  • Conjunto de estratégias onde ninguém pode melhorar mudando sozinho.
• Algoritmo Minimax
  • Encontra a melhor jogada assumindo que o oponente joga otimamente.
  • Alfa-Beta Pruning: Otimização que elimina ramos irrelevantes.

Algorithmus 1 Berechnung der Quadratwurzel

• Eingabe:* Eine natürliche Zahl $n$
• Ausgabe:* $\lfloor \sqrt{n} \rfloor$

1. Setze $x \leftarrow 0$ und $y \leftarrow 1$
2. Solange $y \leq n$ gilt:

• Erhöhe $x$ um 1
• Erhöhe $y$ um $2x + 1$

3. Gib $x$ zurück

Analyse

• Korrektheit:*
• Die Schleife berechnet sukzessive die Quadratzahlen $1, 4, 9, 16, \dots$
• In jedem Schleifendurchlauf wird $x$ um 1 erhöht, und $y$ enthält den Wert von $x^2$. Die Schleife wird solange ausgeführt, wie $x^2 \leq n$ gilt.
• Sobald $x^2 > n$ gilt, wird die Schleife verlassen, und $x$ enthält den Wert von $\lfloor \sqrt{n} \rfloor$.
• Laufzeit:*
• Die Schleife wird $\lfloor \sqrt{n} \rfloor$ mal ausgeführt.
• Jeder Schleifendurchlauf benötigt konstante Zeit.
• Daher ist die Laufzeit von Algorithmus 1 $O(\sqrt{n})$.

Beispiel

Für $n = 10$ ergibt sich folgende Ausführung:

Der Algorithmus gibt den Wert $x = 3$ zurück, was korrekt ist, da $\lfloor \sqrt{10} \rfloor = 3$.