IF689

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. É ministrada pelo professor Ruy José Guerra Barretto de Queiroz (Ciência da Computação) e pela professora Anjolina Grisi de Oliveira (Engenharia da Computação). Para ciência da computação os alunos são avaliados através de 6 Mini-Provas, 2 Projetos e de 2 Provas, o grande número de Mini-Provas ajuda o aluno a não acumular assunto para as provas e são corrigidas pelos monitores. Você pode ir para o site da disciplina aqui

Professores

Os dois professores que ministram a disciplina são Ruy Queiroz e Anjolina Grisi.

Monitoria

A monitoria é responsável pela correção das mini-provas então acesse também o site da monitoria [www.cin.ufpe.br/~mteorica aqui]

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