Lições Interativas de Matemática e Ciências

Computação

Um computador faz exatamente o que lhe foi dito, depressa o suficiente para tornar impossível ignorar a diferença entre um bom algoritmo e um mau. Aqui correm os dois e vê-se a distância abrir-se.

Newest in this category

Capítulos

Sequências curtas em vez de ferramentas soltas. Cada passo entrega ao seguinte algo específico, pelo que vale a pena seguir a ordem.

L1: fundamentos

Como um computador executa um programa

COMPDe uma porta lógica a um programa em execução. Só com portas NAND podemos construir qualquer circuito. Um somador construído com portas lógicas também faz subtrações. No Little Man Computer, esse somador trabalha com uma centena de caixas de correio: o programa ocupa a mesma memória que os números, e a máquina executa o que encontrar no endereço indicado pelo contador de programa.

  1. 01Portas lógicas
  2. 02Aritmética binária
  3. 03O Little Man Computer
  4. 04Memória e bytes
  5. 05A pilha de chamadas
  6. 06Cache e localidade

L1: fundamentos

Como se quebram os códigos

COMPCada cifra aqui esconde as letras e deixa outra coisa à vista. A substituição preserva a contagem das letras, a cifra com palavra-chave organiza-as em colunas e o bloco de uso único usado duas vezes expõe os espaços. Só uma chave aleatória tão longa quanto a mensagem não revela rigorosamente nada. O difícil é fazer chegar essa chave ao outro lado, proeza que as duas últimas páginas realizam em público.

  1. 01Cifra de substituição
  2. 02Cifra de Vigenère
  3. 03Bloco de uso único
  4. 04Diffie–Hellman
  5. 05RSA

L2: escola

O que custa pouco numa estrutura de dados

COMPCada estrutura responde depressa a uma pergunta, mas paga por isso noutro ponto. Um filtro de Bloom não guarda nenhuma chave e ainda assim consegue dizer de certeza que não. Uma árvore de prefixos responde a perguntas sobre prefixos que uma tabela de dispersão não consegue resolver; um amontoado sabe sempre qual é a sua menor chave e pouco mais. Na última página, é preciso decidir que página retirar da memória. A melhor escolha exige conhecer o futuro.

  1. 01Filtro de Bloom
  2. 02Árvore de prefixos
  3. 03Amontoado binário
  4. 04Substituição de páginas

L3: universidade

Proteger uma transmissão: revogar um dispositivo e depois descobrir qual

COMPDuas metades do mesmo problema, na ordem em que um estúdio se depara com elas. Primeiro, uma chave foi exposta e a licença tem de continuar a funcionar para todos os outros, o que acaba por custar um cabeçalho que não cresce de todo com a dimensão do sistema. Depois vem a parte mais complexa: saber de quem era a chave a partir de uma cópia que vários subscritores construíram em conjunto com o propósito expresso de não identificar ninguém.

  1. 01Revogação de dispositivos
  2. 02Marca de água forense

L3: universidade

A transformada de Fourier na prática

COMPUm sinal é uma soma de setas giratórias. Na prática, qualquer interpretação acarreta custos que as fórmulas dos manuais omitem. Uma janela finita dispersa por todas as bandas os tons que nela não couberem. Janelas curtas compram tempo. Pagam em afinação. Uma média também atua como um filtro com forma própria. A última página explica a lógica que permite calcular tudo isto atempadamente.

  1. 01Transformada discreta de Fourier
  2. 02Espectrograma
  3. 03Média móvel como filtro
  4. 04Transformada rápida de Fourier

L3: universidade

Por que razão um algoritmo está correto

COMPUm algoritmo está correto por uma razão que se pode enunciar, e incorreto por uma falha que um pequeno teste revela. Cada página confronta uma versão correta com uma alternativa plausível mas errada: catorze das dezasseis formas de programar uma busca binária falham. O algoritmo guloso para o troco perde nas antigas moedas britânicas. Nunca falha com os cêntimos americanos. Kruskal e Prim concordam por um motivo claro. E um código concebido para corrigir um bit invertido torna duas inversões ainda piores.

  1. 01Busca binária
  2. 02Troco em moedas
  3. 03Árvore de expansão mínima
  4. 04Código de Hamming

