IF114 - Linguagens e Máquinas

• O usenet newsgroup  depto.cursos.grad.if114 foi criado para discussões técnicas, anúncios e questões relacionadas com a disciplina.

Professor:   Marco Luis Ferramola

Breve descrição

O curso provê uma introdução a teoria da computação. O tratamento é matemático, mas o ponto de vista é informático. Vamos nos restringir ao estudo dos autômatos e gramáticas formais, mas mesmo assim o espectro de aplicações é imenso. Serão mencionadas aplicações em geração de imagens fractais, computaço DNA, linguagens naturais, compiladores, sistemas operacionais,  computação neural,  computação analógica, sistemas dinâmicos simbólicos, etc.

Pré-requisitos

   Lógica Aplicada à Computação, IF312

Ementa

   1. autômatos finitos
   2. expressões regulares
   3. gramáticas regulares
   4. equivalência entre os modelos
   5. propriedades de linguagens regulares
   6. autômatos a pilha determinísticos e não-determinísticos
   7. gramáticas livres-de-contexto, propriedades de LLC
   8. ambigüidade
   9. autômatos `linear-bounded'
  10. linguagens sensíveis-ao-contexto
  11. a hierarquia de Chomsky.

Referências Bibliográficas

Principal

• Kozen, D.: Automata and Computability, Springer-Verlag, New York, 1997 (Corr. 3rd printing 1999). ISBN 0-387-94907-0.

Auxiliares

• Hopcroft, J., & Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979, ISBN 0-201-02988-X. (A segunda edição, completamente reescrita, e com um terceiro autor, será publicada em Novembro de 2001:
  Hopcroft, J., Motwani, R. & Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Longman, 2001, ISBN 0-201-44124-1.)
• Acióly, B. M. & Bedregal, B.R.C.: Notas de Aula de Teoria da Computação, Departamento de Informática e Matemática Aplicada - UFRN. (Disponível também no formato booklet para impressora dual: notas-booklet.ps)

Material mencionado na aula de 15/09/2000

• Notas de aula de D. Kozen: aqui
• Lista de exercícios de J. Ullman: aqui (FAQ)

  Material Didático

  1. Referência 2 acima;
  2. Slides em PowerPoint.
  1. Aulas 02 a 06.
  2. Aulas 07 e 08.
  3. Aulas 09 e 10.
  4. Aula 11.
  5. Aula 12.
  6. Aula 13.
  7. Aula 14.
  8. Aulas 18-19
  9. Aulas 19-20
  10. Aulas 21-n
  11. Aula do dia 02/12/99
  12. Aula do dia 05/12/99
  13. Aula do dia 09/12/99
  Cronograma
   

  Unidades Programáticas

  Aula	Data	Horário	Conteúdo
  01	17/12/2001	SEG14-16h	Apresentação do Curso
  02	07/01/2002	SEG 13:30-16:00h	Conceitos Básicos
  03	09/01/2002	QUAR 12:30-14:00h	Introd. aos Autômatos Finitos (AF)
  04	14/01/2002	SEG 13:30-16:00h	Propriedades das Linguagens Regulares
  05	16/01/2002	QUAR 12:30-14:00h	AF não-determinísticos (AFND)
  06	21/01/2002	SEG 13:30-16:00h	Equivalência entre  AF determinísticos e AFND
  07	23/01/2002	QUAR 12:30-14:00h	Epsilon movimentos
  08	28/01/2002	SEG 13:30-16:00h	Mais propriedades das Linguagens Regulares
  09	30/01/2002	QUAR 12:30-14:00h	Expressões Regulares
  10	04/02/2002	SEG 13:30-16:00h	Exercícios
  11	06/02/2002	QUAR 12:30-14:00h	Gramáticas
  	11/02/2002	SEG 13:30-16:00h	CARNAVAL
  	13/02/2002	QUAR 12:30-14:00h	CARNAVAL
  12	18/02/2002	SEG 13:30-16:00h	Gramáticas Regulares
  13	20/02/2002	QUAR 12:30-14:00h	Aplicações de Linguagens Regulares
  14	25/02/2002	SEG 13:30-16:00h	Minimização de AFs
  15	27/02/2002	QUAR 12:30-14:00h	Gramáticas Livres de Contexto (GLC)
  16	04/03/2002	SEG 13:30-16:00h	Exemplos e Propriedades das GLC
  17	06/03/2002	QUAR 12:30-14:00h	Aplicações de GLC
  18	11/03/2002	SEG 13:30-16:00h	1o EXERCÍCIO ESCOLAR
  19	13/03/2002	QUAR 12:30-14:00h	Resolução do 1o Exercício e Revisão
  20	18/03/2002	SEG 13:30-16:00h	Autômatos a Pilha (PDAs)
  21	20/03/2002	QUAR 12:30-14:00h	Propriedades dos PDAs
  22	25/03/2002	SEG 13:30-16:00h	PDAs não-Determinísticos
  23	27/03/2002	QUAR 12:30-14:00h	Aplicações
  24	01/04/2002	SEG 13:30-16:00h	Autômatos Lineares Limitados
  25	03/04/2002	QUAR 12:30-14:00h	Linguagens Sensíveis ao Contexto
  26	08/04/2002	SEG 13:30-16:00h	Máquinas de Turing
  27	10/04/2002	QUAR 12:30-14:00h	Hierarquia de Chomsky
  28	15/04/2002	SEG 13:30-16:00h	Apresentação de Trabalhos
  29	17/04/2002	QUAR 12:30-14:00h	Apresentação de Trabalhos
  30	22/04/2002	SEG 13:30-16:00h	2o EXERCÍCIO ESCOLAR
  	24/04/2002	QUAR 12:30-14:00h
  31	29/04/2002	SEG 13:30-16:00h	PROVA FINAL

Avaliação: Para efeito de cálculo da média serão levados em conta o 1^o.EE  e o  2^o.EE (eventualmente também uma  Monografia). Os temas sugeridos para as monografias estão aqui. Sugestões de temas fora da lista  são bem-vindas mas a aprovação dependerá de análise.
 
 
  Última atualização: 21 de Janeiro de 2002, 18:15:40 GMT-0300.
if114@cin.ufpe.br