BCM0505-15 - Processamento da Informação

Aula 01 – 12/02

Busca Sequencial

Considere o seguinte problema de busca, fundamental em computação / programação:

Problema 1.1: Dados uma sequência $$A = [ a_0,a_1,\ldots,a_{n-1} ]$$ de $n\geq 0$ elementos e um elemento $x$, devolva um índice $j$ tal que $a_j=x$ caso $x\in A$, ou devolva $j=n$ em caso contrário.

Uma boa estratégia na procura por soluções a problemas algorítmicos (como o acima) consiste em começar respondendo às seguintes perguntas:

• Há hipóteses? Quais?
  Observamos que a lista $A$ é finita — podendo ser vazia — e indexada e que os elementos em $A$ e devem ser comparáveis a $x$. Além disso, não há relações entre os elementos em $A$ (não estão ordenados, por exemplo) e pode haver repetições.

• O que representa uma solução? Ela está bem definida?
  Caso $x$ ocorra em $A$, a resposta é um índice $0\leq j< n$ tal que $a_j=x$; no caso de $x$ ocorrer múltiplas vezes em $A$, qualquer índice que satisfaça a relação é válido. Caso $x$ não ocorra em $A$, a resposta é igual ao número de elementos $n$ em $A$; observe que, como $A$ está indexada de $0$ a $n-1$, não há problemas de definição.

• O problema então faz sentido?
  Claramente faz! Trata-se de um problema abstrato de busca — pode resolver um número infinito de instâncias, cada qual fornecida como entrada em uma execução do algoritmo — em uma coleção não estruturada de elementos.

Como próximo passo, é conveniente testarmos nossa compreensão do problema com um exemplo concreto. Suponha, sem perda de generalidade, que os elementos em $A$ são números inteiros e tome $$A = [ 4,5,-1,0,5,2,8,-9,5 ].$$ Uma busca por $x=0$ deve devolver $j=3$; por $x=5$, deve devolver $j=1$, ou $j=4$ ou $j=8$; já por $x=1$, deve devolver $n=9$.

Um Algoritmo

A resolução de um exemplo muitas vezes fornece a ideia de um algoritmo. Neste problema, em que a sequência $A$ não tem estrutura, este é certamente o caso: podemos realizar uma varredura (da esquerda para a direita) em $A$, comparando os elementos de $A$ um a um a $x$ até que encontremos um índice $j$ válido, ou esgotemos a sequência.

A descrição acima, apesar de fazer sentido para nós, ainda é um tanto vaga para a execução em um computador. Por exemplo, é claro para nós o que a referida varredura significa neste contexto, mas um computador não possui e nem compartilha deste contexto. Precisamos, então, descrever tal algoritmo de maneira mais precisa e formal. As linguagens de programação foram desenvolvidas para auxiliar nesta tarefa.

Uma reanálise da descrição apresentada revela que são necessários:

1. um mecanismo sintático para lidar com sequências de elementos (inteiros),
2. um artifício que possamos controlar e utilizar para indexar uma tal sequência,
3. uma estrutura que permita realizar um conjunto de tarefas repetidamente, sujeita à satisfação de alguma condição de término,
4. um invólucro que permita o acesso a nosso algoritmo, recebendo dados de entrada e a devolvendo respostas como saída.

Em Python, tais instrumentos são disponibilizados via listas, variáveis, laços while, e funções, respectivamente. O código abaixo é uma descrição formal de nosso algoritmo.

# Busca Sequencial
# - recebe : uma lista A de inteiros e um elemento x
# - devolve: um índice j tal que A[j] == x se x ocorre em A, ou j == len(A) em caso contrario
#
def seq_search (A, x):
  j, n = 0, len(A)
  while j < n and A[j] != x: # (*)
    j = j + 1
  return j

Um exemplo de uso é:

  A = [4, 5, -1, 0, 5, 2, 8, -9, 5]
  x = int (input ("Valor de x: "))  
  j = seq_search (A, x)
  if j == len (A):
    print (x, " não ocorre em A")
  else:
    print (x, " ocorre na posição ", j)

Correção

