bc1435 – Problema computacional e medidas de complexidade de algoritmos: pior caso e caso médio

Um problema computacional abstrato é caracterizado  por uma terna

\displaystyle (\mathcal I, \mathcal O, R)

em que {\mathcal I} é um conjunto cujos elemento são ditos instâncias do problema, {\mathcal O} é conjunto cujos elemento são ditos respostas do problema, e {R \subset \mathcal I \times \mathcal O} é uma relação que associa instâncias a respostas do problema.Por exemplo:

Problema 1 Multiplicar dois inteiros positivos

Instância {x,y\in {\mathbb N} \setminus \{0\}}

Resposta x\cdot y \in {\mathbb N} \setminus \{0\}

R = \{((x,y),z)\colon x,y,z\in {\mathbb N} \setminus \{0\}, ~z=x\cdot y\}

Problema 2 Decidir se um número inteiro e positivo é primo

Instância {n\in {\mathbb N} \setminus \{0\}}

Resposta sim ou não.

R = \{(n,sim)\colon n \textrm{ natural primo}\}\cup \{(n,nao)\colon n \textrm{ natural composto}\}

Problema 3 Busca em vetor de inteiros

Instância uma sequência A=(a_1,a_2,\cdots,a_n) de inteirose x inteiro.

Resposta sim  ou não.

R = \{(A,sim)\colon A=(a_i)_{i=1}^n \text{ e } x=a_i \text{ para algum }i \}\cup \{(A,nao)\colon A=(a_i)_{i=1}^n \text{ e } x\neq a_i \text{ para todo } i\}

Outro exemplo, seja s=(a_1,\dots,a_n) uma sequência de inteiros. Uma permutação \pi dos índices de s ordena s, se a_{\pi(1)} \leq a_{\pi(2)}\leq \cdots \leq a_{\pi(n)}

Problema 4 Ordenar uma sequência de inteiros

Instância sequência finita s de inteiros

Resposta permutação \pi dos índices de s

R = \{(s,\pi)\colon \pi \textrm{ ordena }s\}

Em resumo, um problema computacional consiste na caracterização de uma coleção legal, possivelmente infinita, de entradas ou instâncias, uma especificação das saídas ou respostas desejadas e dadas em função das entradas.

— Representação das instâncias do problema —

Ao considerar os problemas computacionais, uma instância (e uma resposta) do problema é dada por uma cadeia sobre um alfabeto; formalmente uma representação ou codificação é uma função

\displaystyle \varrho \colon \mathcal{I}\rightarrow \Sigma^*

e, normalmente, o alfabeto é o alfabeto binário {\Sigma = \{0,1\}}. Por exemplo, inteiros podem ser representados em notação binária, e grafos podem ser codificados por suas matrizes de adjacência ou listas de adjacência (em binário). A rigor,  ao alfabeto pede-se apenas que seja finito e tenha pelo menos dois símbolos.

Notação: Usualmente, nestas notas, representamos uma codificação da instância I por \langle I \rangle ao  invés de \rho(I).

Definimos o tamanho de uma instância {I} como o número de elementos do alfabeto usados na codificação da instância. Em vários casos permitimos algumas simplificações, como no caso do Problema de ordenação onde o tamanho de uma instância é o número de elementos a serem ordenados; com problemas em grafos usualmente adotamos tamanho como o número de vértices mais arestas. Há justificativas para isso (que não formalizamos aqui); e mesmo que façamos escolhas concretas de codificação de entrada, tentamos manter a discussão abstrata o suficiente para ser independente da escolha da codificação. Por exemplo, no Problema 1 o tamanho de uma instância é o número de bits necessários para para representar x,~y, no Problema 2 é o numero de bits para representar n, enquanto que nos problemas 3 e 4 o tamanho da entrada é o número de elementos da sequência A e s, respectivamente.

Um problema computacional concreto é dado por uma terna que define um problema abstrato juntamente com uma codificação das instâncias e das respostas.

— Algoritmo —

Uma solução de um problema computacional (quando existe) é um algoritmo que para cada (representação da) instância I\in\mathcal I do problema computa uma (representação da) resposta O\in\mathcal O de modo que (I,O)\in R.

Uma solução para o Problema 2 acima é qualquer algoritmo que recebe um número inteiro e positivo e responde sim quando o número é primo e responde não quando o número não é primo. Aqui está uma solução para o problema. Uma solução para o Problema 4 é o Merge-Sort (a rigor, o algoritmo não computa uma permutação dos índices dos elementos da instância, mas uma permutação dos próprios elementos da instância).

Para a solução de um problema computacional supomos que esteja fixado uma descrição das ações básicas permitidas — um modelo de computação — para nós, essas ações são as que estamos acostumados como atribuições, laços, desvios condicionais. Uma solução para um problema computacional consiste de um algoritmo, que é um dispositivo de um modelo de computação, composto por instruções elementares prescrevendo ações básicas permitidas. Esse algoritmo, quando executado para qualquer entrada legal produz uma saída.

