Notas de rodapé: matemática


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


Crescente

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.


Sequência versus conjunto

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


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


Subsequências e subvetores

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 = ai1s2 = 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.


Segmentos

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 ≤ ikn.  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 ≤ ikn.  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.  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 ⌉ .


Logaritmo na base 2

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 é  log2n,  não  log 2 n,  nem  log 2n,  nem tampouco  log2n.)

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