L3: universidade

Compressão manual

COMPQuatro codificadores que poderia fazer no papel, ordenados por aquilo que cada um consegue ver e que o anterior não conseguia. O quarto não comprime absolutamente nada, e é a razão pela qual o primeiro funciona com texto.

  1. 01Run-length
  2. 02Huffman
  3. 03LZ77
  4. 04Burrows-Wheeler

Problemas resolvidos na íntegra

O que se descobre aqui

Artigos escritos a partir destas ferramentas

Todas as ferramentas desta secção

Algorithms & Data Structures

Árvore geradora mínima: Kruskal e Prim
Doze aldeias, 66 estradas possíveis. Kruskal e Prim escolhem 11 delas por ordens diferentes e chegam aos mesmos 199,04 km, porque cada estrada escolhida é a mais curta que atravessa um corte. Seguir sempre para a aldeia mais próxima custa mais 10,76%; para três cidades separadas por 40 km, uma junção entre elas permite poupar 13,40%.
Bloco de uso único: inquebrável uma vez, vulnerável em duas
Cifre uma mensagem com uma chave aleatória do mesmo tamanho; depois, digite outra frase qualquer com esse comprimento e descubra a chave que a teria gerado. Ao reutilizar a chave numa segunda mensagem, ela anula-se: arraste uma palavra provável ao longo do resultado para ler os dois textos.
Caminho mais curto de Dijkstra
O nó 1 está a uma aresta da origem com um custo de 4, e a sua distância mais curta é de 3 através do nó 3. Carregue a predefinição de aresta negativa e o nó 3 estabiliza em −1, enquanto a reconstrução da rota regista um ciclo.
Cifra de Vigenère: encontre o comprimento da chave e quebre a cifra
Cifre o início de Alice no País das Maravilhas com uma palavra-chave e depois decifre o texto: encontre o comprimento da chave pelo índice de coincidência a cada k letras, confirme o resultado com as repetições do teste de Kasiski e deduza cada letra da chave pela pontuação do qui-quadrado.
Cifras de Substituição: 26! Chaves, Quebradas a Contar Letras
Decifre uma cifra de César e uma substituição completa a partir da contagem de letras. O teste do qui-quadrado identifica o deslocamento de César correto em 99,1% das vezes com 31 letras; já a ordenação por frequência, mesmo num conto inteiro de 32.725 letras, erra cinco das 26 letras.
Corrida de Algoritmos de Ordenação
Uma sequência invertida de 64 elementos custa ao bubble sort exatamente 2016 trocas, uma por inversão, e qualquer algoritmo de troca de vizinhos tem esse mesmo limite. O quicksort resolve o problema com 32 trocas, movendo os elementos por 63 posições.
Diffie–Hellman: um segredo combinado em público
Alice e Bob combinam um segredo num canal aberto, e o leitor veste a pele de bisbilhoteiro. Acompanhe a força bruta e o algoritmo de Pohlig–Hellman tentativa a tentativa, e veja por que razão o primo 1621 cede em apenas 21 tentativas, enquanto 1619, dois números abaixo, resiste durante 811.
Explorador da Árvore de Recursão
Conte as chamadas, os subproblemas distintos e a profundidade da pilha de uma árvore de chamadas recursivas ingênua para Fibonacci, a Torre de Hanói, a regra de Pascal, o merge sort e a subida de escadas, e veja exatamente onde uma tabela de memoização compensa o esforço.
Explorador de Coloração de Grafos
Colora os vértices de um grafo, teste restrições cromáticas e explore limites inferiores por clique.
Explorador de complexidade Big-O
Visualize como as taxas de crescimento O(1), O(log N), O(N), O(N²), O(2ᴺ) e O(N!) se comparam em diferentes escalas.
Filtro de Bloom: de certeza que não ou provavelmente sim
Insira palavras num filtro de Bloom, uma de cada vez, pesquise outras e conte os falsos positivos em 10 000 cadeias de caracteres que nunca foram inseridas. Compare a estimativa habitual com os resultados deste filtro, encontre o melhor número de funções de dispersão e descubra por que razão um filtro de Bloom simples não permite eliminar palavras.
Heap binário: uma fila de prioridades num vetor
Quinze chaves que chegam por ordem decrescente exigem 34 comparações quando inseridas uma a uma e 22 na construção a partir do último pai; com 1.023 chaves, são 8.194 e 2.026. Acompanhe cada comparação e cada troca, com a árvore e o vetor lado a lado, e extraia as chaves por ordem crescente.
Pesquisa binária: quatro escolhas, dezasseis ciclos
Um ciclo de pesquisa binária envolve quatro escolhas, e apenas 2 das 16 combinações possíveis estão certas. Construa o ciclo, veja-o percorrer um pequeno vetor e teste-o em todos os vetores até 256 elementos. Qualquer ciclo errado já terá falhado com dois elementos.
Substituição de páginas: FIFO, LRU e a política ótima
Percorra uma sequência de referências com algumas molduras de memória, usando FIFO, LRU e a política ótima de Bélády, e conte cada falha de página. Na sequência 1 2 3 4 1 2 5 1 2 3 4 5, FIFO produz 9 falhas com três molduras e 10 com quatro; em LRU e OPT, aumentar a memória nunca aumenta o número de falhas.
Trie: a árvore de prefixos, passo a passo
Guarde palavras numa trie e acompanhe, passo a passo, uma pesquisa, um preenchimento automático e uma inserção. Compare quantas letras a trie, a pesquisa binária e uma tabela de dispersão leem para encontrar a mesma palavra, e quantos bytes ocupa cada estrutura. Mesmo partilhando 40 das suas 70 letras, a trie ocupa 2,6 vezes o espaço da lista simples.
Troco em moedas: método guloso contra solução ótima
Para pagar 48d no antigo sistema monetário britânico, o método guloso entrega uma meia-coroa, um xelim e uma moeda de seis pence, quando bastariam dois florins. Compare-o com a solução ótima por programação dinâmica em qualquer sistema de moedas, acompanhe o preenchimento da tabela célula a célula e veja o limite que torna finita a verificação de um sistema.
Visualizador BFS vs DFS
O nó 15 encontra-se a 6 arestas do início; a pesquisa em profundidade pode apresentar-lhe uma rota de 12 arestas até lá. A componente contém 15 nós distribuídos por 16 arestas, pelo que as 2 arestas excedentes são a causa de todas as divergências entre os dois painéis.
Visualizador da Distância de Levenshtein
Calcula a distância de edição (inserções, eliminações, substituições) entre duas cadeias de texto e visualiza a comparação.
Visualizador de algoritmos de busca de caminho
Veja A*, Dijkstra, Greedy Best-First e BFS percorrerem uma grade, passo a passo.
Visualizador de árvores BST / AVL
Ao inserir 10, 20, 30, 40, 50, 60, 70 por esta ordem, a árvore torna-se numa cadeia de altura 7, necessitando de sete comparações para encontrar a última chave quando três bastariam. As rotações AVL colocam essas mesmas sete chaves a uma altura de 3.
Visualizador de Tabela Hash
Veja como as tabelas hash armazenam dados com resolução de colisões por encadeamento, sondagem linear e sondagem quadrática.

