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 2007

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

Monitoria

Antonius Pyetro do Amaral Ferreira (apaf)
João Victor Guimarães de Lemos (jvgl)
Rodrigo Diego Melo Amorim (rdma)

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.

    Programação de Aulas

    25-Mai
    Motivação: Problemas de Decisão
    O Entscheidungsproblem
    Alfabetos e Linguagens

    30-Abr
    Autômatos Finitos

    02-Mai
    Autômatos Finitos Determinísticos
    Linguagem de um Autômato
    Linguagens regulares

    04-Mai
    Operações com linguagens regulares
    Fecho sob operações regulares (Complementação, união, interseção)
    Autômatos Finitos Não-Determinísticos:
    Motivação; Exemplos; Árvores de Computação

    09-Mai
    (Mini-Prova)
    De Autômatos Finitos Não-Determinísticos para Autômatos Finitos Determinísticos
    Fecho sob operações regulares (Concatenação, estrela)

    11-Mai
    Expressões Regulares
    De Expressões Regulares para Autômatos Finitos

    16-Mai
    (Mini-Prova)
    De Autômatos Finitos para Expressões Regulares

    18-Mai
    Linguagens Não-Regulares
    Lema do Bombeamento

    23-Mai
    Primeira Prova

    25-Mai
    Gramáticas Livres-do-Contexto
    Forma Normal de Chomsky
    Árvores sintáticas

    30-Mai
    Ambigüidade em gramáticas
    Autômatos com Pilha

    01-Jun
    Autômatos com Pilha versus Gramáticas Livres-do-Contexto

    06-Jun
    Segunda Prova

    13-Jun
    Máquinas de Turing
    Linguagens Turing-reconhecíveis

    15-Jun
    Variantes da Máquinas de Turing: Várias fitas

    20-Jun
    Máquinas de Turing Não-Determinísticas

    22-Jun
    (Mini-Prova)
    Enumeradores

    27-Jun
    Decidibilidade
    Problemas concernentes a Linguagens Regulares

    29-Jun
    Problemas concernentes a Linguagens Livres-do-Contexto

    04-Jul
    (Revisão)

    06-Jul
    O Problema da Parada
    Indecidibilidade do Problema da Parada
    Uma linguagem Não-Turing-reconhecível

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

    13-Jul
    O Problema da Correspondência de Post
    Redutibilidade por mapeamento

    18-Jul
    Complexidade de Tempo

    20-Jul
    Medindo complexidade
    Classes de complexidade de tempo

    25-Jul
    (Mini-Prova)
    A Classe P

    27-Jul
    A Classe NP
    A Questão P versus NP (em português)

    01-Ago
    Redutibilidade em Tempo Polinomial
    NP-Completude

    03-Ago
    O Problema SAT

    08-Ago
    Teorema de Cook-Levin

    10-Ago
    (Mini-Prova)
    Complexidade de Espaço

    15-Ago
    Teorema de Savitch

    17-Ago
    A Classe PSPACE

    22-Ago
    Terceira Prova

    24-Ago
    Segunda Chamada

    29-Ago
    Prova Final

    ATENÇÃO: Newsgroup

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

    Última atualização: 06 de Julho de 2007, 10:39am GMT-3