Dicionário

coleção: É o mesmo que conjunto. (Veja a nota Sequência versus conjunto.) Notação: { a, b, c, d } é um conjunto cujos elementos são a, b, c, d.
cardinalidade de um conjunto: É o número de elementos do conjunto, ou seja, o tamanho do conjunto. A cardinalidade de um conjunto S é denotada por ⎮S⎮.
subconjunto próprio: Um subconjunto A de um conjunto B é próprio se for diferente de B. Notação: A ⊂ B.
superconjunto próprio: Um superconjunto B de um conjunto A é próprio se for diferente de A. Notação: B ⊃ A.
complemento: Dado um subconjunto A de um conjunto B, o complemento de A (em relação a B) é o conjunto B − A. Notação: A.
conjunto vazio: O conjunto vazio pode ser denotado por ∅, Ø, ou { }.
disjunto: Um conjunto A é disjunto de um conjunto B se A ∩ B é vazio. Uma coleção de conjuntos é disjunta se seus elementos são disjuntos dois a dois.
dois a dois: Os elementos de um vetor v são distintos dois a dois se forem todos diferentes entre si, ou seja, se v[i] ≠ v[ j] sempre que i ≠ j.
vetor característico: Dado um conjunto S, o vetor característico de um subconjunto X de S é o vetor x definido assim: x[i] = 1 se i ∈ X e x[i] = 0 se i ∈ S − X.
permutação: Uma permutação dos elementos de um conjunto finito é uma sequência em que cada elemento do conjunto aparece uma e uma só vez. Um conjunto com n elementos tem n! diferentes permutações. Exemplo: uma das permutação do conjunto {1, 2, 3, 4, 5, 6, 7, 8} é (1, 3, 5, 7, 2, 4, 6, 8). Outra permutação do mesmo conjunto é (1, 2, 3, 4, 5, 6, 7, 8).
partição de um conjunto: Uma partição de um conjunto X é qualquer coleção Π de subconjuntos não vazios de X tal que todo elemento de X pertence a um e apenas um dos elementos de Π. Cada elemento de Π é um bloco da partição. Exemplo: {{1,3}, {2,4,7}, {5}, {6,8}} é uma partição de {1, 2, 3, 4, 5, 6, 7, 8}. O conjunto {6,8} é um dos blocos da partição. (É errado dizer que {6,8} é uma das partições do conjunto!)
bipartição de um conjunto: Uma bipartição é uma partição com exatamente dois blocos.
refinamento de uma partição: Dadas partições Π e Π′ de um conjunto, dizemos que Π′ é um refinamento de Π se todo elemento de Π′ é subconjunto de algum elemento de Π. Exemplo: A partição {{1,3}, {2,4,7}, {5}, {6,8}} de {1, 2, 3, 4, 5, 6, 7, 8} é um refinamento da partição {{1,3,2,4,7}, {5,6,8}}.
número natural: Qualquer número do conjunto { 0, 1, 2, 3, 4, … } . Essencialmente o mesmo que número inteiro não-negativo.
número composto: Um número natural n é composto se existem números naturais p e q, ambos maiores que 1, tais que n = p × q. (Imagine que queremos dispor n cubos de madeira sobre uma mesa de maneira a formar um retângulo, sem buracos, com pelo menos duas linhas e pelo menos duas colunas. Isto é possível se e somente se n é composto.)
número primo: Um número natural n > 1 é primo se não for composto.
número inteiro: Qualquer número do conjunto { … , −4, −3, −2, −1, 0, 1, 2, 3, 4, … } .
número racional: Qualquer número da forma p/q , sendo p e q números inteiros e q ≠ 0. (Por exemplo, todo número inteiro é racional.) Quando um número racional é escrito em notação decimal, a sequência de casas depois da vírgula pode ser finita (15/4 = 3.75) ou infinita (13/11 = 1.181818…) O conjunto dos números ponto flutuante do computador é uma pequena parte do conjunto dos número racionais. A esmagadora maioria dos números racionais não pode ser representada em ponto flutuante.
número real: O conjunto dos números reais inclui todos os números racionais bem como todos os irracionais (como √2, , lg 3, etc.). Evitamos trabalhar com números reais porque os irracionais não podem ser representados exatamente num computador.
intervalo de números inteiros: É um conjunto de inteiros consecutivos. O intervalo p .. r é o conjunto de números { p, p+1, … , r }.
positivo e negativo: Um número x é positivo se x > 0 e negativo se x < 0. Um número x é não-negativo se x ≥ 0.
crescente: Um vetor A[1 .. n] é crescente se A[1] ≤ A[2] ≤ … ≤ A[n].
estritamente crescente: Um vetor A[1 .. n] é estritamente crescente se A[1] < A[2] < … < A[n].
decrescente: Análogo a crescente.
estritamente decrescente: Análogo a estritamente crescente.
exponencial: Uma função exponencial de parâmetro n é qualquer função em que n aparece como expoente. (Veja a nota Exponencial.)
lg n ou lg (n): Logaritmo na base 2. O mesmo que log₂ n. (Veja propriedades de lg no Apêndice.)
ln n ou ln (n): Logaritmo natural, ou logaritmo na base e. O mesmo que log_e n. A base e é o número de Euler (número irracional próximo de 2.718281828). Como se sabe, ln n = lg n / lg e.
⌊x⌋ ou piso(x): O único inteiro i tal que i ≤ x < i+1. (Veja propriedades do piso e do piso de log no Apêndice.)
⌈x⌉ ou teto(x): O único inteiro i tal que i−1 < x ≤ i. (Veja propriedades do teto e do teto de log no Apêndice.)
minimal: Suponha que Π é uma coleção de conjuntos. Um elemento X de Π é minimal se nenhum subconjunto próprio de X pertence a Π. Em outras palavras, X é minimal se não existe Y em Π tal que Y ⊂ X. (Veja exemplo com cobertura por vértices.)
maximal: Suponha que Π é uma coleção de conjuntos. Um elemento X de Π é maximal se nenhum superconjunto próprio de X pertence a Π. Em outras palavras, X é maximal se não existe Y em Π tal que Y ⊃ X.
mínimo: Suponha que Π é uma coleção de conjuntos. Um elemento X de Π é mínimo se não existe Y em Π tal que ⎮Y⎮ < ⎮X⎮. Em outras palavras, X é mínimo se ⎮X⎮ ≤ ⎮Z⎮ para todo Z em Π. (Cuidado! Esta definição pode ser diferente daquela usada na teoria das ordens parciais.) É evidente que todo mínimo é minimal. Mas a recíproca longe está de ser verdadeira.
máximo: Suponha que Π é uma coleção de conjuntos. Um elemento X de Π é máximo se não existe Y em Π tal que ⎮Y⎮ > ⎮X⎮. Em outras palavras, X é máximo se ⎮X⎮ ≥ ⎮Z⎮ para todo Z em Π. É evidente que todo máximo é maximal. Mas a recíproca longe está de ser verdadeira.
E[X]: Esperança da variável aleatória X, ou seja, ∑_k k Pr[X=k].
Pr[X=k]: Probabilidade de que a variável aleatória X tenha valor k.
CQD: Como queríamos demonstrar. É o mesmo que CQP (como queríamos provar). É o mesmo que QED (quod erat demonstrandum). (A propósito, veja a página O que é uma prova matemática?)
algoritmo: Não preciso explicar o que é um algoritmo, não é?
heurística: Uma heurística é um método que tenta resolver um problema mas (ao contrário de um algoritmo) não garante sucesso, ou seja, não garante produzir uma solução do problema. (Herbert Wilf diz que uma heurística é um método que parece funcionar bem na prática, por razões que ninguém compreende.)
FIFO: FIFO (= First In First Out) é a política de administração de uma fila: o próximo elemento a ser removido é o que foi inserido há mais tempo.
LIFO: LIFO (= Last In First Out) é a política de administração de uma pilha: o próximo elemento a ser removido é o que está lá há menos tempo. O topo da pilha contém o elemento que foi inserido mais recentemente.
Ω: Letra grega ômega maiúscula.
Θ: Letra grega teta maiúscula.
bla bla bla para todo n suficientemente grande: O mesmo que dizer que existe um número n₀ tal que bla bla bla vale para todo n que seja maior que n₀.
assintótico: Para n tendendo a infinito, ou seja, para todo n suficientemente grande. Dadas funções f e g de n, dizemos que f é assintoticamente igual a g se f(n) tende a g(n) quando n tende a infinito. Dizemos que f é assintoticamente menor que g se f(n) < g(n) para todo n suficientemente grande.
f(n) = Ο(g(n)): O mesmo que dizer que existe um número c tal que f(n) ≤ c · g(n) para todo n suficientemente grande. (Estou supondo que f e g são funções que levam inteiros não-negativos em reais não-negativos.)
f(n) = Ω(g(n)): O mesmo que dizer que existe um número c ≥ 0 tal que f(n) ≥ c · g(n) para todo n suficientemente grande. (Estou supondo que f e g são funções que levam inteiros não-negativos em reais não-negativos.)
f(n) = Θ(g(n)): O mesmo que dizer que f(n) = Ο(g(n)) e f(n) = Ω(g(n)).
logarítmico: Algoritmo cujo consumo de tempo é Ο(log n), sendo n o parâmetro que mede o tamanho da entrada do algoritmo. Mas, em geral, a expressão algoritmo logarítmico só é aplicada a algoritmos que consomem tempo Θ(log n).
linear: Algoritmo cujo consumo de tempo é Ο(n), sendo n o parâmetro que mede o tamanho da entrada do algoritmo. Mas, em geral, a expressão algoritmo linear só é aplicada a algoritmos que consomem tempo Θ(n).
linearítmico (ou ene-log-ene): Algoritmo cujo consumo de tempo é Ο(n log n), sendo n o parâmetro que mede o tamanho da entrada do algoritmo. Mas, em geral, a expressão algoritmo linearítmico só é aplicada a algoritmos que consomem tempo Θ(n log n).
quadrático: Algoritmo cujo consumo de tempo é Ο(n²), sendo n o parâmetro que mede o tamanho da entrada do algoritmo. Mas, em geral, a expressão algoritmo quadrático só é aplicada a algoritmos que consomem tempo Θ(n²).
cúbico: Algoritmo cujo consumo de tempo é Ο(n³), sendo n o parâmetro que mede o tamanho da entrada do algoritmo. Mas, em geral, a expressão algoritmo cúbico só é aplicada a algoritmos que consomem tempo Θ(n³).