TEORIA DA COMPUTAÇÃO
Motivação
Licenciatura em Ciência e Tecnologia da
Computação
Licenciatura em Engenharia Informática e de
Computadores (Prep.)
1
TEORIA DA COMPUTAÇÃO

CIÊNCIAS DA COMPUTAÇÃO
Processamento da informação
 Processos de informação
 Estruturas de informação e respectivos
procedimentos de representação
 Implementação de sistemas
 ...

2
PRINCIPAIS ÁREAS DE ESTUDO DAS CIÊNCIAS DA
COMPUTAÇÃO

Concepção

Formulação

Implementação em computador

Análise

Avaliação de algoritmos
3
RELAÇÃO DAS CIÊNCIAS DA COMPUTAÇÃO COM OUTRAS
CIÊNCIAS

MATEMÁTICA

ENGENHARIA

LINGUÍSTICA

BIOLOGIA

ETC.
4
QUESTÕES FUNDAMENTAIS NAS CIÊNCIAS DA
COMPUTAÇÃO

O que é que pode ser automatizado de
forma eficiente?

Pode um problema ser resolvido por um
computador? É possível escrever o
respectivo programa? O programa estará
correcto? É eficiente?

Como garantir a correcção de programas?

Como compor sistemas?
5
ALGORITMO
Noção que está no centro da Ciência
da Computação
 É um método para desempenhar uma
operação de forma mecânica
 Os primeiros algoritmos (informais)
surgiram no tempo da Grécia Antiga
 A formulação precisa do conceito de
algoritmo só surgiu no século XX

6
Estudos actualmente desenvolvidos em
torno da noção de algoritmo:







Limitações do método algorítmico
(computabilidade e decidibilidade)
Eficiência (complexidade)
Correcção (verificação)
Linguagens de programação (sintaxe e
semântica)
Modelos de dados (teorias de tipos de
dados)
Paradigmas da programação (imperativo,
declarativo, etc.)
...
7
Alguns modelos alternativos no
estudo da computabilidade






Turing : Máquina de Turing (1936);
Church: Funções definidas por termos  (1936);
Gödel e Kleene : Funções (parciais) recursivas
(1936);
Post : Sistemas de derivação de Post (1943)
Markov : Algoritmos de Markov(1951)
Shepherdson e Sturgis : Máquina URM (1963)
Todas estas abordagens definem a mesma classe de
funções.
Máquinas Físicas versus Máquinas Abstractas
8
Postulado de Church- Turing

A classe intuitiva e formal das funções
efectivamente computáveis coincide com a classe
das funções computáveis pela máquina URM.

Diversas propostas para a formulação precisa do
conceito de função efectivamente computável têm
conduzido à mesma classe de funções.

Todas as funções efectivamente computáveis
conhecidas são computáveis pela máquina URM
(Turing,...).

Ainda não foi encontrada uma função
intuitivamente computável que não seja
computável pela máquina URM (Turing,...).
9
“Mapa” dos principais conceitos associados a programa
Matemática
discreta
Arquitectura de
Computadores
Álgebra Especificações
Estruturas de
Informação
Controlo
Processadores
de linguagens
Abstracções
Processo
Computacional
Linguagem
Programa
Estudo de
linguagens
formais
Complexidade
Computacional
Algoritmo
Computabilidade
Fundamentos
Teoria da
Computação
Adaptado de “Programação em Scheme”, J. Pavão Martins e Mª dos Remédios Cravo, IST Press, 2004
10
“Mapa” dos principais conceitos associados a programação
Arquitectura de Programas
Programação
imperativa
Inteligência
artificial
Interfaces
gráficas
Técnicas
Programação
Paradigmas
Programação
funcional
Programação
com objectos
Bases de Dados
Programação
em Lógica
Sistemas operativos
Arquitectura de Computadores
Adaptado de “Programação em Scheme”, J. Pavão Martins e Mª dos Remédios Cravo, IST Press, 2004
11
“Os especialistas de informática, na vida de todos
os dias, devem ser capazes de traduzir
problemas reais em abstracções baseadas no
uso de modelos formais, para manipular essas
descrições formais e para raciocinar acerca das
suas propriedades de modo rigoroso. Esta
atitude muito particular distingue o especialista
de informática da maior parte dos técnicos
profissionais...
Os tópicos teóricos não devem ser considerados
como opções a serem mais tarde acrescentadas
aos currículos. Deviam antes ser vistos como a
base que inspirará e informará todos os
currículos, e, em especial, todos os outros
cursos práticos"
In Theoretical Foundations of Computer Science
Mandrioli e Ghezzi
John Wiley, 1987
12