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 D218)
  3a Feira, de 10h às 13h
  6a Feira, de 08h às 10h

Professores

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

Regras gerais para condução da disciplina

aqui

Programa da Unidade II

aqui

Lista

aqui

Monitoria

Antonius Pyetro do Amaral Ferreira (apaf)
Fagner Nascimento e Silva (fns2)
Nicole Sultanum (nbs2)

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
    25 02-fev Máquinas de Turing
    Linguagens Turing-reconhecíveis     		50
    26 06-fev Variantes da Máquinas de Turing
    Máquinas de Turing Não-Determinísticas
    Enumeradores     		52
    27 09-fev Mini-Prova 12-13hs
    Decidibilidade
    Problemas concernentes a Linguagens Regulares     		54
    28 13-fev Problemas concernentes a Linguagens Livres-do-Contexto
    O Problema da Parada     		56
    29 16-fev Mini-Prova 12-13hs
    Indecidibilidade do Problema da Parada
    Uma linguagem Não-Turing-reconhecível
    		 58
    30 23-fev Redutibilidade 60
    31 27-fev Reduções via histórias de computação 62
    32 02-mar Mini-Prova 12-13hs
    O Problema da Correspondência de Post     		64
    33 02-mar Mini-Prova 12-13hs
    Complexidade de Tempo     		66
    34 06-mar Medindo complexidade
    Classes de complexidade de tempo     		68
    35 09-mar A Classe P 70
    21 13-mar A Classe NP (cont.)
    A Questão P versus NP (em português)
    NP-Completude     		63
    21 13-mar O Problema SAT
    Teorema de Cook-Levin     		63
    22 27-mar Terceira Prova 66
    23 30-mar Segunda Chamada 69
    24 03-abr 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: 12 de Dezembro de 2006, 11:31am GMT-3