Aula 06 - Estruturas de Dados Homogêneas e Heterogêneas (Listas, Tuplas e Dicionários)

Navegação Rápida

📍 Disciplina: 01 Lógica de Programação | 🗺️ Área: 06 Computação e Telecomunicações | 🏠 Hub Principal

Metadados da Aula

• Área: 06 Computação e Telecomunicações
• Carga Horária Equivalente: 4 horas-aula teóricas e práticas
• Pré-requisitos: Aula 05 - Modularização e Funções
• Palavras-chave: Vetores Dinâmicos, Arrays Contíguos, Tabelas Hash Compactas, SipHash, Tuplas Imutáveis, Conjuntos (Set), Complexidade Big-O, Matriz de Admitância Nodal (Ybus), NBR 5410

---

📌 Sumário da Aula

1. 🧭 1. Contextualização e Objetivos de Aprendizagem
2. 📋 2. Sumário Executivo dos Tópicos
3. ⚡ 3. Fundamentação Teórica e Modelagem Matemática
   • 3.1 Vetores Dinâmicos em CPython: A Mecânica Interna das Listas
   • 3.2 Tuplas: Imutabilidade, Pegada de Memória e Chaves de Hashing
   • 3.3 Tabelas de Dispersão (Hash Tables): Dicionários e Conjuntos com Busca O(1)
   • 3.4 Modelagem Matricial em Sistemas Elétricos de Potência: A Matriz Ybus
4. 🖼️ 4. Diagrama Técnico Integrado
5. 💻 5. Implementação Prática em Engenharia Elétrica
   • 5.1 Dimensionador Automatizado de Condutores por Ampacidade e Queda (NBR 5410)
   • 5.2 Algoritmo de Montagem de Matriz Ybus Esparsa com Dicionários
   • 5.3 Rastreamento Topológico de Ilhamento Elétrico com Conjuntos (set)
6. 📝 6. Banco de Questões de Fixação e Concursos Auditados
   • Questão 01 — Amortização Big-O e Alocação Geométrica de Memória em Listas
   • Questão 02 — Resolução de Colisões em Tabelas Hash e Ataques de Negação de Serviço
   • Questão 03 — Modelagem Esparsa de Topologia de Rede Elétrica: Dicionário versus Matriz Densa
7. 📚 7. Referências Bibliográficas e Normas Técnicas

---

🧭 1. Contextualização e Objetivos de Aprendizagem

O dimensionamento de condutores de uma planta industrial, a simulação estática de fluxo de potência em sistemas interligados com dezenas de milhares de barras ou o despacho centralizado de cargas no Operador Nacional do Sistema (ONS) dependem da organização eficiente de grandes volumes de dados heterogêneos. Selecionar a estrutura de dados inadequada para representar uma topologia de rede pode degradar a complexidade temporal de um algoritmo de $O(1)$ para $O(N)$, inviabilizando a resposta de sistemas de supervisão em tempo real.

Esta aula final de Lógica de Programação estuda a arquitetura interna e a complexidade assintótica das estruturas de dados canônicas do Python 3: listas (vetores dinâmicos de referências contíguas), tuplas (registros imutáveis de alta velocidade), dicionários (tabelas de dispersão compactas com tempo médio de consulta constante) e conjuntos (álgebra booleana de pertinência). Conclui demonstrando a aplicação prática dessas estruturas na modelagem algorítmica da Matriz de Admitância Nodal ($Y_{\text{bus}}$) em Sistemas Elétricos de Potência.

Ao término desta aula, o engenheiro será capaz de:

• Analisar quantitativamente o consumo de memória e a complexidade Big-O de operações de inserção, remoção, busca e fatiamento em listas e dicionários.
• Compreender a mecânica interna de realocação geométrica com sobrealocação (over-allocation) que garante o custo amortizado $O(1)$ para o método append().
• Explicar o funcionamento de tabelas hash compactas (PEP 468) e a resolução de colisões por endereçamento aberto (open addressing) com dispersão criptográfica SipHash.
• Modelar redes elétricas de potência complexas utilizando estruturas de dados esparsas em memória, mitigando em mais de $95\%$ o desperdício computacional em relação a matrizes densas tradicionais.

