Teoria da Computação
(cod.11562)

Departamento de Informática
Universidade da Beira Interior



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 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 numa única prova escrita (frequência), prevista na data anunciada na secção 6.

Da avaliação qualitativa da frequência 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óricaSegunda-Feira das 16h00 às 18h006.03S. Melo de Sousa
Práticas LaboratoriaisQuarta-Feira das 9h00 às 11h006.13S. Melo de Sousa
Práticas LaboratoriaisQuinta-Feira das 9h00 às 11h006.13S. Melo de Sousa
Práticas LaboratoriaisQuinta-Feira das 11h00 às 13h006.13S. Melo de Sousa
Práticas LaboratoriaisQuinta-Feira das 14h00 às 16h006.13S. Melo de Sousa

8  Atendimento

Por marcação (e.g. via email) ou

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

Computação Simbólica e Programação

Aula 0

Aula 1

Aula 2

Aula 3

Aula 4

Sebenta OCaml

em alternativa: aula executável de OCaml

Primeiro Guião OCaml

Segundo Guião OCaml

Terceiro Guião OCaml

Quarto Guião OCaml

Modelos de Computação

Práticas

Algumas resoluções

Exercícios Por Entregar

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.