O Papel dos Algoritmos na Computação

O que é um algoritmo

Desenvolver um algoritmo é escolher um procedimento — uma sequência de decisões que um agente sem criatividade consegue executar.

Um algoritmo é uma sequência finita de passos bem definidos que, dada uma entrada válida, produz uma saída e termina. Cada passo precisa ser executável: não há "e então faça o óbvio". Linguagem natural, fluxograma ou pseudocódigo são só escritas do mesmo objeto.

Formalmente, um algoritmo $A$ associa cada entrada $i$ de um conjunto $I$ a uma saída $A(i)$ no conjunto das respostas aceitáveis. "Somar de $1$ a $n$" e "encontrar o maior de $n$ números" são problemas; o laço que acumula, a varredura que atualiza o máximo — isso é o algoritmo.

A definição impõe três condições ao mesmo tempo:

• Finitude e término. Uma receita que pode girar para sempre não é algoritmo: o texto dos passos é finito e a execução para.
• Passos claros. "Escolha um número bom" não é passo. "Compare $a[i]$ com $m$ e, se for maior, substitua $m$" é.
• Correção. Sem a garantia de que $A(i)$ responde o problema para toda $i\in I$ válida, o que se tem é um processo que às vezes acerta.

Por exemplo, máximo de $4,1,7$: $m\leftarrow 4$; compare com $1$ (fica $4$); compare com $7$ (fica $7$). Três comparações, termina, devolve $7$. Já é um algoritmo.

Correção e custo

Dois juízos distintos, nesta ordem:

• Correção. Para toda entrada válida, a saída é uma resposta do problema. Sem isso não há algoritmo útil.
• Custo (eficiência). Quanto tempo e memória o procedimento consome em função do tamanho $n$ da entrada. Dois algoritmos corretos para o mesmo problema podem diferir por ordens de grandeza.

A correção pergunta "sempre dá a resposta certa?". O custo pergunta "dá para esperar o fim quando $n$ cresce?". Uma varredura linear e uma busca que corta o vetor já ordenado ao meio a cada passo encontram um elemento, se ele existir; a segunda faz bem menos comparações.

Para medir custo define-se uma função $f$ de $n$:

• Se $f(n)$ mede o trabalho para executar o algoritmo numa entrada de tamanho $n$, $f$ é função de complexidade de tempo.
• Se $f(n)$ mede a memória extra (além da entrada) usada na execução, $f$ é função de complexidade de espaço.

A função estima quantas vezes uma operação relevante — comparação, atribuição, acesso — é executada. A mesma $f$ descreve o algoritmo em qualquer processador; o cronômetro da máquina mistura processador, linguagem e carga do sistema.

A análise de pior caso estabelece um limite superior para o tempo que vale para qualquer entrada de tamanho $n$ — o limite "nunca pior que isto". Melhor caso e caso médio existem; o que segura todas as entradas é o de pior caso.

Quando o procedimento é recursivo — chama a si mesmo em entradas menores —, o tempo não se lê num único laço: descreve-se por uma relação de recorrência $T(n)$, equação que define o custo a partir de $T$ nos subproblemas, mais o trabalho de combinar. No iterativo, o custo é a soma de laços; no recursivo, essa recorrência.

Um algoritmo pode ser correto e mesmo assim inútil na prática: enumerar as $n!$ permutações de um vetor — as $n!$ ordens possíveis — e devolver a ordenada está correto e custa um fatorial só para listá-las. É a escolha da família de projeto que muda essa ordem de grandeza.

Correção não se prova no relógio. Três vetores de teste não substituem uma prova para toda entrada válida. Custo não se prova só com um $n$ pequeno: constantes escondidas enganam o cronômetro.

Cinco famílias de projeto

Antes de escrever laços, escolhe-se como o problema será atacado. Cada linha da tabela é uma família, não um algoritmo pronto.

O guloso, quando vem com prova (escolha gulosa), devolve ótimo. A heurística é um palpite organizado: pode falhar. O aproximado admite erro, mas o erro tem teto — uma razão $\rho$. Tentativa e erro percorre o espaço; backtracking é a versão que poda ramos já inviáveis.

