# Algoritmos Probabilísticos (Randomized Algorithms)

### 📌 Visão Geral

**Algoritmos probabilísticos** (ou randomizados) utilizam **aleatoriedade** como parte de sua lógica para resolver problemas. Diferente de algoritmos determinísticos (que sempre produzem o mesmo resultado para a mesma entrada), algoritmos randomizados podem ter diferentes saídas ou tempos de execução a cada execução.

```
Entrada → [Aleatoriedade] → Processamento → Saída (com alta probabilidade)
                         ↓
                   Pode errar, mas com probabilidade controlável
```

#### Analogia

> *"Algoritmos determinísticos são como seguir uma receita de bolo exata: sempre dá no mesmo. Algoritmos probabilísticos são como cozinhar 'a olho': funciona na maioria das vezes, é mais rápido, mas pode dar errado ocasionalmente."*

***

### 🏷️ Tipos de Algoritmos Probabilísticos

| Tipo            | Descrição                                            | Exemplo                              |
| --------------- | ---------------------------------------------------- | ------------------------------------ |
| **Monte Carlo** | Resposta pode estar errada (com baixa probabilidade) | Teste de primalidade de Miller-Rabin |
| **Las Vegas**   | Resposta sempre correta, tempo pode variar           | QuickSort Aleatório                  |
| **Sherwood**    | Elimina casos ruins de algoritmos determinísticos    | QuickSort com pivô aleatório         |
| **Aproximação** | Resposta aproximada (mas dentro de um fator)         | Simulated Annealing                  |

***

### 📋 Algoritmos por Categoria

#### 🧪 Monte Carlo (Resposta com erro controlado)

| Algoritmo        | Problema             | Probabilidade de Erro | Aplicação          |
| ---------------- | -------------------- | --------------------- | ------------------ |
| **Miller-Rabin** | Teste de primalidade | 4⁻ᵏ (k iterações)     | Criptografia (RSA) |
| **Monte Carlo**  | Simulação/integração | Configurável          | Física, finanças   |

#### 🎲 Las Vegas (Tempo aleatório, resposta correta)

| Algoritmo               | Problema           | Complexidade Esperada | Aplicação       |
| ----------------------- | ------------------ | --------------------- | --------------- |
| **QuickSort Aleatório** | Ordenação          | O(n log n)            | Ordenação geral |
| **Sherwood**            | Eliminar pior caso | Variável              | Otimização      |

#### 🔄 Otimização

| Algoritmo               | Problema             | Tipo         | Aplicação             |
| ----------------------- | -------------------- | ------------ | --------------------- |
| **Random Walk**         | Exploração de espaço | Markov chain | Modelagem financeira  |
| **Simulated Annealing** | Otimização global    | Metropolis   | Problemas NP-difíceis |

#### 📊 Estruturas de Dados

| Algoritmo            | Problema             | Falso Positivo     | Aplicação          |
| -------------------- | -------------------- | ------------------ | ------------------ |
| **Filtros de Bloom** | Teste de pertinência | Sim (configurável) | Caching, databases |

***

### 🔢 Algoritmos em Detalhe

#### 1. Filtros de Bloom

**Como funciona:** Estrutura de dados probabilística que testa se um elemento pertence a um conjunto.

```python
import hashlib
import math

class BloomFilter:
    def __init__(self, n, p):
        """
        n: número esperado de elementos
        p: probabilidade de falso positivo
        """
        self.n = n
        self.p = p
        
        # Tamanho do vetor (bits)
        self.m = int(-(n * math.log(p)) / (math.log(2) ** 2))
        
        # Número de funções hash
        self.k = int((self.m / n) * math.log(2))
        
        self.bits = [False] * self.m
        self.hash_count = self.k
    
    def _hash(self, item, seed):
        """Função hash com seed diferente"""
        return int(hashlib.md5(f"{seed}{item}".encode()).hexdigest(), 16) % self.m
    
    def add(self, item):
        for i in range(self.k):
            self.bits[self._hash(item, i)] = True
    
    def contains(self, item):
        for i in range(self.k):
            if not self.bits[self._hash(item, i)]:
                return False
        return True

# Exemplo
bf = BloomFilter(n=1000, p=0.01)  # 1000 elementos, 1% falso positivo

# Adicionar elementos
bf.add("maçã")
bf.add("banana")

# Verificar
print(bf.contains("maçã"))   # True
print(bf.contains("banana")) # True
print(bf.contains("laranja")) # False (provavelmente)
```

| Característica     | Valor                                     |
| ------------------ | ----------------------------------------- |
| **Falso negativo** | ❌ Não (se diz que não está, é verdade)    |
| **Falso positivo** | ✅ Sim (pode dizer que está, mas não está) |
| **Remoção**        | ❌ Não (não suporta)                       |
| **Espaço**         | O(m) bits                                 |
| **Tempo**          | O(k) por operação                         |

