Trabalho destinado à disciplina de Elementos da Teoria da Computação e Automação, aos cuidados do professor Dr. Leonardo Emmendorfer.
Discente: 111989 - Márcio J. Ramos Torres Data: 2016-05-09
Disponível on-line no endereço https://gist.github.com/marciojrtorres/5bf013f419e3dc4a51bcc59d8c41ff44
Desde o começo da computação teórica e da resolução de problemas em sua representação algorítmica, certas questões intrigam e interessam aos cientistas da computação em relação a resolução de problemas, quais sejam:
- quando um problema pode ser representado algoritmicamente: saber que suas entradas são aceitas pela máquina;
- quando um problema pode ser resolvido: saber se é possível computá-lo e receber uma resposta;
- qual o custo de sua solução: avaliando, sendo um problema computável, a complexidade e demanda de tempo e espaço necessário para obter uma resposta em tempo útil.
A avaliação dessas questões, na Teoria da Computação, pode ser realizada com a verificação dos problemas sendo representados e executados em um modelo de computador de propósito geral, a saber, a Máquina de Turing (MT). A MT não é o único modelo disponível para realizar experimentos de computabilidade e a expressão de algoritmos, da mesma forma que existem linguagens de programação diferentes hoje em dia que podem, embora não exatamente da mesma maneira, expressar o mesmo resultado.
Outra notação que é extremamente importante para o entendimento de algoritmos e sua definição veio do trabalho de Alonzo Church, que é conhecida como λ-cálculo. Ambas definições, de Turing e Church, são equivalentes, sendo, por exemplo, baseadas no conceito de uma memória infinita. A conexão desses dois modelos, possibilitou uma melhor definição de algoritmos e os computadores que poderiam executá-lo, sendo chamada de Tese de Church-Turing. Em síntese, um algoritmo deve consistir em um conjunto finito de instruções escrito com um conjunto finito de símbolos e produzir resultado em um número finito de passos.
As definições de MT e algoritmo, permitem verificar se, então, uma dada linguagem é reconhecida por uma MT - se ela é Turing-reconhecível - e se produz uma resposta, sendo aceita ou rejeitada - se ela é Turing-decidível. Concernente a finitude de passos para a resolução do problema, propriedade essencial de um algoritmo, por vezes o problema pode depender de demasiada quantidade de etapas, característica conhecida como Complexidade, fazendo com que nem sempre o algoritmo descrito seja viável, carecendo de uma descrição que realize a computação em menos etapas. As características de decidibilidade e complexidade serão descritas nos tópicos a seguir.
A decidibilidade explora a solubilidade de problemas através da representação algoritimica, segundo a Tese de Chuch-Turing. Saber se um dado problema é solúvel (decidível, computável) é importante para qualquer cientista da computação. Reconhecer, antecipadamente, se um problema é indecidível pode poupar esforços buscando uma simplificação do problema antes de realmente implementá-lo. Ter noções do que é não-computável também pode oferecer um vislumbre das classes de problemas que podem ser (ou não) um desafio para pesquisadores.
Um primeiro passo para verificar a decidibilidade é observar a entrada determinando se esta pode ser enumerável. É um questão desafiadora, já que as MTs lidam com o conceito de memória infinita, mas que de fato nem todo conjunto infinito poderia ser computável. Então, para medir se um conjunto infinito de entrada é enuméravel, pode ser usar a técnica de diagonalização.
A diagonalização foi descoberta pela matemático Georg Cantor, sendo usada para medir os tamanhos de conjuntos infinitos. A técnica não é muito complexa, surgindo da necessidade de comparar conjuntos infinitos sem ter de recorrer à contagem, fazendo, então, o emparelhamento dos elementos de dois conjuntos infinitos buscando demonstrar que há uma correspondência entre eles. Por exemplo, para confirmar a enumerabilidade dos conjuntos dos números naturais e seu quadrado, basta demonstrar que ambos têm o mesmo tamanho emparelhando n e sua função quadrado f(n) = n * n, como a seguir:
n | f(n)
---------
1 | 1
2 | 4
3 | 9
... ...
Com base nesse princípio, sabe-se que nem toda entrada pode ser enumerada, pois não pode ser representada por uma tabela de correspondência com outro conjunto infinito. Um exemplo bem conhecido é o conjunto de números reais. A incontabilidade de algumas linguagens evita que estas sejam usadas nas MTs, NÃO sendo consideradas Turing-reconhecíveis e, portanto, não sendo computáveis. Esse conceito é fundamental para entender o Problema da Parada no tópico a seguir.
O Problema da Parada é um exemplo de problema indecidível. A questão é relativamente simples: dada uma MT que reconheça outra MT', aceitando a entrada se MT' aceita sua entrada ou rejeitando se MT' rejeita. No Problema da Parada, essa MT entra em loop sobre a entrada, pois enquanto a aceitação demonstra que a MT realmente pára, a rejeição não pode ser verificada pois não há como saber em que tempo a sub-rotina pára. A formalização do Problema da Parada é:
Amt = {<M, w>|M é uma MT e M aceita w}
Para provar a indecidibilidade do problema definimos uma MT H que executada sobre a entrada <M, w>, onde M é uma MT e w uma cadeia, H pára e aceita se M aceita w e pára e rejeita se M rejeita w. Então, definimos outra MT D para determinar o que a MT M faz quando recebe a si mesma (M) como cadeia. D deve fazer o oposto, rejeitar se M aceita M e aceitar caso contrário. Após essas definições rodamos D tendo como entrada ela mesma D. Se independente do que D faz ela é forçada a fazer o oposto, isso denota uma contradição, levando ao entendimento que ambas MTs não podem existir.
O complemento de uma MT de uma MT não é sequer Turing-reconhecível, levando a conclusão de que uma linguagem é decidível quando ela e seu complemento são ambas Turing-reconhecíveis.
Mesmo quando os problemas são Turing-decidíveis resta saber se a sua solução pode ser encontrada em tempo hábil, em outras palavras, a quantidade de tempo necessária para resolver um problema. Essa característica é conhecida como Complexidade de Tempo.
A aferição de Complexidade é realizada através da Análise do Algoritmo, antecipando a quantidade de passos necessários para a solução de um problema particular. Entretanto, a quantidade de passos depende de fatores como o tamanho e tipo da entrada, por exemplo. Neste sentido, o mesmo algoritmo pode ser bastante rápido para uma entrada e inviável para outra. Cada instância particular do problema pode consumir um tempo diferente. Por este motivo, a análise de um algoritmo considera:
- o pior caso: em que condições, mais extremas, um algoritmo pode executar e o tempo que ele leva;
- o caso médio: entre várias execuções com condições variáveis, qual é a média de tempo;
- o melhor caso: em qual condição o algoritmo tem seu melhor desempenho.
Normalmente, os cientistas têm interesse no pior caso, em outras palavras, o que levará o tempo mais longo para computar uma resposta.
Geralmente não é possível medir com precisão o tempo de execução de algoritmo, por este motivo geralmente ele é estimado. Para fazer esta estimativa faz-se uso de uma notação especial conhecida como Análise Assintótica, aplicada, normalmente, a entradas grandes.
Entre vários passos de um algoritmo e suas instruções, algumas instruções são executadas com mais frequência. A quantidade de execuções dessas instruções frequentes, ignorando as instruções esporadicamente executadas, que determina a análise assintótica e define um limite de execução, entre os mais conhecidos o o-pequeno e O-grande.
A análise assintótica sempre leva em conta, dada uma expressão, o termo de mais alta ordem, por exemplo: 5n³ + 2n² + 4n, recebe a notação assintótica de O(n³), sendo que todo problema que pode ser resolvido em tempo O(n^k) é conhecido como algoritmo de Tempo Polinomial.
Em Teoria da Computação essas análises são realizadas com base em Máquinas de Turing Determinísticas (MTD) e Não-Determinísticas (MTND). Neste sentido, os problemas são classificados segundos a sua solubilidade em Tempo Polinomial em uma dessas máquinas. Por exemplo, todos os problemas solúveis em Tempo Polinomial por uma MTD são conhecidos como classe P, que será visto a seguir.
Os problemas classificados como P são considerados solúveis em Tempo Polinomial por uma Máquina de Turing Determinística. Os problemas nessa classes podem ser resolvidos com tempo de execução O(n^k) com um k constante.
Vários problemas clássicos e bem conhecidos estão na Classe P, por exemplo, cálculo do MDC e determinar se um número é primo.
Para alguns problemas não foram encontrados algoritmos de Tempo Polinomial (o que não quer dizer que não existam), sendo conhecidos por serem, então, problemas difíceis de resolver (mesmo, e especialmente, para um computador). A Classe NP é usada para agrupar os problemas que são solúveis em Tempo Polinomial por uma Máquina de Turing Não-Determinística (o N de NP é de Non-deterministic Polynomial), mas que são verificáveis em tempo polinomial por uma MTD, em outras palavras, testar a solução e validá-la é mais simples que descobrí-la.
Existem muitos problemas em NP, a maioria de forte interesse dos pesquisadores e utilidade para a ciência, onde é um desafio encontrar um algoritmo que os resolva em tempo polinomial.
NP-Completo é um subconjunto da classe NP de problemas contendo os exemplares considerados mais difíceis. Todos os problemas NP-Completo não tiveram soluções encontradas que sejam executadas em tempo polinomial (e que parecem distantes de serem encontradas).
Existem vários problemas NP-Completo que podem ter uma solução aproximada, através de métodos probabilísticos, restringindo a entrada e com heurísticas.
Cientistas se esforçam para provar a NP-Completude de um dado problema que geralmente é semelhante a outros muitos problemas da Classe NP. Neste sentido, sabendo-se que tal problema NP-Completo é solúvel em tempo polinomial, uma grande quantidade de problemas NP na mesma categoria também seriam.
A Máquina de Turing e a computação teórica oferecem um arcabouço essencial para a compreensão de computabilidade, muito além da implementação e tentativa exaustiva de solução de problemas. Isso se estende às noções de decidibilidade e complexidade, que são utensílios não só à teoria mas também à computação aplicada e projetos de pesquisa onde problemas complexos devem ser modelados computacionalmente e podem (devem) ser classificados quando a sua complexidade.