Teoria da Computação

Teoria da Computação

1. automatos

   • capacidade de operar sem interferencia humana ou ate mesmo simulando uma mente ou açoes humanas de forma "independente"
     • deterministicos
     • nao deterministicos
     • Com pilha
     • linguagens
     • expressoes regulares

2. complexidade

   • Busca criar algoritmos mais complexos para criar sistemas dinamicos e mais imprevisiveis, que nao seguem por caminhos lineares de execução buscando assim sistemas que precisem de menos interferencia humana "aumentando" a IA
     • otimização e busca NP: dificil
     • NP-completo
     • Classe NP
     • Anàlise assintotica
     • Classe P

3. computabilidade

   • determina o que é possivel utilizando as tecnologias existentes atualmente
     • define o que é possivel e o que nao é possivel de ser calculado de acordo com o grau de complexidade do algoritmo e da tecnologia
       • turing
       • tese de Church Turing
       • maquina de turing universal
       • problema da parada e redutbilidade