**Quando usar:** Caches, sistemas de recomendação, prevenção de duplicatas.

***

#### 2. Miller-Rabin (Teste de Primalidade)

**Como funciona:** Teste probabilístico que determina se um número é primo.

```python
import random

def miller_rabin(n, k=10):
    """
    Teste de primalidade de Miller-Rabin
    n: número a testar
    k: número de iterações (probabilidade de erro = 4⁻ᵏ)
    """
    if n < 2:
        return False
    if n in [2, 3]:
        return True
    if n % 2 == 0:
        return False
    
    # Escrever n-1 como d * 2^r
    r, d = 0, n - 1
    while d % 2 == 0:
        d //= 2
        r += 1
    
    def teste(a):
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return True
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                return True
        return False
    
    for _ in range(k):
        a = random.randint(2, n - 2)
        if not teste(a):
            return False
    
    return True

# Exemplo
print(miller_rabin(17))      # True (primo)
print(miller_rabin(100))     # False (composto)
print(miller_rabin(561))     # False (pseudoprimo de Carmichael)

# Número grande (2048 bits) - usado em RSA
# Probabilidade de erro: 4⁻²⁰ ≈ 1 em 1 trilhão
```

| Característica            | Valor                         |
| ------------------------- | ----------------------------- |
| **Tempo**                 | O(k × log³ n)                 |
| **Probabilidade de erro** | 4⁻ᵏ (k iterações)             |
| **Determinístico**        | ❌ (mas aceito pela indústria) |

**Quando usar:** Geração de primos grandes para criptografia (RSA, Diffie-Hellman).

***

#### 3. QuickSort Aleatório (Las Vegas)

**Como funciona:** QuickSort que escolhe o pivô aleatoriamente, evitando o pior caso O(n²).

```python
import random

def quicksort_aleatorio(arr):
    if len(arr) <= 1:
        return arr
    
    # Pivô aleatório (evita pior caso)
    pivot = random.choice(arr)
    
    esquerda = [x for x in arr if x < pivot]
    meio = [x for x in arr if x == pivot]
    direita = [x for x in arr if x > pivot]
    
    return quicksort_aleatorio(esquerda) + meio + quicksort_aleatorio(direita)

# Versão in-place
def quicksort_aleatorio_inplace(arr, baixo=0, alto=None):
    if alto is None:
        alto = len(arr) - 1
    
    if baixo < alto:
        # Pivô aleatório
        pivot_idx = random.randint(baixo, alto)
        arr[pivot_idx], arr[alto] = arr[alto], arr[pivot_idx]
        
        p = particao(arr, baixo, alto)
        quicksort_aleatorio_inplace(arr, baixo, p - 1)
        quicksort_aleatorio_inplace(arr, p + 1, alto)

def particao(arr, baixo, alto):
    pivot = arr[alto]
    i = baixo - 1
    
    for j in range(baixo, alto):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[alto] = arr[alto], arr[i + 1]
    return i + 1

# Exemplo
arr = [3, 7, 8, 5, 2, 1, 9, 5, 4]
quicksort_aleatorio_inplace(arr)
print(arr)  # [1, 2, 3, 4, 5, 5, 7, 8, 9]
```

| Característica  | Determinístico           | Aleatório               |
| --------------- | ------------------------ | ----------------------- |
| **Melhor caso** | O(n log n)               | O(n log n)              |
| **Pior caso**   | O(n²) (ordenado/reverso) | O(n log n) (prob. alta) |
| **Esperado**    | O(n log n)               | O(n log n)              |

**Quando usar:** Sempre! O pivô aleatório elimina o pior caso na prática.

***

#### 4. Monte Carlo (Simulação)

**Como funciona:** Usa amostragem aleatória para aproximar resultados.

```python
import random
import math

def monte_carlo_pi(n):
    """Estimar π usando amostragem aleatória"""
    pontos_dentro = 0
    
    for _ in range(n):
        x = random.uniform(-1, 1)
        y = random.uniform(-1, 1)
        if x*x + y*y <= 1:
            pontos_dentro += 1
    
    return 4 * pontos_dentro / n

# Exemplo: estimar π
pi_estimado = monte_carlo_pi(1000000)
print(f"π estimado: {pi_estimado}")
print(f"Erro: {abs(pi_estimado - math.pi):.6f}")
```

