|
|
Bacharelado em Ciência da
Computação
2005/1
|
|
| Ementa | Noções de
computabilidade efetiva. Modelos de computação. Problemas
indecidíveis. Classes e relações de
complexidade. |
| Referências | Notas de aula LEWIS, H. R. Elementos de Teoria da Computação. S. Paulo, Bookman, 1998. SIPSER, M. Introduction to Theory of Computation. Boston, Thomson, 2003. |
| Plano 2005/1 Horários das aulas A disciplina TGS será ministrada sempre às terças, entre os dias 28 de fevereiro e 05 de julho de 2005, das 10:10 às 11:50 horas Obs.: O plano de ensino está sujeito a mudanças, sempre que isso se fizer necessário. |
Março 01 - Apresentação do plano 2005/1; Introdução à TC. Conjuntos, relações e funções. Relações binárias e grafos. 08 - Conjuntos finitos e infinitos. Técnicas de prova. 15 - Fechamento, algorítmo. Alfabetos e linguagens. Representações finitas de linguagens. 22 - Modelos de computação. Autômatos finitos determinísticos. 29 - Autômatos finitos não determinísticos.
Abril 05 - Teste 12 - Autômatos finitos e expressões regulares. 19 - Linguagens regulares e irregulares. Minimização de estados. 26 - Teste.
Maio 03 - Algorítmos para autômatos finitos. Autômatos finitos como algorítmos. 10 - Linguagens livres de contexto. 17 - Máquina de Turing. 24 - Computando com Máquina de Turing. Extensões da Máquina de Turing. 31 - Indecidibilidade. Tese de Church-Turing. Máquinas de Turing Universais.
Junho 07 - O problema da parada. Problemas indecidíveis sobre a máquina de Turing.
14 - Problemas insolúveis de Gramática. Um problema
insolúvel de organização lado a lado. 21 - Complexidade computacional. Classes e relações de complexidade. 28 - Teste Final. |
