Otimização Combinatória | Dicionário | Índice remissivo

Dicionário de Otimização Combinatória

Este dicionário define alguns termos de uso frequente nas minhas notas de aula de Otimização Combinatória:

sequência

Uma sequência é caracterizada pela ordem de seus elementos: há um primeiro elemento, um segundo elemento, etc., um último elemento. Exemplo: a sequência de dígitos de um número de telefone.  Notação: escreva os elementos da sequência em ordem, embrulhados em parênteses. Por exemplo: $(a,b,c,d)$.

subsequência

Uma subsequência é o que sobra depois que alguns elementos de uma sequência são apagados.  Mais exatamente, uma subsequência de uma sequência $(a_1,a_2,\dots ,a_n)$ é qualquer sequência $(b_1,b_2,\dots ,b_k)$ tal que  $b_1=a_{i_1},b_2=a_{i_2},\dots ,b_k=a_{i_k}$  para alguma sequência  $i_1<i_2<\cdots <i_k$ de índices.  Por exemplo, $(2,3,5,8)$ é subsequência de $(1,2,3,4,5,6,7,8)$ mas não é subsequência de $(1,2,3,8,4,5,6,7)$.

segmento

Um segmento de uma sequência é uma subsequência contínua. Em outras palavras, um segmento é o que sobra depois que alguns dos termos iniciais e alguns dos termos finais da sequência são apagados.  Mais exatamente, uma segmento de uma sequência  $(a_1,a_2,\dots ,a_n)$ é qualquer sequência da forma $(a_i,a_{i+1},a_{i+2},\dots ,a_k)$ com $1\le i$ e $k\le n$.  Por exemplo, $(2,3,4,5)$ é um segmento de $(1,2,3,4,5,6,7,8)$.

coleção

Uma coleção é o mesmo que um conjunto.  Notação: $\{a,d,b,c\}$ é o conjunto cujos elementos são $a$, $b$, $c$, $d$.

união

Para qualquer coleção $\mathcal{A}$, a expressão $\bigcup \mathcal{A}$ denota a união de todos os elementos de $\mathcal{A}$. Por exemplo, se os elementos de $\mathcal{A}$ são $A_1,$ $A_2,\dots ,$ $A_k$ então $\bigcup \mathcal{A}=$ $A_1\cup A_2\cup \cdots \cup A_k$ .

cardinalidade

A cadinalidade de um conjunto é o número de elementos do conjunto, ou seja, o tamanho do conjunto. A cardinalidade de um conjunto $V$ é denotada por $|V|$.

complemento

Dado um subconjunto $S$ de um conjunto $V$, o complemento de $S$ é o conjunto $V\setminus S$.  Notação: $\bar{S}$ ou $S^{\mathsf{c}}$. [Pode ser necessário aumentar ou diminuir (Ctrl+ ou Ctrl-) o tamanho da fonte no seu browser para que a barra horizontal acima do $S$ fique visível.] 

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]\ne v[j]$ sempre que $i\ne 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 $\{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 $V$ é qualquer coleção $\mathcal{P}$ de subconjuntos não vazios de $V$ tal que todo elemento de $V$ pertence a um e apenas um dos elementos de $\mathcal{P}$. Cada elemento de $\mathcal{P}$ é 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 $\mathcal{P}$ e ${\mathcal{P}}^{\prime }$ de um conjunto, dizemos que ${\mathcal{P}}^{\prime }$ é um refinamento de $\mathcal{P}$ se todo elemento de ${\mathcal{P}}^{\prime }$ é subconjunto de algum elemento de $\mathcal{P}$. 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\}\}$.

minimal

Suponha que $\mathcal{P}$ é uma coleção de conjuntos. Um elemento $P$ de $\mathcal{P}$ é minimal se nenhum subconjunto próprio de $P$ pertence a $\mathcal{P}$. Em outras palavras, $P$ é minimal se não existe $Q$ em $\mathcal{P}$ tal que $Q\subset P$.

maximal

Suponha que $\mathcal{P}$ é uma coleção de conjuntos. Um elemento $P$ de $\mathcal{P}$ é maximal se nenhum superconjunto próprio de $P$ pertence a $\mathcal{P}$. Em outras palavras, $P$ é maximal se não existe $Q$ em $\mathcal{P}$ tal que $Q\supset P$.

mínimo

Suponha que $\mathcal{P}$ é uma coleção de conjuntos. Um elemento $P$ de $\mathcal{P}$ é mínimo se não existe $Q$ em $\mathcal{P}$ tal que $|Q|<|P|$. Em outras palavras, $P$ é mínimo se $|P|\le |R|$ para todo $R$ em $\mathcal{P}$.  (Esta definição pode ser diferente daquela usada na teoria das ordens parciais.)  É evidente que todo mínimo é minimal. Mas a recíproca está longe de ser verdadeira.

