Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Graduação em Ciência da Computação

IF689 - Informática Teórica

Segundo Semestre de 2004

Horário de Aulas
Turma I4 (Sala ?)
  3a Feira, de 10h às 12h
  6a Feira, de 8h às 10h

Listas:
  • Gramática
  • Gram. e Aut. Pilha

    Professores: Anjolina Grisi de Oliveira e Ruy José Guerra Barretto de Queiroz.

    Planilha de Notas: aqui

    Monitoria
    Nome (e-mail)
    Horário de Atendimento
    Responsabilidade
    Carlos Eduardo A. da Cunha (ceac) 3as. 14 às 16hs Correções de listas e mini-provas
    Carlos Eduardo dos S P Silva (cesps) 4as. e 6as. Correções de listas e mini-provas
    Geraldo Fernandes da Silva Filho (gfsf) ? Correções de listas e mini-provas
    Paulo Roberto (prsof) ? Correções de listas e mini-provas
    Stelita Maria (sms) - Aulas de revisão
    Mariana Pinto Xavier (mpx) - Aulas de Revisão
    Francisco Valadares (famv) - Projetos
    Marcos Aurelio (maas) - Projetos

    Avaliação
    1a. Unidade
    2a. Unidade
    3a. Unidade
    Média Aritmética de Listas e Mini-Provas: 30% Média Aritmética de Listas e Mini-Provas: 30% Média Aritmética de Listas e Mini-Provas: 30%
    Projeto: 30% - Projeto: 30%
    Prova: 40% Prova: 70% Prova: 40%

    Média Final: Média Aritmética das médias da 1a., 2a. e 3a. unidades.

    Bibliografia Básica

  • Introdução à Teoria de Autômatos, Linguagens e Computação, John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Editora Campus, ISBN 85-352-1072-5, Outubro 2002. (Tradução para o português de Introduction to Automata Theory, Languages, and Computation, 2/E, Addison-Wesley, 2001, ISBN: 0-201-44124-1. Página de apoio: http://www-db.stanford.edu/~ullman/ialc.html)
  • Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company, 1997.

    Bibliografia Suplementar

  • Elements of the Theory of Computation (Second Edition), Harry R. Lewis and Christos Papadimitriou, Prentice-Hall, 1998, ISBN: 0-13-262478-8.
  • Automata and Computability, Dexter Kozen, Springer, 1997, ISBN: 0-387-94907-0.
  • Computational Complexity, Christos Papadimitriou, Addison Wesley, 1994, ISBN: 0-201-53082-1.
  • Computability, Algorithms and Complexity, Ian Hodkinson, Department of Computing, Imperial College London, lecture notes, 1996.
        Information.ps     ch1-2.ps     ch3.ps     ch4-5.ps     ch6-8.ps     ch9-10.ps     ch11-12.ps

    Atenção: Apontadores Interessantes:
    Entscheidungsproblem.
    Zum Hilbertschen Aufbau der reelen Zahlen, por W. Ackermann, publicado em Mathematische Annalen 99:118-133, 1928.
    Über die Erfüllbarkeit gewisser Zählausdrücke, por W. Ackermann, publicado em Mathematische Annalen 100:638-649, 1928. (generalização do Entscheidungsproblem)
    On formally undecidable propositions of Principia Mathematica and related systems I, por K. Gödel, 1931.

    Programação de Aulas

    Aula
    Data
    Assunto
    Horas Acum.
    1 15-out Motivação: Problemas de Decisão
    O Entscheidungsproblem
    Alfabetos e Linguagens
    02
    2 19-out Autômatos Finitos 04
    3 22-out Autômatos Finitos
    Operações: Produto, Seqüenciamento
    06
    4 26-out Autômatos Finitos Não-Determinísticos
    08
    5 29-out Equivalência entre Autômatos 10
    6 05-nov Expressões Regulares
    De Expressões Regulares para Autômatos Finitos
    12
    7 09-nov De Autômatos Finitos para Expressões Regulares 14
    8 12-nov Linguagens Não-Regulares
    Lema do Bombeamento
    16
    9 16-nov Linguagens Regulares: Propriedades de Fechamento 18
    10 19-nov Propriedades de Decisão para Linguagens Regulares 20
    11 23-nov Primeira Prova 22
    12 26-nov Gramáticas Livres-de-Contexto
    24
    13 30-nov Árvores sintáticas
    26
    14 07-dez Autômatos a Pilha
    28
    15 10-dez Autômatos a Pilha (cont.) 30
    16 14-dez Equivalência entre AP e LLC 32
    17 17-dez Propriedades de Fechamento de Linguagens Livres-de-Contexto
    Propriedades de Decisão de Linguagens Livres-de-Contexto
    Forma Normal de Chomsky
    34
    18 21-dez Segunda Prova 36
    19 18-jan Máquinas de Turing 38
    20 21-jan Máquinas de Turing 40
    21 25-jan Máquinas de Turing Universais
    42
    22 28-jan Indecidibilidade e o Problema da Parada 44
    23 01-fev Propriedades de Linguagens RE
    Teorema de Rice
    46
    24 04-fev Máquinas de Turing Algoritmos como Máquinas de Turing
    Linguagens Recursivas e Recursivamente Enumeráveis
    48
    25 11-fev Variantes da Máquina de Turing 50
    26 15-fev Máquinas de Turing Universais
    Indecidibilidade e o Problema da Parada
    52
    27 18-fev Propriedades de Linguagens RE 54
    28 22-02 Problema Indecidíveis sobre MT
    Teorema de Rice
    56
    29 25-02 O Problema da Correspondência de Post 58
    30 01-mar Problema Intratáveis
    Tempo-polinomial não-determinístico
    Reduções
    60
    31 04-mar Problemas NP-Completos
    O Problema SAT
    62
    32 08-mar Exemplos 62
    33 11-mar Terceira Prova 64
    34 15-mar Segunda Chamada 66
    35 18-mar Prova Final 68


    ATENÇÃO: Newsgroup
    Todas as mensagens relativas à disciplina são veiculadas no grupo de notícias depto.cursos.grad.if689.

    Última atualização: 23 de Março de 2005, 12:04hs