|
(1601RA)
Teoria da Computação - 2011 Bacharelado em Sistemas de Informação |
|
|
1. Introdução e conceitos básicos
1.1 Linguagens
1.2. Gramáticas
1.3. Autômatos
2. Autômatos finitos
2.1. Reconhecedores finitos determinísticos
2.2. Linguagens regulares
2.3. Reconhecedores finitos não-determinísticos
2.4. Equivalência de reconhecedores finitos determinístico e não-determinístico
2.5. Redução de número de estados do autômato finito
3. Linguagens e gramáticas regulares
3.1. Expressões regulares
3.2. Conexão entre expressões regulares e linguagens regulares
3.3. Gramáticas regulares
3.4. Propriedades de linguagens regulares
4. Linguagem livre de contexto (LLC)
4.1. Gramática livre de contexto (GLC)
4.2. Parsing e ambigüidade
4.3. Métodos para simplificar GLC
4.4 Formas Normais para GLC
4.4.1 Forma Normal Chomsky
4.4.2 Forma Normal Greibach
5. Autômatos a Pilha
5.1. Autômato a pilha não-determinístico
5.2. Autômato a pilha determinístico
5.3. Autômato a pilha e linguagem livre de contexto
5.4. Propriedades das LLC
6. Máquinas de Turing (MT)
6.1. Máquina de Turing como reconhecedores
6.2. Máquina de Turing como transdutores
6.3. Combinando MT em tarefas complicadas
6.4. Outros modelos de MT
7. Hierarquia das Linguagens Formais
7.1. Linguagem recursiva
7.2. Linguagem recursivamente enumerável
7.3. Gramáticas não-restritas
7.4. Gramáticas sensíveis ao contexto
8. Limites da computação algorítmica
8.1. Computabilidade
8.2. Decidibilidade
8.3. Redutibilidade
EPSTEIN,R.L. & CARNIELLI,W.A.Computability.
Wadswoth & Brooks/Cole, 1989.
GRIES,D. Construccion de Compiladores.
Paraninfo, Madri, 1975.
HOPCROFT, J.E. Introdução à Teoria dos autômatos,
Linguagens e Computação. Campus, 2003. (na biblioteca: 005.1
H76i)
JONES,N.D.
Computability Theory: An Introduction. Academic Press, 1973.
MENEZES, P.B. Linguagens Formais e Autômatos.
Ed Sagra Luzzato, 2000.(na biblioteca: 005.131 M512l 3.ed.)
SIPSER,
M. Introduction to the Theory of Computation, PWS Pub, 2005
Considerando-se
que:
MP = Média das N Provas
regimentais, para N=1 a nota será dividida por 3
MT = Média aritmética dos
Trabalhos de implementação computacional
ME = Média aritmética dos
Exercícios entregues em sala de aula
MF = Média Final
MF = 0,90*MP +
0,06*MT + 0,04*ME se MP < 5.0
MF = 0,70*MP + 0,20*MT + 0,10*ME se
MP >= 5.0
Provas:
- As provas serão realizadas nos dias e horários
marcados.
- Nas provas serão distribuídas notas de 0 a 10
pontos.
- A P4 não é substitutiva.
- Se o aluno fizer as três provas, a P4
compreenderá a matéria de todo semestre e será feita a média aritmética
entre as 04 provas.
- Se deixar de fazer uma das provas (P1 ou P2 ou
P3) a P4 compreenderá a matéria da prova não feita.
- Se o aluno fizer apenas uma prova no semestre,
MP é a nota da prova dividida por 3.
Trabalhos computacionais
- Os problemas serão definidos na medida em que a
disciplina for sendo desenvolvida
- O trabalho entregue deve conter os programas
fontes.
- A entrega do trabalho deverá ser feita de duas
maneiras: (1) via e-mail com os arquivos zipados, (2) impresso em folha
A4. Em ambos os casos entregar com o(s) nome(s) e o(s) respectivo(s)
RA(s).
- A cada dia de atraso na entrega serão
descontados 5% do valor do trabalho. Sábado, Domingo e Feriado serão considerados
como dias de atraso.
Exercícios em sala de aula
- Deverá ser entregue no final de cada aula ou
quando for definido pelo professor
- Se não for entregue dentro do prazo, o exercício
será descartado.
1a. Prova: A DEFINIR
2a. Prova: A DEFINIR
3a. Prova: A DEFINIR
4a. Prova: A DEFINIR
Apostila 01 – Fundamentos (Lista de exercícios)
Apostila 02 – Linguagens Regulares (Lista de exercícios)
Apostila 03 – Linguagens Livres de Contexto (Lista de exercícios)
Apostila 04 – Máquinas de Turing (Lista de exercícios)
Apostila 05 – Linguagens do tipo 0 e 1 (Recursivamente Enumerável, Recursiva, Sensível ao Contexto)
Apostila 06 – Teoria da Computação
Esta página não é uma publicação oficial da UNESP, e seu conteúdo não foi
examinado e/ou editado por esta instituição. A responsabilidade por seu
conteúdo é exclusivamente do autor.
Simone das Graças Domingues Prado (e-mail)
Última atualização em 10 de agosto de 2010