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

Segundo Semestre de 2005

Horário e local

Turmas 4C e 6E (Sala 9)
  3a Feira, de 10h às 13h
  6a Feira, de 07h às 10h

Professores

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

Regras gerais para condução da disciplina

aqui

Monitoria

Antonius Pyetro do Amaral Ferreira (apaf)
Carlos Eduardo Albuquerque Cunha (ceac)
Daniel de Andrade Penaforte (dap4)
Fernando Henrique Calheiros Lopes (fhcl)
Tiago Buarque Assunção de Carvalho (tbac)

Planilha com as notas

aqui

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-set Motivação: Problemas de Decisão
    O Entscheidungsproblem
    Alfabetos e Linguagens
    Autômatos Finitos     		03
    2 23-set Autômatos Finitos Determinísticos
    Linguagem de um Autômato
    Operações regulares     		06
    3 27-set Autômatos Finitos Não-Determinísticos:
    Motivação; Exemplos; Árvores de Computação
    De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
    Fecho sob operações regulares     		09
    4 30-set Mini-Prova 12-13hs
    Expressões Regulares
    De Expressões Regulares para Autômatos Finitos
    Autômatos Finitos versus Expressões Regulares
    		 12
    5 04-out Linguagens Não-Regulares
    Lema do Bombeamento     		15
    6 07-out Primeira Prova 18
    7 11-out Gramáticas Livres-do-Contexto
    Forma Normal de Chomsky
    Árvores sintáticas     		21
    8 14-out Mini-Prova 12-13hs
    Ambigüidade em gramáticas
    Autômatos com Pilha     		24
    9 18-out Autômatos com Pilha versus Gramáticas Livres-do-Contexto 27
    10 21-out Segunda Prova 30
    11 25-out Máquinas de Turing
    Linguagens Turing-reconhecíveis     		33
      28-out FERIADO - Dia do Funcionário Público  
    12 01-nov Variantes da Máquinas de Turing
    Máquinas de Turing Não-Determinísticas
    Enumeradores     		36
    13 04-nov Mini-Prova 12-13hs
    Decidibilidade
    Problemas concernentes a Linguagens Regulares     		39
    14 08-nov Problemas concernentes a Linguagens Livres-do-Contexto
    O Problema da Parada     		42
    15 11-nov Mini-Prova 12-13hs
    Indecidibilidade do Problema da Parada
    Uma linguagem Não-Turing-reconhecível
    		 45
    16 18-nov Redutibilidade 48
    17 22-nov Reduções via histórias de computação 51
    18 25-nov Mini-Prova 12-13hs
    O Problema da Correspondência de Post
    Complexidade de Tempo
    		 54
    19 29-nov Medindo complexidade
    Classes de complexidade de tempo     		57
    20 02-dez A Classe P
    A Classe NP     		60
    21 06-dez A Classe NP (cont.)
    A Questão P versus NP (em português)
    NP-Completude
    O Problema SAT
    Teorema de Cook-Levin     		63
    22 09-dez Terceira Prova 66
    23 13-dez Segunda Chamada 69
    24 16-dez 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: 2 de Dezembro de 2005, 10:38hs