Disciplina Curricular

Teoria da Computação TComput

Licenciatura Bolonha em Engenharia Informática - 3_Plano 2015/16

Contextos

Grupo: 3_Plano 2015/16 > 1º Ciclo > 3º Ano

Período:

Peso

6.0 (para cálculo da média)

Objectivos

Pretende-se que o aluno compreenda: como se podem representar problemas reais utilizando modelos computacionais abstratos; as capacidades e limitações relativas dos vários modelos; as relações entre linguagens e modelos; o conceito "ser reconhecível" (uma dada linguagem é ou não é reconhecível por um determinado modelo); o conceito de "ser derivável"; o conceito de parsing; que há linguagens que são indecidíveis; o conceito de complexidade de um problema, conseguindo determinar a complexidade de alguns problemas; e, finalmente, a diferença entre tratável e intratável.

Programa

1. Modelos de computação para: 1.1 Linguagens regulares: 1.1.1 Autómatos finitos: Autómatos finitos deterministas (DFA) e não-deterministas (NDFA). Definição formal e representação em forma de diagrama. Definição de computação. Linguagem reconhecida por um autómato finito. Equivalência DFA e NDFA. 1.1.2 Expressões regulares: operações de união, concatenação e fecho de Kleene para expressões regulares. Expressões regulares e linguagens regulares. Equivalência com os autómatos. 1.1.3 Lema de Bombeamento: Prova e aplicação do Lema de Bombeamento. Como demonstrar que há linguagens não regulares. 1.2 Linguagens livres de contexto. 1.2.1 Gramáticas livres de contexto: Definição formal; noção de derivação; Árvore sintática. Linguagem gerada. Ambiguidade. Formas normais. 1.2.2 Autómatos de pilha: Noção de PDA; computação num PDA; Derivação; Equivalência às CFG. 1.3 Linguagens computáveis: 1.3.1 Máquinas de Turing: Definição e variantes de Máquinas de Turing (e.g.: deterministas e não deterministas). Equivalência ao modelo padrão. Criação de máquinas de Turing. Computação numa MT. Máquinas enumeradoras. Descrição de alto nível. 1.3.2 A tese de Church-Turing. 2 Decidibilidade: 2.1 Noção de decidibilidade (ou computável ou recursiva) e semi-decidibilidade (ou reconhecível ou recursivamente enumerável). Diferenças entre decidibilidade e semi-decidibilidade; 2.2 Linguagens decidíveis e reconhecíveis. 2.3 Indecidibilidade e o problema da paragem e suas variações. 2.4 Noção de redução entre problemas e e seu uso em indecidibilidade. 2.5 O Teorema de Rice. 3. Complexidade 3.1 Noções de complexidade: temporal e espacial; 3.2 Avaliar a complexidade; 3.3 Classes de complexidade temporal: a classe $P$ dos problemas com resolução eficiente; a classe $NP$ dos problemas com uma solução verificável; a classe dos Problemas $NP$ difíceis e $NP$ completos; a questão $P$ vs $NP$ e implicações; reduções polinomiais;

Métodos de ensino e avaliação

Aulas teóricas de exposição da matéria e aulas teórico-práticas de resolução de exercícios. Avaliação contínua (2 valores); exame escrito final (18 valores) ou três testes parcelares (18 valores).

Disciplinas Execução

2020/2021 - 1º semestre

2019/2020 - 1 Semestre

2018/2019 - 1 Semestre

2017/2018 - 1 Semestre

2016/2017 - 1 Semestre