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

IF689 - Informática Teórica

Primeiro Semestre de 2004

Horário de Aulas
Turma I4 (Sala 9)
  4a Feira, de 16h às 18h
  6a Feira, de 12h às 14h

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

Monitoria
Nome (e-mail)
Horário de Atendimento
Responsabilidade
Daniel Arraes (dap) 2a.,4a.,5a.,6a. 12:30-14:00 Correção de Listas/Mini-Provas
Sergio Clemente (sscf) 2a.,5a.,6a. 12:30-14:00 Correção de Listas/Mini-Provas
Marcelo Simões (msv2) - Aulas de Revisão
Gustavo Henrique (ghpc) 2a.,3a.,5a.,6a. 12:30-14:00 Aulas de Revisão
Marcos Tulio (mtcfa) 2a.,5a. 12:00-14:00 Correção de Listas/Mini-Provas
Eduardo Lourenço (ela) 3a.,4a. 12:30-14:00 Correção de Listas/Mini-Provas
Mariana Pinto Xavier (mpx) 2a.,4a. 13:00-14:00 Aulas de Revisão
Paulo Roberto (prsof) - Correção de Listas/Mini-Provas
Francisco Valadares (famv) - Projetos
Marcos Aurelio (maas) - Projetos

Avaliação
1a. Unidade
2a. Unidade
3a. Unidade
Média Aritmética de Listas e Mini-Provas: 30% Média Aritmética de Listas e Mini-Provas: 30% Média Aritmética de Listas e Mini-Provas: 30%
Projeto: 30% - Projeto: 30%
Prova: 40% Prova: 70% Prova: 40%

Média Final: Média Aritmética das médias da 1a., 2a. e 3a. unidades.

Listas de Exercícios

  • Capítulo 5: em ps e em pdf
  • Capítulos 6 e 7: em ps e em pdf

    Bibliografia Básica

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

    Bibliografia Suplementar

  • Elements of the Theory of Computation (Second Edition), Harry R. Lewis and Christos Papadimitriou, Prentice-Hall, 1998, ISBN: 0-13-262478-8.
  • Automata and Computability, Dexter Kozen, Springer, 1997, ISBN: 0-387-94907-0.
  • Computational Complexity, Christos Papadimitriou, Addison Wesley, 1994, ISBN: 0-201-53082-1.
  • Computability, Algorithms and Complexity, Ian Hodkinson, Department of Computing, Imperial College London, lecture notes, 1996.
        Information.ps     ch1-2.ps     ch3.ps     ch4-5.ps     ch6-8.ps     ch9-10.ps     ch11-12.ps

    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. (generalização do Entscheidungsproblem)
    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 12-mai Motivação: Problemas de Decisão
    O Entscheidungsproblem     		02
    2 14-mai Alfabetos e Linguagens
    Representação Finita de Linguagens     		04
    3 19-mai Autômatos Finitos
    Operações: Produto, Seqüenciamento     		06
    4 21-mai Autômatos Finitos Não-Determinísticos
    		 08
    5 26-mai Equivalência entre Autômatos 10
    6 28-mai Expressões Regulares
    De Expressões Regulares para Autômatos Finitos     		12
    7 02-jun De Autômatos Finitos para Expressões Regulares 14
    8 04-jun Linguagens Não-Regulares
    Lema do Bombeamento     		16
      09-jun Semana Pedagógica  
    9 11-jun Linguagens Regulares: Propriedades de Fechamento 18
    10 16-jun Propriedades de Decisão para Linguagens Regulares 20
    11 18-jun Primeira Prova 22
    12 30-jun Gramáticas Livres-de-Contexto
    		 24
    13 02-jul Árvores sintáticas
    		 26
    14 07-jul Autômatos a Pilha
    		 28
    15 09-jul Autômatos a Pilha (cont.) 30
    16 14-jul Equivalência entre AP e LLC 32
      16-jul Feriado - Nossa Senhora do Carmo  
    17 21-jul Revisão 34
    18 23-jul Mini-Prova 36
    19 28-jul Propriedades de Fechamento de Linguagens Livres-de-Contexto 38
    20 30-jul Propriedades de Decisão de Linguagens Livres-de-Contexto 40
    21 04-ago Forma Normal de Chomsky 42
    22 30-jul Máquinas de Turing Universais
    Indecidibilidade e o Problema da Parada     		44
    23 04-ago Propriedades de Linguagens RE
    Teorema de Rice     		46
    24 06-ago Máquinas de Turing Algoritmos como Máquinas de Turing
    Linguagens Recursivas e Recursivamente Enumeráveis     		48
    25 11-ago Variantes da Máquina de Turing 50
    26 13-ago Máquinas de Turing Universais
    Indecidibilidade e o Problema da Parada     		52
    27 18-ago Propriedades de Linguagens RE 54
    28 20-ago Problema Indecidíveis sobre MT
    Teorema de Rice     		56
    29 25-ago O Problema da Correspondência de Post 58
    30 27-ago Problema Intratáveis
    Tempo-polinomial não-determinístico
    Reduções     		60
    31 01-set Problemas NP-Completos
    O Problema SAT     		62
    32 03-set Terceira Prova 64
    33 08-set Segunda Chamada 66
    34 10-set Prova Final 68


    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 Maio de 2004, 16:02hs