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 2003

Horário de Aulas
Turma I4 (Sala 7)
  2a Feira, de 8h às 10h
  6a Feira, de 10h às 12h
Turma I5 (Sala 5)
  3a Feira, de 16h às 18h
  5a Feira, de 14h às 16h

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

Nome, Horário e Local de Atendimento dos Monitores
Francisco de Assis Mesquita Valadares (famv): 5a.f 12h-14h
Rafael Magalhães Borges (rmb2): 4a.f 12h-14h

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)

    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, 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 17/18-nov Motivação: Problemas de Decisão
    O Entscheidungsproblem
    02
    2 20/21-nov Alfabetos e Linguagens
    Representação Finita de Linguagens
    04
    3 24/25-nov Autômatos Finitos
    Operações: Produto, Seqüenciamento
    06
    4 27/28-nov Autômatos Finitos Não-Determinísticos
    Equivalência entre Autômatos
    08
    5 1/2-dez Autômatos Finitos e Expressões Regulares 10
    6 4/5-dez Linguagens Não-Regulares
    Lema do Bombeamento
    12
    7 9-dez Minimização de Estados 14
    8 11/12-dez Propriedades de Fechamento e de Decisão para Linguagens Regulares 16
    9 15/16-dez Gramáticas Livres-de-Contexto 18
    10 18/19-dez Árvores sintáticas
    Autômatos a Pilha
    20
    11 12/13-jan Autômatos a Pilha e Gramáticas Livres-de-Contexto 22
    12 15/16-jan Propriedades de Linguagens Livres-de-Contexto
    Formas Normais (Chomsky e Greibach)
    24
    13 19/20-jan Linguagens Não-Livres-de-Contexto
    Lema do Bombeamento
    26
    14 22/23-jan Propriedades de Fechamento para Linguagens Livres-de-Contexto 28
    15 26/27-jan Propriedades de Decisão para Linguagens Livres-de-Contexto 30
    16 29/30-jan Primeira Prova 32
    17 2/3-fev Máquinas de Turing 34
    18 5/6-fev Algoritmos como Máquinas de Turing
    Linguagens Recursivas e Recursivamente Enumeráveis
    36
    19 9/10-fev Variantes da Máquina de Turing 38
    20 12/13-fev Máquinas de Turing Não-Determinísticas 40
    21 16/17-fev Máquinas de Turing Universais
    Indecidibilidade e o Problema da Parada
    42
    22 19/20-fev Propriedades de Linguagens RE
    Teorema de Rice
    44
    23 23/24-fev O Problema da Correspondência de Post 46
    24 26/27-fev Hierarquia de Chomsky
    Hierarquia Aritmética
    48
    25 26/27-fev Complexidade Computacional
    Problemas Intratáveis
    Reduções
    50
    26 1/2-mar Classes de Complexidade
    Problemas Completos para uma Classe
    O problema SAT
    52
    27 4/5-mar Complemento de Classes de Complexidade
    Propriedades de Fechamento
    54
    28 8/9-mar O Recurso "Espaço" 56
    29 11/12-mar Um Problema Completo para "Espaço-Polinomial" 58
    30 15/16-mar Classes de Complexidade baseadas em "Aleatoriedade" 60
    32 18/19-mar Teste de "Primalidade"
    Dealeatorização
    64
    34 22/23-mar Segunda Prova 68
    36 29/30-mar Prova Final 72


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

    Última atualização: 19 de Março de 2004, 08:56hs