---

📋 2. Sumário Executivo dos Tópicos

• Listas (list): Vetores dinâmicos de ponteiros indexados a partir de zero. Acesso posicional instantâneo $O(1)$, anexação ao final append() com custo $O(1)$ amortizado e custo $O(N)$ para inserções/deleções no início ou meio da estrutura.
• Tuplas (tuple): Sequências contíguas imutáveis. Eliminam a sobrecarga de capacidade reservada excedente (over-allocation), consumindo menos memória que listas e atuando como chaves válidas de tabelas hash.
• Dicionários (dict): Tabelas de dispersão compactas formadas por uma matriz esparsa de índices e uma matriz densa de entradas (hash, key, value). Busca, inserção e remoção com custo médio constante $O(1)$. Preservam a ordem de inserção deterministicamente desde o Python 3.7.
• Conjuntos (set): Coleções não ordenadas de elementos únicos com busca $O(1)$ baseada em hash. Implementam nativamente a teoria dos conjuntos: união (|), interseção (&), diferença (-) e diferença simétrica (^).
• Matriz de Admitância Nodal ($Y_{\text{bus}}$): Representação matricial $\mathbf{I}={\mathbf{Y}}_{\text{bus}}\mathbf{V}$. Elementos diagonais $Y_{kk}=y_{\text{shunt},k}+\sum y_{km}$; elementos fora da diagonal $Y_{km}=-y_{km}$. Estruturada computacionalmente através de mapeamentos esparsos.

---

⚡ 3. Fundamentação Teórica e Modelagem Matemática

3.1 Vetores Dinâmicos em CPython: A Mecânica Interna das Listas

Em CPython, uma lista (list) não é implementada como uma lista encadeada (linked list) com nós dispersos ligados por ponteiros. Trata-se de um vetor dinâmico de ponteiros contíguos (dynamic array):

3.3.1 Acesso Posicional em Tempo Constante $O(1)$

Como o vetor ob_item é contíguo na memória primária, o endereço físico do elemento no índice $i$ é determinado instantaneamente por simples aritmética de ponteiros da CPU:

$\text{Enderec¸o}(lista[i])=\text{Enderec¸o Base}+i\cdot \text{sizeof}({\text{PyObject}}^{\ast })$

Essa operação consome exatamente uma instrução de soma e deslocamento no hardware, garantindo tempo de acesso estritamente constante $O(1)$.

3.3.2 Sobrealocação Geométrica e Amortização de append()

Quando uma lista atinge sua capacidade máxima (size == allocated) e o método .append() é invocado, o interpretador não aloca apenas espaço para 1 novo elemento (o que exigiria realocar e copiar todo o vetor em cada inserção, gerando complexidade quadrática $O(N^2)$ para $N$ inserções). O CPython aplica a fórmula de Sobrealocação Geométrica (Over-allocation):

${\text{allocated}}_{\text{novo}}=\text{size}+(\text{size}\gg 3)+(\text{size}<9?3:6)$

O fator de expansão assintótico é de aproximadamente $\approx 1,125$ ($12,5\%$ de margem adicional).

Pelo Método Contábil de Amortização:

• A imensa maioria das chamadas .append() consome apenas $1\text{ ciclo}$ de escrita no índice livre subsequente e incremento de size ($O(1)$);
• Raramente ocorre a realocação com cópia de memória (realloc via memmove), cujo custo é $O(N)$;
• Como o custo da realocação é diluído ao longo das $k$ inserções anteriores que não demandaram realocação, o custo médio por operação é matematicamente comprovado como $O(1)$ Amortizado.

Em contrapartida, inserções ou remoções no início da lista (lista.insert(0, x) ou lista.pop(0)) exigem o deslocamento físico de todos os $N$ ponteiros subsequentes na memória, apresentando custo linear obrigatório de $O(N)$.

---

3.2 Tuplas: Imutabilidade, Pegada de Memória e Chaves de Hashing

