Teoria da Computação
(cod.5384)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2012/2013



Esta página no formato pdf

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

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

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:

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

5.6  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
1IntroOCaml5FSMFSM(*)9PDAPDA13ChurchChurch
2FSMOCaml6GramFSM10PDAPDA14Indec.Church
3FSMOCaml(*)7GramGram11MTMT15FreqIndec.
4FSMFSM8Freq.Gram(*)12MTMT(*)16Indec.Indec.(*)
(*) - 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 14h00 às 16h006.02S. Melo de Sousa
Práticas Laboratoriais 1Quinta-Feira das 9h00 às 11h006.13S. Melo de Sousa
Práticas Laboratoriais 2Quarta-Feira das 16h00 às 18h006.13S. Melo de Sousa
Práticas Laboratoriais 3Quinta-Feira das 11h00 às 13h006.13S. Melo de Sousa

9  Atendimento

HorárioDocente
Quarta-Feira das 16h00 às 18h00S. 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"

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

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.