Teoria da Computação
(cod.5384)

1  Novidades

• Notas da avaliação contínua entregues no Balcão Virtual (NA = Não Admitido por não ter nota mínima na NCT).
• Fase de melhoria para NCP: Só o problema D e o problema E poderão ser melhorados. Datas: entre o dia 30 de Janeiro até ao dia 7 (00:00) de fevereiro.
• Em jeito de boas entradas para 2013, as notas da primeira frequência serão entregues no fim da segunda frequência.
• Votos de umas Boas Festas!
• O Problema E encontra-se completeamente configurado no sistema de avaliação online.
• Enterga do exercício D adiada para a data de entrega do exercício E.
• A sebenta “introdução ao OCaml” já se encontra actualizada na secção 10.
• 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 "TC: 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
  • 4.1  Competências da UC ou Resultados da Aprendizagem
• 5  Critérios de Avaliação
  • 5.1  Actividades de Ensino-Aprendizagem e Metodologias Pedagógicas
  • 5.2  Fraudes
  • 5.3  Componente Prática
  • 5.4  Componente Teórica
  • 5.5  Avaliação Contínua
  • 5.6  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.

4.1  Competências da UC ou Resultados da Aprendizagem

O aluno deverá ser capaz de perceber e usar a capacidade de computação das máquinas, assim como os seus limites teóricos.

Deverá ser capaz de formalizar adequadamente e avaliar se determinados problemas tem solução computacional ou não.

Deverá perceber e saber usar modelos, técnicas e algoritmos de computação simbólica introduzidos na resolução de problemas informáticos do dia-a-dia.

5  Critérios de Avaliação

5.1  Actividades de Ensino-Aprendizagem e Metodologias Pedagógicas

Por fim a avaliar as competências adquiridas, as actividades de Ensino-Aprendizagem avaliarão tanto a compreensão dos conceitos teóricos expostos como a capacidade em por estes em prática.

Assim, a avaliação será constituída por duas componentes: a componente prática ( exercícios práticos entregues à equipa docente) e a componente teórica (provas escritas).

Mais precisamente a avaliação será realizada por uma prova escrita e por avaliação contínua baseada em.

5.2  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.3  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.4  Componente Teórica

A avaliação da componente teórica consiste em duas frequências, previstas para o dia 7 de Novembro e o dia 5 de Janeiro.

Da média destas duas provas resulta a Nota da Componente Teórica (NCT, 20 valores).

5.5  Avaliação Contínua

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

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

(*) - Entrega Prevista de Trabalho

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

---

7  Datas Importantes

• Entrega do segundo, terceiro e quarto exercício: 7 de Dezembro de 2012
• Entrega do quinto exercício: 18 de Janeiro de 2013
• Primeira Frequência: Aula teórica do dia 7 de Novembro 2012.
• Segunda Frequência: Aula teórica do dia 9 de Janeiro 2013.
• 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"

Algumas resoluções

Algarismos

Horner

Conjunto das listas

Zip contendo os enunciados das provas dos anos anteriores

Correcção da Frequência

Trabalhos Práticos

Primeiro exercício por entregar (pdf)

Segundo exercício por entregar (pdf)

"Emparelhamentos, Casamentos Estáveis e Algoritmos de Colocacão de Professores - Ana Paula Tomás- Uma ajuda completa para o segundo exercício por entregar (pdf)
 

Terceiro exercício por entregar (pdf)

Quarto exercício por entregar (pdf)

Quinto exercício por entregar (pdf)

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.