Teoria da Computação
Ano Letivo: 2015/16
Departamento: Informática
Carga horária: T: 2:00 h; TP: 1:30 h; OT: 2:00 h;
Área Científica: Informática;
Objetivos da Unidade Curricular
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.
Pré-requisitos
- Linguagens Formais e Autómatos (26729)
Conteúdos
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.
Descrição detalhada dos conteúdos programáticos
Componente Teórica
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.
Componente Teórica-Prática
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.
Componente Prática
NA
Bibliografia
Recomendada
Sipser, Michael, 2007, Introdução à Teoria da Computação, São Paulo: Thomson, isbn 978-85-221-0499-4.
tradução portuguesa de:
Sipser, Michael, 2004, Introduction to the Theory of Computation, 2ª edição, Boston: Thomson, isbn 978-0-6192-1764-8 (cota 2476, Biblioteca DIFCUL).
Outros elementos de estudo
Slides e outro material de apoio às aulas teóricas e teórico-práticas.
Manual para parsing:
Sudkamp, Thomas, 2006, Languages and Machines, 3ª edição, Boston: Addison-Wesley, isbn 0-321-32221-5 (cota2048, biblioteca DIFCUL).
Métodos de Ensino
Aulas teóricas de exposição da matéria e aulas teórico-práticas de resolução de exercícios.
Métodos de Avaliação
Avaliação contínua (2 valores); exame escrito final ou três testes parcelares (18 valores).
Língua de ensino
Português