Plano de Estudos
Teoria da Computação TComput
Contextos
Groupo: 5_LMat 2026/27 > 1º Ciclo > Matemática ou Matemática com Minor - 3º Ano > Licenciatura em Matemática > Optativas > 1212 - LMat - Opção B - 1ºSem (CMAT/CEI)
ECTS
6.0 (para cálculo da média)
Objectivos
Pretende-se que o aluno: 1. seja capaz de representar problemas reais utilizando modelos computacionais abstratos (autómatos finitos deterministas e não deterministas, gramáticas livres de contexto, máquinas de Turing); 2. seja capaz de identificar as capacidades e limitações dos vários modelos computacionais; 3. compreenda processos simples de análise sintática; 4. seja capaz de classificar um problema como “Turing-reconhecível” ou “Turing-decidível”; 5. compreenda e seja capaz de avaliar a complexidade de um problema e a diferença entre problemas tratáveis e intratáveis.
Programa
Linguagens regulares: Autómatos finitos deterministas (DFA) e não-deterministas (NFA). Def. formal e representação diagramática. Def. de computação. Linguagem reconhecida por um autómato finito. Equivalência entre DFAs e NFAs. Expressões regulares. Operações regulares. Lema do Bombeamento. Linguagens livres de contexto: Gramáticas livres de contexto. Derivação. Árvore sintática. Linguagem gerada. Ambiguidade. Formas normais. Autómatos de pilha. Análise sintática. Lema do Bombeamento. Teoria da Computabilidade: Máquinas de Turing. Variantes de Máquinas de Turing e equivalência ao modelo padrão. A tese de Church-Turing. Linguagens computáveis (decidíveis). O problema da paragem. Noção de redução entre linguagens e seu uso em (in)decidibilidade. Teorema de Rice. Teorema da Recursão. Teoria da Complexidade: Definição formal. Classes de complexidade. As classes P e NP. NP-completude. Uso da redução em tempo polinomial para provas de NP-completude.
Método de Avaliação
Exame (E) (obrigatório) + Questões de aula (QA) (opcionais) Exame: realiza-se em data anunciada pela faculdade. Questões de aula: realizam-se durante as aulas TP. Condições de aprovação: Nota do exame >= 9.5. Cálculo da nota final: NF = if(E≥9.5, max(E, 0.9*E +0.1*QA), E)
Carga Horária
Carga Horária de Contacto -
Trabalho Autónomo - 119.0
Carga Total -
Bibliografia
Principal
- Introduction to the Theory of Computation: Michael Sipser 2013 ISBN 978-113-318-781-3
Secundária
- Elements of the theory of computation: Harry Lewis, Christos Papadimitriou 1997 ISBN 978-013-262-478-7
- Introduction to Automata Theory, Languages and Computation: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman 2001 ISBN 020-144-124-1
- Languages and Machines: Thomas Sudkamp 2006 ISBN 032-131-534-0