Tentativa e erro

O espaço de candidatos é finito. O procedimento parte o trabalho em subtarefas — um dígito do cadeado, uma rainha numa linha, um item entra-ou-não no subconjunto — e explora cada ramo até achar resposta ou esgotar. Sem poda, isso é pesquisa exaustiva: $k^n$ ou $n!$, conforme o objeto. Com poda (um ramo já viola a restrição), o mesmo desenho vira backtracking.

Dividir e conquistar

O problema de tamanho $n$ vira dois (ou $a$) problemas de tamanho $n/b$, mais um custo de combinação. Ordenar as metades e intercalar é o caso-guia: depois das partes, junta — diferente de "escolher o melhor item e seguir". O custo desse desenho é uma recorrência.

Guloso

Constrói a solução em etapas. Em cada etapa seleciona o melhor elemento da entrada que ainda é viável (cabe no troco, não sobrepõe o último intervalo) e não desfaz a escolha. Se houver prova de que essa escolha local leva ao ótimo global, o algoritmo é guloso no sentido forte. Troco com moedas $1,5,10$ (sempre a maior que cabe) é o exemplo mínimo — e neste sistema de moedas acerta.

Aproximado

Abre mão do ótimo. O que resta é uma razão: se $\mathrm{OPT}$ é o valor ótimo e $A$ o valor produzido, garante-se $A/\mathrm{OPT}\le\rho$ (minimização) ou $\mathrm{OPT}/A\le\rho$ (maximização) para um $\rho$ fixo. Uma cobertura de vértices é um conjunto $C$ de vértices que toca toda aresta. O procedimento que pega um emparelhamento maximal (conjunto de arestas sem vértice em comum, impossível de aumentar) e devolve os dois extremos de cada aresta escolhida é $2$-aproximado: cada aresta do emparelhamento exige pelo menos um vértice em qualquer cobertura ótima, e o algoritmo cobra dois, logo $A\le 2\cdot\mathrm{OPT}$. Sem esse teto, o procedimento cai na classe heurística.

Heurística

Pode produzir um bom resultado, às vezes o ótimo, e pode devolver saída sem garantia ou nenhuma solução. Não há prova de otimalidade nem razão $\rho$. Subir sempre ao vizinho de maior valor (subida de encosta) para num pico local: um ponto maior que os vizinhos imediatos, menor que o máximo global. Um "guloso" sem prova é, nesta classificação, heurística: a regra local é a mesma, a garantia é que some.

Balanceamento: partes de tamanho semelhante

Vetor de tamanho $n=8$. Recortar esses $n$ itens custa $O(n)$: no máximo uma constante vezes $n$ quando $n$ é grande.

Exemplo: nomear o desenho

O mesmo enunciado admite mais de uma família. O mapa serve para nomear o desenho. Considere o problema: dado um conjunto de intervalos na reta, escolher o maior subconjunto em que nenhum par se sobrepõe. Quatro intervalos, já escritos como $\bigl[\text{início},\text{fim}\bigr]$:

Metodologia em quatro perguntas

A metodologia de desenvolvimento é o mapa das cinco famílias mais as quatro perguntas abaixo.

1. O que entra e o que sai? Conjunto de intervalos $\to$ um subconjunto de cardinalidade máxima sem sobreposição.
2. Qual família cabe? Exaustão é tentativa e erro; recortar e costurar é dividir e conquistar; término mais cedo com prova é guloso; "primeiro que parecer bom" sem prova é heurística.
3. O procedimento está correto? Indução — prova que avança de um caso base a $n$ — ou checagem exaustiva nos casos pequenos. Um algoritmo errado e rápido não vira correto por ser barato.
4. Quanto custa? Melhor / pior / médio em função de $n$, contando a operação relevante. Recorrência no recursivo, soma de laços no iterativo.

Não pule a pergunta $1$. Um procedimento que "escolhe intervalos" sem dizer se o critério é cardinalidade, comprimento total ou estabilidade ainda não tem problema. Não misture $3$ e $4$.