Teoria da Computação

Teoria da Computação

1. Computabilidade

   • O que é ?
     • É a habilidade de resolver problemas de forma efetiva.
   • Função
     • Seu objetivo é determinar a solucionabilidade de problemas
   • Importância na Ciência da Computação
     • Sua importância para a computação é determinar o que pode ou não pode ser computado, ou seja, o que pode ou não ser implementado em um computador.

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 que solucione o problema tal que sempre pare para qualquer entrada, com uma reposta afirmativa ou negativa.
     • Problemas Não-Solucionáveis
       • Um problema é dito não-solucionável se não existe um algoritmo que solucione o problema tal que sempre pare, para qualquer entrada.
     • Problemas Parcialmente Solucionáveis
       • Um problema é dito parcialmente solucionável se existe um algoritmo que solucione o problema tal que pare quando a resposta é afirmativa. Entretanto, quando a resposta esperada for negativa, o algoritmo pode parar ou permanecer processando indefinitivamente.

3. Problemas de decisão

   • O problema de verificar se uma determinada cadeia de caracteres pertence ou não a um conjunto de cadeias de caracteres, também chamado de linguagem formal.

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 instâncias cuja resposta é sim, e os não membros da linguagem são aquelas instância cuja saída é não.

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

   • A análise de algoritmo fornece uma medida objetiva de desempenho proporcional ao tempo de execução do algoritmo.
   • Tempo
     • 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.
     • 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'.
   • Espaço
     • Espaço de memória utilizado pelo algoritmo: Quanto é preciso para armazenar as estruturas utilizadas pelo algoritmo.