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

Linguagens regulares ·         Autómatos finitos deterministas (AFD) e não-deterministas (AFN).  ·         Expressões regulares. Operações de união, concatenação e estrela para expressões regulares. Expressões regulares e linguagens regulares. ·         Lema de Bombeamento. Aplicação do Lema de Bombeamento. Linguagens livres de contexto ·         Gramáticas livres de contexto. Derivação. Árvore sintática. Linguagem gerada. Ambiguidade. Formas normais. Parsing. ·         Autómatos de pilha. Teoria da Computabilidade ·         Variantes de Máquinas de Turing e equivalência a modelo padrão. Máquinas enumeradoras.  A tese de Church-Turing. Decidibilidade ·         Linguagens decidíveis. O problema da paragem. Redução e seu uso em  indecidibilidade. Teorema de Rice. Complexidade temporal ·         As classes P e NP. NP-completude. Uso da redução em tempo polinomial para provas de NP-completude.  

Metodologia de 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

2018/2019 - 1 Semestre

2017/2018 - 1 Semestre

2016/2017 - 1 Semestre