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
Formalmente não se exige a aprovação a nenhuma outra UC, mas os conhecimentos e competências transmitidos em Lógica Computacional e em Matemática Discreta são essenciais.
Bibliografia
Notas de Teoria da Computação (Luís Caires, 2015).
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 três componentes de avaliação, uma prática (P), uma teorico-prática (TP) e uma teórica (T). Todas as provas de avaliação são classificadas na escala de 0 a 20.
A componente P, para um valor da nota final, consiste na participação nas aulas práticas, apresentando ao docente uma resolução original de alguns dos exercícios propostos. O registo de presenças é feito no início das aulas.
A componente TP consiste em 4 mini-testes presenciais de resposta múltipla, sem consulta, contando cada um com um valor para a nota final.
A componente T consiste em 2 testes presenciais, valendo cada um 7,5 valores da nota final, ou num exame (a decorrer também presencialmente), valendo 15 valores da nota final. Os testes e o exame são com consulta: uma folha A4 manuscrita com apontamentos originais da/o aluna/o por teste - duas no exame (uma por cada parte correspondente a cada teste), que deve ser entregue identificada. Para aprovar na UC a nota obtida nesta componente T (seja no exame, seja na média dos testes) é de 9,5.
A nota final (NF) é então calculada pela fórmula, arredondada às unidades, onde a nota de cada mini-teste, teste e componente, é arredondado às centésimas.
NF = P + TP + 0,75xT
O exame pode ser realizado parcialmente, sendo feita apenas a parte correspondente a um dos testes. Na parte não realizada terão a nota do teste deste ano lectivo que cobre a matéria dessa parte.
A melhoria é apenas da componente T. Esta é a nota do exame ou a de um teste deste ano lectivo somada a uma das partes do exame. As/Os alunas/os que obtiveram aprovação este ano lectivo, podem melhorar a nota obtida em um dos testes, mantendo a fórmula de cálculo da nota final ou prescindindo da nota dos mini-testes, sendo nesse caso a nota final (NFM) calculada pela fórmula abaixo.
NFM = P + 0,95T
As/Os alunas/os que tenham obtido aprovação em anos lectivos anteriores devem fazer todo o exame e ficam com as notas das componentes P e TP obtidas no ano lectivo em que aprovaram. Para cálculo da nota final, aplica-se a fórmula do ano passado.
Nas provas escritas não é autorizado o uso de quaisquer materiais de consulta além das folhas manuscritas originais referidas, nem o uso de equipamentos electrónicos de qualquer espécie.
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).