Teoria da Computação
(cod.5384)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2011/2012

Esta página no formato pdf, no formato ps

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.

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

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:

componente prática (NCP) × 0.8 +   componente teórica (NCT) × 1.2
2

5.5  Admissão e Avaliação por Exame

6  Calendário das Aulas

Ver tabela 1


Sem.TeóricaPráticasSem.TeóricaPráticasSem.TeóricaPráticasSem.TeóricaPráticas
1IntroOCaml5FSMFSM9PDAPDA(*)13FrequênciaChurch
2IntroOCaml6GramFSM(*)10MTPDA14ChurchChurch
3FSMOCaml7GramGram11MTMT15Indec.Indec.h
4FSMOCaml(*)8PDAGram12ChurchMT(*)16--(*)
(*) - Entrega Prevista de Trabalho
Table 1: Calendário Previsto - Aulas T + Aulas P

7  Datas Importantes

8  Horário

Tipo de aulaHorárioSalaDocente
TeóricaQuarta-Feira das 11h00 às 13h006.18S. Melo de Sousa
Práticas Laboratoriais 1Sexta-Feira das 14h00 às 16h006.14S. Melo de Sousa
Práticas Laboratoriais 2Quarta-Feira das 9h00 às 11h006.14S. Melo de Sousa
Práticas Laboratoriais 3Quinta-Feira das 11h00 às 13h006.14S. Melo de Sousa

9  Atendimento

HorárioDocente
Terça-Feira das 9h00 às 11h00S. Melo de Sousa

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

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 LATEX by HEVEA.