Programa

Teoria da Computação

Licenciatura Bolonha em Engenharia Informática

Licenciatura Bolonha em Tecnologias de Informação

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.