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$.