Notas de rodapé sobre matemática na ciência da computação

Notas de rodapé: matemática

Números naturais e números inteiros

Um número natural é qualquer elemento do conjunto 0 1 2 3 4 … Um inteiro é qualquer elemento do conjunto … −4 −3 −2 −1 0 1 2 3 4 …

Positivo e negativo

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

Sequências e conjuntos

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

Sequências podem ser representadas por vetores ou por listas encadeadas. Conjuntos podem ser representados por vetores estritamente crescentes ou listas encadeadas estritamente crescentes.

Ordem crescente

Uma sequência (v₀, v₁, … , v_n−1) é crescente (ou está em ordem crescente) se v₀ ≤ v₁ ≤ … ≤ v_n−1 . A sequência é 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 vetores e listas encadeadas.

Cuidado: Alguns livros dizem não decrescente onde eu digo crescente. Também dizem crescente onde eu digo estritamente crescente.

Permutação

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 2 3 é uma permutação de 1 2 2 3 4 . É fácil verificar que uma sequência com n elementos tem exatamente n! diferentes permutações.

Ordem lexicográfica

A ordem lexicográfica entre sequências de inteiros é definida grosseiramente assim: uma sequência s é lexicograficamente menor que uma sequência t se o primeiro elemento de s que difere do correspondente elemento de t é menor que aquele elemento de t.

Uma definição precisa pode ser formulada como segue. Dadas sequências distintas s = (s₁, s₂, … , s_m) e t = (t₁, t₂, … , t_n) de inteiros, dizemos que s é lexicograficamente menor que t se

s_k < t_k para o menor k tal que s_k ≠ t_k ou
m < n e não existe k tal que s_k ≠ t_k.

Sob as mesmas condições, dizemos que t é lexicograficamente maior que s.

(Veja um dos exercícios do capítulo Algoritmos de enumeração.)

A ordem lexicográfica é transitiva (ou seja, se s é lexicograficamente menor que t e t é lexicograficamente menor que u então s é lexicograficamente menor que u). Ademais, a ordem lexicográfica é total (ou seja, para quaisquer duas sequências s e t diferentes, ou s é lexicograficamente menor que t ou s é lexicograficamente maior que t).

Agora considere uma sequência de sequências, também conhecida como lista de sequências. Dizemos que a lista está em ordem lexicográfica, ou em ordem de dictionário, se cada sequência da lista for igual ou lexicograficamente menor que cada uma das sequências seguintes da lista. O seguinte exemplo mostra uma lista de sequências em ordem lexicográfica, com uma sequência por linha:

65 66 65
65 66 82 73 82
65 66 82 73 85
65 66 82 79
65 67 85 83 65 82
65 90 65 82
66 65 66 65
66 65 78 67 65
66 65 82
66 65 82 65 84 65
66 69 66 69 82

Ordem lexicográfica para strings. Uma string é uma sequência de bytes. Como cada byte representa um inteiro positivo em notação binária, a ordem lexicográfica entre strings segue da ordem lexicográfica entre sequências de inteiros. (Veja a seção Ordem lexicográfica no capítulo Manipulação de strings.)

Uma lista de strings está em ordem lexicográfica se cada string da lista for lexicograficamente menor ou igual a cada uma das strings seguintes. Eis um exemplo de uma lista de strings em ordem lexicográfica:

A B A
A B R I R
A B R I U
A B R O
A C U S A R
A Z A R
B A B A
B A N C A
B A R
B A R A T A
B E B E R

Subsequências

Uma subsequência é o que sobra quando alguns termos de uma sequência são apagados. Mais exatamente, uma subsequência de uma sequência (a₁, a₂, … , a_n) é qualquer sequência (b₁, b₂, … , b_k) tal que

b₁ = a_i₁, b₂ = a_i₂, … , b_k = a_{i_k}

para alguma sequência i₁ < i₂ < … < i_k de índices. Por exemplo, (2, 3, 5, 8) é uma 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). (Veja o exercício Subsequência no capítulo Vetores.)

Assim como sequências são representadas por vetores, subsequências são representadas por subvetores. Um subvetor de um vetor a[1 .. n] é qualquer vetor b[1 .. k] tal que b[1] = a[i₁], b[2] = a[i₂], … , b[k] = a[i_k] para alguma sequência i₁ < i₂ < … < i_k de índices.

Segmentos

Um segmento de uma sequência é uma subsequência contínua. Em outras palavras, um segmento é o que sobra quando alguns dos termos iniciais e alguns dos termos finais da sequência são apagados. Mais exatamente, uma segmento de uma sequência (a₁, a₂, … , a_n) é qualquer sequência da forma (a_i, a_i+1, a_i+2, … , a_k) com 1 ≤ i e 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 e k ≤ n. Se i > k, a expressão a[i .. k] representa o segmento vazio.

Prefixos e sufixos

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.

Partições

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

Piso e teto

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. O piso de x é denotado por

⌊ x ⌋ .

Em C, o piso de um número real é dado pela função floor da biblioteca math.

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. O teto de x é denotado por

⌈ x ⌉ .

Logaritmo na base 2

Nossos logaritmos são sempre tomados na base 2. Assim, log n é uma abreviatura de log₂ n , ou seja, do número real x tal que 2^x = n. (A propósito: a notação correta é log₂ n, não log 2 n, nem log 2ⁿ, nem tampouco log₂ⁿ .)

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