Teoria da Computação
2022-2023
(cod.14343/14813)

Departamento de Informática
Universidade da Beira Interior


Figure 1: Decision Procedure

Esta página no formato pdf

Paper do David Hilbert sobre o seu programa para a matemática do século XX (“os 23 problemas”) aqui

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

  Paper de Alonzo Church introduzindo o Cálculo Lambda aqui

  Paper de Lance fortnow sobre o estatuto recente do problema P=?NP 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 uma prova escrita 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 entregou com sucesso (“accepted” no mooshak) pelo menos um dos exercícios da componente de avaliação pratica. 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 11h00 às 13h006.01S. Melo de Sousa
Práticas LaboratoriaisTerça-Feira das 9h00 às 11h006.13S. Melo de Sousa
Práticas LaboratoriaisQuarta-Feira das 9h00 às 11h006.13Luís Horta
Práticas LaboratoriaisQuarta-Feira das 11h00 às 13h006.13Luís Horta

(TBD: Por definir)

8 Atendimento

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

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

consultar a página seguinte (link)


Modelos de Computação

Computabilidade e Teoria da Complexidade

Código OCaml para suporte às aulas

Práticas

Algumas resoluções

Exercícios Por Entregar

Por Definir.

10 Bibliografia Principal

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

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]
Olivier Carton. Langages formels, Calculabilité et Complexité. Vuibert Ed., June 2014.
[4]
E. ‍Chailloux, P. ‍Manoury, and B. ‍Pagano. Developing applications with objective caml. http://caml.inria.fr/oreilly-book, 2003.
[5]
Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume ‍3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.
[6]
Jason Hickey, Anil Madhavapeddy, and Yaron Minsky. Real World OCaml. O’Reilly, 2014.
[7]
J.E. Hopcroft, R. ‍Motwani, and J.D. Ullman. Introduction to automata theory, languages, and computation. Pearson education, third edition, 560 pages. edition, 2006.
[8]
Dexter Kozen. Automata and Computability. Springer-Verlag, New York, 1997.
[9]
Dexter Kozen. Theory of Computation. Springer, New York, 2006.
[10]
Harry ‍R. Lewis and Christos ‍H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.
[11]
P. ‍Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.
[12]
M. ‍Sipser. Introducton to the Theory of Computation. PWS Publishing, 2006.



Enviar comentários e dúvidas para (retire os UUU) : desousaUUU@UUUdi.ubi.pt


This document was translated from LATEX by HEVEA.