Teoria da Computação
(cod.5384)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2007/2008

1  Novidades

Contents

2  Docentes

3  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:
  1. 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;
  2. 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.

4  Programa

5  Critérios de Avaliação

A avaliação será constituída por duas componentes: a componente prática e a componente teórica.
Fraudes
A equipa docente gostaria de realçar que qualquer tipo de fraude em qualquer dos itens desta disciplina implica a reprovação automática do aluno faltoso, podendo ainda vir a ser este alvo de processo disciplinar. Listamos a seguir as diferentes componentes da avaliação.

5.1  Componente Prática

5.2  Componente Teórica

A avaliação da componente teórica consiste numa frequência, agendada para a primeira aula teórica do mês de Janeiro de 2008. Desta prova resulta a Nota da Componente Teórica (NCT, 20 valores).

5.3  Avaliação Contínua

A nota da avaliação contínua é determinada como a média da componente prática com a componente teórica.

5.4  Admissão e Avaliação por Exame

6  Calendário das Aulas

Ver tabela 1

Sem. Teórica Práticas Sem. Teórica Práticas Sem. Teórica Práticas Sem. Teórica Práticas
1 Intro OCaml 5 FSM FSM(*) 9 PDA PDA 13 Church Church
2 Intro OCaml 6 Gram FSM 10 MT PDA 14 Frequência Church
3 FSM OCaml(*) 7 Gram Gram(*) 11 MT MT 15 Indec. Church
4 FSM OCaml 8 PDA Gram 12 Church MT(*) 16 Indec. Indec.(*)
(*) - Entrega de Trabalho

Table 1: Aulas T + Aulas P



7  Datas Importantes

8  Material Pedagógico e Funcionamento da Disciplina

Os Apontamentos serão atempadamente disponibilizados nas aulas e no site dos e-conteúdos. É esperado e assumido que o aluno tenha lido os acetatos referentes ao capítulo em curso antes das aulas teóricas.

9  Horário

Tipo de aula Horário Sala Docente
Teórica Quinta-Feira das 14h00 às 16h00 6.02 S. Melo de Sousa
Práticas Laboratóriais 1 Segunda-Feira das 9h00 às 11h00 6.14 P. Crocker
Práticas Laboratóriais 2 Terça-Feira das 16h00 às 18h00 6.14 P. Crocker
Práticas Laboratóriais 3 Quarta-Feira das 11h00 às 13h00 6.14 S. Melo de Sousa
Práticas Laboratóriais 4 Sexta-Feira das 14h00 às 16h00 6.14 S. Melo de Sousa
Práticas Laboratóriais 5 Sexta-Feira das 16h00 às 18h00 6.14 S. Melo de Sousa

10  Atendimento

<\TR>
Horário Docente
Quarta-Feira das 16h00 às 18h00 S. Melo de Sousa
Quinta-Feira das 11h00 Às 13h00 <\TD> S. Melo de Sousa

11  Bibliografia Principal

As referencias principais são: [4, 5, 7, 2] utilizaremos ocasionalmente as referências [3, 6, 1].

12  Links úteis

References

[1]
A. Arnold and I. Guessarian. Mathematics for Computer Science. Prentice-Hall, 1996.
[2]
E. Chailloux, P. Manoury, and B. Pagano. Developing applications with objective caml. http://caml.inria.fr/oreilly-book, 2003.
[3]
Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume 3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.
[4]
Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.
[5]
P. Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.
[6]
M. Sipser. Introducton to the Theory of Computation. PWS Publishing, 2006.
[7]
Pierre Wolper. Introduction à la Calculabilité. Dunod, PAris, France, 3 edition, 2006.



Enviar comentários e dúvidas para (retire os UUU) : desousaUUU@UUUdi.ubi.pt
This document was translated from LATEX by HEVEA.