Teoria da Computação
(cod.11562)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2014/2015



Esta página no formato pdf

Paper do Alan Turing introduzindo as Máquinas de Turing aqui

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 duas provas escritas e por avaliação contínua baseada na resolução individual de exercícios práticos.

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 (i.e. Não Admissão), 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 nas datas anunciadas na secção 6.

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

5.5  Concessão de Frequência e Avaliação Contínua

O parâmetro de "Frequência" atribuído no final desta unidade curricular traduz, no contexto da avaliação contínua, a "avaliação mínima" do estudante ao longo do processo de ensino-aprendizagem no final das actividades de contacto.

Considera-se que o estudante demonstrou ter adquirido o grau de conhecimentos mínimos (durante o processo de aprendizagem ao longo das actividades lectivas) quando este demonstrou as mínimas competências em cada componente avaliada.

É assim concedido Frequência ao aluno que obteve os mínimos (6) em vigor na Universidade da Beira Interior em ambas as componentes (NCP e NCT).

No caso de Frequência, a avaliação quantitativa, designada aqui de nota da avaliação contínua, é determinada da seguinte forma:

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

Se a avaliação quantitativa resultar numa nota maior ou igual a 10 então o aluno é dispensado de exame (Frequência com dispensa de exame)

5.6  Avaliação por Exame

6  Datas Importantes

7  Horário

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

8  Atendimento

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

9  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

Práticas

Algumas resoluções

Trabalhos Práticos

10  Bibliografia Principal

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

11  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.