máximo

Suponha que $\mathcal{P}$ é uma coleção de conjuntos. Um elemento $P$ de $\mathcal{P}$ é máximo se não existe $Q$ em $\mathcal{P}$ tal que $|Q|>|P|$. Em outras palavras, $P$ é máximo se $|P|\ge |R|$ para todo $R$ em $\mathcal{P}$. É evidente que todo máximo é maximal. Mas a recíproca está longe de ser verdadeira.

número natural

Um número natural é qualquer elemento do conjunto $\{0,1,2,3,4,\dots \}$. Um número natural é essencialmente o mesmo que número inteiro não-negativo. O conjunto dos números naturais é denotado por $\mathbf{N}$.

número inteiro

Um número inteiro é qualquer elemento do conjunto $\{\dots ,-4,-3,-2,-1,0,1,2,3,4,\dots \}$.  O conjunto dos números naturais é denotado por $\mathbf{Z}$ e o conjunto dos inteiros não-negativos é denotado por ${\mathbf{Z}}_{+}$. Portanto, ${\mathbf{Z}}_{+}=\mathbf{N}$.

número racional

Um número racional é qualquer número da forma $p/q$, sendo $p$ e $q$ números inteiros e $q\ne 0$. (Por exemplo, todo número inteiro é racional.)  O conjunto dos números racionais é denotado por $\mathbf{Q}$ e o conjunto dos racionais não-negativos é denotado por ${\mathbf{Q}}_{+}$.

O conjunto dos números do tipo double do computador é uma pequena parte do conjunto dos número racionais.  A grande maioria dos números racionais não pode ser representada em double.

número real

O conjunto dos números reais inclui todos os números racionais e todos os irracionais (como $\sqrt{2}$, $\pi$, $\lg 3$, etc.).  O conjunto dos números reais é denotado por $\mathbf{R}$ e o conjunto dos reais não-negativos é denotado por ${\mathbf{R}}_{+}$.

É claro que $\mathbf{N}\subset \mathbf{Z}\subset \mathbf{Q}\subset \mathbf{R}$. Computadores digitais conhecem apenas um subconjunto finito de $\mathbf{Q}$; em particular, desconhecem os números irracionais. Os números conhecidos como reais no mundo da computação são do tipo 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\ge 0$.

$\lfloor x\rfloor$  ou  piso($x$)

$\lfloor x\rfloor$ é o único inteiro $i$ tal que  $i\le x<i+1$.

$\lceil x\rceil$  ou  teto($x$)

$\lceil x\rceil$ é o único inteiro $i$ tal que  $i-1<x\le i$.

intervalo de números inteiros

Um intervalo de números inteiros é qualquer conjunto de inteiros consecutivos. Denotamos por  $p..r$  o intervalo  $\{p,p+1,\dots ,r\}$.

vetor (indexado por um conjunto)

Um vetor indexado por um conjunto finito $M$ é uma função que leva $M$ em um conjunto de números.  (Não é uma boa ideia supor que $M$ é necessariamente um subconjunto de $\mathbf{N}$.)  Um vetor $x$ indexado por $M$ pode ser representado pela expressão $(x_i:i\in M)$.

vetor real

Um vetor real é uma função que leva um conjunto finito $M$ em $\mathbf{R}$.  O conjunto de tais funções pode ser denotado por ${\mathbf{R}}^M$.

vetor racional

Um vetor racional é qualquer vetor cujas componentes são números racionais. Um vetor racional indexado por $M$ é uma função que leva $M$ em $\mathbf{Q}$.  O conjunto de tais funções pode ser denotado por ${\mathbf{Q}}^M$.

vetor inteiro

Um vetor inteiro é qualquer vetor cujas componentes são números inteiros. Um vetor inteiro indexado por $M$ é uma função que leva $M$ em $\mathbf{Z}$. O conjunto de tais funções pode ser denotado por ${\mathbf{Z}}^M$.

vetor não-negativo

Um vetor é não-negativo se todas as suas componentes são não-negativas.

vetor binário

Um vetor binário é qualquer vetor cujas componentes são elementos do conjunto $\{0,1\}$.  Usa-se também a expressão vetor booleano.

vetor unitário

Um vetor unitário indexado por um conjunto $M$ é qualquer vetor $x$ tal que $x[m]=1$ para algum $m$ em $M$ e $x[i]=0$ para todo $i$ em $M\setminus \{m\}$.

vetor característico

O vetor característico de um subconjunto $K$ de um conjunto finito $M$ é o vetor binário $x$ definido assim:  $x[i]=1$ se $i\in K$ e $x[i]=0$ se $i\in M\setminus K$.