```python
def monte_carlo_integral(f, a, b, n=10000):
    """Estimar integral definida usando Monte Carlo"""
    area_total = (b - a) * max(f(a), f(b))
    pontos_abaixo = 0
    
    for _ in range(n):
        x = random.uniform(a, b)
        y = random.uniform(0, area_total / (b - a))
        if y <= f(x):
            pontos_abaixo += 1
    
    return area_total * (pontos_abaixo / n)

# Exemplo: integral de x² de 0 a 2
f = lambda x: x**2
resultado = monte_carlo_integral(f, 0, 2, 100000)
print(f"Integral estimada: {resultado}")
print(f"Valor exato: {8/3:.4f}")
```

| Característica       | Valor                                     |
| -------------------- | ----------------------------------------- |
| **Precisão**         | O(1/√n)                                   |
| **Erro**             | Configurável (mais amostras = menor erro) |
| **Dimensionalidade** | Funciona bem em alta dimensão             |

**Quando usar:** Problemas de alta dimensionalidade, simulações físicas, finanças.

***

#### 5. Random Walk (Caminho Aleatório)

**Como funciona:** Sequência de passos aleatórios em um espaço.

```python
import random
import matplotlib.pyplot as plt

def random_walk_1d(n):
    """Caminho aleatório unidimensional"""
    posicao = 0
    caminho = [posicao]
    
    for _ in range(n):
        passo = random.choice([-1, 1])
        posicao += passo
        caminho.append(posicao)
    
    return caminho

def random_walk_2d(n):
    """Caminho aleatório bidimensional"""
    x, y = 0, 0
    caminho_x, caminho_y = [x], [y]
    
    for _ in range(n):
        direcao = random.choice(['N', 'S', 'L', 'O'])
        if direcao == 'N': y += 1
        elif direcao == 'S': y -= 1
        elif direcao == 'L': x += 1
        else: x -= 1
        
        caminho_x.append(x)
        caminho_y.append(y)
    
    return caminho_x, caminho_y

# Exemplo 1D
caminho = random_walk_1d(1000)
print(f"Posição final: {caminho[-1]}")
print(f"Distância média esperada: √n ≈ {1000**0.5:.1f}")

# Exemplo 2D (descomente para plotar)
# x, y = random_walk_2d(10000)
# plt.plot(x, y)
# plt.title("Random Walk 2D")
# plt.show()
```

| Característica         | Valor                             |
| ---------------------- | --------------------------------- |
| **Distância esperada** | O(√n) (1D)                        |
| **Recorrência**        | 1D/2D: retorna à origem; 3D+: não |

**Quando usar:** Modelagem de difusão, algoritmos de busca, finanças (movimento browniano).

***

#### 6. Sherwood (Eliminação de Casos Ruins)

**Como funciona:** Adiciona aleatoriedade para eliminar casos de pior desempenho.

```python
import random

def busca_binaria_sherwood(arr, alvo):
    """
    Busca binária com shuffle inicial (evita pior caso)
    """
    # Cópia aleatória (Sherwood)
    arr_copy = arr.copy()
    random.shuffle(arr_copy)
    
    # Ordenar para busca binária
    arr_copy.sort()
    
    # Busca binária normal
    esq, dir = 0, len(arr_copy) - 1
    while esq <= dir:
        meio = (esq + dir) // 2
        if arr_copy[meio] == alvo:
            return True
        elif arr_copy[meio] < alvo:
            esq = meio + 1
        else:
            dir = meio - 1
    return False

# QuickSort com pivô aleatório (forma de Sherwood)
def quicksort_sherwood(arr):
    """
    QuickSort que randomiza a entrada (elimina pior caso)
    """
    if len(arr) <= 1:
        return arr
    
    # Sherwood: randomiza a entrada
    random.shuffle(arr)
    
    pivot = arr[0]
    esq = [x for x in arr[1:] if x <= pivot]
    dir = [x for x in arr[1:] if x > pivot]
    
    return quicksort_sherwood(esq) + [pivot] + quicksort_sherwood(dir)
```

**Quando usar:** Quando o algoritmo tem pior caso raro, mas possível (ex: QuickSort com dados ordenados).

***

#### 7. Simulated Annealing (Recozimento Simulado)

**Como funciona:** Técnica de otimização inspirada na têmpera de metais.

