Informática Teórica

De CInWiki
Ir para: navegação, pesquisa
Informática Teórica
Ciência da Computação
Professor Fred Freitas
Website http://cin.ufpe.br/~if689
Período 4º Período
Código IF689
Sala D005
Horário Ter - 10h às 12h / Qui - 08h às 10h
Engenharia da Computação
Professor Ruy
Período 6º Período
Código IF689
Sala D005
Horário Ter - 08h às 10h / Qui - 10h às 12h

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