Introdução à Teoria da Computação

Hierarquia de Chomsky

Tipos de Linguagens

Linguagens Regulares: Máquina de estados finitos.

Linguagens Livres de Contexto:

Linguagens Dependentes de Contexto:

Linguagens Irrestritas: Linguagem natural (português, inglês, mandarim) é um exemplo.

Máquina de Turing

A Máquina de Turing é uma quíntupla.

Linguagens Recursivas e Recursivamente Enumeráveis

Se uma linguagem é recursiva, então também é recursivamente enumerável.

Hipótese de Church

Pergunta: Por que ela é chamada de Hipótese de Church ao invés de Teorema de Church?

Resposta: A Hipótese de Church não é um resultado matemático e, portanto, não pode ser provado.

Problemas de Decisão

Problema Solucionável

Um problema é dito solucionável ou totalmente solucionável se existe um algoritmo que solucione o problema, sempre para qualquer entrada, com uma resposta afirmativa (aceita) ou negativa (rejeita).

Problema Não Solucionável

Um problema é dito não solucionável se não existe um algoritmo que solucione o problema, tal que sempre pare, qualquer que seja a entrada.

Problema Parcialmente Solucionável ou Computável

Um problema é dito parcialmente solucionável ou computável se existe um algoritmo que solucione o problema, tal que pare quando a resposta é afirmativa (aceita). Entretanto, quando a resposta esperada for negativa, o algoritmo pode parar (rejeita) ou permanecer processando indefinidamente.

Problema Completamente Insolúvel

Um problema é dito completamente insolúvel ou não computável se não existe um algoritmo que solucione o problema, tal que pare quando a resposta é afirmativa.

Observações:

• Alguns problemas não solucionáveis são parcialmente solucionáveis.
• Existem problemas não solucionáveis que possuem solução parcial.
• A classe dos problemas solucionáveis é equivalente à classe das linguagens recursivas.
• A classe dos problemas parcialmente solucionáveis é equivalente à classe das linguagens recursivamente enumeráveis.

Linguagem Recursiva e Turing-Enumerável

Uma linguagem é recursiva se e somente se for Turing-enumerável lexicograficamente.

Ciclo Hamiltoniano

Problema: Dado um grafo G, existe um ciclo que passe por todos os nós de G exatamente uma vez?

O único algoritmo conhecido para este problema consiste em examinar todas as permutações possíveis dos nós e para cada permutação, verificar se trata de um ciclo Hamiltoniano. Trata-se, portanto, de um problema O(n!).

Classes de Complexidade

Definição da Classe P

P é a coleção de todos os conjuntos reconhecíveis por Máquinas de Turing em tempo polinomial.

Definição da Classe NP

NP é a coleção de todos os conjuntos reconhecíveis por máquinas de Turing não determinísticas em tempo polinomial.

Completude NP – Problemas NP-Difíceis

Completude NP – Problemas NP-Difíceis – O Teorema de Gödel