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, João Miguel Lourenço Ribeiro
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 teórico-prática (TP), e uma teórica (T).
* A componente P é dividida em duas componentes, P1 e P2:
- A componente P1 consiste na participação activa nas aulas práticas (1 valor, em proporção directa com o número de aulas práticas em que o aluno participou), apresentando ao docente uma resolução original de alguns dos exercícios propostos.
- A componente P2 consiste na apresentação ao regente (em formato de discussão oral) de certos tópicos de teoria da computação não discutidos em aula (1 valor). Uma lista de possíveis tópicos será apresentada durante o semestre, e os alunos podem também propor outros tópicos do seu interesse, sujeitos a aprovação pelo regente.
A nota desta componente é dada por P = P1 + P2.
* A componente TP consiste em 2 mini-testes à distância de resposta múltipla (MT1 e MT2), sem consulta, contando cada um com 0,5 valores para a nota final. A nota desta componente é calculada através de TP = 0.5*MT1 + 0.5*MT2.
* A componente T consiste em 2 testes presenciais (T1 e T2), ou num exame (Ex) a decorrer também presencialmente. Os testes e o exame são sem consulta. 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 nota desta componente é calculada através de T = 0.5*T1 + 0.5*T2 ou T = Ex. Para aprovar na UC é necessário T ser pelo menos 9.5.
As provas de avaliação nas componentes TP e T são classificadas na escala de 0 a 20.
* Nota final: A nota final (NF) é o máximo entre as seguintes quantidades (as notas de P, TP, e T são arrendondadas às centésimas):
T,
0.95*T + 0.05*TP,
0.9*T + 0.05*TP + P.
Se NF ultrapassar 20, o aluno ficará com nota de 20 valores.
* Melhorias: 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.
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, nem o uso de equipamentos electrónicos de qualquer espécie.
Na componente P1 não há restrições de consulta de material nem de uso de ferramentas de IA tal como ChatGPT.
Na componente P2 não há restrições de consulta de material nem de uso de ferramentas de IA tal como ChatGPT na preparação da discussão oral. Durante a discussão oral não é autorizado o uso de quaisquer materiais de consulta 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).