Teoria da Computação
(cod.5384)

1  Novidades

• Site de avaliação dos trabalhos novamente aberto. Vários alunos presenciaram alguns problemas na submissão de soluções nesta segunda fase (as submissões parecem ser ignoradas). Do meu lado, vejo-as.

  Para resolver este problema proponho-vos duas soluções:

  1. Registar-se novamente com um nome ligeiramente diferente e submeter com este novo login. Se o problema persistir, então:
  2. Registar-se no novo concurso TC1112_exame e proceder às submissões das vossas soluções ao problema D e E neste segundo concurso.
• Notas da avaliação contínua disponíveis sob consulta (por email ou presencialmente).
• O site mooshak será reaberto do dia 5 de Fevereiro 00h00 ao dia 9 de Fevereiro 23h59 para quem quiser terminar (e só isso - os accepted são considerados já entregues) os problemas D ou E para efeitos de avaliação por exame.
• Notas da frequência disponíveis sob consulta (por email ou presencialmente).
• Correcção da frequência disponível na secção 10.
• Zip com provas dos anos anteriores: na secção 10.
• Relembra-se a secção Fraude (ver 5.1) a todos os alunos...
• Como colocar uma dúvida ao regente da Unidade Curricular?
  1. Comparecer nas aulas e colocá-la directamente ao regente
  2. Comparecer no horário de atendimento do regente e colocá-la directamente
  3. enviar um email ao regente (desousaUUU@UUUdi.ubi.pt, (retire os UUU) ) com o assunto "TComp: XXXX" em que XXX é o título da dúvida em questão. Qualquer outro formato no assunto arrisca condenar o email ao esquecimento.

Contents

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

2  Docentes

• Simão Melo de Sousa (regente) - Gabinete 3.17 - Laboratório 6.10 - Bloco VI.

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

• 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

A avaliação será constituída por duas componentes: a componente prática e a componente teórica.

5.1  Fraudes

A equipa docente realça 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.2  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 e individual. Com a excepção do 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 entrega é feita de forma electrónica no site mooshak da UC.
• A Nota da Componente Prática (NCP, 20 valores) é a soma dos valores atribuídos aos diferentes exercícios resolvidos.

5.3  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 2012 (dia 4 de Janeiro).

Desta prova resulta a Nota da Componente Teórica (NCT, 20 valores).

5.4  Avaliação Contínua

A nota da avaliação contínua é determinada da seguinte forma:

5.5  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 da avaliação contínua, dando uma nova NCT.
• Assim a nota final (NFin) após exame é calculada da seguinte forma:

  NFin=if (NCP≥ 6 ∧ NCT≥ 6) then

  NCT× 1.2 + NCP × 0.8 2

  else  Reprovado

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	Frequência	Church
2	Intro	OCaml	6	Gram	FSM(*)	10	MT	PDA	14	Church	Church
3	FSM	OCaml	7	Gram	Gram	11	MT	MT	15	Indec.	Indec.h
4	FSM	OCaml(*)	8	PDA	Gram	12	Church	MT(*)	16	-	-(*)

(*) - Entrega Prevista de Trabalho

Table 1: Calendário Previsto - Aulas T + Aulas P

---

7  Datas Importantes

• Data de entrega dos enunciados: Todos os enunciados se encontram disponíveis.
• Entrega do primeiro exercício: (novo) Semana (6) do dia 31 de Outubro de 2011
• Entrega do segundo exercício: (novo) Semana (9) do dia 21 de Novembro de 2011
• Entrega do terceiro exercício: (novo) Semana (12) do dia 12 de Dezembro de 2011
• Entrega do quarto e do quinto exercício: (novo) Semana (15) do dia 20 de Janeiro de 2012
• Frequência: Aula teórica do dia 4 de Janeiro 2012.
• 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  Horário

9  Atendimento

10  Material Pedagógico e Funcionamento da Disciplina

Os Apontamentos serão atempadamente disponibilizados nas aulas e por meios electrónicos. É esperado e assumido que o aluno tenha lido os acetatos referentes ao capítulo em curso antes das aulas teóricas.

Teóricas

Introdução contextual e histórica à Teoria da Computação

Conceitos preliminares à Teoria da Computação

Complementos sobre técnicas matemáticas para a Teoria da Computação (mais detalhes sobre indução estrutural)

Capítulo "OCaml"

Capítulo "Autómatos"

Acetatos manuscritos "automatos" num só pdf

Acetatos manuscritos "automatos" formato RAR

Execução genérica de autómatos finitos não determinísticos com є-transições (em ocaml)

Execução genérica de autómatos finitos determinísticos (em ocaml)

Capítulo "Linguagens e Gramáticas"

Capítulo "Autómatos PushDown e Linguagens Algébricas"

Capítulo "Máquinas de Turing"

Práticas

Primeiro Guião OCaml

Segundo Guião OCaml

Terceiro Guião OCaml

Quarto Guião OCaml

Ficha "Ocaml"

Ficha "Fundamentos"

Ficha "Técnicas Matemáticas"

Ficha "Linguagens Regulares e Autómatos"

Ficha "Gramáticas, Linguagens Formais e Linguagens Algébricas"

Zip contendo os enunciados das provas dos anos anteriores

Correcção da Frequência

Trabalhos Práticos

Primeiro exercício por entregar (pdf) (html) Solução:(html)

Segundo exercício por entregar (pdf) (html) Solução:(html)

Terceiro exercício por entregar (pdf) (html)

Quarto exercício por entregar (pdf) (html)

Quinto exercício por entregar (pdf) (html)

11  Bibliografia Principal

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

12  Links úteis

• Ocaml
  • Site OCaml
  • 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 o Emacs 23
• Um site sobre Ciências da Computação (contem livros online)
  • Site Programming languages theory texts online

References

[1]

J.B. Almeida, M.J. Frade, J.S. Pinto, and S. Melo de Sousa. Rigorous Software Development, An Introduction to Program Verification, volume 103 of Undergraduate Topics in Computer Science. Springer-Verlag, first edition, 307 p. 52 illus. edition, 2011.

[2]

A. Arnold and I. Guessarian. Mathematics for Computer Science. Prentice-Hall, 1996.

[3]

E. Chailloux, P. Manoury, and B. Pagano. Developing applications with objective caml. http://caml.inria.fr/oreilly-book, 2003.

[4]

M. Fernández. Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer, 2009.

[5]

Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume 3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.

[6]

J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to automata theory, languages, and computation. Pearson education, 2001.

[7]

Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.

[8]

P. Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.

[9]

David Makinson. Sets, Logic and Maths for Computing. Springer Publishing Company, Incorporated, 1 edition, 2008.

[10]

M. Sipser. Introducton to the Theory of Computation. PWS Publishing, 2006.

[11]

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 L^AT_EX by H^EV^EA.