Uma tupla (tuple) é uma sequência de referências a objetos que, após instanciada, não pode ter seus elementos adicionados, removidos ou reatribuídos.

Vantagens Técnicas frente às Listas:

1. Pegada de Memória Mínima: Como o tamanho é invariante, o interpretador aloca rigorosamente o tamanho necessário (size == allocated), eliminando o desperdício da capacidade de sobrealocação das listas:

3.3.1 Algoritmo de Hashing e Tratamento de Colisões

1. Geração do Hash: A chave $k$ é submetida à função criptográfica/aleatorizada SipHash-2-4 (PEP 456), gerando um número inteiro de 64 bits $h=\text{hash}(k)$.
2. Mapeamento de Índice: O índice inicial na tabela esparsa de tamanho $2^p$ é calculado por máscara binária rápida: ${\text{idx}}_0=h\&(2^p-1)$
3. Resolução de Colisão por Sondagem Aberta Perturbada: Se a posição calculada já estiver ocupada por uma chave distinta ($k_{\text{existente}}\ne k$), o CPython aplica a sequência de perturbação pseudo-aleatória: $\text{perturbac¸a˜o}\leftarrow \text{perturbac¸a˜o}\gg 5$ ${\text{idx}}_{j+1}=(5\cdot {\text{idx}}_j+1+\text{perturbac¸a˜o})\&(2^p-1)$ Essa fórmula garante que todos os índices da tabela sejam visitados ciclicamente sem cair em laços de repetição estéreis.

Graças ao fator de carga rigorosamente controlado (a tabela é redimensionada sempre que a ocupação atinge $2/3$ da capacidade total), o custo de busca, inserção e remoção no caso médio é rigorosamente constante $O(1)$.

---

3.4 Modelagem Matricial em Sistemas Elétricos de Potência: A Matriz $Y_{\text{bus}}$

Em análise de redes elétricas industriais e de transmissão, as tensões nas barras e as correntes injetadas são relacionadas no domínio fasorial pela equação matricial de Kirchhoff:

${\mathbf{I}}_{\text{bus}}={\mathbf{Y}}_{\text{bus}}\cdot {\mathbf{V}}_{\text{bus}}$

Onde ${\mathbf{Y}}_{\text{bus}}$ é a Matriz de Admitância Nodal de dimensão $N\times N$ ($N$ sendo o número total de barras do sistema).

$${\mathbf{Y}}_{\text{bus}}=\left[\begin{array}{cccc}{Y}_{11}& Y_{12}& \cdots & Y_{1N}\\ Y_{21}& Y_{22}& \cdots & Y_{2N}\\ ⋮& ⋮& \ddots & ⋮\\ Y_{N1}& Y_{N2}& \cdots & Y_{NN}\end{array}\right]$$

Regras Sistemáticas de Formação Algorítmica:

1. Elementos Diagonais ($Y_{kk}$ — Auto-admitância da Barra $k$): É a soma de todas as admitâncias diretamente conectadas à barra $k$, incluindo os elementos shunt (reatores, capacitores e admitâncias de magnetização de trafos) e todos os ramos que chegam à barra: $\boxed{Y_{kk}=y_{\text{shunt},k}+\sum _{m\in {\Omega }_k}{y}_{km}}$ Onde ${\Omega }_k$ é o conjunto de todas as barras conectadas à barra $k$ por linhas de transmissão ou transformadores, e $y_{km}=\frac{1}{R_{km}+j{X}_{km}}$ é a admitância série do ramo.
2. Elementos Fora da Diagonal ($Y_{km}$ — Admitância Mútua entre as Barras $k$ e $m$): É o negativo da admitância série do ramo que conecta diretamente a barra $k$ à barra $m$: $\boxed{Y_{km}=-y_{km}(k\ne m)}$ Se não houver linha de transmissão direta entre as barras $k$ e $m$, então $Y_{km}=0+j0$.

O Desafio da Esparsidade em Redes Reais:

Em um sistema elétrico real de grande porte (como a rede do ONS com mais de $N=8000$ barras), a imensa maioria dos nós conecta-se a apenas 2, 3 ou 4 vizinhos. Se implementada como uma matriz densa bidimensional tradicional (lista de listas em Python):

• Consumo de memória: $8000\times 8000\times 16\text{ bytes}\approx 1,024\text{ GB}$;
• Percentual de zeros: mais de $99,9\%$ da matriz é preenchida por zeros estéreis.

A solução da engenharia de computação é utilizar estruturas esparsas baseadas em dicionários:

# Mapeia exclusivamente os ramos existentes (Complexidade de espaco O(E), onde E << N^2)
Ybus_esparsa: dict[tuple[int, int], complex] = {}

Isso reduz o consumo de memória de $1\text{ GB}$ para menos de $5\text{ MB}$ e acelera o cálculo do produto ${\mathbf{Y}}_{\text{bus}}\mathbf{V}$ em centenas de vezes.

---

🖼️ 4. Diagrama Técnico Integrado

O diagrama técnico a seguir sintetiza a organização das estruturas de dados: à esquerda, o contraste entre vetores dinâmicos contíguos (list) e tabelas de dispersão de tempo constante (dict); à direita, a aplicação direta em sistemas elétricos na formação da Matriz de Admitância Nodal $Y_{\text{bus}}$:

---

💻 5. Implementação Prática em Engenharia Elétrica

5.1 Dimensionador Automatizado de Condutores por Ampacidade e Queda (NBR 5410)

O algoritmo a seguir automatiza o dimensionamento técnico de condutores de cobre com isolação de PVC segundo os critérios conjugados de capacidade de condução de corrente (ampacidade) e queda de tensão percentual admissível máxima ($\Delta V\le 4\%$):

"""
Dimensionador Tecnico de Condutores Eletricos segundo a ABNT NBR 5410.
 
Metodo de Instalacao: B1 (Condutores isolados em eletroduto embutido em alvenaria).
Material: Cobre eletrolitico com isolacao em PVC (temperatura de operacao 70 °C).
"""
 
from typing import Dict, Tuple
 
# Banco de Dados Estruturado em Dicionario:
# Chave: Secao Nominal [mm2] -> Valor: Tupla (Capacidade Iz [A], Resistencia a 70°C [Ohm/km])
TABELA_CABOS_NBR5410: Dict[float, Tuple[float, float]] = {
    1.5:  (17.5, 14.80),
    2.5:  (24.0,  8.91),
    4.0:  (32.0,  5.57),
    6.0:  (41.0,  3.71),
    10.0: (57.0,  2.24),
    16.0: (76.0,  1.41),
    25.0: (101.0, 0.889),
    35.0: (125.0, 0.641),
    50.0: (151.0, 0.473),
    70.0: (192.0, 0.328),
    95.0: (232.0, 0.236),
}
 
 
def dimensionar_alimentador(
    corrente_projeto_ib: float,
    comprimento_metros: float,
    tensao_fase_v: float = 220.0,
    queda_max_percentual: float = 4.0,
    is_circuito_trifasico: bool = False,
) -> dict:
    """
    Determina a menor secao de condutor que atende simultaneamente ampacidade e queda.
    """
    secao_adotada = None
    laudo_detalhado = []
 
    # Fator multiplicativo da queda de tensao: 2 para monofasico, sqrt(3) para trifasico
    fator_fases = math.sqrt(3.0) if is_circuito_trifasico else 2.0
 
    for secao, (iz_nominal, r_km) in TABELA_CABOS_NBR5410.items():
        # Criterio 1: Capacidade de Corrente (Iz >= Ib)
        atende_ampacidade = iz_nominal >= corrente_projeto_ib
 
        # Criterio 2: Queda de Tensao
        resistencia_total_linha = (r_km / 1000.0) * comprimento_metros
        delta_v_volts = fator_fases * resistencia_total_linha * corrente_projeto_ib
        queda_percentual = (delta_v_volts / tensao_fase_v) * 100.0
        atende_queda = queda_percentual <= queda_max_percentual
 
        status = atende_ampacidade and atende_queda
 
        laudo_detalhado.append({
            "secao_mm2": secao,
            "iz_amperes": iz_nominal,
            "queda_v": delta_v_volts,
            "queda_pct": queda_percentual,
            "aprovado": status
        })
 
        if status and secao_adotada is None:
            secao_adotada = secao
 
    return {
        "corrente_ib": corrente_projeto_ib,
        "comprimento_m": comprimento_metros,
        "secao_recomendada_mm2": secao_adotada,
        "historico": laudo_detalhado
    }

---

5.2 Algoritmo de Montagem de Matriz $Y_{\text{bus}}$ Esparsa com Dicionários

A rotina a seguir implementa a formação algorítmica da Matriz de Admitância Nodal $Y_{\text{bus}}$ utilizando dicionários com chaves em tuplas imutáveis (barra_k, barra_m) para suportar sistemas com numeração arbitrária de barras:

"""
Modulo de Montagem Algoritmica da Matriz de Admitancia Nodal (Ybus).
Utiliza dicionarios esparsos para representacao computacional eficiente.
"""
 
from typing import Dict, List, Tuple
 
 
class RedeEletricaYbus:
    def __init__(self, lista_barras: List[int]):
        self.barras = sorted(lista_barras)
        # Dicionario esparso: Chave (k, m) -> Valor: Admitancia complexa Y_km
        self.ybus_esparsa: Dict[Tuple[int, int], complex] = {}
        # Elementos shunt de cada barra (capacitores ou reatores para o terra)
        self.admitancia_shunt: Dict[int, complex] = {b: 0.0 + 0.0j for b in self.barras}
 
    def adicionar_elemento_shunt(self, barra: int, y_shunt: complex):
        """Adiciona capacitor ou reator conectado entre a barra e a referencia (terra)."""
        self.admitancia_shunt[barra] += y_shunt
 
    def adicionar_linha_transmissao(self, barra_de: int, barra_para: int, r_ohm: float, x_ohm: float):
        """Insere ramo serie entre as barras k e m."""
        z_serie = complex(r_ohm, x_ohm)
        y_ramo = 1.0 / z_serie
 
        k, m = barra_de, barra_para
 
        # 1. Atualizacao dos termos fora da diagonal (Mutua): Y_km = Y_mk = - y_ramo
        self.ybus_esparsa[(k, m)] = self.ybus_esparsa.get((k, m), 0.0j) - y_ramo
        self.ybus_esparsa[(m, k)] = self.ybus_esparsa.get((m, k), 0.0j) - y_ramo
 
        # 2. Acumulacao da admitancia serie nos termos da diagonal (Auto-admitancia)
        self.ybus_esparsa[(k, k)] = self.ybus_esparsa.get((k, k), 0.0j) + y_ramo
        self.ybus_esparsa[(m, m)] = self.ybus_esparsa.get((m, m), 0.0j) + y_ramo
 
    def finalizar_matriz(self):
        """Incorpora os elementos shunt na diagonal principal da matriz."""
        for b in self.barras:
            self.ybus_esparsa[(b, b)] = self.ybus_esparsa.get((b, b), 0.0j) + self.admitancia_shunt[b]
 
    def obter_elemento(self, k: int, m: int) -> complex:
        """Consulta em tempo constante O(1) de qualquer posicao da matriz Ybus."""
        return self.ybus_esparsa.get((k, m), 0.0 + 0.0j)
 
    def imprimir_matriz_formatada(self):
        print("MATRIZ DE ADMITANCIA NODAL YBUS [Ohms^-1 ou pu]:")
        for k in self.barras:
            linha_str = ""
            for m in self.barras:
                val = self.obter_elemento(k, m)
                linha_str += f"{val.real:+7.3f}{val.imag:+7.3f}j  "
            print(f"Barra {k:2d}: [ {linha_str}]")
 
 
def main():
    # Sistema Teste de 3 Barras
    # Linha 1-2: Z = 0.02 + j0.08 pu
    # Linha 1-3: Z = 0.01 + j0.04 pu
    # Linha 2-3: Z = 0.02 + j0.06 pu
    # Capacitor shunt na Barra 2: Y_shunt = +j0.10 pu
    rede = RedeEletricaYbus(lista_barras=[1, 2, 3])
    rede.adicionar_linha_transmissao(1, 2, 0.02, 0.08)
    rede.adicionar_linha_transmissao(1, 3, 0.01, 0.04)
    rede.adicionar_linha_transmissao(2, 3, 0.02, 0.06)
    rede.adicionar_elemento_shunt(2, complex(0.0, 0.10))
    rede.finalizar_matriz()
 
    rede.imprimir_matriz_formatada()
 
 
if __name__ == "__main__":
    main()

---

5.3 Rastreamento Topológico de Ilhamento Elétrico com Conjuntos (set)

O algoritmo a seguir utiliza conjuntos (set) para determinar se a abertura de disjuntores provocou a desconexão ou ilhamento de barras em relação à barra de referência (slack bus):

def detectar_ilhamento(todas_barras: set[int], linhas_ativas: list[tuple[int, int]], barra_slack: int = 1) -> set[int]:
    """
    Identifica o conjunto de barras eletricamente isoladas utilizando busca em grafo com sets.
    """
    barras_energizadas = {barra_slack}
    houve_expansao = True
 
    # Algoritmo de alcance: propaga conectividade ate saturar
    while houve_expansao:
        tamanho_anterior = len(barras_energizadas)
        for de, para in linhas_ativas:
            if de in barras_energizadas:
                barras_energizadas.add(para)
            elif para in barras_energizadas:
                barras_energizadas.add(de)
        
        # Verifica se novas barras foram alcancadas
        houve_expansao = len(barras_energizadas) > tamanho_anterior
 
    # O conjunto de barras ilhadas e a diferenca de conjuntos: Todas - Energizadas
    barras_ilhadas = todas_barras - barras_energizadas
    return barras_ilhadas

---

📝 6. Banco de Questões de Fixação e Concursos Auditados

Questão 01 — Amortização Big-O e Alocação Geométrica de Memória em Listas

(Petrobras — Engenharia de Equipamentos / Eletrônica — Adaptada)
Um registrador digital de perturbações de subestação armazena amostras transitórias de tensão em tempo real. O engenheiro avalia duas estratégias de código em Python para acumular $N=100.000$ amostras sucessivas em memória:

• Estratégia A: Inserir cada nova amostra no final através do método lista.append(amostra);
• Estratégia B: Inserir cada nova amostra no início através do método lista.insert(0, amostra).
  a) Determine a complexidade assintótica de tempo total ($T_A(N)$ e $T_B(N)$) para a inserção das $N$ amostras em cada estratégia.
  b) Justifique fisicamente a diferença de desempenho com base na organização contígua do vetor ob_item e na rotina memmove da biblioteca padrão C.

💡 Resolução Analítica Passo a Passo:

a) Determinação das Complexidades Big-O:

• Estratégia A (append):
  Como o método append() aproveita a sobrealocação geométrica da lista em CPython, cada inserção ao final é realizada em tempo amortizado $O(1)$.
  Para $N$ amostras consecutivas: $T_A(N)={\sum }_{k=1}^{N}O(1)=\boxed{O(N)(\text{Tempo Linear})}$ Para $N=100.000$, a execução dura frações de milissegundo ($\approx 5\text{ ms}$).
• Estratégia B (insert(0, x)):
  Para inserir um elemento na posição 0 de um vetor contíguo com $k$ elementos, todos os $k$ ponteiros já existentes devem ser fisicamente deslocados uma posição para a direita na memória.
  O tempo da $k$-ésima inserção é proporcional a $k$. Para $N$ amostras consecutivas: $T_B(N)={\sum }_{k=1}^{N}k=\frac{N(N+1)}{2}=\boxed{O(N^2)(\text{Tempo Quadraˊtico})}$ Para $N=100.000$, o número de movimentações na memória é de aproximadamente: $\frac{(10^5{)}^2}{2}=5\times 10^9\text{ operac¸o˜es de ponteiro}$ resultando em um tempo de execução de dezenas de segundos ou minutos, com saturação da CPU.

b) Justificativa em Nível de Hardware:
Em CPython, o array ob_item é um bloco linear contínuo de endereços de memória virtual.
Ao executar insert(0, x), a máquina virtual invoca a função memmove(destino, origem, bytes). Essa chamada bloqueia a CPU enquanto copia milhões de bytes para a direita para abrir espaço de 8 bytes no índice 0, provocando poluição de linhas de cache L1/L2 e invalidação de predições de branch. Na estratégia append(), o ponteiro é simplesmente gravado na próxima posição livre previamente reservada (allocated), sem deslocamento de dados existentes.

---

Questão 02 — Resolução de Colisões em Tabelas Hash e Ataques de Negação de Serviço

(Marinha do Brasil — Corpo de Engenheiros / Computação)
Sistemas supervisórios SCADA que utilizam tabelas de dispersão (hash tables) para indexar comandos de manobra podem ser vulneráveis a ataques de negação de serviço algorítmico (Hash Collision DoS Attacks).
a) Explique o que ocorre com o tempo de consulta e inserção de um dicionário se um invasor forjar intencionalmente centenas de milhares de chaves que resultem exatamente no mesmo valor de hash ($h(k_1)=h(k_2)=\cdots =h(k_N)$).
b) Apresente o mecanismo de segurança incorporado a partir da PEP 456 no Python 3 para neutralizar esse vetor de ataque.

💡 Resolução Analítica Passo a Passo:

a) Degradação Assintótica por Colisões Múltiplas:
A complexidade de tempo de busca em uma tabela de dispersão é $O(1)$ no caso médio sob a hipótese de distribuição uniforme e independente das chaves.
No entanto, se $N$ chaves colidirem no mesmo índice de hash, o mecanismo de resolução de conflitos por endereçamento aberto (open addressing) é forçado a percorrer exaustivamente a sequência completa de sondagem perturbada a cada inserção ou consulta:

• A $k$-ésima inserção demandará a verificação de $k-1$ posições colididas;
• O tempo total para inserir $N$ chaves degrada de $O(N)$ para: $T(N)={\sum }_{k=1}^{N}O(k)=O(N^2)$ Um servidor SCADA que consumiria $10\text{ ms}$ para processar $50.000$ pacotes legítimos consumirá vários minutos de $100\%$ de CPU para processar o lote forjado, causando paralisia operacional no controle da subestação e bloqueio de telemetrias críticas.

b) Mitigação Normativa via PEP 456 (SipHash com Semente Aleatória):
Para mitigar definitivamente essa vulnerabilidade, o Python 3.4+ implementou a especificação PEP 456, adotando a função pseudo-aleatória criptograficamente robusta SipHash-2-4.
A cada inicialização do processo Python, o interpretador gera uma semente secreta de 128 bits (hash seed) obtida do gerador de números aleatórios do sistema operacional (/dev/urandom): $h=\text{SipHash}(\text{chave},\text{semente\_secreta})$ Como a semente varia imprevisivelmente a cada reinicialização e não é exposta externamente pela rede, um invasor remoto é matematicamente incapaz de prever quais sequências de strings colidirão entre si no interpretador do servidor, inviabilizando completamente a geração de ataques DoS por colisão de hash.

---

Questão 03 — Modelagem Esparsa de Topologia de Rede Elétrica: Dicionário versus Matriz Densa

(ENADE — Engenharia Elétrica / Computação)
Deseja-se modelar computacionalmente a rede de distribuição de uma concessionária de energia contendo $N=10.000\text{ barras}$ e $E=12.000\text{ linhas de transmissa˜o/alimentadores}$.
Considere que cada valor de admitância complexa ocupa $16\text{ bytes}$ de memória (dois float de 64 bits para parte real e imaginária) e que cada ponteiro em arquitetura de 64 bits consome $8\text{ bytes}$.
a) Calcule o consumo teórico de memória da Matriz de Admitância Nodal ${\mathbf{Y}}_{\text{bus}}$ implementada como uma matriz densa bidimensional ($N\times N$).
b) Calcule o consumo aproximado utilizando uma estrutura esparsa baseada em dicionário Python, onde apenas os ramos existentes e os termos da diagonal são registrados.
c) Determine o percentual de redução de memória obtido pela abordagem esparsa.