```python
import random
import math

def simulated_annealing(funcao_objetivo, vizinhanca, temperatura_inicial=1000, 
                        temperatura_final=0.01, resfriamento=0.995, iteracoes_por_temp=100):
    """
    Simulated Annealing para otimização global
    
    funcao_objetivo: função a minimizar
    vizinhanca: função que gera vizinhos
    """
    # Solução inicial aleatória
    solucao_atual = vizinhanca(seed=True)
    valor_atual = funcao_objetivo(solucao_atual)
    
    melhor_solucao = solucao_atual.copy()
    melhor_valor = valor_atual
    
    T = temperatura_inicial
    
    while T > temperatura_final:
        for _ in range(iteracoes_por_temp):
            # Gerar vizinho
            novo = vizinhanca(solucao_atual)
            valor_novo = funcao_objetivo(novo)
            
            # Aceitar se melhor
            if valor_novo < valor_atual:
                solucao_atual = novo
                valor_atual = valor_novo
                
                if valor_novo < melhor_valor:
                    melhor_solucao = novo.copy()
                    melhor_valor = valor_novo
            else:
                # Aceitar com probabilidade (pior solução)
                delta = valor_novo - valor_atual
                probabilidade = math.exp(-delta / T)
                if random.random() < probabilidade:
                    solucao_atual = novo
                    valor_atual = valor_novo
        
        # Resfriar
        T *= resfriamento
    
    return melhor_solucao, melhor_valor

# Exemplo: encontrar mínimo da função f(x) = x² + sin(x)
def exemplo_otimizacao():
    def f(x):
        return x**2 + math.sin(x)
    
    def vizinhanca(x=None, seed=False):
        if seed:
            return random.uniform(-10, 10)
        return x + random.uniform(-1, 1)
    
    melhor_x, melhor_valor = simulated_annealing(f, vizinhanca)
    print(f"Mínimo encontrado: x={melhor_x:.4f}, f(x)={melhor_valor:.4f}")
    print(f"Mínimo global esperado: x≈-0.5, f(x)≈-0.5")

# exemplo_otimizacao()
```

| Característica              | Valor                        |
| --------------------------- | ---------------------------- |
| **Tipo**                    | Otimização global            |
| **Escapa de ótimos locais** | ✅ Sim                        |
| **Garantia**                | Converge probabilisticamente |

**Quando usar:** Problemas NP-difíceis (caixeiro viajante), otimização de parâmetros, design de redes.

***

### 📊 Comparação de Algoritmos

| Algoritmo               | Tipo        | Erro           | Tempo       | Aplicação Principal |
| ----------------------- | ----------- | -------------- | ----------- | ------------------- |
| **Filtro de Bloom**     | Monte Carlo | Falso positivo | O(k)        | Caching             |
| **Miller-Rabin**        | Monte Carlo | 4⁻ᵏ            | O(k log³ n) | Primalidade         |
| **QuickSort Aleatório** | Las Vegas   | 0              | O(n log n)  | Ordenação           |
| **Monte Carlo**         | Monte Carlo | Configurável   | O(n)        | Simulação           |
| **Random Walk**         | Markov      | 0              | O(n)        | Exploração          |
| **Sherwood**            | Las Vegas   | 0              | Variável    | Eliminar pior caso  |
| **Simulated Annealing** | Aproximação | Aproximado     | O(iters)    | Otimização          |

***

### 🎯 Guia de Seleção

#### "Preciso testar se um número é primo..."

| Seu cenário                    | Use                                        |
| ------------------------------ | ------------------------------------------ |
| Números pequenos (< 10¹²)      | Teste determinístico                       |
| Números grandes (criptografia) | Miller-Rabin (k=20)                        |
| Segurança máxima               | Miller-Rabin (k=40) + teste determinístico |

#### "Preciso ordenar uma lista..."

| Seu cenário          | Use                          |
| -------------------- | ---------------------------- |
| Geral                | QuickSort Aleatório          |
| Não confio nos dados | QuickSort Aleatório (sempre) |

#### "Preciso verificar se um elemento está em um conjunto..."

| Seu cenário                                | Use             |
| ------------------------------------------ | --------------- |
| Memória limitada, falso positivo aceitável | Filtro de Bloom |
| Memória abundante, precisão absoluta       | HashSet         |

#### "Preciso otimizar uma função complexa..."

| Seu cenário                     | Use                   |
| ------------------------------- | --------------------- |
| Função convexa                  | Gradiente descendente |
| Função com muitos ótimos locais | Simulated Annealing   |
| Espaço discreto (ex: TSP)       | Simulated Annealing   |

***

### 🔗 Links Úteis

* [Bloom Filters - Interactive Demo](https://www.jasondavies.com/bloomfilter/)
* [Miller-Rabin Visualization](https://www.wolframcloud.com/objects/demonstrations/MillerRabinPrimalityTest-source.nb)
* [Simulated Annealing Demo](https://www.mathworks.com/help/gads/simulated-annealing.html)

***

### 📚 Livros Recomendados

| Livro                     | Autor               | Foco       |
| ------------------------- | ------------------- | ---------- |
| Randomized Algorithms     | Motwani, Raghavan   | Teoria     |
| Probability and Computing | Mitzenmacher, Upfal | Aplicações |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos/algoritmos-probabilisticos-randomized-algorithms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.