|
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
|
| UNIDADE: INSTITUTO DE MATEMÁTICA E ESTATÍSTICA | ||
| DEPARTAMENTO: DEPTO. DE INFORMATICA E CIENCIAS DA COMPUTACAO | ||
| DISCIPLINA: Teoria da Computação | ||
| CARGA HORÁRIA: 60 | CRÉDITOS: 4 | CÓDIGO: IME04-10826 |
| MODALIDADE DE ENSINO: Presencial | TIPO DE APROVAÇÃO: Nota e Frequência | |
| STATUS | CURSO(S) / HABILITAÇÃO(ÕES) / ÊNFASE(S) |
| Obrigatória | IME - Ciência da Computação (versão 1) IME - Informática e Tecn. Informação (versão 3) |
| TIPO DE AULA | CRÉDITO | CH SEMANAL | CH TOTAL |
| Teórica | 4 | 4 | 60 |
| TOTAL | 4 | 4 | 60 |
OBJETIVO(S):
Permitir que o aluno adquira noções dos fundamentos da computação, através de seus modelos abstratos, explorando suas capacidades e limitações. O tratamento é matemático, mas o ponto de vista é o da ciência da computação. Os temas abordados são a teoria dos autômatos e linguagens formais, computabilidade por máquina de Turing e funções recursivas, não-computabilidade, complexidade computacional. Esses fundamentos ajudam o aluno a adquirir habilidade de raciocínio e comunicação mais precisa e serão úteis nas disciplinas mais avançadas da Ciência da Computação.
EMENTA:
Linguagens formais. Gramáticas. Linguagens Regulares e Autômatos finitos. Linguagens livres de contexto e Autômatos de pilha. Lema de bombeamento. Linguagens tipo O (sem restrição) e Máquinas de Turing. Linguagens sensíveis ao contexto e autômatos linearmente limitados. Teoria da computabilidade: Máquina de Turing, computabilidade efetiva, funções recursivas, tese de Church, teoria da incompleteza de Gödel, problemas indecidíveis.
| DISCIPLINA(S) CORRESPONDENTE(S): IME04-05721 Compiladores I |
BIBLIOGRAFIA: -John E. Hopcroft. Rajeev Motwani. Jeffrey D. Ullman, "Introdução à Teoria de Autômatos, Linguagens e Computação", Editora Campus. 2002.
-H.R. Lewis; C.H. Papadimitriou. "Elementos de Teoria da Computação", Editora Bookman, 2ª edição.