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 2008

Horário e local

4a 14-16, 6a 14-16, Sala D-218

Professores

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

Regras gerais para condução da disciplina

aqui

ATENÇÃO: Newsgroup

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

Monitoria

Antonius Pyetro do Amaral Ferreira (apaf)
Jesus Sanchez-Palencia Fernandez Filho (jspff)
João Victor Guimarães de Lemos (jvgl)
Rodrigo Diego Melo Amorim (rdma)
Tiago de Farias Silva (tfs)

Bibliografia Básica

  • Introdução à Teoria da Computação, Michael Sipser, Thomson Pioneira, ISBN 8522104999, 2007. (Tradução brasileira de Introduction to the Theory of Computation, Michael Sipser, Second Edition, PWS Publishing Company, February 2005, ISBN 0-534-95097-3.)

    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.

    LISTA DA UNIDADE 2

    aqui

    Programação de Aulas

    27-Fev
    Motivação: Problemas de Decisão
    O Entscheidungsproblem
    Exibição do trailer do filme Julia Robinson and Hilbert's Tenth Problem
    Alfabetos e Linguagens

    29-Fev
    Autômatos Finitos

    05-Mar
    Autômatos Finitos Determinísticos
    Linguagem de um Autômato
    Linguagens regulares

    07-Mar
    Operações com linguagens regulares
    Fecho sob operações regulares (união)
    Autômatos Finitos Não-Determinísticos

    12-Mar
    (Mini-Prova)
    De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
    Fecho sob operações regulares (concatenação, estrela)
    Expressões Regulares
    De Expressões Regulares para Autômatos Finitos
    De Autômatos Finitos para Expressões Regulares

    19-Mar
    (Mini-Prova)
    Linguagens Não-Regulares
    Lema do Bombeamento

    26-Mar
    Primeira Prova

    28-Mar
    Gramáticas Livres-do-Contexto
    Forma Normal de Chomsky
    Árvores sintáticas

    02-Abr
    Ambigüidade em gramáticas
    Autômatos com Pilha

    04-Abr
    Autômatos com Pilha versus Gramáticas Livres-do-Contexto

    09-Abr
    Segunda Prova

    11-Abr
    Máquinas de Turing
    Linguagens Turing-reconhecíveis

    16-Abr
    Variantes da Máquinas de Turing: Várias fitas

    18-Abr
    Máquinas de Turing Não-Determinísticas

    23-Abr
    (Mini-Prova)
    Enumeradores

    25-Abr
    Decidibilidade
    Problemas concernentes a Linguagens Regulares

    30-Abr
    Problemas concernentes a Linguagens Livres-do-Contexto

    02-Mai
    O Problema da Parada

    07-Mai
    Indecidibilidade do Problema da Parada
    Uma linguagem Não-Turing-reconhecível

    09-Mai
    (Mini-Prova)
    Redutibilidade
    Reduções via histórias de computação

    14-Mai
    O Problema da Correspondência de Post
    Redutibilidade por mapeamento

    16-Mai
    Complexidade de Tempo

    21-Mai
    Medindo complexidade
    Classes de complexidade de tempo

    23-Mai
    (Mini-Prova)
    A Classe P

    28-Mai
    A Classe NP
    A Questão P versus NP (em português)

    30-Mai
    Redutibilidade em Tempo Polinomial
    NP-Completude

    04-Jun
    O Problema SAT

    06-Jun
    Teorema de Cook-Levin

    11-Jun
    (Mini-Prova)
    Complexidade de Espaço

    13-Jun
    Teorema de Savitch

    18-Jun
    A Classe PSPACE

    20-Jun
    Terceira Prova

    25-Jun
    Segunda Chamada

    27-Jun
    Prova Final


    Última atualização: 17 de Março de 2008, 09:19am GMT-3