Teoria da Computação
Objetivos
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. Reconhecer linguagens decidíveis e semi-decidíveis.
Distinguir conjuntos contáveis de não contáveis. Modelar sistemas com autómatos finitos deterministas (DFAs) e não-deterministas (NFAs). 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 os limites de expressividade das linguagens e 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 - 70
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).
Notas de Teoria da Computação (João Ribeiro, 2024).
Christos Papadimitriou and Harry Lewis: “Elements of the theory of computation”, Prentice-Hall, 1982, second edition 1997.
Michael Sipser: "Introduction to the Theory of Computation", Cengage Learning, 2012, 3rd edition.
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 teórico-prática (T).
* A componente P, que não é obrigatória, é 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 cada aluna/o participou), apresentando ao docente em aula resoluções originais de alguns dos exercícios propostos.
- A componente P2 consiste na apresentação ao regente (em formato de discussão oral) da resolução detalhada de um exercício (1 valor) proposto pelo regente. Possíveis exercícios são os de provas de avaliação (testes ou exames) de anos lectivos passados. A realização desta prova acontece a pedido das/os alunas/os e decorre no período de aulas. 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.
A nota desta componente é dada por P = P1 + P2.
* A componente T consiste em 3 testes individuais presenciais (T1 a T3), ou num exame (Ex) a decorrer também presencialmente. Os testes e o exame são com consulta: uma página A4 manuscrita com apontamentos originais da/o aluna/o por teste - três no exame (uma por cada parte correspondente a cada teste), que deve ser entregue identificada com o número de estudante da/o aluna/o. As provas de avaliação na componente T são classificadas na escala de 0 a 20.
A nota desta componente é a média dos três testes ou a nota do exame, convertida para a escala 0-18, ou seja, T = 0.9*(T1 + T2 + T3)/3 ou T = 0.9*Ex. Para aprovar na UC é necessário T ser pelo menos 8.5.
Há pré-inscrição nos testes. Quando for divulgada a distribuição das/os estudantes pelas salas, será identificada uma sala onde quem não se inscreveu no teste talvez o possa realizar, de acordo com a seguinte regra: se 15 minutos após o início efetivo do teste, o número de estudantes não inscritos que pretendem realizar o teste tiver lugar na sala referida e existirem enunciados disponíveis, esses estudantes podem realizar o teste, não lhes sendo concedido tempo extra; se não existirem lugares ou enunciados para todos esses estudantes, nenhum realizará o teste.
* Nota final: A nota final (NF) é dada pela fórmula seguinte, sendo as notas de P e T arrendondadas às centésimas: NF = P + T. Para aprovar na UC é necessário que a nota NF seja maior ou igual a 9.5.
* Melhorias: A melhoria é apenas da componente T. A nota do exame substitui a obtida por testes nessa componente.
As/Os alunas/os que tenham obtido aprovação em anos lectivos passados devem fazer todo o exame e ficam com as notas das componentes P e TP obtidas nesse ano lectivo. 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 do referido acima, nem o uso de equipamentos electrónicos de qualquer espécie.
Durante uma prova de avaliação, um estudante não pode ter junto a si dispositivos electrónicos com capacidade de acesso à internet ou ligação bluetooth (e.g. smartphones, smartwatches, smartglasses, tablets, laptops, etc), ainda que desligados. A violação desta regra implica a reprovação liminar na unidade curricular por exclusão e será comunicada à Comissão Científica do respectivo Curso.
Conteúdo
1. Teoria de Conjuntos
Cardinalidade de conjuntos, conjuntos contáveis e não-contáveis, argumento diagonal de Cantor. Diferença entre função e algoritmo. Problemas de decisão e linguagens.
2. Máquinas, Autómatos e Especificações
O que é um modelo computacional? Automátos finitos 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). Máquinas de Turing.
3. Computabilidade
Universalidade Turing. Tese de Church-Turing. Indecidibilidade de problemas (e.g., terminação) e (semi-)decidibilidade de linguagens.