A palavra positivo sempre deixa uma dúvida: positivo é > 0 ou ≥ 0? Algo análogo acontece com a palavra negativo.
Neste sítio, um número x é considerado positivo se x ≥ 0 e estritamente positivo se x > 0. (Para dar ênfase, podemos ocasionalmente usar a expressão positivo ou nulo no lugar de positivo.)
Analogamente, um número x é negativo se x ≤ 0 e estritamente negativo se x < 0. (Para dar ênfase, podemos usar a expressão negativo ou nulo no lugar de negativo.)
Um vetor v[0..n-1] é crescente (ou está em ordem crescente) se
v[0] ≤ v[1] ≤ . . . ≤ v[n-1] .
O vetor é
estritamente crescente se
tivermos <
no lugar dos
≤
.
Os conceitos de vetor decrescente e
estritamente decrescente são definidos
de maneira análoga.
Definições análogas se aplicam a sequências e listas encadeadas.
Cuidado:
Alguns livros dizem
não decrescente
onde eu digo crescente
.
Também dizem
crescente
onde eu digo estritamente crescente
.
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.) Para especificar os elementos de uma sequência, escreva-os, em ordem, embrulhados em parênteses: (a, b, c, …). Se isso não causar confusão, você pode dispensar os parênteses e vírgulas e escrever simplesmente a b c …
Uma conjunto não tem ordem.
Não há um primeiro elemento
nem um último elemento.
(Exemplo: o conjunto das dezenas em um sorteio da Loteria Federal.)
Como consequência, um conjunto não tem elementos repetidos
.
Para especificar os elementos de um conjunto,
escreva-os, em qualquer ordem,
embrulhados em chaves:
{a, b, c, …}.
Usaremos a notação a . . b para designar o conjunto de números inteiros {a, a+1, a+2, … , b}. Dependendo do contexto, essa notação também pode designar a sequência (a, a+1, a+2, … , b).
Uma permutação de uma sequência finita é qualquer sequência que tem os mesmos elementos numa ordem possivelmente diferente. Por exemplo, 2 1 4 3 é uma permutação de 1 2 3 4 . É fácil verificar que uma sequência com n elementos tem exatamente n! diferentes permutações.
Uma subsequência é o que sobra quando alguns termos de uma sequência são apagados. Mais precisamente, uma subsequência de uma sequência (a1, a2, … , an) é qualquer sequência (s1, s2, … , sk) tal que
s1 = ai1, s2 = ai2, … , sk = aik
para alguma sequência i1 < i2 < … < ik de índices. Por exemplo, (2, 3, 5, 8) é uma subsequência de (1, 2, 3, 4, 5, 6, 7, 8).
O conceito de subvetor é essencialmente o mesmo, uma vez que um vetor é essencialmente o mesmo que uma sequência. Assim, um subvetor de um vetor a[1 .. n] é qualquer vetor s[1 .. k] tal que
s[1] = a[i1], s[2] = a[i2], … , s[k] = a[ik]
para alguma sequência i1 < i2 < … < ik de índices. Se k = 0, o subvetor é vazio.
Um segmento
de uma sequência é uma subsequência contínua
:
é o que sobra quando alguns dos termos iniciais
e alguns dos termos finais
da sequência são apagados.
Mais precisamente,
uma segmento
de uma sequência
(a1,
a2,
… ,
an)
é qualquer sequência da forma
(ai,
ai+1,
ai+2,
… ,
ak)
com
1 ≤ i ≤ k ≤ n.
Por exemplo,
(2, 3, 4, 5)
é um segmento de
(1, 2, 3, 4, 5, 6, 7, 8).
Analogamente, um segmento de um vetor a[1 .. n] é qualquer vetor da forma a[i .. k] com 1 ≤ i ≤ k ≤ n. Se i > k, a expressão a[i .. k] representa o segmento vazio.
Um prefixo de uma sequência é um segmento que contém o primeiro termo da sequência. Um sufixo de uma sequência é um segmento que contém o último termo da sequência.
Uma partição de um conjunto X é qualquer coleção P de subconjuntos não vazios de X dotada da seguinte propriedade: todo elemento de X pertence a um e apenas um dos elementos de P. Cada elemento de 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.
(É um erro dizer
o conjunto {6,8} é uma partição de {1,2,3,4,5,6,7,8}.
)
O piso (= floor) de um número real x é o resultado do arredondamento de x para baixo. Em outras palavras, o piso de x é o único número inteiro i tal que
i ≤ x < i + 1 .
Por exemplo, o piso de 3.99 é 3. Em notação C, podemos denotar o piso de x por (int) x , desde que x não seja estritamente negativo. Em notação mais tradicional, o piso de x é denotado por
⌊ x ⌋ .
O teto (= ceiling) de um número real x é o resultado do arredondamento de x para cima. Em outras palavras, o teto de x é o único número inteiro j tal que
j − 1 < x ≤ j .
Por exemplo, o teto de 3.01 é 4. Em notação tradicional, o teto de x é denotado por
⌈ x ⌉ .
Nossos logaritmos são sempre tomados na base 2. Assim, log n é uma abreviatura de log2 n , ou seja, do número real x tal que 2x = n. (A propósito: a notação correta é log2 n, não log 2 n, nem log 2n, nem tampouco log2 n .)
Portanto, log n é essencialmente igual ao número de dígitos na representação binária de n, ou, equivalentemente, cerca de 3.3 vezes o número de dígitos na representação decimal de n.
(Nossa notação está em conflito com a notação da biblioteca math da linguagem C, onde a função log dá o logaritmo natural, ou seja, o logaritmo na base e = 2.71828….)