Dicionário

Este dicionário reúne alguns termos de uso frequente em otimização combinatória.

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 de alguma constante.  Exemplos: $2^n$, $1.2^n$, $10^n$.

número natural
Qualquer número do conjunto $\conj{0, 1, 2, 3, 4, \ldots}$. Essencialmente o mesmo que número inteiro não-negativo.
número inteiro
Qualquer número do conjunto $\conj{\ldots,-4, -3, -2, -1, 0, 1, 2, 3, 4, \ldots}$.
número racional
Qualquer número da forma $p/q$, sendo $p$ e $q$ números inteiros e $q \neq 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 $\sqrt{2}$, $\pi$, $\lg 3$, etc.). Computadores não sabem o que são números irracionais; eles conhecem apenas um pequeno conjunto de racionais. Os números conhecidos como reais no mundo da computação são do tipo float ou double e todos esses números são racionais.
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 \geq 0$.
intervalo de números inteiros
Conjunto de inteiros consecutivos. O intervalo  $p \tdots r$ é o conjunto de números  $\conj{p, p+1, \ldots, r}$.
vetor inteiro
Qualquer vetor cujas componentes são números inteiros.
vetor binário
Qualquer vetor cujas componentes são elementos do conjunto $\conj{0,1}$.
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 \in X$ e $x[i] = 0$ se $i \in S\setm X$.
vetor unitário
Dado um conjunto $S$, um vetor $x$ indexado por $S$ é unitário se $x[i] = 1$ para algum $i$ em $S$ e $x[s] = 0$ para todo $s$ em $S\setm\conj{i}$.
coleção
É o mesmo que conjunto.  Notação: $\conj{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|$.
complemento de um conjunto
Dado um subconjunto $S$ de um subconjunto $C$, o complemento de $S$ em relação a $C$ é o conjunto $C\setm S$. Notação: $\bar{S}$ ou $\overline{S}$ ou $S^{\mathsf{c}}$.
subconjunto próprio
Um subconjunto $A$ de um conjunto $B$ é próprio se for diferente de $B$. Notação: $A \subset B$.
superconjunto próprio
Um superconjunto $B$ de um conjunto $A$ é próprio se for diferente de $A$. Notação: $B \supset A$.
disjunto
Um conjunto $A$ é disjunto de um conjunto $B$ se $A \cap 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] \neq v[j]$ sempre que $i \neq j$.
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 $\conj{1, 2, 3, 4, 5, 6, 7}$ é $(1,3,5,7,2,4,6)$. Outra permutação do mesmo conjunto é $(1,2,3,4,5,6,7)$.
partição de um conjunto
Uma partição de um conjunto $X$ é qualquer coleção $\Pi$ de subconjuntos não vazios de $X$ tal que todo elemento de $X$ pertence a um e apenas um dos elementos de $\Pi$. Cada elemento de $\Pi$ é um bloco da partição.  Exemplo: $\conj{\conj{1,3}, \conj{2,4,7}, \conj{5}, \conj{6,8}}$  é uma partição de  $\conj{1, 2, 3, 4, 5, 6, 7, 8}$. O conjunto  $\conj{6,8}$  é um dos blocos da partição.  (É errado dizer que $\conj{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 $\Pi$ e $\Pi'$ de um conjunto, dizemos que $\Pi'$ é um refinamento de $\Pi$ se todo elemento de $\Pi'$ é subconjunto de algum elemento de $\Pi$. Exemplo: A partição $\conj{\conj{1,3}, \conj{2,4,7}, \conj{5}, \conj{6,8}}$ de $\conj{1, 2, 3, 4, 5, 6, 7, 8}$ é um refinamento da partição $\conj{\conj{1,3,2,4,7}, \conj{5,6,8}}$.
CQD
Abreviatura de como queríamos demonstrar. É o mesmo que CQP (como queríamos provar) e o mesmo que QED (quod erat demonstrandum).
crescente
Um vetor $A[1\tdots n]$ é crescente se  $A[1] \leq A[2]\leq \cdots \leq A[n]$.
estritamente crescente
Um vetor $A[1 \tdots n]$ é estritamente crescente se  $A[1] \lt A[2] \lt \cdots \lt 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 $\log_2 n$.
$\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$.
$\floor{x}$  ou  piso($x$)
O único inteiro $i$ tal que  $i \leq x \lt i+1$.
$\ceil{x}$  ou  teto($x$)
O único inteiro $i$ tal que  $i-1 \lt x \leq i$.
bla bla bla para todo $n$ suficientemente grande
O mesmo que dizer que existe um número  $n_0$  tal que  bla bla bla  vale para todo $n$ que seja maior que $n_0$.
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) \lt g(n)$ para todo $n$ suficientemente grande.
$f(n) = \Oh(g(n))$
O mesmo que dizer que existe um número $c$ tal que  $f(n) \textcolor{red}{\leq} c \cdot 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) = \Omega(g(n))$
O mesmo que dizer que existe um número $c \geq 0$ tal que  $f(n) \textcolor{red}{\geq} c \cdot 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) = \Theta(g(n))$
O mesmo que dizer que  $f(n) = \Oh(g(n))$  e  $f(n) = \Omega(g(n))$.
algoritmo logarítmico
Algoritmo cujo consumo de tempo é  $\Oh(\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 $\Theta(\log n)$.
algoritmo linear
Algoritmo cujo consumo de tempo é  $\Oh(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 $\Theta(n)$.
algoritmo linearítmico (ou ene-log-ene)
Algoritmo cujo consumo de tempo é  $\Oh(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 $\Theta(n \log n)$.
algoritmo quadrático
Algoritmo cujo consumo de tempo é  $\Oh(n^2)$,  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 $\Theta(n^2)$.
algoritmo cúbico
Algoritmo cujo consumo de tempo é  $\Oh(n^3)$,  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 $\Theta(n^3)$.
minimal
Suponha que $\Pi$ é uma coleção de conjuntos. Um elemento $X$ de $\Pi$ é minimal se nenhum subconjunto próprio de $X$ pertence a $\Pi$. Em outras palavras, $X$ é minimal se não existe $Y$ em $\Pi$ tal que $Y \subset X$.
maximal
Suponha que $\Pi$ é uma coleção de conjuntos. Um elemento $X$ de $\Pi$ é maximal se nenhum superconjunto próprio de $X$ pertence a $\Pi$. Em outras palavras, $X$ é maximal se não existe $Y$ em $\Pi$ tal que $Y \supset X$.
mínimo
Suponha que $\Pi$ é uma coleção de conjuntos. Um elemento $X$ de $\Pi$ é mínimo se não existe $Y$ em $\Pi$ tal que $|Y| \lt |X|$. Em outras palavras, $X$ é mínimo se $|X| \leq |Z|$ para todo $Z$ em $\Pi$. (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 $\Pi$ é uma coleção de conjuntos. Um elemento $X$ de $\Pi$ é máximo se não existe $Y$ em $\Pi$ tal que $|Y| > |X|$. Em outras palavras, $X$ é máximo se $|X| \geq |Z|$ para todo $Z$ em $\Pi$. É evidente que todo máximo é maximal. Mas a recíproca longe está de ser verdadeira.
$\mathbf{E}[X]$
Esperança da variável aleatória $X$, ou seja, $\sum_k k\:\mathbf{Pr}[X{=}k]$.
$\mathbf{Pr}[X{=}k]$
Probabilidade de que a variável aleatória $X$ tenha valor $k$.