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

IF689 - Informática Teórica

Primeiro Semestre de 2005

Horário e local

Turmas 4C e 6E (Sala 9)
  4a Feira, de 14h às 16h
  6a Feira, de 13h às 15h

Professores

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

Regras gerais para condução da disciplina

aqui

Monitoria

Mariana Pinto Xavier (mpx)
Fernando Henrique Calheiros Lopes (fhcl)
Carlos Eduardo Albuquerque Cunha (ceac)

Listas da unidade II

l1, l2, l3

Bibliografia Básica

  • Introduction to the Theory of Computation, Michael Sipser, Second Edition, PWS Publishing Company, February 2005, ISBN 0-534-95097-3. (Tradução para o português Introdução à Teoria da Computação, por Ruy J.G.B. de Queiroz, será publicada em breve pela Editora Pioneira-Thomson Learning.)

    Bibliografia Suplementar

  • 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)

    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.
    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 20-abr Motivação: Problemas de Decisão
    O Entscheidungsproblem
    Alfabetos e Linguagens
    Autômatos Finitos
    02
      22-abr FERIADO - Tiradentes  
    2 27-abr Autômatos Finitos Determinísticos
    Linguagem de um Autômato
    04
    3 29-abr Operações regulares 06
    4 04-mai Autômatos Finitos Não-Determinísticos:
    Motivaçço; Exemplos; Árvores de Computaçço
    08
    5 06-mai Mini-Prova 12-13hs
    De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
    Fecho sob operações regulares
    10
    7 11-mai Expressões Regulares
    De Expressões Regulares para Autômatos Finitos
    14
    8 13-mai Autômatos Finitos versus Expressões Regulares
    Linguagens Não-Regulares
    Lema do Bombeamento
    16
    9 18-mai Lema do Bombeamento (cont.) 18
    10 20-mai Mini-Prova 12-13hs
    Revisão
    20
    11 25-mai Primeira Prova 22
    12 27-mai Gramáticas Livres-do-Contexto
    Árvores sintáticas
    24
    13 01-jun Forma Normal de Chomsky
    26
    14 03-jun Mini-Prova 13-14hs
    Ambigüidade em gramáticas
    Autômatos com Pilha
    28
      08-jun Semana Pedagógica  
      10-jun Semana Pedagógica  
    15 15-jun Autômatos com Pilha (cont.) 30
    16 17-jun Exercícios 32
    17 22-jun Máquinas de Turing 34
    18 29-jun Segunda Prova 36
    19 01-jul Máquinas de Turing (cont.)
    Linguagens Turing-reconhecíveis
    38
    20 06-jul Variantes da Máquinas de Turing 40
    21 08-jul Máquinas de Turing Não-Determinísticas
    Enumeradores
    42
    22 13-jul Mini-Prova 13-14hs
    Decidibilidade
    Problemas concernentes a Linguagens Regulares
    44
    23 15-jul Problemas concernentes a Linguagens Livres-do-Contexto
    O Problema da Parada
    46
    24 20-jul Exercícios 48
    25 22-jul Mini-Prova 12-13hs
    50
    26 27-jul Indecidibilidade do Problema da Parada
    Uma linguagem Turing-irreconhecível
    Redutibilidade
    52
    27 29-jul Reduções via histórias de computação
    O Problema da Correspondência de Post
    Redutibilidade por mapeamento
    54
    28 03-ago Mini-Prova 12-13hs
    Complexidade de Tempo
    Medindo complexidade
    56
    29 05-ago Classes de complexidade de tempo
    A Classe P
    58
    30 10-ago A Classe NP
    A Questão P versus NP
    60
    31 12-ago NP-Completude
    O Problema SAT
    62
    32 17-ago Teorema de Cook-Levin 64
    33 19-ago Terceira Prova 66
    34 24-ago Segunda Chamada 68
    35 26-ago Prova Final 70

    ATENÇÃO: Newsgroup

    Todas as mensagens relativas à disciplina são veiculadas no grupo de notícias depto.cursos.grad.if689.

    Última atualização: 15 de Julho de 2005, 15:38hs