Complexidade Algorítmica (para leigos)

Motivação

Imagine uma moeda que é lançada 10 vezes consecutivas, com o seguinte resultado: CaCaCaCaCaCaCaCaCaCa (isto é, 10 caras). Seria natural que alguém questionasse a justiça do processo, afirmando ser a moeda viciada. No entanto, outro ainda poderia dizer que essa é uma das 2^10 sequências possíveis e que esse não é um argumento suficiente para provar que a moeda é viciada.

Quanto a distribuição de caras e coroas, espera-se que uma moeda não viciada gere uma frequência aproximada de 50% para cada um dos resultados. Mas se repetirmos o processo e obtivermos um resultado precisamente regular – CaCoCaCoCaCoCaCoCaCo, por exemplo -, a sequência continuará causando surpresa.

Voltando à primeira sequência, o que aconteceria se alguém dissesse que a mesma moeda produzia 1/3 de caras? Ou 2/3? Ou qualquer outra distribuição? De algum modo, essa probabilidade não parece afetar a aleatoriedade aparente de uma sequência. Parece existir uma previsibilidade inerente à sequência em si.

O que torna uma sequência aleatória? Se você participar de um jogo de lançamento de moedas, logo perceberá a possibilidade de prever o resultado do próximo lançamento. Diante de uma sequência de 4 caras, você poderá supor que o próximo lançamento também será de uma cara. Ou, mais precisamente, terá alguma segurança em prever uma nova cara. Nesse caso, em nosso “modelo” não será preciso memorizar toda a sequência, mas apenas que é “Ca repetida N vezes”. E quanto à segunda sequência acima? “CaCo repetida N vezes”. E CaCoCaCaCoCaCaCaCoCaCaCaCaCo …? É como CaCo …, mas incluindo uma nova Ca a cada passo da sequência. E CoCoCoCaCoCoCaCoCoCoCoCaCaCaCaCoCaCaCaCa …?

Para algumas sequências, a forma mais simples de descrevê-las parece ser o de simplesmente memorizá-las em sua totalidade. A essas sequências chamaremos de “aleatórias.” E quanto às outras sequências? Estas possuem um tipo de conteúdo informacional algorítmico, uma capacidade inerente de ser comprimida em um conjunto mais simples de instruções. Chamaremos a essa propriedade de Complexidade Algorítmica (também conhecida como Complexidade de Kolmogorov).

Mas o que significa dizer que uma sequência é mais “curta” que outra? “Cara repetido 2 vezes” é mais longo que “CaCa”, 21 caracteres contra 4. Mas e se aumentarmos o número de caracteres? “Cara repetido 30 vezes” é, na verdade, mais curto que “CaCaCaCaCa CaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCaCa”. E se usarmos um idioma diferente? Em japonês, por exemplo, poderíamos dizer “Hは30回繰り返す”, que só tem 9 caracteres. Poderíamos comprimir uma sequência de 10 caras desse jeito. Talvez seja possível encontrar descrições ainda mais curtas. Existe uma maneira ideal de representar um algoritmo, um tipo de idioma universal, algo que nos permitisse chegar a uma medida definitiva? Sim e esse é o idioma “falado” por uma Máquina de Turing (MT).

Máquina de Turing

Uma MT é a concepção abstrata mais simples que existe para o que é/faz um computador – uma fita com células adjacentes contendo símbolos (por exemplo, números), um cabeçote para ler e escrever na fita (e que pode mover-se para a direita e para a esquerda), um registrador de estados e uma tabela de ação (que diz à máquina que símbolo escrever na fita, para onde movê-la e qual será o próximo estado). Existe uma forma simples –  uma linguagem Turing completa – de codificar um algoritmo qualquer em uma MT que faz uso de apenas 6 caracteres distintos: “>”, “<” (mover à esquerda/direita), “+”, “-“ (adicionar/subtrair 1 do número atual) e “[“, “]” (se o número atual é 0, desconsidere a expressão que aparece entre os colchotes, do contrário comece da primeira instrução).

Desde a publicação do conceito (1936), foram desenvolvidos outros tipos de modelos de computação, arquiteturas de máquina e linguagens de programação, mais sofisticadas mas que são provadamente equivalentes a uma MT. De fato, é a princípio possível representar qualquer algoritmo, concebido em qualquer linguagem de programação, por meio de uma MT.

Segundo a Wikipedia (ênfase minha):

“Toda máquina de Turing computa uma certa função computável parcial a partir da cadeia dada formada pelos símbolos do alfabeto. Neste sentido ela comporta-se como um computador com um programa fixo. No entanto, como Alan Turing descreveu, podemos codificar a tabela de ação de qualquer máquina de Turing em uma cadeia de símbolos. Portanto, podemos tentar construir uma máquina de Turing que espera em sua fita uma cadeia descrevendo a tabela de ação seguida por uma cadeia descrevendo a fita de entrada, e então computa a fita que a máquina de Turing codificada teria computado.”

Essa é uma definição de uma Máquina de Turing Universal (MTU), que proporciona uma linguagem de programação no mínimo tão expressiva quanto qualquer outra concebível.

Voltando ao problema inicial da aleatoriedade, uma sequência poderá ser representada por diferentes algoritmos em uma MTU. O comprimento do algoritmo mais curto possível e capaz de gerar essa sequência corresponde à sua complexidade algorítmica. Naturalmente, para sequências muito curtas (como “CaCa”), o conjunto de instruções iniciais poderá ser mais longo que a sequência em si.

Em suma, podemos extrair uma medida da “aleatoriedade” de uma sequência pela inspeção dos algoritmos capazes de produzi-la. Se tivermos um conjunto bem curto de instruções – mais curto que a sequência em si -, então esta não poderá ser considerada aleatória. Quanto mais curto o algoritmo, mais regular e compressível será uma sequência.

(Incidentalmente, essa também é parte da razão para a divisão entre Frequentismo x Bayesianismo na Teoria da Probabilidade. Basicamente, Frequentistas argumentam que a probabilidade de um resultado/evento depende de sua distribuição. Assim, você não poderia lançar uma moeda uma única vez e já fazer inferências/previsões sobre o processo. Seria necessário lançá-la muitas vezes e esperar que a distribuição de caras x coroas convirja para alguma razão fixa. Bayesianos, por sua vez, afirmam que a probabilidade é uma construção mental, uma medida da nossa capacidade de prever o mundo. Se ainda não sabemos nada sobre a moeda, então a escolha do algoritmo subjacente é irrelevante, do qual podemos afirmar igual probabilidade de cara e coroa. Mas, com a repetição do processo, tão logo algum padrão seja reconhecido, poderemos prever o resultado de um novo lançamento, com um certo grau de confiança. Portanto, a probabilidade de um resultado/evento depende de toda a evidência disponível e de nossa capacidade de encontrar maneiras simples (modelos) para fazer previsões sobre os novos resultados – que também serão novas evidências – que encontraremos no futuro.)

 

 

 

 

Anúncios

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