Algoritmos são descritos no que costumamos chamar de pseudocódigo, que é uma mistura  de algumas palavras-chave em português com sentenças construídas como em uma  linguagem de programação, por exemplo C, que não dá margem a dúvida sobre a ação do algoritmo. Embora pseudocódigo seja uma maneira informal de descrever um algoritmo, uma descrição em pseudocódigo é inequívoca assim como é fácil contar a partir dele o número de passos elementares que são executados por um determinado algoritmo com uma entrada. A análise de uma solução, ou a análise do algoritmo determina

  1. sua correção — dado I demonstra que o algoritmo determina O tal que (I,O)\in R e
  2. sua eficiência — uma estimativa para o consumo de recursos pelo algoritmo para resolver uma classe de instâncias. Em geral, tais estimativas são dadas em função do tamanho da instância que, formalmente, é o número de bits que usamos para representar a instância (mas na prática fazemos algumas concessões pra simplificar as contas).

Neste texto começaremos a tratar o tema eficiência, correção está tratada aqui.

Há problemas computacionais que não tem solução, o mais conhecido é o Problema da Parada.

— Modelos de computação —

Um modelo de computação é uma abstração simplificada de um computador que executa um programa. A especificação de um modelo de computação inclui uma descrição do que é um dispositivo de computação (máquina/programa) do modelo, como uma entrada é apresentada, o que é permitido para o dispositivo do modelo calcular para que a saída seja obtida a partir da entrada. Além disso, o modelo deve fornecer uma noção de passo elementar de computação da qual derivamos medidas de complexidade de tempo do dispositivo. O tempo de execução de um dispositivo do modelo, como função da instância, é o número de passos elementares necessários para concluir uma computação. Da mesma forma, o modelo deve fornecer uma abstração da noção de uso de memória ou de espaço de armazenamento.

Formalmente, consideramos algoritmos como máquinas de Turing ou  programas RAM que terminam a computação qualquer que seja a entrada tomada do  conjunto de instâncias do problema que tal máquina resolve. Máquina de Turing é um modelo de computação que, juntamente com alguns outros  modelos, como os propostos por Church, por Kleene e por Post, nasceu por volta de 1936  (portanto, antes da criação do primeiro computador eletrônico) com a finalidade de  formalizar o que intuitivamente os matemáticos chamavam de algoritmo. Esses modelos  são equivalentes no sentido de que tudo que pode ser computado num, também pode ser no outro.

Simulações entre modelos formais e o modelo genérico fornecido, por exemplo, pela linguagem C são possíveis. Um programa C que executa no máximo T(n) instruções nas  entradas de tamanho n admite uma versão no modelo RAM com complexidade de  tempo O(T(n)); um programa RAM com complexidade de tempo T(n) para as entradas  de tamanho n pode ser simulado por um programa em linguagem C que executa O(T(n)) instruções desde que todos os inteiros caibam num palavra do tipo básico para inteiros (int ou long). Sob a hipótese de não haver manipulação de  inteiros muito grandes temos equivalência entre programas RAM e pseudocódigo que preserva a complexidade assintótica. Como sempre expressamos a complexidade de tempo  de algoritmos usando notação assintótica e, nesse caso, o modelo RAM fornece os mesmos resultados de um modelo baseado em pseudocódigo, consideramos o pseudocódigo para descrever e analisar algoritmos; os modelos abstratos têm a vantagem de serem  matematicamente mais simples e bem definidos e a desvantagem de serem mais difíceis de descrever um algoritmo específico.

— Medida de eficiência —

Alguns recursos para os quais podemos querer estimar a eficiência de uma algoritmo no consumo desses ao resolver um problema são: espaço, tempo e comunicação, para citar os mais comuns. O primeiro está associado a vários parâmetros, por exemplo, a quantidade de variáveis, a quantidade e tamanho das estruturas de dados usadas pelo algoritmo; o segundo é dado em função do número de ações elementares realizadas pelo algoritmo e o terceiro em função da quantidade de unidades de informação transmitidas e recebidas. Essas medidas geralmente diferem com a instância e, consequentemente, o desempenho de um algoritmo reflete a forma como esses recursos são consumidos quando as entradas variam.

É natural esperarmos que instâncias maiores demandem mais recurso. Isso significa que devemos expressar seu desempenho em função do tamanho da representação das instâncias. Notemos que mesmo entre instâncias de mesmo tamanho a quantidade de recursos usados pode variar de modo que adotamos alguma estratégia para expressarmos o consumo de recursos pelo algoritmo para resolver o problema na classe das instâncias de mesmo tamanho: tomamos o pior caso — aquele em que o algoritmo consome mais recursos — ou o caso médio — a média de consumo numa classe; eventualmente olhamos o melhor caso — aquele em que o algoritmo consome menos recursos.

