Dicionário

algoritmo
Não preciso explicar o que é um algoritmo, não é?
heurística
Uma heurística é um algoritmo que tenta resolver um problema mas não garante sucesso, ou seja, não garante produzir uma solução.  (Herbert Wilf diz que uma heurística é um método que parece funcionar bem na prática, por razões que ninguém compreende.)
exponencial

Uma função exponencial de parâmetro n é qualquer função em que n aparece como expoente. (Veja a nota Exponencial.)

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, cd.
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: AB.
superconjunto próprio
Um superconjunto B de um conjunto A é próprio se for diferente de A.  Notação: BA.
disjunto
Um conjunto A é disjunto de um conjunto B se AB é 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}}.
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.
número inteiro
Qualquer número do conjunto { … , −4, −3, −2, −1, 0, 1, 2, 3, 4, … } .
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 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.)  O conjunto dos números ponto flutuante do computador é uma pequena parte do conjunto dos número racionais.  (A grande 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, pi, lg 3, etc.). Evitamos trabalhar com números reais porque os irracionais não podem ser representados exatamente num computador.
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.
CQD
Como queríamos demonstrar. É o mesmo que CQP (como queríamos provar). É o mesmo que QED (quod erat demonstrandum).
intervalo de números inteiros
É um conjunto de inteiros consecutivos. O intervalo  p .. r  é o conjunto de números  { p, p+1, … , r }.
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.
lg n  ou  lg (n)
Logaritmo na base 2.  O mesmo que log2 n. (Veja propriedades de lg no Apêndice.)
ln n  ou  ln (n)
Logaritmo natural, ou logaritmo na base e.  O mesmo que loge 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  ix < 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 < xi. (Veja propriedades do teto e do teto de log no Apêndice.)
Ω
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  n0  tal que  bla bla bla  vale para todo n que seja maior que n0.
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)).
algoritmo 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).
algoritmo 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).
algoritmo 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).
algoritmo 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²).
algoritmo 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³).
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.
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 kPr[X=k].
Pr[X=k]
Probabilidade de que a variável aleatória X tenha valor k.