Information Theory & Encoding

Aritmética binária e complemento de dois
Somar 100 + 50 em oito bits resulta num byte com a leitura de 150 sem sinal e −106 com sinal, pelo que a flag de transporte indica sucesso e a de transbordo assinala um erro. Ao somar 200 + 100 as flags invertem-se, sendo este o motivo pelo qual um somador necessita de ambas.
Codificação run-length (RLE)
Comprima símbolos repetidos em pares de contagem e valor e examine os melhores e piores casos.
Demo do compressor LZ77
Acompanhe passo a passo as referências retroativas de janela deslizante usadas no DEFLATE, ZIP e gzip.
Detector e conversor de codificação/base
Detecta a codificação provável ou o formato estruturado e, em seguida, decodifica e explica do que provavelmente se trata.
Laboratório de entropia em PLN
Entropia dos tokens, entropia cruzada, perplexidade e divergência KL: os quatro valores usados para treinar e avaliar um modelo de linguagem.
Playground de codificação de entropia
Relaciona distribuições de símbolos com a entropia de Shannon, o ganho de compressão esperado e a previsão do próximo token em IA/LLMs.
Ponto flutuante
Digite um número decimal e acompanhe o computador a convertê-lo: sinal, binário, normalização, viés e arredondamento. Veja o valor final armazenado, o erro e a distância até ao próximo número possível de representar.
Transformada de Burrows-Wheeler (BWT)
Veja como a BWT reordena o texto em sequências repetidas que comprimem melhor, e como revertê-la sem perdas.
Visualizador de Codificação de Huffman
Codificar hello world reduz 88 bits para 32, contra um limite entrópico de 31,3, correspondendo os 0,7 aos comprimentos de código arredondados para bits inteiros. Uma fonte de 90/10 transporta 0,469 bits por símbolo e, no entanto, a codificação de Huffman gasta 1.

Signal & Media Processing

A Transformada Rápida de Fourier
A transformada rápida de Fourier obtém os mesmos N números da soma direta com cerca de N log N multiplicações em vez de N². Acompanhe os seus diagramas de borboleta, refaça o exemplo de doze pontos do manuscrito não publicado de Gauss de 1805, e meça o tempo de ambos os métodos no seu navegador.
Detector de bordas Sobel vs Canny
Aplique gradientes de Sobel e histerese de Canny para comparar pipelines de detecção de bordas.
Espectrograma
Um espectrograma desliza uma transformada de Fourier de curto termo por uma peça musical, e o comprimento da janela decide o que pode ser revelado. Distinguir o Lá4 do Lá♯4 exige 72,0 ms com uma janela de Hann; um semitom em Lá1, a 55 Hz, requer 576,2 ms, mais do que quatro semicolcheias. Assim, num trilo rápido de baixo, a nota tocada surge em menos de um quarto das fatias com qualquer janela até um segundo de duração.
Laboratório de amostragem de pixels
Entenda amostragem, Nyquist e aliasing com visualizações de sinal e de grade de pixels.
Laboratório de Codificação de Vídeo
Aprenda sobre taxa de bits, codec, CRF/CBR e os compromissos de qualidade com estimativas visuais em tempo real.
Laboratório de quantização
A quantização de oito bits regista aqui 56,18 dB, quando a fórmula teórica de 6,02N + 1,76 indica 49,92. O desvio de 6,2 dB deve-se ao fator de crista: essa regra refere-se a um seno de escala completa, e esta rampa tem mais do dobro do seu valor eficaz.
Laboratório de subamostragem de crominância
Compare 4:4:4, 4:2:2 e 4:2:0 para ver a perda de detalhe de cor na compressão de imagem e vídeo.
Playground de convolução e mapas de características
Catorze camadas de 3×3 sobrepostas permitem que um píxel de saída veja toda a imagem de 28×28, com 126 multiplicações e acumulações. Um núcleo de 29×29 com o mesmo alcance custa 841, e é por isso que as redes de visão são longas e estreitas.
Simulador de controle de taxa
Tanto o CRF como o CBR gastam aqui os mesmos 2000 bits por quadro, e ainda assim o CRF atinge 89,8 contra 79. Estes 10,8 pontos compram um pico plano: o maior quadro do CBR tem 2000 bits, enquanto o do CRF tem 4078.
Simulador de estimativa de movimento
As 225 posições de pesquisa por bloco formam uma janela de 15×15, de −7 a +7 píxeis, com um custo que é quadrático em relação ao raio: 961 para 15, e 3969 para 31. Uma pesquisa em três passos verifica apenas 27 posições e aceita um vetor inferior.
Transformada Discreta de Fourier
Amostre um tom puro 64 vezes e calcule a sua transformada discreta de Fourier: com exatamente 10 ciclos obtém-se uma barra nítida. A 10,5 ciclos todas as barras se acendem e a mais alta regista 64,61% do tom. Cada barra é desenhada como as 64 setas que a compõem. Uma janela permite trocar a dispersão por um pico mais largo.
Verificador de Contraste de Cores (Luminância WCAG)
Verifique o contraste entre cores de texto e de fundo em relação aos limites de acessibilidade do WCAG 2 — e veja como a fórmula de luminância por trás disso descende da necessidade da televisão em cores de 1953 de encaixar a cor em um sinal preto e branco já existente.
Visualizador de estrutura do GOP
Entenda os padrões de quadros I/P/B, latência de busca e os trade-offs de compressão em transmissões de vídeo.

Automata & Cryptography

A Marca de Água que Sobrevive a um Conluio
Cada cópia transporta uma sequência de bits diferente, logo um vazamento identifica o assinante. Quatro deles comparam cópias e forjam uma que não identifica ninguém. Isto a menos que a sequência tenha 2.490 bits de comprimento, sendo que dezesseis deles precisam de 39.833.
A pilha de chamadas: registos de ativação, endereços de retorno e transbordamentos
Veja como cada chamada de função escreve na memória: coloca um argumento, um endereço de retorno e um ponteiro de registo de ativação guardado numa pilha de 128 bytes. Cada retorno salta para o endereço que estiver na posição reservada para esse fim. Explore a recursão, o transbordamento da pilha, um vetor que sobrescreve o seu próprio endereço de retorno e uma variável que contém o valor deixado pela chamada anterior.
Animador de Autômato Finito
Percorra as transições de um AFD em um diagrama de estados ao vivo — observe qual estado está ativo após cada símbolo e se a entrada é aceita.
Explorador de Portas Lógicas
Visualizador interativo de portas lógicas e pequenos circuitos com pulsos de sinal, diagramas de tempo e tabelas de verdade compactas.
Localidade na cache: a ordem das leituras importa
Some a mesma matriz por linhas e por colunas com uma pequena cache de mapeamento direto e conte cada acerto e cada falha. As mesmas adições, nos mesmos endereços, dão 48 acertos em 64 leituras numa ordem e nenhum na outra. Com 4 inteiros não utilizados por linha, a ordem por colunas alcança o mesmo número de acertos.
Memória e bytes: ordem dos bytes, tipos e endereços
Trinta e dois bytes de memória, sem nada que diga o que representam. Lê-os como um inteiro de 8, 16 ou 32 bits, um número de vírgula flutuante ou texto, em little-endian ou big-endian, e vê por baixo de cada byte o seu valor posicional. Se leres 1 pela ordem errada, obténs 16 777 216; os bytes de π em vírgula flutuante, lidos como inteiro, dão 1 078 530 011.
Revogar um dispositivo sem avisar os restantes
Sessenta e quatro dispositivos comprometidos num milhão exigem um cabeçalho de licença com 846, 77 ou 3 chaves. O valor exato depende do esquema. Depende também de os sessenta e quatro pertencerem a um único lote.
RSA: Criptografia de Brinquedo
Com p = 61 e q = 53 obtemos n = 3233, valor que dezasseis tentativas de divisão quebram. A revelação de φ = 3120 compromete o sistema com a mesma gravidade: p + q = 114 e pq = 3233 formam uma equação quadrática que devolve ambos os primos.
Simulador de Máquina de Turing
Um palíndromo de 5 células custa 21 movimentos e um de 21 células custa 253, porque uma cabeça tem de percorrer toda a fita por cada par. Uma segunda fita torna o trabalho linear, e Hennie provou em 1965 que uma única fita não o consegue fazer.
Solucionador de Expressões Booleanas
Escreve expressões lógicas booleanas e gera uma tabela de verdade completa com colunas de subexpressões intermédias.
Uma CPU em miniatura: o Little Man Computer
Avança no Little Man Computer uma transferência entre registos de cada vez e acompanha cada leitura e escrita na memória: PC, MAR, MDR, CIR e acumulador, cem caixas de correio e programas que podes editar. Calcula que parte dos acessos à memória de um programa corresponde à leitura das próprias instruções.

Demos & Utilities

