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

IF689 - Informática Teórica (2a. Parte)

Primeiro Semestre de 2003

Horário de Aulas
Turma I5 (Sala 9)
  3a Feira, de 10h às 12h
  5a Feira, de 8h às 10h

Professor: Ruy José Guerra Barretto de Queiroz.

Nome, Horário e Local de Atendimento dos Monitores
(a confirmar)

Segunda Prova (em PDF)

Bibliografia Básica

  • Elements of the Theory of Computation (Second Edition), Harry R. Lewis and Christos Papadimitriou, Prentice-Hall, 1998, ISBN: 0-13-262478-8.

    Bibliografia Suplementar

  • 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, I. Hodkinson, Department of Computing, Imperial College London, lecture notes, 1996.

    Video a ser exibido (caso haja tempo)

  • The Machine that Changed the World, uma série produzida por WGBH Television em Boston (MA, EUA) em cooperação com a BBC (Inglaterra), com o apoio de ACM, NSF e UNISYS.

    Atenção:
    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.
    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 ?-??? Motivação: Problemas de Decisão
    O Entscheidungsproblem
    02
    2 ?-??? Alfabetos e Linguagens
    Representação Finita de Linguagens
    04
    3 ?-??? Autômatos Finitos
    Operações: Produto, Seqüenciamento
    06
    4 ?-??? Autômatos Finitos Não-Determinísticos
    Equivalência entre Autômatos
    08
    5 ?-??? Autômatos Finitos e Expressões Regulares 10
    6 15-jul Linguagens Não-Regulares
    Lema do Bombeamento
    12
    7 ?-??? Minimização de Estados 14
    8 22-jul Algoritmos e Autômatos Finitos 16
    9 24-jul Gramáticas Livres-de-Contexto 18
    10 29-jul Árvores sintáticas
    Autômatos a Pilha
    20
    10 29-jul Forma Normal de Chomksy 22
    10 29-jul Forma Normal de Greibach 24
    11 31-jul Linguagens Não-Livres-de-Contexto
    Lema do Bombeamento
    22
    12 5-ago Máquinas de Turing 24
    13 7-ago Algoritmos como Máquinas de Turing
    Linguagens Recursivas e Recursivamente Enumeráveis
    26
    14 12-ago Variantes da Máquinas de Turing
    Máquinas de Turing Não-Determinísticas
    28
    15 14-ago Máquinas de Turing Universais 30
    16 19-ago Indecidibilidade e Problema da Parada
    Hierarquia de Chomsky
    Hierarquia Aritmética
    32
    17 21-ago Segunda Prova 34
    18 26-ago Prova Final 36


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

    Última atualização: 26 de Agosto de 2003, 09:49hs