Informática
Linguagens formais
O que são uma linguagem formal, um alfabeto e uma palavra. Conceitos básicos da teoria das linguagens formais, explicados por comparação com a língua do dia a dia e com exemplos.
Autômatos finitos
O autômato finito como modelo de computação com estados e transições. Definição, diagrama de estados, formalização da computação e exemplos de palavras aceitas.
Minimização de autômatos
Estados inacessíveis de um autômato finito, aos quais não se pode chegar a partir do estado inicial. Definição e como removê-los do autômato com segurança.
Propriedades de fecho das linguagens regulares
As linguagens regulares são fechadas sob união, interseção, concatenação e fecho. O que significa o fechamento sob uma operação e por que ele vale para as linguagens regulares.
Expressões regulares
O que é uma expressão regular e como ela descreve um conjunto de palavras. Definição, comparação com expressões aritméticas e relação com os autômatos finitos.
Estimativa do número de valores distintos
Linear counting: como estimar o número de valores distintos em dados enormes. Funções hash, mapas de bits e por que o método ingênuo não basta.
Bloom filter: um elemento está no conjunto?
O Bloom filter é uma estrutura de dados probabilística que responde rapidamente se um elemento está no conjunto. Princípio, funções hash e uso prático.
Cifra de César
Como funciona a cifra de César, um dos métodos mais antigos de cifrar um texto. O princípio do deslocamento das letras, a generalização da cifra e uma ferramenta online.
Cifra de Vigenère
A cifra de Vigenère usa vários alfabetos e, por isso, resiste à análise de frequência. Princípio da cifragem, quadrado de Vigenère, escolha da chave e uma ferramenta.
