Disciplina Curricular
Teoria da Computação TComput
Licenciatura Bolonha em Matemática - 4_LMat 2022/23
Contextos
Grupo: 4_LMat 2022/23 > 1º Ciclo > Licenciatura em Matemática ou Minor > Licenciatura em Matemática > Opcionais 3º Ano > 108_Opção B (CMAT/CEI)
Período:
Peso
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étodos de ensino e avaliação
Avaliação contínua (3 testes, valendo cada um 1/3 da nota final) OU Exame final