Daqui em diante nos fixamos no consumo de tempo dos algoritmos como medida de sua eficiência que expressa o número de instruções básicas executadas pelo algoritmo em função do tamanho da entrada descrita em notação assintótica. Isso nos permite algumas simplificações: podemos (quase sempre) assumir que cada linha consome tempo constante (desde que as operações não dependam do tamanho da entrada), mesmo as operações aritméticas podem (quase sempre) serem assumidas de tempo constante — isso tem de ser feito com cuidado, essa hipótese não pode ser assumida nos problemas 1 e 2 acima, onde as operações aritméticas tem custo proporcional ao tamanho dos operandos, já nos problemas 3 e 4 podemos assumir que o número de instruções básicas executadas por um algoritmo que resolve o problema é proporcional ao numero de comparações entre elementos da entrada que o algoritmo realiza.

Por exemplo, dessas hipóteses e do que estudamos aqui afirmamos que o consumo de tempo no pior caso do Merge-Sort e da Busca Binária é, respectivamente O(n\log_2 n) e O(\log_2 n).

— Melhor caso, pior caso e caso médio —

Fixado um problema computacional {(\mathcal I, \mathcal O, R)} e uma codificação \varrho, seja {A} um algoritmo que resolve tal problema. Denotemos por {T_A(I)} o tempo consumido pelo algoritmo {A} com a instância {I\in\mathcal{I}}. Denotemos por {\mathcal{I}_n} o subconjunto das instâncias de tamanho {n}.

Melhor caso para todo tamanho de instância {n}

\displaystyle t_A(n) = \min \{T_A(I) \colon I\in\mathcal{I}_n\}

Pior caso para todo tamanho de instância {n}

\displaystyle T_A(n) = \max \{T_A(I) \colon I\in\mathcal{I}_n\}

Caso Médio para todo tamanho de instância {n}

