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