Ciência da Computação — Currículo Fundamental Formação geral orientada por pré-requisitos e lacunas explicitadas.
Material educacional independente, sem endosso das empresas citadas.
Progresso da trilha 0 / 0
O progresso fica armazenado somente neste navegador. Limpar progresso
1. Matemática, algoritmos e implementação Fundamentos de programação: controle de fluxo, funções e invariantes Aprenda condicionais, laços, funções, escopo e invariantes ao derivar um algoritmo linear de arrays com casos-limite. Tipos e representação de dados: inteiros, bytes, texto e precisão Aprenda contratos de tipos, limites de inteiros, endianness, UTF-8 e precisão numérica com formato binário verificável. Lógica, técnicas de demonstração e invariantes de laço Construa argumentos precisos com proposições, quantificadores, contraexemplos, indução, invariantes e provas de terminação. Semântica de programação, aliasing e contratos executáveis Analise avaliação, igualdade, mutação, exceções e contratos de funções antes de aplicar recursos da linguagem em algoritmos. Fundamentos de memória: referências, aliasing e duração de objetos Compreenda associação de nomes, identidade, referências mutáveis, quadros de chamadas e snapshots imutáveis com exemplos. Fundamentos de C: ponteiros, arrays, limites e duração de objetos Aprenda ponteiros em C, conversão de arrays, aritmética válida, propriedade e duração com um programa C11 verificável. Matemática discreta: conjuntos, contagem e probabilidade exata Demonstre identidades de contagem, permutações, combinações, probabilidade condicional, Bayes e esperança com frações exatas e verificações exaustivas. Relações Binárias, Classes de Equivalência e Ordens Parciais Deduza partições, ordens parciais, fecho de alcançabilidade e dependências topológicas com contraexemplos executáveis. Análise assintótica e custo de algoritmos Aprenda a deduzir custos de tempo e memória por contagens, invariantes e recorrências, distinguindo pior caso, custo amortizado e esperança matemática. Cálculo em ponto flutuante: arredondamento, cancelamento e soma compensada Analise aproximação binária, adição não associativa e soma compensada de Neumaier com oráculos racionais exatos. Estatística numericamente estável: média online e variância de Welford Derive atualizações em uma passagem, diferencie variâncias amostral e populacional e teste com frações exatas. Fundamentos de teoria dos números: divisibilidade, MDC e algoritmo de Euclides Derive divisibilidade, algoritmo de Euclides e coeficientes de Bézout com provas, inteiros negativos e exercícios. Aritmética modular: congruências, inversos e exponenciação rápida Derive congruências, inversos modulares e quadrados sucessivos com invariantes de correção e testes exaustivos. Raciocínio algorítmico: especificação, força bruta, invariantes e otimização Aprenda um método de resolução de problemas ao derivar um algoritmo linear correto a partir de uma solução quadrática. Recursão, pilha de chamadas e divisão e conquista Entenda contratos recursivos, casos-base, quadros da pilha, provas de término e recorrências de divisão e conquista com testes. Resolução de Recorrências: Árvores, Substituição e Teorema Mestre Deduza e verifique recorrências de divisão e conquista, contagens exatas, casos do Teorema Mestre, contraexemplos e uso da pilha. Arrays e strings: representação, custos e percursos corretos Compreenda arrays contíguos, crescimento dinâmico, indexação, slices, Unicode e invariantes de limites com exemplos testados. Tipos abstratos de dados: interfaces, invariantes e custos Separe o contrato do TAD da representação e derive uma fila circular limitada com provas de FIFO e complexidade. Arrays dinâmicos: capacidade, redução e análise amortizada Implemente array redimensionável com append, pop e redução de capacidade; demonstre custos amortizados. Listas ligadas: nós, inversão, ciclos e propriedade Implemente e demonstre a inversão de lista simplesmente ligada e a detecção de ciclo de Floyd, comparando custos com arrays. Pilhas e filas: LIFO, FIFO, deques e invariantes Diferencie contratos de pilhas e filas, demonstre seus invariantes e implemente verificação de delimitadores e filas para BFS. Algoritmos de ordenação: estabilidade, mergesort, quicksort e heapsort Deduza insertion, merge, quick e heap sort, compare custos e estabilidade e verifique duas implementações completas. Busca binária: limites, invariantes e predicados monótonos Deduza a busca binária com invariante de partição, implemente limites, analise complexidade e identifique condições de invalidade. Tabelas hash, colisões e invariantes Entenda funções hash, tratamento de colisões, fator de carga e entradas adversariais por meio de um algoritmo verificável e suas limitações. Heaps binários e filas de prioridade Explique os invariantes de forma e ordem, derive atualizações logarítmicas, heapify linear e resolva top-k com exemplos executáveis. Árvores binárias e BSTs: percursos, ordenação e altura Explique estrutura de árvores binárias, DFS/BFS, ordenação BST e complexidade dependente da altura com implementação iterativa. Busca em grafos com BFS e DFS Deduza BFS e DFS, caminhos mínimos em grafos sem pesos, invariantes de visitação e limites de custo em função de vértices e arestas. Linguagens Formais e Autômatos Finitos: AFD, AFN, Fecho Épsilon e Determinização Fundamentos de AFD e AFN: linguagens regulares, fecho épsilon, determinização, provas e testes independentes em Python. Gramáticas Livres de Contexto, Autômatos com Pilha e Análise Sintática Fundamentos de gramáticas livres de contexto: pilha, árvores sintáticas, reconhecimento por tabela e testes independentes em Python. Compilador de Expressões: Análise Léxica, AST, Bytecode e Máquina Virtual Implemente uma linguagem aritmética: tokens ASCII, parser com precedência, AST, bytecode de pilha e avaliação racional exata. Sistemas de Tipos Estáticos, Escopos Léxicos e Compilador de Expressões Tipadas Amplie o compilador com variáveis tipadas, escopos léxicos, verificação estática, expressões condicionais e bytecode testado. Funções Tipadas, Closures Léxicas e Quadros de Chamada da Máquina Virtual Compile funções tipadas, closures e chamadas de ordem superior com quadros de ativação explícitos e testes independentes de execução. Células Mutáveis, Closures Compartilhadas e Funções Recursivas Tipadas Estenda o compilador tipado com células mutáveis, atribuições e let rec, verificando compartilhamento de memória e recursão na VM. Endereços Léxicos, Verificação de Bytecode Tipado e Máquina Virtual por Slots Resolva variáveis por slots, analise controle de fluxo e tipos da pilha do bytecode e confira os resultados com uma VM independente. Serialização Versionada de Bytecode, Integridade e Carregamento Verificado Defina um formato versionado e limitado para bytecode com JSON determinístico, checksum, decodificação rigorosa e verificação da VM. Alcançabilidade no Heap, Tempo de Vida e Coleta Mark-and-Sweep Derive alcançabilidade e construa um coletor mark-and-sweep limitado com closures, células compartilhadas, ciclos e testes independentes. Garbage Collection Integrado à VM: Raízes, Closures e Ciclos Recursivos Integre mark-and-sweep por raízes explícitas à VM de slots, preservando closures mutáveis e coletando ciclos recursivos inacessíveis. Programação dinâmica: estados e recorrências Aprenda a definir estados, derivar recorrências, demonstrar transições e escolher memoização ou tabulação com limites de custo explícitos. 2. Projeto e engenharia de software Programação modular: coesão, interfaces explícitas e funções puras Aprenda a decompor programas em módulos coesos, separar cálculos de entrada/saída e testar contratos sem depender de frameworks. Contratos de erro em Python: exceções e liberação de recursos Defina entradas inválidas, propague exceções e verifique limpeza com context managers e streams reproduzíveis. Fundamentos de arquivos e dados: bytes, UTF-8, JSON e validação Leia arquivos JSON UTF-8 limitados, rejeite dados ambíguos e grave registros validados com limites explícitos. Fundamentos de Git: diretório de trabalho, index, commits e branches Compreenda os três estados do Git, snapshots versionados, branches e merges com uma sequência testável em repositório isolado. Testes, contratos e manutenção segura Aprenda a realizar alterações verificáveis com invariantes, testes de fronteira, contratos de integração, regressões e análise de riscos operacionais. Fundamentos de Clean Code: coesão, acoplamento e mudanças seguras Derive fronteiras de código legível por coesão, acoplamento, funções puras, contratos e testes de um planejador de estoque reproduzível. Design orientado a objetos: encapsulamento, composição e polimorfismo Projete fronteiras orientadas a objetos com encapsulamento, composição, polimorfismo, contratos e modelo testado de preços. Low-Level Design: contratos, máquinas de estados e dependências Projete componentes sustentáveis a partir de invariantes, transições, interfaces e direção de dependências, com modelo testado. SOLID, inversão de dependências e contratos de comportamento Aplique SRP, OCP, LSP, ISP e DIP com contratos Python, fronteiras estáveis e testes de comportamento verificáveis. Arquitetura de software: fronteiras de dependência e projeto modular Derive arquiteturas em camadas e portas/adaptadores, imponha dependências entre módulos, registre decisões e teste um monólito modular. Modelagem de domínio: entidades, objetos de valor e invariantes de agregados Diferencie identidade de valores imutáveis, escolha fronteiras transacionais e imponha invariantes de pedidos com contratos executáveis. Estratégias de testes: unidades, contratos, integração e E2E Diferencie testes unitários, de propriedades, integração, contrato e E2E com exemplos executáveis e limites de evidência. Refatoração e padrões: Strategy, Adapter e preservação de comportamento Refatore com testes de contrato; compare Strategy, Adapter e Decorator em Python, com exemplos e limites práticos. Famílias de padrões de projeto: Builder, Facade e Observer Derive padrões criacionais, estruturais e comportamentais com exemplos executáveis de Builder, Facade e Observer e contratos de falha. Padrões State e Command: transições, repetição e contratos de falha Separe regras de estado de solicitações encapsuladas com State e Command, testando versões, ações inválidas e execução repetida. Padrões criacionais: Factory Method, Abstract Factory e fábricas simples Compare seleção de construtores, métodos de criação sobrescritos e famílias de objetos compatíveis em pipelines de exportação testados. Debugging e profiling: reprodução, CPU, memória e tracing Diagnostique falhas com casos reproduzíveis, oráculos independentes, profiling de CPU, memória e telemetria. Ciclo de vida do software: dos requisitos à operação Acompanhe requisitos, arquitetura, entregas testáveis, releases mensurados, aprendizado em incidentes e manutenção. CI/CD e engenharia de releases: canary, schema e rollback Projete gates de CI, artefatos imutáveis, canary, migrações seguras, segredos e procedimentos de recuperação. 3. Processos, threads, memória e redes Lógica digital: portas booleanas, tabelas-verdade e somadores binários Derive AND, OR, NOT e XOR por tabelas-verdade e construa meios-somadores, somadores completos e soma de largura fixa. Fundamentos de lógica sequencial: relógio, registradores e máquinas de estados Derive transições síncronas, flip-flops D, registradores e máquinas de estados com rastreamentos e invariantes executáveis. Representação de máquina, instruções de CPU e mapeamento de cache Derive complemento de dois, endianness, execução de instruções e conflitos de cache com modelos Python reproduzíveis e casos-limite. Fundamentos de CPU: caminho de dados, controle e ciclo de instruções Rastreie PC, acumulador, memória, ALU e desvios em uma CPU didática de oito bits com semântica explícita. Pipeline de CPU: dependências, forwarding e previsão de desvios Derive latência, vazão, stalls, dependências de carga e previsão de desvios de dois bits com modelos e testes independentes. Do código C ao executável: pré-processamento, objetos e ligação Compile C11 com vários arquivos e compreenda unidades de tradução, símbolos, falhas de ligação e carregamento. Fundamentos de build: grafos de dependência, compilação incremental e GNU Make Derive o grafo de build e teste regras C11 com dependências de cabeçalhos, alvos phony e propagação de falhas. Como programas executam: argumentos, ambiente, streams e status de saída Estude a execução de programas C11 com argumentos, ambiente, stdout, stderr e testes de processo. Processos, memória virtual e chamadas de sistema Deduza isolamento de processos, tradução de endereços, tabelas de páginas, TLB, troca de contexto e proteção do kernel. Alocação de memória: listas livres, fragmentação e coalescência Modele alocação first-fit e best-fit, blocos livres, fragmentação interna e externa, divisão e coalescência com testes independentes. Descritores de arquivos, buffering de I/O e persistência com fsync Estude descritores, dup, offsets compartilhados, read/write, buffering e fsync com modelos Python e testes independentes. Sistemas de arquivos: inodes, blocos, journaling e recuperação Modele inodes, entradas de diretório, alocação não contígua de blocos e recuperação por redo log com testes finitos independentes. Escalonamento de CPU: FCFS, Round Robin, métricas e justiça Derive políticas FCFS e Round Robin, preempção, tempo de resposta, espera e turnaround com simuladores e testes independentes. Concorrência: corridas, locks, condições e deadlocks Deduza invariantes de sincronização, seções críticas, condições de corrida, variáveis de condição, deadlocks e filas limitadas. Escalonamento por prioridades: MLFQ, aging e herança de prioridade Analise escalonamento MLFQ, boost periódico, starvation e inversão de prioridades com modelos de CPU e locks verificáveis. Modelos de memória: atômicos, happens-before e visibilidade Explique data races em C++, ordem por objeto, release/acquire, operações relaxed, consistência sequencial e publicação segura. Oficina de C++17: token bucket thread-safe e compilação no CI Construa token bucket em C++17 com relógio monotônico injetado, mutex, invariantes, validação e testes compilados no CI. Fundamentos de HTTP: cliente, servidor, requisições e respostas Entenda métodos, códigos de status, semântica de GET/POST/PUT/DELETE e responsabilidades de APIs antes de system design. Roteamento IP e DNS: seleção de prefixos, resolução e cache TTL Derive seleção de rotas IPv4 por prefixo e cache de DNS com TTL, expiração e modelos Python avaliados por oráculos independentes. Tamanho de pacotes IP: fragmentação IPv4 e descoberta da MTU do caminho Deduza offsets IPv4 de oito bytes, flags MF/DF, remontagem e descoberta clássica de MTU com modelos finitos verificáveis. DNS autoritativo: cadeias CNAME e cache de respostas negativas Estude autoridade DNS, delegações, CNAME, NXDOMAIN/NODATA e TTL negativo da SOA com modelos Python e testes independentes. Fundamentos de redes: DNS, TCP, TLS e HTTP Acompanhe uma requisição por DNS, transporte, TLS e HTTP; derive custos de latência e falhas e diferencie TCP de QUIC. TCP como fluxo de bytes: enquadramento, ACK e controle de fluxo Derive enquadramento de mensagens TCP, sequência de bytes, ACK cumulativo e limites de envio com modelos Python verificados independentemente. Temporizadores TCP: estimativa de RTT, retransmissão e janelas de congestionamento Derive SRTT, RTTVAR, RTO e backoff da RFC 6298; diferencie uma simulação por rodadas de cwnd/ssthresh do TCP real. 4. Segurança, armazenamento e sistemas distribuídos TLS 1.3: autenticação, HKDF e derivação de chaves Entenda autenticação e derivação de chaves TLS 1.3, diferencie HKDF de cifragem e valide HKDF-SHA256 e rótulos TLS com vetores normativos. Segurança de APIs: identidade, autorização e modelos de ameaça Distinga autenticação da autorização por objeto, analise fronteiras OAuth e JWT e derive isolamento multi-tenant e controles de API. Segurança OAuth 2.0: PKCE, vinculação de tokens e replay Deduza o fluxo de código com PKCE, fronteiras de ameaça, rotação de refresh tokens, audiência e resistência a replay a partir de RFCs. Fundamentos de bancos relacionais: chaves, JOINs e integridade Derive tabelas, chaves primárias e estrangeiras, normalização e consultas SQL com restrições e exemplos executáveis. Fundamentos de SQLite: CRUD parametrizado e transações atômicas Construa e teste um repositório SQLite com parâmetros vinculados, limites de saldo e rollback transacional. Migrações de esquema SQLite: user_version, compatibilidade e rollback Evolua o esquema SQLite entre versões preservando registros, rejeitando estados inconsistentes e revertendo falhas. Armazenamento de bancos: páginas, MVCC, B-trees e WAL Analise armazenamento de tuplas, splits de B-tree, visibilidade MVCC e recuperação por WAL com base no PostgreSQL. Planejamento SQL: seletividade, estatísticas, índices e joins Compreenda planos SQL por custo, estimativa de cardinalidade, índices compostos, joins e EXPLAIN ANALYZE com contas verificáveis. Transações, isolamento e consistência distribuída Diferencie ACID, anomalias transacionais, serialização, linearizabilidade e defasagem de réplicas usando modelos explícitos de operações. Índices transacionais: MVCC, unicidade e isolamento serializável Explique constraints únicas com concorrência, índices multiversão, locks de predicado, write skew, retries e custos de indexação. Filas, semântica de entrega e idempotência Projete processamento assíncrono com confirmações, reentregas, filas de erro, consumidores idempotentes e controle explícito de pressão. Consenso distribuído: Raft, quóruns e logs replicados Deduza interseção de quóruns e termos do Raft, eleições, replicação de logs, regras de commit e limites sob partições. Modelos de partições de rede: verificação exaustiva de quoruns Enumere grafos de conectividade de três e cinco nós, demonstre exclusividade de maioria e delimite falhas ainda não testadas. 5. Arquitetura e julgamento operacional Estimativas de capacidade e restrições de sistemas Derive estimativas de tráfego, armazenamento, utilização e capacidade de pico com hipóteses explícitas, sem confundir médias com garantias. Método de System Design: requisitos, capacidade, interfaces e falhas Aprenda um método completo de projeto de sistemas com requisitos, dimensionamento, APIs, dados, tratamento de falhas e SLOs verificáveis. System Design: escrita autoritativa, projeções de leitura e consistência Projete caminhos de escrita e projeções de leitura com eventos seguros para replay, limites de atraso e verificação de recuperação. Seleção de armazenamento: relacional, documentos, chave-valor e objetos Escolha armazenamento por consultas, invariantes de consistência e custos; compare SQL, documentos, chave-valor, blobs e busca. Fronteiras de serviços: monólitos modulares, microsserviços e eventos Escolha fronteiras entre serviços por autoridade, consistência, falhas síncronas e custos reais de escala. Resposta a incidentes em produção, recuperação e postmortems Organize comando de incidentes, estabilize serviço, meça impacto, preserve evidências e produza ações verificáveis de postmortem. Verificação formal: invariantes, exploração de estados e TLA+ Aprenda safety, liveness, atomicidade e refinamento com exploração finita de estados num protocolo concorrente de reservas e fundamentos TLA+. Ainda não publicado nesta edição Não publicados: teoria dos números além de Euclides e aritmética modular básica, e recorrências de ordem superior, florestas de análise, recursão mútua, coleta incremental e análise detalhada do layout de objetos, distribuição autenticada de bytecode e código nativo, computabilidade de Turing, P/NP, temporização física de circuitos sequenciais, implementação microarquitetural, coerência de cache, alocadores de produção, escalonamento multicore avançado, recuperação real de filesystems e injeção de falhas, modelos completos de sequência circular/retransmissão e congestionamento TCP por ACK, DNSSEC, descoberta de vizinhos IPv6 e capturas reais de pacotes, AEAD/assinaturas/PKI além de HKDF, P2P e blockchain opcional.
Requisitos documentados publicamente https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/ https://pages.cs.wisc.edu/~remzi/OSTEP/