Pesquisa e Pós-Graduação em
Ciência da Computação

ÁREA DE TEORIA DA COMPUTAÇÃO

IN???? - Computabilidade e Lógica

2000.1

Professor: Ruy J. Guerra B. de Queiroz
Horário: Quarta-Feira 10:00-12:00
             Quinta-Feira 14:00-16:00
Local: Sala M4 ou M5, Bloco C, DI-UFPE

De que se trata?

Em poucas palavras

Estudaremos:
(i) modelos de computação, em particular, a Máquina de Turing, e as funções recursivas;
(ii) os fundamentos da representação simbólica, e da noção de conseqüência lógica.

Importância para o profissional da Informática

A noção de procedimento efetivo, que deu origem às primeiras "máquinas abstratas de computação efetiva" (como, por exemplo, a chamada Máquina de Turing, o primeiro modelo de computador programável por software, e que deu origem à chamada Tese de Church que afirma que qualquer função efetivamente computável pode ser computável por uma Máquina de Turing apropriadamente definida) está intimamente ligada à noção de "dedução em um sistema formal (simbólico)", como concebido por Gottlob Frege, o mentor da Lógica Moderna, justamente porque esta última veio como a implementação do sonho do filósofo Leibniz (século XVII) de criar uma máquina de verificação da validade de argumentos.

Além do mais, o conceito de máquina de processamento simbólico e as noções de representação e manipulação simbólica, fundamentais para qualquer estudioso da ciência da computação, são estudados no curso de forma abstrata e bastante geral, independente da linguagem utilizada para a representação.

(Para algumas considerações sobre a influência da Lógica Matemática na fundamentação dos conceitos básicos da Ciência da Computação, ver História da Computação (por Cléuzio Fonseca Filho), particularmente o item Evolução dos Conceitos.)

Conteúdo do Curso

Bibliografia Básica

[1] Computability, Algorithms and Complexity, por Ian Hodkinson, Notas de Aula, Imperial College, Londres, 1996.
[2] Computational Complexity, por Christos Papadimitriou, Addison-Wesley, 1994.

Bibliografia Adicional

[3] Computability and Logic, por George Boolos e Richard Jeffrey, Cambridge University Press, 3rd edition, 1990.
[4] Computability. An introduction to recursive function theory, por Nigel Cutland, Cambridge University Press, 1980.

Avaliação

  • Listas de exercícios e/ou exposições em aula
  • Exame escrito

    Programação de Aulas

    Aula
    Data
    Assunto
    Horas Acum.
    1 29/mar Apresentação do Curso
    Preliminares Matemáticos
    Cardinalidade, Enumerabilidade    		 02
    2 30/mar Máquinas de Turing
    (Fonte Bibliográfica: [1], Cap. 1 e 2)    		 04
    3 5/abr Máquinas de Turing com Múltiplas Fitas
    (Fonte Bibliográfica: [2], Cap. 2, Sec. 2.3, 2.4, 2.5)     		06
    4 6/abr Máquinas de Turing Não-Determinísticas
    (Fonte Bibliográfica: [2], Cap. 2, Sec. 2.7)    		 08
    5 12/abr Máquinas de Turing Universais
    (Fonte Bibliográfica: [1], Cap. 4; [2] Cap. 3, Sec. 3.1, 3.2)    		 10
    6 13/abr Problemas Insolúveis
    (Fonte Bibliográfica: [1], Cap. 5; [2], Cap. 3, Sec. 3.3)     		12
    7 ??/??? (a definir) 14
    8 ??/??? (a definir) 16
    9 ??/??? (a definir) 18
    10 ??/??? (a definir) 20
    11 ?/??? (a definir) 22
    12 ?/??? (a definir) 24
    13 ?/??? (a definir) 26
    14 ??/??? (a definir) 28
    15 ??/??? Primeira Prova 30
    16 ??/??? (a definir) 32
    17 ??/??? (a definir) 34
    18 ??/??? (a definir) 36
    19 ?/??? (a definir) 38
    21 ?/??? (a definir) 42
    22 ??/??? (a definir) 44
    23 ??/??? (a definir) 46
    24 ??/??? (a definir) 48
    25 ??/??? (a definir) 50
    26 ??/??? (a definir) 52
    27 ??/??? (a definir) 54
    28 ??/??? (a definir) 56
    29 ?/??? (a definir) 58
    30 ?/??? Segunda Prova 60

    Última atualização: 30 de Março de 2000, 17:12:06 GMT-0300.