do Estruturas de dados e seus algoritmos – Superior
Plano de aulas da disciplina de Estruturas de Dados e Algoritmos (ADS, INF006). São 36 encontros em quatro blocos: 32 aulas e 4 apresentações de projeto (aulas 9, 18, 27 e 36). Fora dos 36 encontros há um anexo, Base Prática em C (módulos B1 a B5, para estudar antes do bloco 1), e um bloco complementar opcional que aprofunda a ordenação (C1 a C5).
- Teoria, a partir de Cormen et al., Algoritmos: teoria e prática (3ª edição), com as figuras do livro e o pseudocódigo em português.
- Prática em C: implementação comentada, testada, para baixar e rodar.
- Experimento: uma hipótese tirada da teoria, um programa em C que mede, e o gráfico do medido contra a curva teórica. Rode na sua máquina:
gcc -O2 arquivo.c -o exp -lm && ./exp. - Conexões: onde o conceito aparece em outras áreas da computação.
Anexo Base Prática em C
Cinco módulos de apoio, antes do bloco 1, com o C que as estruturas de dados exigem além do básico: memória e alocação dinâmica, ponteiros (simples, duplos, para funções e para structs), structs, funções genéricas e arquivos.
B1 Memória: pilha, heap e alocação dinâmica AnexoKernighan e Ritchie, C: a linguagem de programação, seções 5.4 e 8.7; Cormen et al., seção 10.3
Objetivos
- Distinguir a pilha (variáveis locais) do heap (alocação dinâmica)
- Usar malloc, calloc, realloc e free corretamente
- Reconhecer vazamentos, ponteiros soltos e liberações duplas
- Medir quanto um malloc pequeno custa em bytes e em tempo
Experimento
Quantos bytes de heap e quantos nanossegundos custa cada malloc de 16 bytes?
Cada malloc de 16 bytes ocupa 32 bytes e custa dezenas de nanossegundos. Uma lista ligada de inteiros gasta muito mais memória e tempo que um vetor com os mesmos dados. É por isso que estruturas de alto desempenho alocam em blocos (pools) e por isso a aula 16 mostra listas guardadas em vetores.
Conexões
- Sistemas operacionais: malloc pede páginas ao kernel com brk e mmap; a memória virtual e a paginação ficam por trás de cada ponteiro.
- Segurança: Estouros de buffer e uso após free são as falhas mais exploradas da história; linguagens como Rust impedem esses erros já na compilação.
- Linguagens com coleta de lixo: Java, Python e Go liberam a memória sozinhas (coletor de lixo); C dá controle total, e a responsabilidade junto.
- Sistemas embarcados: Em microcontroladores com poucos KB, o heap fragmenta: por isso o padrão MISRA C proíbe malloc depois da inicialização.
B2 Ponteiros: endereços, aritmética e ponteiro para ponteiro AnexoKernighan e Ritchie, C: a linguagem de programação, capítulo 5; Cormen et al., seção 10.3
Objetivos
- Usar & e * e entender o que um ponteiro guarda
- Relacionar vetores e ponteiros pela aritmética de ponteiros
- Passar parâmetros por referência e alterar um ponteiro dentro de uma função (int **)
- Alocar matrizes dinâmicas e medir o efeito da ordem de percurso
Experimento
Percorrer uma matriz por linhas e por colunas custa o mesmo tempo por elemento?
A mesma conta, na ordem errada, fica 30 vezes mais lenta para \(n = 4096\). Ponteiros dão acesso direto à memória, e a memória tem geografia: vizinhos são baratos, saltos são caros. Nas próximas aulas, a mesma lição aparece em listas ligadas (aula 14) e em grafos (aula 29).
Conexões
- Sistemas operacionais: O kernel manipula páginas, processos e dispositivos por ponteiros; um ponteiro inválido no kernel derruba a máquina inteira.
- Compiladores: Otimizadores trocam a ordem de laços (loop interchange) para percorrer matrizes por linhas; a análise de aliasing decide se dois ponteiros podem se sobrepor.
- Hardware e GPUs: Bibliotecas de álgebra linear (BLAS) e GPUs dividem matrizes em blocos que cabem no cache: o mesmo efeito do experimento, explorado ao máximo.
- Bancos de dados: Bancos orientados a linhas (OLTP) e a colunas (OLAP, como DuckDB) são as duas ordens do experimento: cada um vence num tipo de consulta.
B3 Structs: registros, ponteiros para structs e nós AnexoKernighan e Ritchie, C: a linguagem de programação, capítulo 6; Cormen et al., seção 10.3
Objetivos
- Declarar structs com typedef e acessar campos com . e ->
- Construir vetores de structs e structs autorreferentes (nós)
- Entender alinhamento e preenchimento (sizeof, offsetof)
- Medir vetor de structs (AoS) contra struct de vetores (SoA)
Experimento
Somar um único campo de n registros custa o mesmo num vetor de structs (AoS) e num vetor só com aquele campo (SoA)?
A organização dos dados na memória muda o desempenho em 5 vezes, com o mesmo algoritmo. Agrupar em structs é o natural para programar; separar em vetores é o natural para o hardware. Bancos colunares, motores de jogos e bibliotecas de ciência de dados escolhem SoA pelo mesmo motivo.
Conexões
- Redes: Cabeçalhos IP, TCP e Ethernet são structs com campos em posições fixas; o preenchimento errado corrompe pacotes (__attribute__((packed))).
- Sistemas de arquivos: O inode do Linux e as entradas de diretório são structs gravadas no disco byte a byte.
- Motores de jogos: Arquiteturas entity component system guardam cada componente (posição, velocidade) num vetor próprio: SoA para atualizar milhões de objetos por quadro.
- Ciência de dados: NumPy, pandas e Apache Arrow guardam cada coluna num vetor contíguo: é o SoA do experimento, e a razão de serem tão rápidos.
B4 Funções: recursão, ponteiros para funções e código genérico AnexoKernighan e Ritchie, C: a linguagem de programação, seções 4.10, 5.11 e B.5
Objetivos
- Entender a pilha de chamadas e o custo de memória da recursão
- Declarar e usar ponteiros para funções
- Escrever código genérico com void * e qsort
- Medir os bytes de pilha por chamada e as comparações do qsort
Experimento
Quantos bytes de pilha cada chamada recursiva usa? Quantas vezes o qsort chama o comparador?
A pilha cresce exatamente em linha reta com a profundidade (um quadro de tamanho fixo por chamada), e o qsort chama o comparador \(n\lg n - 1{,}26\,n\) vezes: a fórmula do merge sort. Medir revela o que a biblioteca faz por dentro: o nome diz “quick”, mas o comportamento é de merge sort.
Conexões
- Sistemas operacionais: Tratadores de sinais e de interrupções, pthread_create e os drivers de dispositivo (struct file_operations) são tabelas de ponteiros para funções.
- Interfaces gráficas: Botões e eventos chamam funções registradas (callbacks): GTK, o DOM do navegador e o Android funcionam assim.
- Programação orientada a objetos: Métodos virtuais do C++ são ponteiros para funções numa tabela (vtable); o mesmo padrão aparece no kernel escrito em C.
- Inteligência artificial: Funções de ativação, de perda e otimizadores são passados como parâmetros: um treinador genérico recebe “qual função usar.
B5 Arquivos, argumentos e erros AnexoKernighan e Ritchie, C: a linguagem de programação, capítulo 7 e seção 5.10
Objetivos
- Ler e escrever arquivos texto e binários
- Receber parâmetros pela linha de comando (argc, argv)
- Tratar erros com valores de retorno, perror e assert
- Medir o tamanho e o tempo de arquivos texto contra binários
Experimento
Quantos bytes e quantos nanossegundos custa cada número gravado e relido em texto e em binário?
Os dois formatos são lineares, mas com constantes muito diferentes: o texto é 72% maior e 35 vezes mais lento. O binário é exatamente \(4n\) bytes. Por isso bancos de dados, imagens e modelos de IA são guardados em binário, e dados para trocar com pessoas e outras ferramentas, em texto.
Conexões
- Bancos de dados: Tabelas e índices ficam em arquivos binários de páginas de tamanho fixo (4 a 16 KB); fseek para a página \(k\) é k * tamanho.
- Redes: Protocolos binários (TCP/IP, gRPC/Protobuf) são compactos e rápidos; protocolos de texto (HTTP/1.1, JSON) são legíveis. A escolha é a mesma do experimento.
- Ciência de dados: CSV é universal, mas Parquet e Arrow (binários e colunares) são até dezenas de vezes menores e mais rápidos para grandes volumes.
- Ferramentas de linha de comando: grep, sort e gcc leem argv, leem stdin, escrevem stdout e devolvem um código de saída: é o que permite encadeá-los com |.
Bloco 1 Fundamentos, ordenação e custo
Análise de algoritmos, ordenação por inserção, merge sort, notação assintótica, recorrências, dividir e conquistar e heaps. Termina com o Projeto 1.
1 Algoritmos, eficiência e o método experimental Cormen, capítulo 1
Objetivos
- Definir algoritmo, instância e corretude
- Explicar por que eficiência importa mais que hardware
- Medir tempo de execução em C de forma confiável
- Usar a razão de dobra para reconhecer crescimento linear e quadrático
Experimento
Ao dobrar n, o tempo de um algoritmo linear dobra e o de um quadrático quadruplica?
Os dois tempos seguem a forma prevista: a curva do quadrático é uma parábola e a do linear, uma reta. Para \(n = 32.000\), o algoritmo quadrático já gasta cerca de 100 vezes mais que o linear, e a distância cresce com \(n\). A forma da curva é uma propriedade do algoritmo; a constante é da máquina.
Conexões
- Inteligência artificial: Treinar um modelo de linguagem custa da ordem de \(6 \times\) parâmetros \(\times\) tokens operações: a análise de custo decide quais modelos são viáveis.
- Criptografia: A segurança do RSA depende de não existir algoritmo eficiente conhecido para fatorar inteiros grandes: a ineficiência vira proteção.
- Computação verde: Data centers consomem cerca de 1–2% da energia elétrica mundial. Trocar \(n^2\) por \(n\lg n\) economiza energia, não só tempo.
- Engenharia de desempenho: Ferramentas como perf, gprof e testes de regressão de desempenho em integração contínua aplicam o método desta aula na indústria.
2 Ordenação por inserção e invariantes de laço Cormen, seção 2.1
Objetivos
- Executar a ordenação por inserção à mão, passo a passo
- Provar a corretude com um invariante de laço: inicialização, manutenção e término
- Traduzir o pseudocódigo (índices \(1..n\)) para C (índices \(0..n-1\))
- Medir comparações e confrontar com \(n-1\), \(n^2/4\) e \(n(n-1)/2\)
Experimento
Quantas comparações a ordenação por inserção faz em entradas ordenadas, aleatórias e invertidas?
As três previsões se confirmam: exatamente \(n-1\) e \(n(n-1)/2\) nos casos extremos, e \(n^2/4\) com desvio abaixo de 3% no caso aleatório. A ordenação por inserção é linear em dados ordenados e quadrática em dados aleatórios: o tipo de entrada importa tanto quanto o tamanho.
Conexões
- Bibliotecas de linguagens: O Timsort (sorted do Python, Arrays.sort de objetos no Java) ordena trechos curtos com inserção binária: para \(n\) pequeno, ela vence algoritmos \(n\lg n\).
- Sistemas embarcados: No lugar, sem recursão e com código minúsculo: cabe em microcontroladores com poucos KB de RAM, onde malloc e pilha profunda são luxo.
- Fluxos de dados: É um algoritmo online: ordena à medida que os dados chegam. Manter um placar ao vivo ou as \(k\) maiores leituras de um sensor é uma inserção por evento.
- Verificação formal: Invariantes de laço são a base de ferramentas como Dafny, Frama-C (ACSL) e Why3, que provam código real. Sem o invariante, o provador não consegue.
3 Análise de algoritmos: o modelo RAM e os casos Cormen, seção 2.2
Objetivos
- Descrever o modelo RAM e o que ele ignora
- Calcular \(T(n)\) da inserção somando custo \(\times\) vezes de cada linha
- Distinguir melhor caso, pior caso e caso médio
- Prever e medir o caso médio exato: \(n(n-1)/4 + n - H_n\)
Experimento
A média de comparações da inserção em permutações aleatórias bate com n(n−1)/4 + n − H_n?
A fórmula do caso médio é confirmada: a média medida fica a menos de 1% de \(n(n-1)/4 + n - H_n\), praticamente a metade do pior caso. O histograma mostra que execuções muito diferentes da média são raras. Caso médio quadrático: para dados aleatórios, a inserção não escapa de \(\Theta(n^2)\).
Conexões
- Sistemas de tempo real: Freio ABS e marca-passo não podem atrasar: a análise de pior caso de tempo de execução (WCET) garante que todo prazo seja cumprido.
- Segurança: Ataques de complexidade enviam a entrada do pior caso de propósito: expressões regulares catastróficas (ReDoS) e colisões em tabelas hash derrubam servidores.
- Compiladores: Otimizadores usam modelos de custo por instrução, como a tabela desta aula, para decidir desenrolar laços, embutir funções ou vetorizar.
- Serviços web: Média engana: plataformas monitoram a cauda (latência p99, p99,9), porque com milhões de requisições o pior caso acontece a cada segundo.
4 Dividir e conquistar: merge sort Cormen, seção 2.3
Objetivos
- Aplicar o paradigma dividir, conquistar e combinar
- Executar Merge e provar sua corretude por invariante
- Escrever a recorrência do merge sort e resolvê-la pela árvore de recursão
- Medir \(n\lg n\) e achar o ponto em que a inserção deixa de valer a pena
Experimento
O merge sort faz cerca de n lg n comparações? Para que n ele passa a vencer a inserção?
O merge sort faz \(n\lg n - 1{,}26\,n\) comparações, com desvio menor que 1%. Mas a ordem de crescimento não diz tudo: para \(n\) até algumas centenas, a inserção é mais rápida. Algoritmos híbridos (Timsort, introsort) usam inserção abaixo de um limiar e dividir e conquistar acima dele.
Conexões
- Bancos de dados: O sort-merge join ordena duas tabelas pela chave e as intercala. A ordenação externa ordena arquivos maiores que a RAM em blocos e depois os intercala.
- Armazenamento (LSM-trees): RocksDB, Cassandra e LevelDB escrevem em blocos ordenados e os compactam por intercalação: o Merge em escala de terabytes.
- Big Data: MapReduce e Spark dividem os dados entre máquinas, processam em paralelo e combinam os resultados: o mesmo paradigma, num cluster.
- Computação paralela: As duas metades são independentes: o merge sort paraleliza naturalmente em CPUs com vários núcleos e em GPUs.
5 Notação assintótica: \(O\), \(\Omega\) e \(\Theta\) Cormen, capítulo 3
Objetivos
- Definir \(\Theta\), \(O\), \(\Omega\), \(o\) e \(\omega\) e interpretá-las graficamente
- Provar relações assintóticas exibindo constantes \(c\) e \(n_0\)
- Ordenar funções comuns pela taxa de crescimento
- Estimar a ordem de crescimento a partir de medições (log-log e razão de dobra)
Experimento
Medindo operações de quatro algoritmos, conseguimos identificar lg n, n, n lg n e n²?
As contagens batem exatamente com \(n(n-1)/2\), \(n\lg n\), \(n\) e \(\lg n\). Em escala log-log, a ordem de crescimento aparece como inclinação. Para estimar \(k\) a partir de duas medições: \(k \approx \lg\big(T(2n)/T(n)\big)\), a razão de dobra da aula 1.
Conexões
- Ciência de dados: O \(k\)-means custa \(O(n\,k\,d\,i)\); um algoritmo \(O(n^2)\) inviabiliza bases com milhões de linhas. A notação assintótica decide o que escala.
- Teoria da complexidade: P contra NP pergunta se problemas verificáveis em tempo polinomial também são resolvíveis em tempo polinomial: um dos sete problemas do milênio.
- Bioinformática: Alinhar duas sequências custa \(\Theta(mn)\): para genomas de bilhões de bases, isso força heurísticas como BLAST.
- Contratos de serviço (SLA): Garantir resposta em 100 ms para qualquer carga exige saber como o tempo cresce com os dados; a ordem de crescimento entra no planejamento de capacidade.
6 Recorrências: árvore de recursão e teorema mestre Cormen, seções 4.3 a 4.5
Objetivos
- Modelar algoritmos recursivos por recorrências
- Resolver recorrências pela árvore de recursão e confirmar por substituição
- Aplicar os três casos do teorema mestre
- Conferir numericamente as previsões do teorema
Experimento
Os valores exatos de quatro recorrências seguem as soluções do teorema mestre?
As soluções exatas coincidem com os valores calculados, e a de Strassen converge para \(\frac73\,n^{\lg 7}\). O teorema mestre acerta a ordem de crescimento; para a constante, é preciso resolver a recorrência com mais cuidado (substituição ou árvore completa).
Conexões
- Processamento de sinais: A FFT satisfaz \(T(n) = 2T(n/2) + \Theta(n)\): \(n\lg n\) em vez de \(n^2\) viabiliza áudio digital, 4G/5G, ressonância magnética e compressão JPEG/MP3.
- Álgebra linear e IA: Strassen (\(n^{2,81}\)) e sucessores mostram que multiplicar matrizes, o núcleo das redes neurais, pode custar menos que \(n^3\).
- Computação paralela: Algoritmos paralelos são analisados por duas recorrências: trabalho total e span (caminho crítico). O paralelismo é a razão entre elas.
- Linguagens e sistemas: A profundidade da recursão é a altura da árvore: com \(\lg n\) níveis, a pilha de chamadas fica pequena; com \(n\) níveis, ocorre estouro de pilha.
7 Subarranjo máximo: três algoritmos, três ordens Cormen, seção 4.1
Objetivos
- Reduzir o problema de compra e venda de ações ao subarranjo máximo
- Resolver por força bruta, por divisão e conquista e pelo algoritmo linear
- Analisar o algoritmo de divisão e conquista pela recorrência \(2T(n/2) + \Theta(n)\)
- Medir \(n^2/2\), \(n\lg n\) e \(n\) operações
Experimento
Quantas somas fazem a força bruta, a divisão e conquista e o algoritmo de Kadane?
As contagens são exatamente \(n(n+1)/2\), \(n\lg n\) e \(n\), e as três respostas coincidem em todos os testes. Divisão e conquista melhora muito a força bruta, mas uma ideia melhor (programação dinâmica, aula 33) chega a \(\Theta(n)\): nenhum paradigma é a última palavra.
Conexões
- Finanças: Melhor janela de compra e venda, maior sequência de lucro ou de perda (drawdown) numa carteira: o problema desta aula com dados reais.
- Bioinformática: Atribuindo pesos a aminoácidos ou nucleotídeos, o segmento de soma máxima localiza regiões transmembranares em proteínas e ilhas CpG no DNA.
- Visão computacional: A versão 2D, o retângulo de soma máxima, encontra a região mais clara ou mais “ativa de uma imagem em \(O(n^3)\), com Kadane nas colunas.
- Monitoramento: Em séries temporais (CPU, batimentos, tráfego), subtrair a média e achar o subarranjo máximo localiza a janela de maior anomalia.
8 Heaps e heapsort Cormen, capítulo 6 (seções 6.1 a 6.4)
Objetivos
- Representar uma árvore binária quase completa em um vetor
- Manter a propriedade de heap com Max-Heapify
- Mostrar que Build-Max-Heap é \(O(n)\), não \(O(n\lg n)\)
- Medir comparações: \(\approx 2n\) na construção, \(\approx 2n\lg n\) no heapsort
Experimento
Construir um heap faz O(n) comparações e o heapsort faz cerca de 2 n lg n?
A construção é linear (cerca de \(1{,}9\,n\) comparações), confirmando que a análise ingênua \(O(n\lg n)\) era pessimista. O heapsort completo fica perto de \(1{,}8\,n\lg n\): o dobro de comparações do merge sort, mas no lugar, sem memória extra.
Conexões
- Sistemas operacionais: Temporizadores do kernel, filas de prioridade de processos e o temporizador do runtime de Go usam heaps para achar o próximo evento em \(O(\lg n)\).
- Simulação de redes: Simuladores de eventos discretos (ns-3, OMNeT++) mantêm uma fila de eventos ordenada por tempo: extrair o próximo é Extract-Min.
- Sistemas embarcados: Heapsort garante \(O(n\lg n)\) sem memória extra nem recursão profunda; o std::sort do C++ (introsort) recorre a ele quando o quicksort degenera.
- Jogos e mapas: Dijkstra e A*, usados em GPS e na movimentação de personagens, dependem de uma fila de prioridade em heap (aulas 17 e 31).
9 Projeto 1: laboratório de ordenação Projeto
Apresentação dos projetos do Bloco 1. Cada equipe implementa, instrumenta e compara algoritmos de ordenação, e confronta as medições com a teoria.
Entregas
- Implementação em C de inserção, merge sort, heapsort e um híbrido (inserção abaixo de um limiar \(k\))
- Experimento com \(n\) até \(10^6\) em quatro tipos de entrada: aleatória, ordenada, invertida e quase ordenada (1% fora do lugar)
- Gráficos de comparações e de tempo com as curvas teóricas ajustadas e a razão medido/teórico
- O melhor limiar \(k\) do híbrido na máquina da equipe, com justificativa
- Apresentação de 10 minutos: hipótese, método, resultados, o que não bateu com a teoria e por quê
Bloco 2 Dicionários e estruturas lineares
Dicionários, pilhas, filas, vetores dinâmicos e listas: simplesmente e duplamente ligadas, circulares, com sentinela e em vetores; filas de prioridade. Termina com o Projeto 2.
10 Dicionários e conjuntos dinâmicos Cormen, introdução da parte III e seção 10.1
Objetivos
- Definir conjunto dinâmico e as operações de dicionário
- Separar consultas (busca, mínimo, máximo, sucessor) de modificações (inserção, remoção)
- Implementar um dicionário em vetor ordenado com busca binária
- Medir o custo de inserir e de buscar em vetor ordenado e desordenado
Experimento
Quanto custam n inserções e n buscas num dicionário em vetor ordenado e em vetor desordenado?
As três previsões se confirmam: \(n^2/4\) deslocamentos e \(n\lg n\) comparações no vetor ordenado, \(n(n+1)/2\) comparações no desordenado. Vetores obrigam a escolher entre inserir rápido e buscar rápido. O resto do curso mostra estruturas que fazem as duas coisas em \(O(1)\) ou \(O(\lg n)\).
Conexões
- Bancos de dados: Uma tabela é um conjunto dinâmico de registros; índices são dicionários sobre uma coluna, e o otimizador escolhe entre varrer e buscar conforme o custo.
- Linguagens: dict e set do Python, Map do JavaScript, std::map e std::unordered_map do C++: o mesmo tipo abstrato com implementações diferentes.
- Compiladores: A tabela de símbolos é um dicionário de identificadores; escopos aninhados viram uma pilha de dicionários (aula 11).
- Redes: Tabelas ARP, de rotas e de conexões são dicionários consultados milhões de vezes por segundo: a implementação define a latência.
11 Pilhas Cormen, seção 10.1
Objetivos
- Implementar pilhas em vetor (com transbordamento) e em lista ligada
- Analisar Push e Pop em \(O(1)\)
- Avaliar expressões pós-fixas com uma pilha
- Medir o custo por operação das duas implementações
Experimento
Quanto custa, em nanossegundos, cada operação de pilha em vetor e em lista ligada?
As duas implementações têm custo constante por operação, como prevê a análise, mas a lista ligada é cerca de 25 vezes mais cara: malloc, free e saltos pela memória. A notação \(O\) esconde constantes; quando a capacidade é previsível, o vetor (ou o vetor dinâmico da aula 13) é a melhor pilha.
Conexões
- Compiladores: Analisadores sintáticos casam parênteses e blocos com pilhas; a máquina virtual da JVM e a do Python são máquinas de pilha: iadd desempilha dois e empilha a soma.
- Navegadores e editores: Voltar e avançar, desfazer e refazer: duas pilhas. Calculadoras HP usavam notação pós-fixa por ser mais rápida de digitar e de avaliar.
- Sistemas operacionais: Cada thread tem sua pilha de chamadas; o estouro dela (stack overflow) é o transbordamento desta aula, em hardware.
- Inteligência artificial: Busca em profundidade com backtracking (labirintos, sudoku, provadores de teoremas) guarda as alternativas pendentes numa pilha (aula 29).
12 Filas Cormen, seção 10.1
Objetivos
- Implementar filas em vetor circular e em lista ligada
- Distinguir fila cheia de fila vazia
- Conhecer deques (filas de duas pontas)
- Simular uma fila de atendimento e conferir com a teoria das filas
Experimento
Na simulação de uma fila M/M/1, o tempo médio de espera segue ρ/(1−ρ)?
A simulação reproduz \(\rho/(1-\rho)\) com erro de poucos por cento. A fila FIFO, uma estrutura simples, é o coração de toda simulação de atendimento. A lição prática: um sistema com 85% de ocupação já tem esperas longas; perto de 100%, elas explodem.
Conexões
- Sistemas operacionais: Processos prontos esperam numa fila; o escalonamento round robin é uma fila circular. Buffers de teclado, disco e impressão são filas.
- Redes: Roteadores guardam pacotes em filas de saída; a teoria das filas desta aula explica o atraso e a perda quando o enlace fica congestionado.
- Computação em nuvem: Filas de mensagens (RabbitMQ, Kafka, SQS) desacoplam serviços: quem produz enfileira, quem consome desenfileira no seu ritmo.
- Algoritmos de grafos: A busca em largura (aula 28) explora um grafo camada por camada usando exatamente uma fila FIFO.
13 Vetores dinâmicos e análise amortizada Cormen, seções 17.1 e 17.4
Objetivos
- Fazer um vetor crescer e encolher conforme o uso
- Calcular o custo amortizado pelo método agregado
- Entender por que encolher só com \(1/4\) de ocupação
- Medir \(2n\) cópias contra \(n^2/2000\) para duas estratégias de crescimento
Experimento
Quantas cópias custam n inserções num vetor que dobra e num que cresce 1000 posições por vez?
Dobrar custa \(\approx 2n\) cópias: \textbf{amortizado \(O(1)\)} por inserção. Somar uma constante custa \(\approx n^2/2000\): quadrático, por maior que seja a constante. Por isso std::vector, ArrayList e as listas do Python crescem por um fator (1,5 ou 2), nunca por uma quantidade fixa.
Conexões
- Linguagens: A lista do Python cresce cerca de 12%, o vector do C++ (GCC) dobra e o ArrayList do Java cresce 50%: fatores diferentes, todos amortizados \(O(1)\).
- Bancos de dados: Tabelas hash de bancos e caches (Redis) dobram de tamanho e reinserem tudo, às vezes aos poucos (rehash incremental) para não travar o serviço.
- Redes: O TCP aumenta a janela de envio por fator e a reduz pela metade em congestionamento: crescimento multiplicativo, como o vetor dinâmico.
- Sistemas embarcados: Em tempo real, um pico de \(\Theta(n)\) numa cópia pode estourar um prazo: lá se prefere capacidade fixa ou crescimento sem cópia (listas de blocos).
14 Listas simplesmente ligadas Cormen, seção 10.2
Objetivos
- Representar uma sequência com nós e ponteiros
- Inserir no início e no fim, buscar e remover
- Inverter uma lista sem memória extra
- Medir a vantagem da lista na inserção e o custo do cache no percurso
Experimento
Quanto custa inserir no início de um vetor? E percorrer uma lista ligada cujos nós estão espalhados pela memória?
Inserir no início confirma a teoria: \(n(n-1)/2\) movimentos no vetor, nenhum na lista. No percurso, os dois são \(\Theta(n)\), mas a lista espalhada fica até 200 vezes mais lenta que o vetor quando sai do cache. O modelo RAM não vê a hierarquia de memória; a medição vê.
Conexões
- Sistemas operacionais: Filas de processos, listas de arquivos abertos e de páginas livres são listas ligadas dentro do kernel; a inserção \(O(1)\) é essencial.
- Alocação de memória: malloc encadeia os blocos livres numa lista; programas em C que vazam memória costumam “perder a cabeça de uma lista.
- Arquitetura de computadores: O experimento mostra a hierarquia de memória: L1 (\(\approx\)1 ns), L2, L3 e RAM (\(\approx\)100 ns). Estruturas cache-friendly vencem na prática.
- Linguagens funcionais: Em Lisp, Haskell e Erlang a lista ligada é a estrutura básica: inserir na cabeça cria uma lista nova compartilhando o resto, sem copiar nada.
15 Listas duplamente ligadas e listas circulares Cormen, seção 10.2
Objetivos
- Implementar a lista duplamente ligada e seus casos especiais sem sentinela
- Remover um nó dado em \(O(1)\)
- Fechar a lista num círculo e percorrê-la sem fim
- Resolver o problema de Josefo e comparar lista circular com vetor
Experimento
Quantos passos a lista circular e quantos deslocamentos o vetor gastam para resolver o problema de Josefo?
A lista circular resolve Josefo em exatamente \((n-1)(k-1)\) passos; o vetor, em \(\approx 0{,}3\,n^2\) deslocamentos: 4.800 vezes mais trabalho para \(n = 32.000\). Quando a operação dominante é remover no meio, a lista ligada vence; quando é acessar por posição, o vetor vence.
Conexões
- Sistemas operacionais: O kernel Linux usa listas duplas circulares (list_head) em toda parte; o escalonador round robin percorre uma lista circular de processos.
- Navegadores: O histórico com voltar e avançar e as abas em ordem são listas duplas: sair de uma aba no meio é remover um nó em \(O(1)\).
- Caches LRU: Um cache LRU combina uma tabela hash com uma lista dupla: o item usado vai para a frente, o mais antigo sai do fim, tudo em \(O(1)\).
- Jogos: Turnos de jogadores, animações em laço e trilhas de áudio em repetição são percorridos como listas circulares.
16 Sentinelas e listas sem ponteiros Cormen, seções 10.2 e 10.3
Objetivos
- Usar uma sentinela para eliminar os casos especiais das listas
- Implementar a lista circular duplamente ligada com sentinela do livro
- Representar listas com vetores e gerenciar posições livres
- Medir quantos testes a sentinela economiza numa busca
Experimento
Quantos testes uma busca sem sucesso faz com e sem sentinela? E quanto tempo?
A sentinela corta os testes exatamente pela metade (\(n + 1\) contra \(2n + 1\)) e economiza cerca de 10% do tempo. Mais importante: elimina os casos especiais de lista vazia, cabeça e cauda, que são a fonte da maioria dos erros com listas. Na representação em vetores, a lista livre faz o papel do malloc: alocar e liberar em \(O(1)\).
Conexões
- Kernel Linux: Toda lista do kernel (list_head) é circular, dupla e com sentinela: a “cabeça é um nó sem dados, exatamente \(L.\mathit{nil}\).
- Alocadores de memória: malloc mantém listas livres de blocos por tamanho; alocadores de pool (jogos, servidores) usam a pilha livre da Figura 10.7.
- Sistemas de arquivos: O FAT do MS-DOS e de pendrives é uma lista em vetor: cada posição diz o próximo bloco do arquivo; os blocos livres formam outra lista.
- Bancos de dados: Páginas livres de um arquivo de banco são encadeadas numa lista livre guardada no próprio arquivo, com índices no lugar de ponteiros.
17 Filas de prioridade Cormen, seção 6.5
Objetivos
- Definir as operações de uma fila de prioridade
- Implementar inserção, extração do máximo e aumento de chave num heap
- Comparar heap, vetor ordenado e vetor desordenado como filas de prioridade
- Medir \(\Theta(n\lg n)\) contra \(\Theta(n^2)\) em \(n\) inserções e \(n\) extrações
Experimento
Para n inserções seguidas de n extrações, quantas comparações fazem heap, vetor ordenado e vetor desordenado?
O vetor desordenado faz exatamente \(n(n-1)/2\) comparações e o ordenado, \(n^2/4\); o heap fica em \(\approx 1{,}8\,n\lg n\). Para \(n = 16.000\), o heap é 150 vezes mais barato que o vetor ordenado. A estrutura certa muda a ordem de crescimento.
Conexões
- Sistemas operacionais: Escalonadores escolhem o próximo processo pela prioridade; temporizadores do kernel disparam o evento mais próximo: Extract-Min num heap.
- Redes de computadores: Roteadores com QoS servem primeiro os pacotes de voz e vídeo; o roteamento OSPF roda Dijkstra com fila de prioridade em cada roteador.
- Simulação de eventos: Simuladores (filas de banco, tráfego, epidemias) processam eventos em ordem de tempo: o próximo evento sai de uma fila de mínimo.
- Compressão de dados: O código de Huffman (aula 34) junta repetidamente os dois símbolos menos frequentes, retirados de uma fila de prioridade.
18 Projeto 2: simulador de escalonamento de processos Projeto
Apresentação dos projetos do Bloco 2. Cada equipe constrói um simulador de escalonamento de CPU com as estruturas do bloco e compara políticas com experimentos.
Entregas
- Simulador em C: processos chegam com tempo de execução e prioridade; fila circular (FIFO e round robin), lista duplamente ligada com sentinela (processos bloqueados), pilha (chamadas de cada processo) e fila de prioridade em heap (menor trabalho primeiro)
- Três políticas: FIFO, menor trabalho primeiro (heap) e round robin (fila circular)
- Experimento: tempo médio de espera e vazão para 1.000 a 1.000.000 de processos, com o custo das operações confrontado com a teoria
- Relatório: qual política vence em cada carga e quanto custa cada estrutura (gráficos com curvas teóricas)
- Apresentação de 10 minutos com demonstração ao vivo
Bloco 3 Tabelas hash e árvores
Tabelas hash (encadeamento, funções hash, endereçamento aberto), árvores binárias de busca, AVL, rubro-negras e árvores B. Termina com o Projeto 3.
19 Tabelas hash com encadeamento Cormen, seções 11.1 e 11.2
Objetivos
- Explicar endereçamento direto e por que ele não escala
- Resolver colisões por encadeamento
- Analisar a busca em função do fator de carga \(\alpha = n/m\)
- Medir \(\alpha\) e \(1 + \alpha/2\) elementos examinados por busca
Experimento
Quantos elementos uma busca examina, com e sem sucesso, em função do fator de carga α?
Os teoremas 11.1 e 11.2 se confirmam com desvio menor que 1%: \(\alpha\) elementos sem sucesso, \(1 + \alpha/2\) com sucesso. O custo depende de \(\alpha\), \textbf{não de \(n\)}: com \(\alpha\) fixo, uma tabela com um bilhão de chaves busca tão rápido quanto uma com mil.
Conexões
- Bancos de dados: Índices hash respondem WHERE id = ? em \(O(1)\); o hash join monta uma tabela hash com a menor relação e varre a maior.
- Compiladores e linguagens: A tabela de símbolos guarda identificadores numa tabela hash; dicionários do Python, objetos do JavaScript e HashMap do Java também.
- Cache distribuído: Memcached e Redis distribuem chaves entre servidores com hash; o hashing consistente minimiza as chaves movidas quando um servidor entra ou sai.
- Redes: Switches mantêm a tabela de endereços MAC em hash; roteadores e firewalls classificam fluxos (5-tupla) por hash para decidir em nanossegundos.
20 Funções hash e hashing universal Cormen, seção 11.3
Objetivos
- Construir funções hash pelos métodos da divisão e da multiplicação
- Reconhecer escolhas ruins de \(m\) (potências de 2 com chaves estruturadas)
- Definir hashing universal e o que ele garante
- Medir o efeito da função hash em chaves com padrão
Experimento
Com chaves múltiplas de 64 e fator de carga 1, quanto custa uma busca com cada função hash?
A escolha da função muda o custo em mais de 30 vezes com as mesmas chaves: dividir por potência de 2 dá exatamente 32,5; dividir por um primo dá 1. O hashing universal fica em 1,5 em média, como garante o teorema, sem depender das chaves. Uma função isolada sorteada, porém, pode ter azar: a garantia é sobre a média da família.
Conexões
- Segurança: Em 2011, ataques de hash flooding derrubaram servidores web enviando parâmetros que colidiam; Python, Ruby e Java passaram a sortear a função (SipHash).
- Sistemas distribuídos: Hashing consistente (Dynamo, Cassandra) e rendezvous hashing decidem qual servidor guarda cada chave; uma função ruim desequilibra o cluster.
- Big data: Contagem aproximada (HyperLogLog), filtros de Bloom e count-min sketch dependem de funções hash independentes e bem espalhadas.
- Criptografia: Hashes criptográficos (SHA-256) vão além: resistência a colisões e a pré-imagem. Senhas, assinaturas e blockchain dependem disso.
21 Endereçamento aberto Cormen, seção 11.4
Objetivos
- Guardar todas as chaves no próprio vetor, sem listas
- Comparar sondagem linear, quadrática e hash duplo
- Explicar por que a remoção exige marcas
- Medir as sondagens e confrontar com \(1/(1-\alpha)\) e com a fórmula de Knuth
Experimento
Quantas sondagens fazem a sondagem linear e o hash duplo, com e sem sucesso, para α de 0,05 a 0,9?
As quatro fórmulas se confirmam com desvios de poucos por cento. Até \(\alpha \approx 0{,}5\), linear e duplo empatam; acima disso, os aglomerados da linear explodem o custo. Regra prática: endereçamento aberto com \(\alpha \le 0{,}7\); acima disso, redimensione.
Conexões
- Hardware: Caches de CPU são tabelas hash em hardware: o endereço escolhe o conjunto, e cada conjunto tem poucas “posições (associatividade).
- Linguagens: O HashMap do Rust (SwissTable), o dict do Python e o absl::flat_hash_map do C++ usam endereçamento aberto pela localidade de memória.
- Sistemas embarcados: Sem malloc nem listas: uma tabela de tamanho fixo com endereçamento aberto cabe em memória estática, ideal para microcontroladores.
- Bancos de dados: Agregações (GROUP BY) e joins em memória usam tabelas com sondagem linear vetorizada (SIMD) em sistemas analíticos.
22 Árvores binárias de busca: percursos e consultas Cormen, seções 12.1 e 12.2
Objetivos
- Enunciar a propriedade de árvore binária de busca
- Percorrer em ordem, pré-ordem e pós-ordem
- Buscar, achar mínimo, máximo, sucessor e predecessor em \(O(h)\)
- Medir o custo médio de busca em árvores aleatórias: \(\approx 1{,}39\lg n\)
Experimento
Numa ABB construída com chaves em ordem aleatória, quantos nós uma busca com sucesso visita em média?
O custo médio segue \(2(1 + 1/n)H_n - 3\) com desvio abaixo de 1%: para dois milhões de chaves, 27 nós por busca. Uma árvore aleatória é só 39% mais funda (em média) que uma perfeitamente balanceada. O perigo está nas entradas não aleatórias (próxima aula).
Conexões
- Sistemas de arquivos: Diretórios são árvores; ext4 e Btrfs indexam nomes em árvores de busca para achar um arquivo entre milhões sem varrer todos.
- Compiladores: Árvores sintáticas são percorridas em pós-ordem para gerar código e avaliar expressões; o percurso em ordem imprime a expressão infixa.
- Bancos de dados: Consultas por intervalo (BETWEEN) usam o sucessor: acha-se o início e anda-se em ordem. Hash não faz isso; árvores fazem.
- Geometria computacional: Árvores k-d e de intervalos generalizam a ABB para pontos no plano: “quais restaurantes estão neste retângulo do mapa?.
23 Inserção, remoção e altura das árvores de busca Cormen, seções 12.3 e 12.4
Objetivos
- Inserir mantendo a propriedade de ABB
- Remover nos três casos com Transplant
- Entender por que a altura esperada de uma ABB aleatória é \(O(\lg n)\)
- Medir a altura de árvores aleatórias e o desastre da entrada ordenada
Experimento
Qual a altura de uma ABB com chaves aleatórias? E com chaves em ordem crescente?
Com chaves aleatórias, a altura fica sempre entre \(\lg n\) e \(3\lg n\): para dois milhões de chaves, cerca de 54 níveis. Com chaves em ordem, exatamente \(n - 1\): dois milhões de níveis. A mesma estrutura, com a mesma quantidade de dados, fica 40.000 vezes mais funda só pela ordem de chegada.
Conexões
- Bancos de dados: Chaves autoincrementadas chegam em ordem: é exatamente o pior caso de uma ABB comum. Por isso bancos usam árvores balanceadas (B-trees).
- Editores e cordas: Editores de texto grandes guardam o documento numa árvore de trechos (rope); inserir e remover no meio custa \(O(h)\).
- Jogos: Placares (leaderboards) mantêm jogadores ordenados por pontuação com inserção e remoção constantes; a altura define a latência.
- Redes: Tabelas de roteamento e de temporizadores de conexões TCP mudam o tempo todo: remoções e inserções eficientes são essenciais.
24 Árvores AVL Cormen, problema 13-3 e seção 13.2 (rotações)
Objetivos
- Definir o fator de balanceamento AVL
- Aplicar rotações simples e duplas
- Provar que a altura de uma AVL é \(O(\lg n)\) (árvores de Fibonacci)
- Medir a altura com chaves em ordem e o número de rotações por inserção
Experimento
Qual a altura de uma AVL com chaves em ordem e com chaves aleatórias? Quantas rotações custa cada inserção?
Com chaves em ordem, a AVL tem altura exatamente \(\lg n\), contra \(n - 1\) da ABB comum (21 níveis contra dois milhões). Com chaves aleatórias, fica abaixo de \(1{,}44\lg n\), e o reequilíbrio custa só \(\approx 0{,}7\) rotação por inserção.
Conexões
- Bancos em memória: Bancos e caches em memória que priorizam leituras usam árvores AVL ou parecidas: a altura menor que a da rubro-negra acelera buscas.
- Tempo real: Garantia de \(O(\lg n)\) no pior caso, sem amortização: adequada a sistemas que não podem ter picos de latência.
- Linguagens funcionais: Conjuntos e mapas imutáveis (Data.Map em Haskell, Set em OCaml) usam árvores balanceadas por tamanho ou altura, parentes da AVL.
- Roteamento: Tabelas de prefixos e estruturas de intervalos em roteadores usam árvores balanceadas para manter a busca curta mesmo sob atualizações constantes.
25 Árvores rubro-negras Cormen, seções 13.1 a 13.3
Objetivos
- Enunciar as cinco propriedades rubro-negras
- Provar que a altura é no máximo \(2\lg(n+1)\)
- Executar RB-Insert-Fixup nos três casos
- Medir altura e rotações e conferir as propriedades a cada experimento
Experimento
A altura de uma rubro-negra respeita 2 lg(n+1)? Quantas rotações custa uma inserção?
As propriedades valeram em todas as árvores, e a altura ficou sempre abaixo de \(2\lg(n + 1)\), mesmo com chaves em ordem. O conserto custa \(\approx 0{,}58\) rotação por inserção: menos que a AVL, ao preço de árvores um pouco mais altas. É o equilíbrio que levou as bibliotecas padrão a escolher a rubro-negra.
Conexões
- Kernel Linux: O escalonador CFS ordenava processos numa rubro-negra pelo tempo de CPU usado; a memória virtual guarda as áreas mapeadas de cada processo numa delas.
- Bibliotecas padrão: std::map e std::set do C++ e TreeMap do Java são rubro-negras; o HashMap do Java vira rubro-negra quando uma lista fica longa.
- Redes: Temporizadores de alta resolução e tabelas de conexões usam rubro-negras para inserções e remoções frequentes com pior caso garantido.
- Estruturas persistentes: Rubro-negras funcionais (Okasaki) são a base de mapas imutáveis em Scala e Clojure: versões antigas continuam válidas a custo \(O(\lg n)\).
26 Árvores B e memória secundária Cormen, capítulo 18 (seções 18.1 e 18.2)
Objetivos
- Explicar por que o acesso ao disco muda o modelo de custo
- Definir árvore B de grau mínimo \(t\) e limitar sua altura
- Inserir com divisão preventiva de nós cheios
- Medir a altura para \(t = 2\), 16 e 128 e conferir \(\log_t\frac{n+1}2\)
Experimento
Qual a altura de uma árvore B com t = 2, 16 e 128 para até 4 milhões de chaves?
A altura respeitou o teorema 18.1 em todos os casos. Com \(t = 128\), quatro milhões de chaves ficam em 3 níveis: uma busca lê 3 páginas do disco, contra 22 de uma árvore binária balanceada. É por isso que todo banco de dados relacional indexa com árvores B (na verdade, B+).
Conexões
- Bancos de dados: PostgreSQL, MySQL (InnoDB), SQLite e Oracle indexam tabelas com árvores B+: as chaves nas folhas, ligadas em lista para consultas por intervalo.
- Sistemas de arquivos: NTFS, HFS+, APFS, Btrfs e XFS guardam diretórios e metadados em árvores B: abrir um arquivo entre milhões custa poucas leituras.
- Armazenamento chave-valor: LMDB e BoltDB são árvores B mapeadas em memória; MongoDB (WiredTiger) e CouchDB também usam árvores B.
- SSDs e cache: Em SSDs, escrever custa mais que ler: variantes como B\(^\varepsilon\)-trees e LSM-trees (aula 4) trocam leituras por menos escritas.
27 Projeto 3: mecanismo de busca em miniatura Projeto
Apresentação dos projetos do Bloco 3. Cada equipe indexa um conjunto de textos em português com as estruturas do bloco e compara as estruturas experimentalmente.
Entregas
- Índice invertido em C: palavra → lista de documentos e posições, sobre livros de domínio público (Machado de Assis, por exemplo)
- O mesmo índice com quatro dicionários: hash com encadeamento, hash com endereçamento aberto, ABB e uma árvore balanceada (AVL ou rubro-negra)
- Experimento: tempo e número de comparações por busca, altura das árvores e tamanho das listas, para 10 mil a 10 milhões de palavras; confronto com a teoria
- Consultas por prefixo e por intervalo alfabético: quais estruturas permitem e a que custo
- Apresentação de 10 minutos com demonstração de buscas ao vivo
Bloco 4 Grafos
Buscas em largura e em profundidade, ordenação topológica, árvores geradoras mínimas e caminhos mínimos; programação dinâmica, algoritmos gulosos e casamento de cadeias. Termina com o Projeto 4.
28 Grafos e busca em largura Cormen, seções 22.1 e 22.2
Objetivos
- Representar grafos por listas de adjacência e por matriz de adjacência
- Executar a busca em largura e obter distâncias e a árvore de caminhos mínimos
- Provar que a BFS custa \(O(V + E)\)
- Medir o custo linear e o “mundo pequeno de grafos aleatórios
Experimento
A BFS faz exatamente V + 2E operações? Qual a distância média num grafo aleatório com grau médio 10?
A BFS faz exatamente \(V + 2E\) operações: linear. E grafos aleatórios são “pequenos”: com dois milhões de vértices e grau médio 10, a distância média é 6,4, crescendo como \(\ln V\). É o fenômeno dos seis graus de separação, medido por BFS em redes sociais reais.
Conexões
- Redes sociais: O Facebook mediu, com BFS em 721 milhões de usuários, uma distância média de 4,74; “pessoas que você talvez conheça são vértices à distância 2.
- Web e buscadores: Rastreadores (crawlers) percorrem a web em largura a partir de páginas-semente: a BFS encontra primeiro as páginas mais próximas e relevantes.
- Redes de computadores: Broadcast e descoberta de vizinhos inundam a rede camada por camada; o traceroute revela as camadas da BFS da internet.
- Jogos e robótica: Em mapas em grade sem pesos, a BFS dá o menor caminho de um personagem ou robô; o cubo de Rubik foi resolvido (“número de Deus = 20) com buscas em largura.
29 Busca em profundidade e ordenação topológica Cormen, seções 22.3 e 22.4
Objetivos
- Executar a DFS e registrar tempos de descoberta e de término
- Classificar arestas (árvore, retorno, avanço, cruzamento)
- Ordenar topologicamente um grafo acíclico pela ordem de término
- Medir \(V + E\) operações e o efeito do cache no tempo
Experimento
A DFS faz exatamente V + E operações num DAG? O tempo também cresce linearmente?
A contagem é exatamente \(V + E\) e a ordem topológica é sempre válida. O tempo, porém, só é linear enquanto o grafo cabe no cache: depois, cada acesso aleatório custa uma ida à RAM. Bibliotecas de grafos de alto desempenho renumeram os vértices para que vizinhos fiquem próximos na memória.
Conexões
- Compiladores e builds: make, Maven, Bazel e gerenciadores de pacotes (npm, apt) ordenam topologicamente as dependências; um ciclo é um erro de configuração.
- Planilhas: Ao mudar uma célula, a planilha recalcula as dependentes em ordem topológica e detecta referências circulares com a DFS.
- Sistemas operacionais: Detectar deadlock é achar um ciclo no grafo de espera entre processos e recursos: uma aresta de retorno na DFS.
- Gestão de projetos e dados: Diagramas PERT/CPM, pipelines de dados (Airflow) e redes neurais (o grafo de computação do PyTorch) são DAGs executados em ordem topológica.
30 Conjuntos disjuntos e árvores geradoras mínimas Cormen, capítulo 21 e capítulo 23
Objetivos
- Implementar conjuntos disjuntos com união por posto e compressão de caminho
- Enunciar a propriedade de corte que justifica os algoritmos gulosos de AGM
- Executar Kruskal e Prim
- Medir o custo quase constante das operações de conjuntos disjuntos
Experimento
Quantos ponteiros uma operação de conjuntos disjuntos segue, sem e com as heurísticas?
Sem heurísticas, cada operação custa \(\approx 2n/15\): com 16 mil elementos, mais de 2 mil passos. Com união por posto e compressão de caminho, o custo cai para 0,6 e não muda até dois milhões de elementos. É o que torna o Kruskal \(O(E\lg V)\): o gargalo passa a ser só a ordenação das arestas.
Conexões
- Redes de infraestrutura: Projetar redes elétricas, de fibra óptica ou de saneamento ligando todos os pontos com o menor custo de cabo é uma AGM (Borůvka, 1926, eletrificação da Morávia).
- Agrupamento de dados: Remover as \(k - 1\) arestas mais pesadas da AGM separa os dados em \(k\) grupos: o agrupamento por ligação simples (single linkage).
- Visão computacional: A segmentação de imagens de Felzenszwalb e Huttenlocher une pixels parecidos com conjuntos disjuntos, no estilo do Kruskal.
- Compiladores e redes: Conjuntos disjuntos resolvem unificação de tipos (inferência de tipos) e acompanham componentes conexas de redes que mudam em tempo real.
31 Caminhos mínimos: Bellman-Ford e Dijkstra Cormen, seções 24.1 e 24.3
Objetivos
- Definir caminhos mínimos com pesos e o papel dos ciclos negativos
- Usar o relaxamento como operação básica
- Executar Bellman-Ford (\(O(VE)\)) e Dijkstra (\(O((V + E)\lg V)\) com heap)
- Medir vetor contra heap no Dijkstra e o custo do Bellman-Ford
Experimento
Em grafos esparsos, quantas operações fazem Dijkstra com vetor, Dijkstra com heap e Bellman-Ford?
As contagens batem: \(V^2 + E\) e \((V-1)E\) exatos, e \(\Theta(V\lg V)\) com heap. Em grafos esparsos, o heap é 130 vezes mais barato que o vetor para \(V = 4.000\). Em grafos densos (\(E \approx V^2\)), o vetor volta a ser competitivo: a melhor estrutura depende da densidade do grafo.
Conexões
- Navegação (GPS): Google Maps e Waze usam Dijkstra com acelerações (A*, hierarquias de contração) em grafos de bilhões de arestas, com pesos que mudam com o trânsito.
- Roteamento na internet: OSPF e IS-IS rodam Dijkstra em cada roteador; RIP e BGP são variações distribuídas do Bellman-Ford (vetor de distâncias).
- Finanças: Com pesos \(-\log(\text{câmbio})\), um ciclo negativo é uma oportunidade de arbitragem entre moedas: Bellman-Ford a detecta.
- Logística: Roteirização de entregas e planejamento de rotas de transporte público começam com caminhos mínimos entre todos os pontos de interesse.
32 Caminhos mínimos entre todos os pares: Floyd-Warshall Cormen, seção 25.2
Objetivos
- Formular caminhos mínimos entre todos os pares por programação dinâmica
- Executar Floyd-Warshall e reconstruir caminhos
- Calcular o fecho transitivo
- Medir \(V^3\) contra \(V\) execuções de Dijkstra em grafos esparsos
Experimento
Em grafos esparsos, Floyd-Warshall (V³) ou V execuções de Dijkstra (V²lg V)?
As duas formas de crescimento se confirmam: \(V^3\) para Floyd-Warshall e \(V^2\lg V\) para \(V\) execuções de Dijkstra, com as mesmas respostas. Em grafos esparsos, Dijkstra repetido vence; em grafos densos ou pequenos, a simplicidade do Floyd-Warshall compensa, e ele aceita pesos negativos.
Conexões
- Redes: Matrizes de latência entre todos os servidores de um data center ou de uma CDN orientam onde colocar réplicas e como balancear carga.
- Bioinformática: Distâncias entre todas as espécies (ou genes) alimentam a construção de árvores filogenéticas por métodos de distância.
- Mapas e logística: Tabelas de distância entre todas as cidades (o “mapa rodoviário) são pré-calculadas para planejar rotas e entregas.
- Análise de dependências: O fecho transitivo responde “A depende de B, direta ou indiretamente? em compiladores, bancos de dados (consultas recursivas) e controle de acesso.
33 Programação dinâmica Cormen, seções 15.1, 15.3 e 15.4
Objetivos
- Reconhecer subestrutura ótima e subproblemas sobrepostos
- Resolver o corte de hastes de cima para baixo (memoização) e de baixo para cima
- Calcular a maior subsequência comum (LCS) e reconstruí-la
- Medir \(2^n\) chamadas contra \(n(n+1)/2\)
Experimento
Quantas chamadas faz o corte de hastes recursivo ingênuo e quantas faz a versão memoizada?
As contagens são exatamente \(2^n\) e \(n(n+1)/2 + 1\). Guardar as respostas dos subproblemas transforma um algoritmo exponencial em quadrático, com o mesmo resultado. A programação dinâmica troca memória por tempo: uma tabela de \(n + 1\) posições economiza bilhões de chamadas.
Conexões
- Bioinformática: Alinhar sequências de DNA e proteínas (Needleman–Wunsch, Smith–Waterman) é uma LCS com pesos: a base do BLAST e da comparação de genomas.
- Controle de versão: diff e git diff calculam a menor sequência de edições entre dois arquivos, uma variação da LCS.
- Linguagem natural: Corretores ortográficos (distância de edição), reconhecimento de voz (Viterbi) e análise sintática (CYK) são programação dinâmica.
- Finanças e IA: Precificação de opções em árvores binomiais e aprendizado por reforço (equação de Bellman) resolvem subproblemas de baixo para cima.
34 Algoritmos gulosos: seleção de atividades e Huffman Cormen, seções 16.1 a 16.3
Objetivos
- Reconhecer a propriedade da escolha gulosa e a subestrutura ótima
- Resolver a seleção de atividades escolhendo sempre a que termina primeiro
- Construir códigos de Huffman com fila de prioridade
- Medir o comprimento médio de Huffman contra a entropia de Shannon
Experimento
O comprimento médio do código de Huffman fica entre a entropia H e H + 1? Quanto ele ganha do código fixo?
Em todos os alfabetos, \(H \le L < H + 1\), e na prática \(L - H < 0{,}1\) bit: Huffman fica praticamente no limite teórico da compressão sem perdas símbolo a símbolo. Um algoritmo guloso de cinco linhas atinge o ótimo, e a teoria da informação diz que ninguém pode fazer melhor.
Conexões
- Compressão: DEFLATE (ZIP, gzip, PNG), JPEG e MP3 usam códigos de Huffman na etapa final; formatos modernos usam codificação aritmética, que chega ainda mais perto de \(H\).
- Redes: O HTTP/2 comprime cabeçalhos com HPACK, que usa uma tabela de Huffman fixa: cada requisição web economiza bytes.
- Agendamento: Escalonar tarefas por prazo (earliest deadline first) e alocar salas, frequências de rádio ou pistas de pouso são problemas gulosos parentes da seleção de atividades.
- Aprendizado de máquina: Árvores de decisão escolhem gulosamente o atributo de maior ganho de informação (entropia!); o hierarchical softmax usa árvores de Huffman.
35 Casamento de cadeias: o algoritmo de Knuth-Morris-Pratt Cormen, seções 32.1 e 32.4
Objetivos
- Definir o problema de casamento de cadeias e o algoritmo ingênuo
- Calcular a função de prefixo \(\pi\) de um padrão
- Executar o KMP e mostrar que ele é \(\Theta(n + m)\)
- Medir o pior caso do ingênuo contra o KMP
Experimento
Com texto aⁿ e padrão a⁹⁹b, quantas comparações fazem o algoritmo ingênuo e o KMP?
O ingênuo faz exatamente \((n - m + 1)m\) comparações no pior caso; o KMP fica abaixo de \(3n\), \textbf{independente de \(m\)}. A função de prefixo é uma pequena tabela que evita reler o texto: mais uma vez, pré-processar troca memória por tempo.
Conexões
- Busca em texto: grep, o “localizar dos editores e navegadores e as bibliotecas de strings usam KMP, Boyer-Moore ou variações para buscar em gigabytes.
- Segurança: Antivírus e sistemas de detecção de intrusão (Snort, Suricata) procuram milhares de assinaturas ao mesmo tempo com Aho-Corasick, a generalização do KMP.
- Bioinformática: Localizar motivos em DNA, sítios de restrição e sequências repetidas: casamento de cadeias sobre o alfabeto \(\{A, C, G, T\}\).
- Compiladores: Analisadores léxicos reconhecem palavras-chave e tokens com autômatos finitos, o mesmo modelo da seção 32.3.
36 Projeto 4: rotas e redes numa cidade real Projeto
Apresentação dos projetos finais. Cada equipe monta o grafo de ruas de um bairro de Salvador (OpenStreetMap) e resolve problemas reais com os algoritmos do bloco, comparando teoria e medições.
Entregas
- Grafo de ruas extraído do OpenStreetMap (vértices = cruzamentos, arestas = trechos com comprimento), com pelo menos 10 mil vértices
- Menor caminho entre dois endereços com BFS (número de quarteirões), Dijkstra com vetor e com heap, e Bellman-Ford; tempos medidos e confrontados com a teoria
- Rede de menor custo ligando pontos de interesse (escolas, postos de saúde) com Kruskal ou Prim
- Uma técnica de projeto aplicada: programação dinâmica (por exemplo, rota que visita pontos em ordem) ou gulosa (por exemplo, cobertura de pontos)
- Apresentação de 10 minutos com mapa e demonstração ao vivo
Bloco complementar Ordenação avançada (opcional)
Cinco módulos opcionais, fora das 36 aulas, para quem quer ir além do bloco 1: quicksort, quicksort aleatorizado, limite inferior, ordenação em tempo linear e seleção.
C1 Quicksort OpcionalCormen, seções 7.1 e 7.2
Objetivos
- Executar Partition e provar sua corretude pelo invariante das quatro regiões
- Analisar o pior caso (\(\Theta(n^2)\)) e o melhor caso (\(\Theta(n\lg n)\))
- Entender por que partições desbalanceadas em proporção constante ainda dão \(n\lg n\)
- Medir \(\approx 2n\ln n\) comparações em entradas aleatórias e \(n^2/2\) em entradas ordenadas
Experimento
Quantas comparações o quicksort faz em vetores aleatórios e em vetores já ordenados?
A previsão de caso médio, \(2(n+1)H_n - 4n \approx 1{,}39\,n\lg n\), se confirma com desvio de cerca de 1%. E o pior caso é exatamente \(n(n-1)/2\), justamente na entrada mais “fácil”, o vetor ordenado. A próxima aula elimina esse risco com aleatoriedade.
Conexões
- Bibliotecas padrão: qsort (C), std::sort (introsort em C++), Arrays.sort para primitivos (quicksort de dois pivôs no Java) e sort do Go (pdqsort).
- Bancos de dados: Ordenar resultados em memória (ORDER BY) e preparar joins usa quicksort ou variações; a partição também aparece na seleção do \(k\)-ésimo (LIMIT).
- Segurança: Um adversário que conhece o pivô pode montar entradas \(\Theta(n^2)\) (“McIlroy killer): por isso as bibliotecas aleatorizam ou usam introsort.
- Computação paralela: Depois de particionar, as duas partes são independentes; GPUs ordenam com variações paralelas da partição.
C2 Quicksort aleatorizado e a análise do caso médio OpcionalCormen, seções 7.3 e 7.4
Objetivos
- Aleatorizar a escolha do pivô e entender o que isso garante
- Calcular o número esperado de comparações com variáveis indicadoras
- Distinguir caso médio (sobre entradas) de tempo esperado (sobre sorteios)
- Medir a concentração das comparações em torno da esperança
Experimento
Com entrada já ordenada, o pivô sorteado faz o quicksort voltar a 2(n+1)H_n − 4n comparações?
Na entrada que destrói o pivô fixo (\(n(n-1)/2\) comparações), o pivô sorteado volta à esperança \(2(n+1)H_n - 4n\). O histograma mostra execuções concentradas: a probabilidade de algo perto do pior caso é desprezível. Aleatoriedade troca uma entrada ruim por uma sorte ruim, e sorte ruim é rara.
Conexões
- Segurança: Tabelas hash de linguagens (Python, Rust) sorteiam a semente da função hash a cada execução pelo mesmo motivo: impedir que um atacante escolha a entrada do pior caso.
- Redes: O Ethernet usa recuo exponencial aleatório após colisões; balanceadores de carga usam “a melhor de duas escolhas aleatórias para distribuir requisições.
- Aprendizado de máquina: Gradiente estocástico, random forests e dropout: a aleatoriedade torna algoritmos mais rápidos e mais robustos, com garantias em esperança.
- Sistemas distribuídos: Protocolos de fofoca (gossip) e eleição de líder no Raft usam tempos aleatórios para evitar empates e espalhar informação em \(O(\lg n)\) rodadas.
C3 O limite inferior da ordenação por comparação OpcionalCormen, seção 8.1
Objetivos
- Modelar algoritmos de ordenação por comparação como árvores de decisão
- Provar que todo algoritmo desse tipo faz \(\Omega(n\lg n)\) comparações no pior caso
- Usar a aproximação de Stirling para \(\lg(n!)\)
- Medir quão perto do limite o merge sort chega
Experimento
O pior caso do merge sort fica acima de ⌈lg n!⌉? Quão perto do limite ele chega em média?
Em todos os \(n\) testados, o pior caso do merge sort ficou acima de \(\lceil\lg n!\rceil\), como o teorema exige, e para \(n \le 4\) ele atinge o limite. Para \(n = 2^{20}\), o merge sort faz só 1% mais comparações que \(\lg n!\). Não há como fazer muito melhor comparando; para ir além, é preciso usar a estrutura das chaves.
Conexões
- Teoria da informação: O argumento é de Shannon: uma comparação gera no máximo 1 bit. O mesmo raciocínio dá limites para busca (\(\lg n\)) e para jogos como “vinte perguntas.
- Compressão: Nenhum compressor sem perdas reduz todos os arquivos: há \(2^n\) arquivos de \(n\) bits e menos códigos menores. É o argumento de contagem das folhas.
- Criptografia: Uma chave de 128 bits tem \(2^{128}\) possibilidades: um ataque de força bruta precisa de \(\Omega(2^{127})\) tentativas em média. Limites inferiores são a base da segurança.
- Computação quântica: O algoritmo de Grover busca em \(O(\sqrt n)\), e há prova de que nenhum algoritmo quântico faz melhor: limites inferiores também valem no modelo quântico.
C4 Ordenação em tempo linear: contagem e radix OpcionalCormen, seções 8.2 e 8.3
Objetivos
- Ordenar inteiros em \(0..k\) por contagem em \(\Theta(n + k)\)
- Explicar por que a estabilidade é essencial para o radix sort
- Ordenar \(d\) dígitos em \(\Theta(d(n + k))\) e escolher a base
- Medir tempo por elemento: constante no radix, \(\lg n\) no qsort
Experimento
O tempo por elemento do radix sort fica constante enquanto o do qsort cresce como lg n?
O tempo por elemento do radix sort é praticamente constante (linear no total) e mais de 10 vezes menor que o do qsort, cujo custo por elemento cresce como \(\lg n\). O limite \(\Omega(n\lg n)\) não se aplica porque o radix sort não compara chaves: usa os bits delas.
Conexões
- GPUs: Radix sort é o padrão para ordenar em GPU (CUB, Thrust): as contagens e somas de prefixo paralelizam muito bem.
- Bancos de dados: Ordenar por chaves inteiras (datas, códigos) com radix e agrupar por contagem (GROUP BY) aparecem em bancos colunares como DuckDB.
- Bioinformática: Arranjos de sufixos de genomas são construídos com radix sort sobre o alfabeto \(\{A, C, G, T\}\): base 4, chaves curtas.
- Processamento de imagens: O histograma de uma imagem é a primeira etapa da contagem; a equalização de histograma usa exatamente as somas acumuladas de \(C\).
C5 Bucket sort e seleção em tempo linear OpcionalCormen, seção 8.4 e capítulo 9
Objetivos
- Ordenar dados uniformes em \([0, 1)\) em tempo esperado linear com baldes
- Achar o \(i\)-ésimo menor sem ordenar, em tempo esperado \(\Theta(n)\)
- Conhecer a seleção determinística linear (mediana das medianas)
- Medir \(\approx 3{,}39\,n\) comparações para a mediana
Experimento
A seleção da mediana faz cerca de 3,39 n comparações? E o bucket sort depende da distribuição?
A seleção da mediana fica em \(\approx 3{,}39\,n\) comparações em média: linear, sem ordenar. O bucket sort é linear se a hipótese de uniformidade vale; com todos os dados num balde, volta a ser quadrático. Algoritmos de caso médio dependem da distribuição da entrada; aleatorizados, só da sorte.
Conexões
- Estatística e dados: Mediana, quartis e percentis (p50, p99) são seleções. Ferramentas de monitoramento calculam percentis de latência sem ordenar milhões de amostras.
- Bancos de dados: ORDER BY ... LIMIT k e PERCENTILE_CONT usam seleção; histogramas em baldes guiam o otimizador de consultas.
- Aprendizado de máquina: Árvores de decisão (k-d trees) dividem pela mediana de cada coordenada; a mediana é um estimador robusto contra valores extremos.
- Tabelas hash: O bucket sort é uma tabela hash ordenada: a análise dos baldes (\(E[n_i^2]\)) é a mesma do encadeamento da aula 19.