Teoria da Computação

Objetivos

Usar a lógica e a teoria de conjuntos para modelar dados e sistemas. Conhecer os fundamentos teóricos da computação, o conceito formal de algoritmo e a existência de problemas indecidíveis. Conhecer as classes de linguagens formais, os modelos computacionais associadas e a sua relação mútua. Compreender o conceito de universalidade Turing.

Modelar o espaço de estados de sistemas com conjuntos e lógica de 1º ordem. Distinguir conjuntos contáveis de não contáveis. Modelar sistemas com autómatos finitos (DFA e NFA). Construir um autómato dada uma expressão regular e o inverso. Construir um DFA equivalente a um NFA. Definir linguagens independentes de contexto com gramáticas. Construir analisadores LL e LR. Reconhecer a (in)decidibilidade de problemas computacionais.

Caracterização geral

Código

2468

Créditos

6.0

Professor responsável

António Maria Lobo César Alarcão Ravara

Horas

Semanais - 5

Totais - 65

Idioma de ensino

Português

Pré-requisitos

A disponibilizar brevemente

Bibliografia

Notas da UC ITC (Luís Caires, 2011).

Christos Papadimitriou and Harry Lewis: “Elements of the theory of computation”, Prentice-Hall, 1982, second edition 1997.

Método de ensino

O ensino está organizado em aulas teóricas e práticas. Existem notas escritas, que seguem de perto os conteúdos das aulas teóricas.

Nas aulas práticas os alunos discutem e resolvem exercícios propostos pelo docente, de uma lista predefinida. Nas aulas teóricas são apresentados os conceitos e discutidas situações problemáticas, em geral motivadas por desafios gerais de várias áreas da informática. Tipicamente as competências de saber fazer são também exercitadas nas aulas teóricas, de forma a aumentar a ligação entre os conceitos teóricos e a sua aplicação.

Método de avaliação

A UC tem duas componentes de avaliação, uma prática (P) e uma teorico-prática (T).

A componente P, para 2 valores da nota final, consiste na apresentação em aula prática da resolução de 2 exercícios. Cada apresentação tem uma classificação de 0, 0.5 ou 1 valores. As/Os alunas/os que tenham feito a avaliação prática no ano lectivo passado, mas não tenham aprovado, podem ficar com essa nota. Se fizerem alguma apresentação de exercício em aula prática, prescidem da nota da componente P obtida anteriormente.

A componente T consiste em 3 testes presenciais, valendo cada um 6 valores da nota final, ou no exame (a decorrer também presencialmente), valendo 18 valores da nota final. O primeiro teste é sem consulta. O 2º e o 3º teste (e as partes respectivas do exame) são com consulta (uma folha A4 manuscrita com apontamentos originais da/o aluna/o para cada teste). As 2 folhas usadas no exame só podem ter a matéria coberta nas partes relativas ao 2º e 3º testes (uma folha para cada parte).

A nota final (NF) é então calculada pela fórmula, arredondada às unidades, onde a nota de cada teste é arredondado às centésimas.

NF = P + 0,9xT

O exame pode ser realizado parcialmente, sendo feita apenas a parte correspondente a 1 ou a 2 testes. As partes não realizadas terão a nota dos testes deste ano lectivo que cobrem a matéria dessas partes.

A melhoria é apenas da componente T, mantendo-se a fórmula de cálculo da nota final. As/Os alunas/os que obtiveram aprovação este ano lectivo, podem melhorar a nota obtida em 1, 2 ou nos 3 testes. As/Os alunas/os que tenham obtido aprovação em anos lectivos anteriores devem fazer todo o exame e ficam com a nota da componente P obtida anteriormente, convertida para 2 valores.

Conteúdo

1. Modelação com Conjuntos e Lógica

Conjuntos, Funções, Relações (revisão). Finito e Infinito, argumento diagonal de Cantor. Diferença entre função e algoritmo. Definições indutivas. Modelos de sistemas simples e tipos abstractos de dados.

2. Máquinas, Autómatos e Especificações

O que é um modelo computacional? Automátos finitos deterministas e expressões regulares. Determinismo e não determinismo. Linguagens independentes de contexto e máquinas de pilha. Análise sintática (LL e LR).

3. Computabilidade

Complexidade básica (P,NP). Expressividade computacional. Equivalência entre programação funcional e imperativa. Máquinas abstractas e níveis de interpretação. Universalidade Turing. Tese de Church-Turing. Indecidibilidade (da terminação).


Cursos

Cursos onde a unidade curricular é leccionada: