Índice enciclopédico

Todas as páginas do guia de Matemática para Computação em ordem alfabética. Para navegar por assunto, veja o índice por tema.

A

• Análise Assintótica — Notações O, Ômega, Theta, o e ômega pequenos, regras de manipulação, hierarquia de crescimento e os limites do que a análise assintótica diz.
• Aritmética Modular — Congruências, classes residuais, propriedades operatórias, exponenciação rápida e as aplicações em hashing, verificação e criptografia.
• Árvores — Árvores e suas caracterizações equivalentes, árvores enraizadas, percursos, árvore geradora mínima e as estruturas de dados derivadas.
• Autômatos e Linguagens Formais — Autômatos finitos determinísticos e não determinísticos, expressões regulares, lema do bombeamento e a hierarquia de Chomsky.
• Autovalores e Autovetores — Autovalores, autovetores, diagonalização, o teorema espectral e as aplicações em PCA, PageRank e estabilidade de sistemas dinâmicos.

B

• Bibliografia Comentada — Guia de livros por área, com indicação de nível, o que cada um faz melhor e quais estão disponíveis gratuitamente.

C

• Cadeias de Markov — Cadeias de Markov, matriz de transição, distribuição estacionária, ergodicidade, tempo de mistura e as aplicações em PageRank e MCMC.
• Caminhos eulerianos — Introdução aos grafos eulerianos e o problema do carteiro.
• Caminhos Mínimos — Dijkstra, Bellman-Ford e Floyd-Warshall: hipóteses, custos, pesos negativos e a escolha do algoritmo certo para cada situação.
• Classes P, NP e Reduções — As classes P e NP, NP-completude, o teorema de Cook-Levin, reduções polinomiais e o que fazer diante de um problema NP-difícil.
• Coloração de Grafos — Número cromático, coloração gulosa, limites, grafos bipartidos e planares, e a aplicação direta em alocação de registradores e escalonamento.
• Combinatória — Princípios aditivo e multiplicativo, permutações, arranjos, combinações, binômio de Newton, combinações com repetição e inclusão-exclusão.
• Concentração e Algoritmos Aleatorizados — Desigualdades de Markov, Chebyshev e Chernoff, amplificação de probabilidade, algoritmos Las Vegas e Monte Carlo.

D

• Decomposição em Valores Singulares — A SVD, sua interpretação geométrica, aproximação de posto baixo, pseudoinversa e as aplicações em compressão, PCA e sistemas de recomendação.
• Decomposições LU e Cholesky — Fatoração LU com pivoteamento, fatoração de Cholesky para matrizes definidas positivas, e por que fatorar uma vez e reusar é a prática correta.
• Derivadas — Derivada como taxa e como aproximação linear, regra da cadeia, gradiente, hessiana e a ligação com retropropagação e otimização.
• Determinante — O determinante como fator de volume orientado, propriedades, cálculo eficiente por fatoração e por que a regra de Cramer não deve ser usada.
• Distribuições de Probabilidade — Bernoulli, binomial, geométrica, Poisson, uniforme, exponencial e normal — quando cada uma aparece e o que ela modela em computação.
• Divisibilidade e Algoritmo de Euclides — Divisibilidade, MDC e MMC, algoritmo de Euclides e sua versão estendida, identidade de Bézout e inverso modular.

E

• Erro e Condicionamento — Erro absoluto e relativo, condicionamento de um problema, estabilidade de um algoritmo e a distinção entre os dois conceitos.
• Espaço Amostral e Eventos — Espaço amostral, eventos, axiomas de Kolmogorov, probabilidade uniforme e a relação entre contagem e probabilidade.
• Espaços Vetoriais — Espaços vetoriais, combinação linear, independência, base e dimensão, subespaços, e por que essas noções organizam todo o resto da álgebra linear.

F

• Fermat, Euler e Testes de Primalidade — Pequeno teorema de Fermat, teorema de Euler, pseudoprimos e números de Carmichael, e os testes de Miller-Rabin e determinístico.
• Funções — Funções, domínio e imagem, injetividade, sobrejetividade, bijeção, composição, inversa e a relação com hashing e tipos.

G

• Grafos: Fundamentos — Vértices, arestas, grau, representações por matriz e lista de adjacência, conexidade, e as travessias em largura e profundidade.
• Guia de Notação — Referência dos símbolos usados no guia: conjuntos, lógica, somatórios, álgebra linear, probabilidade e assintótica.

I

• Indução Matemática — Indução simples e forte, a estrutura de uma prova por indução, indução estrutural e a relação direta com correção de algoritmos recursivos.
• Integrais — Integral de Riemann, teorema fundamental do cálculo, integrais impróprias e a ligação com probabilidade contínua e valor esperado.
• Interpolação e Integração Numérica — Interpolação polinomial e o fenômeno de Runge, splines, quadratura de Newton-Cotes e de Gauss, e Monte Carlo em dimensão alta.

L

• Limites e Continuidade — A definição épsilon-delta, limites laterais e infinitos, continuidade, teorema do valor intermediário e o método da bisseção.
• Lógica de Predicados — Quantificadores universal e existencial, escopo, negação de quantificadores e o uso em especificação de programas e invariantes de laço.
• Lógica Proposicional — Proposições, conectivos, tabelas-verdade, equivalências, formas normais e a ligação direta com expressões booleanas e circuitos digitais.

M

• Máquina de Turing e Decidibilidade — A máquina de Turing, a tese de Church-Turing, o problema da parada, redução e as consequências práticas da indecidibilidade.
• Matrizes e Operações — Matrizes, produto matricial e seu custo, transposta, inversa, matrizes especiais e as implicações de desempenho em código real.

O

• Ortogonalidade e Fatoração QR — Bases ortonormais, Gram-Schmidt, matrizes ortogonais, refletores de Householder e a fatoração QR aplicada a mínimos quadrados.

P

• Ponto Flutuante — O padrão IEEE 754, epsilon de máquina, valores especiais, cancelamento catastrófico e como comparar números de ponto flutuante corretamente.
• Princípio da Casa dos Pombos — O princípio da casa dos pombos e sua forma generalizada, com aplicações a hashing, compressão sem perdas e detecção de ciclos.
• Probabilidade Condicional e Bayes — Probabilidade condicional, regra do produto, teorema de Bayes, o problema da taxa-base e aplicações em classificação e diagnóstico.
• Produto Interno e Normas — Produto interno, normas vetoriais e matriciais, desigualdade de Cauchy-Schwarz, similaridade do cosseno e o papel das normas em regularização.

R

• Raízes e Método de Newton — Bisseção, Newton-Raphson, secante, ordem de convergência e os critérios de parada que evitam laços infinitos.
• Recorrências — Relações de recorrência, resolução por substituição, árvore de recursão, teorema mestre e a análise de algoritmos de dividir e conquistar.
• Relações — Relações binárias, propriedades reflexiva, simétrica e transitiva, relações de equivalência, ordens parciais, fecho transitivo e aplicações.
• Roteiros de Estudo — Percursos sugeridos pelo guia conforme o objetivo: entrevistas, aprendizado de máquina, criptografia, computação gráfica e computação científica.
• RSA — O criptossistema RSA: geração de chaves, cifragem, decifragem, prova de correção, escolha de parâmetros e os ataques que o preenchimento previne.

S

• Sequências e Séries — Convergência de sequências e séries numéricas: a definição épsilon-N, séries geométrica e harmônica, testes de convergência e o uso na análise de algoritmos.
• Séries de Taylor — Polinômio e série de Taylor, resto de Lagrange, séries conhecidas e o uso em métodos numéricos e implementação de funções matemáticas.
• Sistemas Lineares — Eliminação gaussiana, pivoteamento, existência e unicidade de soluções, sistemas sobredeterminados e mínimos quadrados.

T

• Teorema Chinês do Resto — O teorema chinês do resto, construção da solução, decomposição de módulos compostos e as aplicações em aceleração do RSA e aritmética de resíduos.
• Teoria dos Conjuntos — Conjuntos, operações, leis de De Morgan, produto cartesiano, conjunto potência, cardinalidade e a correspondência com estruturas de dados.
• Transformações Lineares — Transformações lineares e sua representação matricial: a intuição geométrica, rotação e escala em 2D, coordenadas homogêneas e o uso em computação gráfica e PCA.

V

• Variáveis Aleatórias e Esperança — Variáveis aleatórias discretas e contínuas, esperança, linearidade da esperança, variância e a técnica dos indicadores.

Referências

1. Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill.
2. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press.