\displaystyle M_A(n) = \textrm{m\'edia}\{T_A(I)\colon I\in\mathcal{I}_n\}

A descrição acima precisa de alguma explicação. Não podemos simplesmente considerar que as entradas do mesmo tamanho tem a mesma probabilidade e a medida de complexidade média será definida com respeito à distribuição uniforme sobre todas as entradas de tamanho {n}. De modo geral podemos ver o caso médio como o tempo esperado quando um entrada é sorteada de {\mathcal{I}_n} com uma dada distribuição. Na prática consideramos dois tipos de abordagem. Na primeira o custo médio é dado por

{\displaystyle \frac{\sum_ k k|\mathcal I_{k,n}|}{|\mathcal I_n|}}

em que |\mathcal I_{k,n}| é o número de entradas de \mathcal I_n que têm custo k, assim, a probabilidade que uma instância tenha custo k é  {\displaystyle \frac{|\mathcal I_{k,n}|}{|\mathcal I_n|}}. A segunda abordagem é cumulativa, o custo médio é

{\displaystyle \frac{\sum_ {I\in\mathcal I_n} T(I) }{|\mathcal I_n|}}.

 

Exemplo: Busca linear

Consideremos o Problema 3 de uma busca linear em um vetor com {n} elementos.

Busca Linear

Busca-Linear

   Dado um vetor  A[1..n] de inteiros e um inteiro x
   Devolve SIM se x ocorre em A e devolve NÃO caso contrário
   
 1  i <- 1;
 2  enquanto ( A[i]!=x E i < n )   i <- i+1; 
 3  se ( A[i]=x ) então devolve SIM;
 4     senão devolve NÃO.

Notemos que o número de instruções executadas é proporcional ao número de comparações executadas na linha 2. Digamos que uma instrução básica tenha custo no máximo uma constante positiva c. A linha 1 tem custo c. A linha 3 tem duas instruções básicas e a linha 4 uma, no total, durante uma execução, elas contribuem com 3c para o custo do algoritmo. Agora, a linha 2 envolve um laço; o corpo do laço tem custo maximizado por 2c devido a uma soma e uma atribuição. A condição do laço envolve dois testes, portanto tem custo 2c.

No pior caso, o laço da linha 2 é executado n vezes pois caso x\not\in A a pesquisa deve visitar cada posição do vetor uma vez.Assim o custo total é, para uma entrada com n itens, no máximo 2cn+4c, portanto, a complexidade de pior caso é O(n).

Para o caso médio, assumimos que a variável i na linha 3 assume qualquer valor em \{1,2,\dots, n-1\} com probabilidade 1/(n+1) e que i=n com probabilidade 2/(n+1) (que corresponde aos casos A[n]=x e A[n]\neq x. Portanto o tempo médio é

\displaystyle \frac 1{n+1} (1+2+\cdots+ n-1) +\frac 2{n+1}n = O(n).

Exemplo: Busca Binária

No caso da Busca Binária, uma inspeçao do algoritmo nos fornece que as linhas 1,2,3,4 e 9 têm custo c , a linha 5 3c e as linhas 6, 8 e 12 custam 2c. Portanto, o custo final é 10c\ell+3c onde {\ell = \ell(n)} é a quantidade de rodadas do laço. A quantidade de elementos medidos por {d= f-i+1} a cada rodada diminui, apoś a t-ésima rodada {d_t \leq d_{t-1}/2} com d_0=n, de modo que o número de rodadas é no máximo \lceil \log_2(n) \rceil. Logo o custo para buscar um elemento é limitado superiormente, assintoticamente por O(\log_2 n).

Já havíamos argumentado que a complexidade de tempo de pior caso da Busca Binária é O(\log_2 n) baseados na estimativa para o número de comparações; de fato, o custo total é proporcional ao número de comparações. Vejamos a complexidade de tempo médio de uma busca com sucesso.

Para simplificar assumimos que n= 2^k-1 e que x é qualquer um dos n elementos com probabilidade 1/n. Assim, a probabilidade com que o elemento é achado na 1ª comparação é 1/n, na 2ª 1/(n/2), na 3ª 1/(n/4) e assim por diante. Portanto, o numero médio de comparações é

\displaystyle 1\frac 1n + 2\frac 2n + 3 \frac 4n + \cdots + k \frac {2^{k-1}}n = \frac 1n \sum_{i=1}^k i2^{i-1} = \frac{ \log_2(n)(n+1) - n}n = O(\log_2 n).

Pra resolver essa soma usamos que se f(x) = \sum_{i=1}^k x^i, então f'(x) = \sum_{i=1}^k i x^{i-1}. Como f é uma som de PG temos \displaystyle f(x) = \frac{x^{k+1}-1}{x-1}, portanto, \displaystyle f'(x) = \frac{(x-1)(k+1)x^{k} - (x^{k+1}-1)}{(x-1)^2}, portanto, f'(2) = (k+1)2^k - 2^{k+1}+1 = k2^k- 2^k +1 = k(n+1) - n.

Exercício 1 Verifique que a complexidade de tempo médio da Busca Binária é O(\log_2 n) para qualquer n.

Exemplo: Ordenação por inserção

Consideremos o Problema 4 de ordenar uma sequência de {n} inteiros.

Ordenação por Inserção

 Insertion-Sort
   Dado um vetor  A[1..n] de inteiros
   Devolve uma permutação de A com seus elementos 
em ordem não-decrescente
   
   
 1  Para i de 2 até n 
 2       x<- A[i]; j<- i-1;
 3       enquanto ( A[j] > x E j > 0 )
 4             A[j+1]<- A[j]; j <- j-1; 
 5       A[j]<- x
 6  Devolva A.

Notemos que o custo do algoritmo é determinado pelo número de comparações A[j]>x no laço da linha 3 (jusitifique esse fato cuidadosamente). Para i fixo são, no pior caso, i comparações, depois o laço é falso para a segunda condição (j=0).

No pior caso, o custo de ordanação por insercção de uma sequência com n elementos é

\displaystyle T(n) = \sum_{i=2}^n i

portanto T(n)= O(n^2).

Para o caso médio observamos que o fato determinante para o número de comparações executadas é o tipo de ordem dos elementos da sequência e não quais são os elementos em si. Por exemplo, ordenar (1,2,3,4) e (4,7,8,9) usa o mesmo número de comparações, assim como ordenar (1,8,3,9,2) e (11, 15, 14, 20, 13).

Dito isso,  assumimos que as instâncias são formadas por sequências de n inteiros distintos fixos  e que qualquer uma das n! permutações são igualmente prováveis.

Fixado i, {2 \leq i \leq n}, consideremos o subvetor A[1..i]. Definimos {\text{posto}(A[i])} como a posição do elemento A[i] no subvetor A[1..i] ordenado. Por exemplo, o posto de A[4] em [3,6,2,5,1,7,4] é 3.

Exercício 2 Verifique que {\text{posto} A[i]} é igualmente a provável ser qualquer j\in \{1,2,\dots,i\}.

Desse modo, dado i, o subvetor A[1..i-1] está ordenado com os mesmos i-1 primeiros elementos do vetor original da entrada. O teste no laço é executado {i - \text{posto}(A[i]) +1} vezes. Assim, o número médio de teste é, para i

{\displaystyle \sum_{\text{posto}=1}^i \frac{i-\text{posto}+1}{i} = \frac{i+1}2}

O número médio de comparações efetuadas pelo algoritmo de ordenação por inserção é

{\displaystyle \sum_{i=2}^n \frac{i+1}2 = O(n^2)}.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s