-
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:
$\seq{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, \ldots, a_n)$
é qualquer sequência
$(b_1, b_2, \ldots, b_k)$
tal que
$b_1 = a_{i_1},
b_2 = a_{i_2}, \ldots,
b_k = a_{i_k}$
para alguma sequência
$i_1 \lt
i_2 \lt
\cdots \lt 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,
\ldots,
a_n)$
é qualquer sequência da forma
$(a_i,
a_{i+1},
a_{i+2},
\ldots,
a_k)$
com
$1 \leq i$ e
$k \leq 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:
$\conj{a, d, b, c}$
é o conjunto cujos elementos são
$a$, $b$,
$c$, $d$.
-
união
-
Para qualquer coleção $\Acal$,
a expressão $\bigcup \Acal$
denota a união de todos os elementos de $\Acal$.
Por exemplo, se os elementos de $\Acal$ são
$A_1, \text{}$ $A_2, \ldots, \text{}$ $A_k$
então
$\bigcup \Acal = \text{}$
$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\setm S$.
Notação:
$\overline{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] \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 $V$ é qualquer coleção $\Pcal$
de subconjuntos não vazios de $V$ tal que
todo elemento de $V$
pertence a um e apenas um dos elementos de $\Pcal$.
Cada elemento de $\Pcal$ é um bloco da partição.
Exemplo:
$\{\conj{1,3},$
$\conj{2,4,7},$
$\conj{5},$
$\conj{6,8}\}$
é uma partição de
$\{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 $\Pcal$ e $\Pcal'$
de um conjunto,
dizemos que
$\Pcal'$ é um refinamento de $\Pcal$
se todo elemento de
$\Pcal'$ é subconjunto
de algum elemento de $\Pcal$.
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}}$.
-
minimal
-
Suponha que $\Pcal$ é uma coleção de conjuntos.
Um elemento $P$ de $\Pcal$ é
minimal
se nenhum subconjunto próprio de $P$
pertence a $\Pcal$.
Em outras palavras, $P$ é minimal
se não existe $Q$ em $\Pcal$
tal que $Q \subset P$.
-
maximal
-
Suponha que $\Pcal$ é uma coleção de conjuntos.
Um elemento $P$ de $\Pcal$ é
maximal
se nenhum superconjunto próprio de $P$
pertence a $\Pcal$.
Em outras palavras, $P$ é maximal
se não existe $Q$ em $\Pcal$
tal que $Q \supset P$.
-
mínimo
-
Suponha que $\Pcal$ é uma coleção de conjuntos.
Um elemento $P$ de $\Pcal$ é
mínimo
se não existe $Q$ em $\Pcal$
tal que $|Q| \lt |P|$.
Em outras palavras, $P$ é mínimo
se $|P| \leq |R|$
para todo $R$ em $\Pcal$.
(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 $\Pcal$ é uma coleção de conjuntos.
Um elemento $P$ de $\Pcal$ é
máximo
se não existe $Q$ em $\Pcal$
tal que $|Q| > |P|$.
Em outras palavras, $P$ é máximo
se $|P| \geq |R|$
para todo $R$ em $\Pcal$.
É 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
$\conj{0, 1, 2, 3, 4, \ldots}$.
Um número natural é essencialmente o mesmo que número inteiro não-negativo.
O conjunto dos números naturais é denotado por $\N$.
-
número inteiro
-
Um número inteiro é qualquer elemento do conjunto
$\conj{\ldots,-4, -3, -2, -1, 0, 1, 2, 3, 4, \ldots}$.
O conjunto dos números naturais é denotado
por $\Z$
e o conjunto dos inteiros não-negativos
é denotado por $\Zplus$.
Portanto, $\Zplus = \N$.
-
número racional
-
Um 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 racionais
é denotado por $\Q$
e o conjunto dos racionais não-negativos
é denotado por $\Qplus$.
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 $\R$
e o conjunto dos reais não-negativos
é denotado por $\Rplus$.
É claro que $\N \subset \Z \subset \Q \subset \R$.
Computadores digitais conhecem apenas um subconjunto finito de $\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 \geq 0$.
-
$\floor{x}$ ou
piso($x$)
-
$\floor{x}$ é o único inteiro $i$ tal que
$i \leq x \lt i+1$.
-
$\ceil{x}$ ou
teto($x$)
-
$\ceil{x}$ é o único inteiro $i$ tal que
$i-1 \lt x \leq i$.
-
intervalo de números inteiros
-
Um intervalo de números inteiros é qualquer
conjunto de inteiros consecutivos.
Denotamos por
$p \tdots r$
o intervalo
$\conj{p, p+1, \ldots, 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 $\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 $\R$.
O conjunto de tais funções pode ser denotado
por $\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 $\Q$.
O conjunto de tais funções pode ser denotado
por $\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 $\Z$.
O conjunto de tais funções pode ser denotado
por $\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 $\conj{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\setm\conj{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\setm K$.
-
suporte de um vetor
-
O suporte de um vetor $x$
é o conjunto de todos os índices $i$ tais que
$x[i] \neq 0$.
-
crescente
-
Um vetor $v[1\tdots n]$ é crescente se
$v[1] \leq
v[2]\leq
\cdots \leq v[n]$.
-
estritamente crescente
-
Um vetor $v[1 \tdots n]$
é estritamente crescente se
$v[1] \lt v[2] \lt \cdots \lt 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) \lt g(n)$
para todo $n$ suficientemente grande.
-
$f(n) = \Oh(g(n))$
-
Dizer $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))$
-
Dizer $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))$
-
Dizer $f(n) = \Theta(g(n))$ é
o mesmo que dizer que
$f(n) = \Oh(g(n))$
e
$f(n) = \Omega(g(n))$.
-
algoritmo logarítmico
-
Um algoritmo é logarítmico se consume
$\Oh(\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 $\Theta(\log n)$
unidades de tempo.
-
algoritmo linear
-
Um algoritmo é linear se consume
$\Oh(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 $\Theta(n)$
unidades de tempo.
-
algoritmo linearítmico ou ene-log-ene
-
Um algoritmo é linearítmico se consume
$\Oh(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 $\Theta(n \log n)$
unidades de tempo.
-
algoritmo quadrático
-
Um algoritmo é quadrático se consume
$\Oh(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 $\Theta(n^2)$
unidades de tempo.
-
algoritmo cúbico
-
Um algoritmo é cúbico se consume
$\Oh(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 $\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.