suporte de um vetor

O suporte de um vetor $x$ é o conjunto de todos os índices $i$ tais que $x[i]\ne 0$.

crescente

Um vetor $v[1..n]$ é crescente se  $v[1]\le v[2]\le \cdots \le v[n]$.

estritamente crescente

Um vetor $v[1..n]$ é estritamente crescente se  $v[1]<v[2]<\cdots <v[n]$.

decrescente

Análogo a crescente.

estritamente decrescente

Análogo a estritamente crescente.

$\lg n$  ou  $\lg (n)$

Denotamos por  $\lg n$  o logaritmo na base 2 de $n$.  Notação alternativa:  ${\log }_{2}n$.

$\ln n$  ou  $\ln (n)$

Denotamos por  $\ln n$  o logaritmo natural de $n$, ou seja, o logaritmo de $n$ na base $e$.  Notação alternativa:  ${\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$.

assintótico

O adjetivo assintótico e o advérbio assintoticamente significam 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)=\mathrm{O}(g(n))$

Dizer $f(n)=\mathrm{O}(g(n))$ é o mesmo que dizer que existe um número $c$ tal que  $f(n)\le 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)=\mathrm{\Omega }(g(n))$

Dizer $f(n)=\mathrm{\Omega }(g(n))$ é o mesmo que dizer que existe um número $c\ge 0$ tal que  $f(n)\ge 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)=\mathrm{\Theta }(g(n))$

Dizer $f(n)=\mathrm{\Theta }(g(n))$ é o mesmo que dizer que  $f(n)=\mathrm{O}(g(n))$  e  $f(n)=\mathrm{\Omega }(g(n))$.

algoritmo logarítmico

Um algoritmo é logarítmico se consume $\mathrm{O}(\log n)$ unidades de tempo, sendo $n$ o parâmetro que mede o tamanho da entrada do algoritmo.  Em geral, a expressão algoritmo logarítmico só é aplicada a algoritmos que consomem $\mathrm{\Theta }(\log n)$ unidades de tempo.

algoritmo linear

Um algoritmo é linear se consume $\mathrm{O}(n)$ unidades de tempo, sendo $n$ o parâmetro que mede o tamanho da entrada do algoritmo.  Em geral, a expressão algoritmo linear só é aplicada a algoritmos que consomem $\mathrm{\Theta }(n)$ unidades de tempo.

algoritmo linearítmico ou ene-log-ene

Um algoritmo é linearítmico se consume $\mathrm{O}(n\log n)$ unidades de tempo, sendo $n$ o parâmetro que mede o tamanho da entrada do algoritmo.  Em geral, a expressão algoritmo linearítmico só é aplicada a algoritmos que consomem $\mathrm{\Theta }(n\log n)$ unidades de tempo.

algoritmo quadrático

Um algoritmo é quadrático se consume $\mathrm{O}(n^2)$ unidades de tempo, sendo $n$ o parâmetro que mede o tamanho da entrada do algoritmo.  Em geral, a expressão algoritmo quadrático só é aplicada a algoritmos que consomem $\mathrm{\Theta }(n^2)$ unidades de tempo.

algoritmo cúbico

Um algoritmo é cúbico se consume $\mathrm{O}(n^3)$ unidades de tempo, sendo $n$ o parâmetro que mede o tamanho da entrada do algoritmo.  Em geral, a expressão algoritmo cúbico só é aplicada a algoritmos que consomem $\mathrm{\Theta }(n^3)$ unidades de tempo.

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

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

invariante (de processo iterativo)

Um invariante de um processo iterativo é uma relação entre os valores das variáveis que vale no início de cada iteração e não se altera de uma iteração para a seguinte. Essas relações invariantes explicam o funcionamento do processo iterativo e permitem provar, por indução, que o processo tem o efeito desejado.

$\mathbf{E}[X]$

A expressão $\mathbf{E}[X]$ denota a esperança da variável aleatória $X$, ou seja, $\sum _{k}k\mathbf{Pr}[X=k]$.

$\mathbf{Pr}[X=k]$

A expressão $\mathbf{Pr}[X=k]$ denota a probabilidade de que a variável aleatória $X$ tenha valor $k$.

seja

A palavra seja introduz uma notação e serve para dar nomes a coisas. Por exemplo, a expressão seja $x$ um número positivo deve ser entendida assim: escolha um número positivo arbitrário e atribua o nome $x$ a esse número.

A palavra seja refere-se a $x$ e não ao número positivo. Segue daí que a expressão seja um número positivo $x$, com $x$ no fim da expressão, está errada pois soa como um ato de criação — à maneira de Faça-se luz! — que faz surgir um número positivo do nada.