Informática Teórica
De CInWiki
(Redirecionado de IF689)
Erro em Lua: Não é possível criar o processo: proc_open(/dev/null): failed to open stream: Operation not permitted
A disciplina de Informática Teórica aborda os conceitos da teoria da computação, e busca determinar quais problemas podem ser computados em um dado modelo de computação. Estuda os problemas computacionais e as classes das linguagens que podem ser produzidas e reconhecidas por modelos computacionais simbólicos. Também estuda a complexidade dos algoritmos.
Índice
Avaliação
Para ciência da computação os alunos são avaliados normalmente através de 4 mini-provas e 3 provas, as mini-provas são elaboradas e corrigidas pelos monitores.
Tópicos Abordados
1ª unidade:
- Linguagens Regulares
- Automatos Finitos Determinísticos
- Automatos Finitos não Determinísticos
- Expressões Regulares
- Linguagens não Regulares
- Linguagens Livres do Contexto
- Gramáticas
- Autômatos com Pilha
- Linguagens não Livres do Contexto
2ª Unidade:
- Máquinas de Turing
- Variantes da Máquina de Turing
- Definição de Algoritmos
- Décimo Problema de Hilbert
- Decidibilidade
- Problema da Parada
- Redutibilidade
- Teoria da Complexidade
- Classes P, NP, NP-Completos
- O Problema SAT
- A Classe PSPACE