Vamos agora nos certificarmos que este código faz o que promete. Observe que no ponto marcado por $(*)$ — um artifício abstrato colocado dentro de um comentário após a expressão do laço while e antes da instrução j = j + 1 — sempre vale que $$j < n \quad\textrm{e}\quad x\not\in A[0\,..j], \qquad\qquad (1)$$ em que $A[0\,..j]=[ a_0, a_1,\ldots,a_j ]$. A Expressão $(1)$ é um invariante do laço e pode ser facilmente provada por indução em $j$.

A base é trivial pois $A[0\,..-1]$ é vazia quando $j=0$. Suponha, a título de hipótese de indução, que $(1)$ é válida para $j-1$ quando $1\leq j< n$. Temos que $j-1$ avança para $j$ no interior do laço e um novo teste condicional é realizado a seguir na expressão de while.
Caso $j=n$ ou $A[j]=x,$ o laço termina antes que $(*)$ seja atingido e o resultado segue. Em caso contrário, temos que $$j < n\quad \textrm{e}\quad A[j]\neq x \qquad\textrm{e que}\qquad x\not\in A[0\,..j-1],$$ o último por hipótese de indução, resultando na validade de $(1)$ para $j$ e completando a indução.

Quando o laço while termina, temos que $j = n$ ou que $j < n$ e $A[j] = x$ — lembre-se que o operador and em Python é curto-circuitado, de forma que não há um acesso inválido a $A[n]$. No primeiro caso, o invariante garante que $x\not\in A[0\,..n-1]$ e a resposta $n$ devolvida é correta. No segundo, o elemento $x$ foi encontrado no índice $j$ (e não antes, pelo invariante) e a resposta $j$ devolvida é correta.

Uma Variação

Apesar de simples, a técnica de varredura utilizada ocorre como solução de vários outros problemas. O fato de ter sido implementada da esquerda para a direita é irrelevante neste problema; poderíamos tê-la feito de forma reversa. Em sendo o caso, é melhor devolvermos $-1$ em vez de $n$ para indicarmos a não ocorrência de $x$ em $A$, como ilustrado no código abaixo.

# Busca Sequencial Reversa
# - recebe : uma lista A de inteiros e um elemento x
# - devolve: um índice j tal que A[j] == x se x ocorre em A, ou j == -1 em caso contrario
#
def rev_seq_search (A, x):
  j = len(A) - 1
  while j >= 0 and A[j] != x:
    j = j - 1
  return j

Observe que a correção da busca reversa é análoga à direta.

Performance

O cerne das soluções apresentadas é a comparação A[j] != x. O restante, apesar de importante, ocorre somente para garantir que estas comparações sejam feitas corretamente.

Uma pergunta natural então é: dados uma sequência $A$ e um elemento $x$, quantas comparações A[j] != x são realizadas? A naturalidade da pergunta reside nos fatos de que:

• tal número é suficiente para resolvermos o problema (já que o algoritmo é correto), e
• o tempo consumido em execuções dos códigos depende diretamente de tal número.

Não é difícil perceber que o algoritmo de busca sequencial é adaptativo: o número de comparações depende de $x$, dos elementos em $A$ e da ordem em que eles ocorrem. Logo, sem hipóteses adicionais sobre distribuição ou ordem, não é possível fornecermos uma resposta precisa. Antes de seguirmos este caminho, podemos focar em uma pergunta mais fraca, mas não menos importante: quantas comparações são feitas no pior caso?

O algoritmo faz uma varredura em $A$ e existem dois piores casos: quando $x$ ocorre na última posição inspecionada e quando $x\not\in A$. Em ambos, são realizadas $n$ comparações A[j] != x. Logo,

• $n$ comparações são suficientes para determinar se $x\in A$, e
• o tempo requerido no pior caso é linear ($cn+d$, para constante $c>0$ e $d>0$) no número de elementos em $A$.

