Informática Teórica

De CInWiki
(Redirecionado de IF689)
Ir para: navegação, pesquisa

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.

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