Algoritmo de Busca de Grover
Percorra o algoritmo de Grover iteração por iteração. Observe a amplitude alvo crescer — O(√N) vs O(N).
Explorador da esfera de Bloch
Um qubit em θ = 90° é lido como 50/50 na base Z e 100/0 em X, logo 50/50 é um fato sobre a base que escolheu. Gire-o uns completos 360° e o estado inverte-se para −|ψ⟩; apenas uma segunda volta o restaura.
Explorador de fractais
A dimensão de Koch é log 4 / log 3 = 1,262 e a do conjunto de Cantor é de 0,631, inferior a uma linha. Três das oito curvas aqui presentes resultam em exatamente 2, e numa profundidade infinita estas preenchem o plano em vez de o atravessarem.
Extrator de Recursos HTML, Imagens e Markdown
Cola HTML e extrai os ficheiros associados por categoria, com uma galeria de imagens e exportação do texto em Markdown.
Jogo da Vida de Conway
O planador viaja a c/4, e o limite é a própria regra: uma célula vê oito vizinhos, pelo que nada se move mais depressa do que uma célula por geração. O padrão diehard parece saudável até desaparecer na geração 130.
Laboratório Gerador de Lorem Ipsum
O cursor de entropia funciona como a temperatura de um LLM, e possui um teto: o corpus contém 63 palavras distintas, pelo que log₂ 63 = 5,9773 bits é o máximo que qualquer passagem pode transportar, seja qual for o alvo pretendido.
Passeio Aleatório Quântico
Após 100 passos, um caminhante clássico raramente se afasta mais do que 10 posições, enquanto o quântico chega a cerca de 70. Aos 10 passos, as dispersões são de 4,8924 contra 3,1623, logo, o caminhante clássico necessita de 24 passos para o igualar.

Outras ferramentas

Calculadora de bitrate e tamanho
Um megabit extra por segundo custa 450 MB por hora, independentemente do que estiver na imagem. Num clipe de dez minutos a 6 Mbit/s, o áudio representa 3,1% de um ficheiro de 478 MB, pelo que reduzi-lo a metade poupa 7 MB e prejudica cada ouvinte.
Cifrar um bloco em dez (CENC cbcs)
O esquema cbcs cifra um bloco de 16 bytes em cada dez, e uma fatia de 48 bytes resulta num terço de texto cifrado. Os nove décimos em claro de nada servem sem a chave, pois em cada fatia alcançada pelo padrão, o primeiro byte após o cabeçalho é texto cifrado.
Código de Hamming: corrigir um bit identificando a sua posição
Quatro bits de dados em sete, com três verificações de paridade cujas falhas formam, em binário, a posição do bit errado. Assim, qualquer inversão isolada é sempre corrigida. Inverta dois bits e o descodificador, confiante, inverterá um terceiro; mais um bit transforma o erro numa sinalização.
Explorador de tokenização BPE
Veja como a codificação por pares de bytes divide o texto nos tokens que um modelo de linguagem realmente lê. Vocabulário fixo, divisão ao vivo — o inglês custa 13 tokens onde a mesma frase em alemão custa 36.
Resolução do Ecrã e Distância de Visualização
Que porção da resolução de um ecrã atinge de facto o seu olho, consoante a diagonal, o número de píxeis e o lugar onde se senta. Com uma visão 20/20, a resposta é o campo de visão medido em minutos de arco, e numa televisão de sala de estar o valor fica habitualmente abaixo de 1080p.
Rotação das Chaves de uma Transmissão ao Vivo
Uma rotação de chaves a cada dois minutos durante um ano cria 262.800 chaves de conteúdo, ocupando 4,20 MB. O seu verdadeiro custo recai sobre um milhão de reprodutores que pedem cada chave nova nos mesmos dez segundos. A hierarquia de chaves, que diminui os pedidos num fator de 720, também torna cada fuga 720 vezes maior.
Temperatura e amostragem
Veja uma distribuição real do próximo token a ser remodelada pela temperatura e cortada por top-k e top-p. A temperatura nunca muda que token lidera — apenas por quanto, de 278x para 1,76x.
Vetores de tokens e semelhança
Vetores construídos contando que tokens aparecem perto de quais, sobre a prosa deste site. O par mais alto é ␣the e ␣is com 0,505 — mais do que ␣Earth e ␣Sun com 0,299, e não significa nada.
Related categories: Matemática, Física