Teoria da Computação
(cod.5384)

1  Novidades

• e-conteúdos online. Encontrará na página dos e-conteúdos informação actualizada sobre a disciplina de Teoria da Computação.
• Os alunos sem acesso aos e-conteúdos deverão enviar um email ao regente com a seguinte informação:
  Subject: TComp: Acesso aos econteúdos
  Body: numero de aluno
  A autorização de acesso será então processada.
• Inscrição em turmas práticas: Até sexta-feira 28 de Setembro pelo site dos serviços académicos. A partir de segunda feira 1 de Outubro, as inscrições serão feitas no secretariado. Realça-se que um turno com menos do que 10 alunos inscritos não abrirá (os alunos em causa terão de se reagrupar noutros turnos).
• As aulas práticas começam já esta semana, a partir da turma de Quarta-feira 26 de Setembro.

Contents

• 1  Novidades
• 2  Docentes
• 3  Objectivos
• 4  Programa
• 5  Critérios de Avaliação
  • 5.1  Componente Prática
  • 5.2  Componente Teórica
  • 5.3  Avaliação Contínua
  • 5.4  Admissão e Avaliação por Exame
• 6  Calendário das Aulas
• 7  Datas Importantes
• 8  Material Pedagógico e Funcionamento da Disciplina
• 9  Horário
• 10  Atendimento
• 11  Bibliografia Principal
• 12  Links úteis

2  Docentes

• Simão Melo de Sousa (regente) - Gabinete 4.3.
• Paul Crocker - Gabinete 4.10.

3  Objectivos

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

• Apresentação Contextual e Histórica da Teoria da computação
• Modelos da computação: dos autómatos (de estados finitos, com pilha) às máquinas de Turing.
• Modelos de computação alternativos: Funções recursivas de Kleene e calculo lambda.
• Programação em modelos da computação.
• Tese de Church-Turing. Provas de equivalência de modelos.
• A não computabilidade e a indecidibilidade: Problemas indecidíveis, técnica da diagonalização, técnica da redução.

5  Critérios de Avaliação

Fraudes

5.1  Componente Prática

• Esta avaliação mede em termos práticos a aquisição dos conceitos expostos. Como tal é baseada na avaliação da resolução de exercícios durante as práticas laboratoriais.
• Os exercícios avaliados são em número de 5 e resolvidos de uma forma sequencial. Excepto o primeiro enunciado que será comunicado no inicio das aulas, os enunciados serão entregue na semana da resolução do exercício anterior. As datas exactas de entrega encontram-se na secção 7
• A Nota da Componente Prática (NCP, 20 valores) é a soma dos valores atribuídos aos diferentes exercícios resolvidos.

5.2  Componente Teórica

5.3  Avaliação Contínua

5.4  Admissão e Avaliação por Exame

• Mínimos: São seguidas as disposições aprovadas pelo Conselho Científico da Universidade aplicadas individualmente a cada componente da avaliação. Assim, NCP≥ 6 ∧ NCT≥ 6 ⇒ admissão ao exame.
• A prova escrita do exame substituirá a Nota da Componente Teórica (NCT).
• Assim a nota final (NFin) após exame continua a ser calculada como a média da avaliação das duas componentes:

  NFin=

  NPE + NCP 2

6  Calendário das Aulas

---

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

• Entrega do primeiro exercício: Semana (3) do dia 12 de Outubro 2007
• Entrega do segundo exercício: Semana (5) do dia 26 de Outubro de 2007
• Entrega do terceiro exercício: Semana (7) do dia 9 de Novembro de 2007
• Entrega do quarto exercício: Semana (12) do dia 14 de Dezembro de 2007
• Entrega do quinto exercício: Semana (16) do dia 25 de Janeiro de 2008
• Frequência: Aula teórica do dia 10 de Janeiro 2008.
• Exame Época 1 : (conferir no site dos académicos)
• Exame Época 2 : (conferir no site dos académicos)
• Exame Época Especial : (conferir no site dos académicos)

8  Material Pedagógico e Funcionamento da Disciplina

9  Horário

10  Atendimento

11  Bibliografia Principal

12  Links úteis

• Ocaml
  • Site OCaml
  • Performance Ocaml:The great computer language shootout
  • OCamlMakefile: Makefile genérico para OCaml
  • Tuareg: Emacs Mode para Ocaml
  • Livro: Developing Applications With Objective Caml
  • Manual de Referência Ocaml
  • Hump: Repositório de aplicações/bibliotecas/”material” OCaml
• Emacs
  • Site Emacs - XEmacs
  • Documentação Emacs - XEmacs
  • Comandos principais para Emacs 21
• Um site sobre Ciências da Computação (contem livros online)
  • Site Programming languages theory texts online

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.

This document was translated from L^AT_EX by H^EV^EA.