Introdução à Teoria da Computação
Slides in this set (4)
-
- Objetivos:
- Quais as propriedades matemáticas do hardware e software de um computador?
- O que é a computação e o que é um algoritmo?
- Há alguma definição matemática para estes conceitos?
- Quais as limitações dos computadores?
- Será possível computar qualquer coisa?
- No geral, a Teoria da Computação (TC) preocupa-se em desenvolver modelos matemáticos da computação que reflitam os computadores reais.
- A Teoria da Computação divide-se em 3 áreas:
- Teoria da Complexidade
- Teoria da Computabilidade
- Teoria da Automação
-
- Pergunta:
- O que é que faz alguns problemas serem computacionalmente difíceis e outros fáceis*?
- No geral, a Teoria da Complexidade preocupa-se em classificar os problemas segundo o seu grau de complexidade (dificuldade) e em provar isso mesmo matematicamente.
- *Problema computacionalmente fácil:
- Problema que pode ser resolvido de forma eficaz computacionalmente, opondo-se aos problemas difíceis.
-
- Objetivos:
- Classificar problemas como solucionáveis ou impossíveis em termos computacionais.
-
- Pergunta:
- Havendo vários modelos para solucionar um problema computacional, qual será o modelo que resolve mais casos? Qual o modelo mais geral?
- A teoria da Automação divide-se em 3 áreas:
- Finita
- Gramáticas sem contexto
- Máquinas de Turing