1.2 Mathematical Preliminaries

Nesta seção, vamos explorar as notações matemáticas presentes ao longo de The Art of Computer Programming e desenvolver algumas fórmulas básicas que serão utilizadas diversas vezes. Mesmo que o leitor não se interesse pelas derivações matemáticas mais avançadas, é recomendável que se familiarize, ao menos, com o significado das diferentes fórmulas, para que possa aproveitar os resultados dessas derivações.

A notação matemática tem dois objetivos principais neste livro: descrever partes de um algoritmo e avaliar as características de desempenho de um algoritmo. A notação empregada para descrever algoritmos é relativamente simples, conforme detalhado na seção anterior. Já para analisar o desempenho dos algoritmos, recorremos a notações mais específicas e especializadas.

A maioria dos algoritmos que abordaremos vem acompanhada de cálculos matemáticos que estimam a velocidade esperada de execução. Esses cálculos abrangem quase todas as áreas da matemática, e seria necessário um livro à parte para explorar todos os conceitos matemáticos utilizados em diferentes momentos. Ainda assim, a maior parte desses cálculos pode ser compreendida com conhecimentos de álgebra universitária, e quem domina cálculo elementar conseguirá acompanhar quase toda a matemática apresentada. Em alguns casos, recorremos a resultados mais avançados de áreas como teoria de variáveis complexas, teoria de grupos, teoria dos números, teoria da probabilidade, entre outras. Nessas situações, o tema será explicado de forma simples, sempre que possível, ou indicaremos referências a outras fontes de informação.

As técnicas matemáticas usadas na análise de algoritmos têm um caráter bem particular. Por exemplo, é comum lidarmos com somas finitas de números racionais ou com soluções de relações de recorrência. Esses assuntos costumam receber pouca atenção nos cursos tradicionais de matemática, por isso as próximas subseções foram planejadas para oferecer um treinamento detalhado no uso das notações que serão definidas, além de exemplificar em profundidade os tipos de cálculos e métodos mais úteis para nossos propósitos.

Nota importante: As subseções seguintes proporcionam um treinamento abrangente nas habilidades matemáticas relacionadas ao estudo de algoritmos de computador. No entanto, a maioria dos leitores pode não perceber, de início, uma ligação direta entre esse conteúdo e a programação de computadores (exceto na Seção 1.2.1). O leitor pode optar por estudar essas subseções com atenção, confiando na afirmação do autor de que os temas aqui tratados são, sim, muito relevantes. Porém, para manter a motivação, talvez seja melhor dar uma leitura superficial nesta seção inicialmente e, depois de encontrar várias aplicações dessas técnicas nos capítulos seguintes, volte para um estudo mais aprofundado. Passar tempo demais nesse material logo na primeira leitura pode atrasar o avanço para os tópicos de programação! De toda forma, é essencial que cada leitor conheça ao menos o conteúdo geral dessas subseções e tente resolver alguns exercícios, mesmo na leitura inicial. A Seção 1.2.10 merece destaque especial, pois serve como ponto de partida para grande parte do material teórico desenvolvido mais adiante. Já a Seção 1.3, que vem após a 1.2, marca uma transição abrupta da “matemática pura” para a “programação de computadores pura”.

Uma expansão e apresentação mais detalhada de grande parte do material a seguir podem ser encontradas no livro Concrete Mathematics de Graham, Knuth e Patashnik, segunda edição (Reading, Mass.: Addison–Wesley, 1994). Esse livro será chamado simplesmente de CMath quando precisarmos nos referir a ele posteriormente.

1.2.1 Indução Matemática

Seja $P(n)$ alguma afirmação sobre o número inteiro $n$; por exemplo, $P(n)$ pode ser

$$\text{"$$ n $$ vezes $$ (n + 3) $$ é um número par"}$$

ou

$$\text{"se } n \geq 10, \text{ então } 2^n > n^3 \text{."}$$

Suponha que queiramos provar que $P(n)$ é verdadeira para todos os inteiros positivos $n$. Uma maneira importante de fazer isso é:

1. Fornecer uma prova de que $P(1)$ é verdadeira.

2. Fornecer uma prova de que

$$\text{"se todas as afirmações } P(1), P(2), \dots, P(n) \text{ forem verdadeiras, então } P(n + 1) \text{ também é verdadeira."}$$

Essa prova deve ser válida para qualquer inteiro positivo $n$.

Como exemplo, considere a seguinte sequência de equações, que muitas pessoas descobriram independentemente desde os tempos antigos:

$$1 = 1^2,$$

$$1 + 3 = 2^2,$$

$$1 + 3 + 5 = 3^2,$$

$$1 + 3 + 5 + 7 = 4^2,$$

$$1 + 3 + 5 + 7 + 9 = 5^2.$$

Podemos formular a propriedade geral da seguinte maneira:

$$1 + 3 + \dots + (2n - 1) = n^2.$$

Chamemos essa equação temporariamente de $P(n)$; desejamos provar que $P(n)$ é verdadeira para todo $n$ positivo. Seguindo o procedimento descrito acima, temos:

1. Passo Base:

   $$P(1) \text{ é verdadeira, pois } 1 = 1^2.$$
2. Passo Indutivo: Se todas as afirmações $P(1), \dots, P(n)$ forem verdadeiras, então, em particular, $P(n)$ é verdadeira, de modo que a equação acima se mantém. Somando $2n + 1$ em ambos os lados, obtemos

   $$1 + 3 + \dots + (2n - 1) + (2n + 1) = n^2 + 2n + 1 = (n + 1)^2,$$

   o que prova que $P(n + 1)$ também é verdadeira.

Podemos considerar esse método como um procedimento de prova algorítmico. De fato, o seguinte algoritmo gera uma prova de $P(n)$ para qualquer inteiro positivo $n$, assumindo que os passos (1) e (2) acima tenham sido realizados:

Algoritmo $I$ (Construção de uma prova)

Dado um inteiro positivo $n$, este algoritmo fornecerá uma prova de que $P(n)$ é verdadeira.

$I1.$ [Provar $P(1)$] Defina $k \gets 1$ e, de acordo com o passo base, forneça uma prova de $P(1)$.

$I2.$ [Verificar $k = n$] Se $k = n$, termine o algoritmo; a prova necessária foi gerada.

$I3.$ [Provar $P(k + 1)$] De acordo com o passo indutivo, forneça uma prova de que

$\text{"Se todas as afirmações } P(1), \dots, P(k) \text{ forem verdadeiras, então } P(k + 1) \text{ é verdadeira."}$

Além disso, forneça a afirmação:

$\text{"Já provamos } P(1), \dots, P(k); \text{ logo, } P(k + 1) \text{ é verdadeira."}$

$I4.$ [Incrementar $k$] Aumente $k$ em 1 e retorne ao passo 2. ||

Fig. 2. Algoritimo I: Indução Matemática