Benvindo
à página da disciplina de Teoria da
Computação (cod.2813)
[Equipa Docente][Objectivos][Avaliação][Programa]
[News][Horário][Horário
de Atendimento]
[Trabalhos][Material
pedagógico][Links]
Novidades
ATENĒÃO: Notas do Exame da
Época de Recursos encontram-se afixadas no gabinete do regente da disciplina
.
EQUIPA
DOCENTE
(2003/2004)
OBJECTIVOS
Existem limites à capacidade de resolução de
problemas por um computador, mesmo na hipótese ``idealista'' de
ausência de restrições, que sejam essas o tempo (de
execução) ou o espaço (memória).
Para delinear esses limites, visaremos:
- perceber a capacidade de computação das
máquinas, assim como os seus limites teóricos.
Precisaremos de definir formalmente o que é e o que não
é um programa, um algoritmo, ou mais genericamente o que
é um tratamento efectivo;
- perceber os conceitos que fundamentam as linguagens de
programação. Precisaremos de determinar e estudar
formalmente as construções que determinam a
expressividade (ou capacidade de computação) das
linguagens de programação assim como o comportamento dos
programas.
AVALIAÇÃO
A avaliação será realizada
alternativamente:
A nota final da frequência e do exame é determinada de
acordo com a
seguinte
fórmula:
NF = média(NPE,NP)
NF =
Nota Final (da frequência ou do exame)
NPE = Nota da Prova
Escrita
NP =
Nota Prática
Em que a nota prática representa a média das notas
atribuídas
aos trabalhos individuais
realizados durante o semestre lectivo
e entregues
à equipa docente.
Importante: a condição "nota prática maior do que 5 valores"
define o critério de acesso as provas escritas.
Data da Frequência:: Quinta-Feira 18 de Dezembro das
8:00 as 11:00
PROGRAMA
RESUMIDO
- Conceitos Preliminares
- Conjuntos
- Operadores sobre Conjuntos
- Relações
- Conjuntos Ordenados
- Indução Bem Fundada
- Reticulados, CPOs e Pontos fixos
- Definições e propriedades básicas
- Reticulados completos
- Funções monótonas e contínuas
- CPOs e Pontos fixos
- Construção de Funções como Ponto
Fixos de Operadores
- Indução Estrutural
- Conjuntos definidos por indução,
Definições indutivas
- Demonstração por indução
- Indução Estrutural e Conjuntos de Termos
- Funções Estruturalmente Recursivas
- Indução Estrutural, Indução Bem
Fundada e Pontos Fixos
- Cálculo Lambda Puro
- Notações e teoria básica
- Reduções e igualdade
- Propriedades
- Confluência
- Terminação
- Normalização e Estratégias de
Redução
- Definibilidade Lambda
- Teoria das Funções Recursivas de Kleene
- Funções Primitivas Recursivas
- Computabilidade e Decidibilidade
- Teses de Church
- Equivalências de modelos computacionais
- Problemas decidíveis
- Para além da decidibilidade
- Conjuntos recursivos
- Conjuntos recursivamente enumeráveis
- Problemas indecidíveis, problemas semi-decidíveis
- Reduções de problemas
TEÓRICAS
E TURNOS PRÁCTICOS
| Tipo |
Horário |
Sala |
| Teórica |
Quinta-feira, 8:00 - 10:00
|
6.02 |
Teórica-Prática 1
|
Quinta-feira,
16:00 - 17:00
|
2.05E
|
Prática 1
|
Quinta-feira, 14:00 - 16:00 |
2.05E
|
Teórica-Prática 2
|
Quinta-feira, 10:00 - 11:00 |
2.05E |
Prática 2
|
Quarta-feira,
15:00 - 17:00 |
2.05E |
HORÁRIO
DE ATENDIMENTO
| Horário de Atendimento |
|
Quarta-feira, 11:00-13:00
|
|
Quinta-feira, 11:00-13:00
|
TRABALHOS
PRÁTICOS
- O Enunciado do primeiro
trabalho
prático está aqui.
O ficheiro
relacoes.mli está aqui. Data e local de entrega:
Inicio da primeira aula teórica do mês de Novembro.
- O Enunciado do segundo
trabalho
prático está aqui.
Um esqueleto
possível das demonstrações
está aqui.
Um esqueleto possíveldo
relatório
está aqui. Data e local de entrega:
na data e
no local da frequência.
MATERIAL
PEDAGÓGICO
- Complementos
de informação (para os alunos de Mestrado)
A aula de apresentação
está disponível
aqui
LINKS
Site Programming
language theory texts online
Enviar comentários e dúvidas para
: desousaUUU@UUUdi.ubi.pt
(c)
Simão
Melo de Sousa 2003