💡 Resolução Analítica Passo a Passo:

a) Memória da Matriz Densa Bidimensional:
Uma matriz densa de $10.000\times 10.000$ contém: $\text{Total de Elementos}=10.000\times 10.000=10^8\text{ posic¸o˜es (100 milho˜es de elementos)}$ Armazenando cada elemento como um objeto complexo de $16\text{ bytes}$: $\text{Memoˊria dos Dados}=10^8\times 16\text{ bytes}=\mathrm{1.600.000.000}\text{ bytes}=1,60\text{ GB}$ Somando os ponteiros da lista de listas ($10.000\text{ listas}\times 10.000\text{ ponteiros}\times 8\text{ bytes}=800\text{ MB}$), o consumo real totaliza: $\text{Memoˊria Densa Total}\approx 1,60\text{ GB}+0,80\text{ GB}=\boxed{2,40\text{ GB}}$

b) Memória da Estrutura Esparsa (Dicionário):
Na matriz $Y_{\text{bus}}$, os únicos elementos não nulos são:

• A diagonal principal: $N=10.000\text{ elementos}$;
• Os ramos mútuos bidirecionais das $E=12.000\text{ linhas}$: $2\times 12.000=24.000\text{ elementos}$.
  Total de entradas não nulas: $\text{Entradas Ativas}=10.000+24.000=34.000\text{ elementos}$ Em um dicionário compacto moderno do CPython:
• Cada entrada densa armazena o hash (8 bytes), ponteiro da tupla-chave (8 bytes) e ponteiro do objeto complexo (8 bytes) $=24\text{ bytes}$;
• A chave é uma tupla de 2 inteiros ($\approx 56\text{ bytes}$);
• O objeto complexo consome $32\text{ bytes}$;
• Custo por entrada: $\approx 24+56+32=112\text{ bytes}$.
  Para 34.000 entradas (com tabela esparsa redimensionada para a potência de dois mais próxima, $65.536\text{ posic¸o˜es}$): $\text{Memoˊria Esparsa Total}\approx 34.000\times 112\text{ bytes}+65.536\times 2\text{ bytes}\approx \mathrm{3.808.000}+131.072\approx \boxed{3,94\text{ MB}}$

c) Redução Percentual: $\text{Reduc¸a˜o}=\left(1-\frac{3,94\text{ MB}}{2400\text{ MB}}\right)\cdot 100\%=\left(1-0,00164\right)\cdot 100\%\approx \boxed{99,84\%}$ A modelagem esparsa com dicionários proporciona uma economia de mais de $99,8\%$ de memória RAM, permitindo carregar toda a rede elétrica nacional na memória cache de processadores embarcados.

---

📚 7. Referências Bibliográficas e Normas Técnicas

1. CORMEN, Thomas H. et al. Algoritmos: Teoria e Prática. 3. ed. Rio de Janeiro: Elsevier, 2012.
2. ABNT NBR 5410:2004 (Versão Corrigida 2008): Instalações Elétricas de Baixa Tensão. Rio de Janeiro: ABNT, 2008.
3. GRAINGER, John J.; STEVENSON, William D. Power System Analysis. New York: McGraw-Hill, 1994.
4. HETTINGER, Raymond. *PEP 468 – Preserving the Order of *kwargs in a Function. Python Enhancement Proposals, 2016.
5. AUMASSON, Jean-Philippe; BERNSTEIN, Daniel J. SipHash: A Fast Short-Input PRF. In: Progress in Cryptology – INDOCRYPT 2012. Lecture Notes in Computer Science, v. 7668, p. 489-508, 2012.
6. MONTICELLI, Alcir. Fluxo de Carga em Redes de Energia Elétrica. São Paulo: Edgard Blücher, 1983.