Teoria da computação

Teoria da computação

1. Computabilidade

   • É o fato de solucionar problemas matemáticos através de meios finitos.
   • Seu objetivo é determinar solucionabilidade de problemas.
   • Se tornando assim muito importante no âmbito computacional, pois indicam problemas que não podem ser solucionados.

2. Classificação dos problemas

   • Solucionabilidade
     • Objetiva evitar a pesquisa de soluções inexistentes de problemas.
   • Tipos de problemas
     • Problemas Solucionáveis: Um problema é dito Solucionável se existe um algoritmo (Máquina Universal) que solucione o problema tal que sempre pára para qualquer entrada, com uma resposta afirmativa (ACEITA) ou negativa (REJEITA).
     • Problemas Parcialmente Solucionáveis: Um problema é dito Parcialmente Solucionável ou Computável se existe um algoritmo (Máquina Universal) 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 (LOOP).
     • Problemas não solucionáveis: Um problema é dito não solucionável se não existe um algoritmo (Máquina Universal) que solucione o problema tal que sempre pára para qualquer entrada.

3. Problemas de decisão

   • Foi proposto por, David Hilbert em 1928 e consiste na existência de um procedimento mecânico capaz de decidir se dado um enunciado (proposição) da lógica de primeira ordem seria válido ou não, em um tempo finito.
   • Problema de Decisão começou apresentar resultados em 1936. a partir de pesquisas de Alonzo Church e Alan Turing . Além disso Turing transformou o Problema de Decisão em Problema da Parada em sua máquina
   • Surgiu então a Técnica da Redução , que transforma partes de um problema em outro usando resultados já conhecidos para obter resolução de partes do problema atual e, assim, resolvê-lo
   • A solução definitiva do Problema de Decisão veio em 1970, quando o matemático Yuri Matiyasevich provou que tal procedimento efetivo (algoritmo) não existe, pois se R é relação que pode ser codificada em um número natural, então R é equação diofantina se e somente se R é enumerável isso resulta em conjunto das equações diofatinas com raízes inteiras não é solucionável (decidível)

4. Relação dos problemas e as linguagens formais

   • Um problema de decisão pode ser visto como uma linguagem formal, onde os membros da linguagem são instâncias cuja resposta é sim, e os não membros da linguagem são aquelas instâncias cuja saída é não. O objetivo é decidir, com a ajuda de um algoritmo, se uma dada sequência de entrada é um membro da linguagem formal em consideração. Se o algoritmo decidir este problema, ele retorna a resposta sim, diz-se que o algoritmo aceita a sequência de entrada, caso contrário, diz-se que rejeita a entrada.
     • Um exemplo de um problema de decisão é o seguinte. A entrada é um grafo arbitrário. O problema consiste em decidir se o dado grafo é conexo ou não. A linguagem formal associada a este problema de decisão é então o conjunto de todos os grafos conexos—obviamente, para obter uma definição precisa dessa linguagem, é preciso decidir como grafos são codificados como cadeias binárias.

5. Classificação por complexidade e por espaço

   • Tempo
     • Tempo de execução do algoritmo determinado pelas instruções executadas :quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n;
     • O tempo de execução de um algoritmo para uma determinada entrada pode ser medido pelo número de operações primitivas que ele executa.
   • Espaço
     • Espaço de memória utilizado pelo algoritmo : quanto “espaço de memória/disco” é preciso para armazenar a(s) estrutura(s) utilizada(s) pelo algoritmo.
   • A análise de algoritmo fornece uma medida objetiva de desempenho proporcional ao tempo de execução do algoritmo.