A determinação das constantes $c$ e $d$ depende de detalhes do código, das otimizações existentes no interpretador Python, e do tipo e da velocidade do hardware na qual está sendo executado. A dependência em $n$, entretanto, é absorta a todos esses detalhes. Por esses (e outros) motivos, utilizamos a notação assintótica Big-Oh para esconder constantes e termos de menor ordem, e dizemos que o algoritmo que desenvolvemos requer tempo $O(n)$ no pior caso.

Nota: o número de comparações no melhor caso é claramente $1$, em que $x$ é encontrado na primeira posição inspecionada de $A$.

Limitante Inferior

Vimos que $n$ comparações A[j] != x são suficientes para determinarmos se $x\in A$. Elas são necessárias? Isto é, há possibilidade de resolvermos o problema realizando menos de $n$ comparações no pior caso? A resposta é negativa.

Suponha que existe um algoritmo $\mathscr{A}$ que recebe $A$ e $x$ e determina se $x\in A$ fazendo $k<n$ comparações A[j] != x. Como $A$ não possui nenhuma estrutura, as $k$ posições inspecionadas por $\mathscr{A}$ não revelam nenhuma informação sobre o conteúdo das demais $n-k$. Logo, é possível que $x$ ocorra em uma dessas $n-k$ posições e não ocorra nas outras $k$. Em sendo o caso, $\mathscr{A}$ devolve a incorreta resposta que $x\not\in A$. Portanto, $n$ comparações são necessárias no pior caso.

Extra: Caso Médio *

Esta seção é opcional (e não foi feita em sala).

Considere que $x$ e os elementos de $A$ são dados. Caso $x\not\in A$, o número de comparações A[j] != x é igual a $n$, o mesmo do pior caso. Suponha então que $x\in A$ e que os elementos em $A$ são dispostos de maneira equiprovável — isto é, não há ordem preferida. Desta forma, a chance de $x$ ocorrer em qualquer posição $j$ é igual a $\frac{1}{n}$. seq_search (A, x) encontra $x$ na posição $j$ após $j+1$ comparações. Utilizando uma variável aleatória $X$ para denotar o número de comparações A[j] != x em uma execução de seq_search (A, x), temos que o número esperado de comparações é $$\mathbb{E}[X] = \sum_{j=0}^{n-1}(j+1)\frac{1}{n} = \frac{1}{n}\sum_{j=1}^{n}j = \frac{1}{n}\cdot\frac{n(n+1)}{2} = \frac{n+1}{2}.$$

Portanto, em média, $(n+1)/2$ comparações são realizadas quando $x$ ocorre uma vez em $A$. Uma análise mais cuidadosa pode ser feita para o caso em que $x$ ocorre $k\geq 1$ vezes em $A$, resultando em $\mathbb{E}[X] = \frac{n+1}{k+1}.$ Deixo a derivação desta como exercício para os mais interessados.

Notas Finais

Esta aula teve como objetivo ilustrar alguns princípios do “pensamento computacional” e passos a serem seguidos na obtenção de uma solução algorítmica. De forma resumida, devemos:

• investigar o problema (o que está sendo pedido),
• auxiliar nossa compreensão via a construção de um ou mais exemplos,
• inspecionar tais exemplos na tentativa de obtermos uma possível solução,
• descrever o algoritmo de forma precisa e não ambígua; possivelmente em uma linguagem de programação,
• certificarmos de que o algoritmo desenvolvido é correto (em todos os casos que satisfaçam as hipóteses),
• analisarmos a performance da solução, procurando por possíveis pontos de melhoria; em sendo o caso, repetimos alguns dos passos acima.

Fomos, então, do problema a um algoritmo e a um código, à prova de sua correção e à análise de sua performance.

Este, no entanto, é um primeiro curso de programação. Logo, apesar de estarmos sempre interessados na correção e na performance de nossos algoritmos, não vamos mais:

• fazer provas de correção formais por indução (ou via qualquer outra técnica),
• realizar análises assintóticas que sejam elaboradas, e
• desenvolver sempre o “melhor” algoritmo para um problema.

Existem outros cursos apropriados para isso na grade. Desta vez, vamos nos contentar com argumentos simples e informais para algoritmos interessantes que resolvem — não necessariamente da melhor forma — os problemas que investigarmos.