Teoria da Computação

Conhecimentos de Base Recomendados

Lógica, estruturas discretas, álgebra, análise matemática, programação, Inglês

Métodos de Ensino

 2h por semana de aulas teóricas em anfiteatro, 1 h por semana de teórico-prática em anfiteatro, 2h por semana para resolver problemas em aula laboratorial a pequenos grupos.

Resultados de Aprendizagem

Estudar os diversos tipos de autómatos (finitos, de pilha, Máquinas de Turing) e de gramáticas formais (regulares, independentes e dependentes do contexto, recursivas) e as relações entre eles, bem como sua relação com linguagens de programação e compiladores. São conhecimentos estruturantes da informática enquanto disciplina científica que desenvolvem a capacidade mental para acompanhar a evolução presente e futura da informática e computação. Também os diversos modelos de computação desenvolvidos no passado são comparativamente abordados. Introduz-se a teoria da complexidade, em torno da noção de Turing-computabilidade, para mostrar os atuais limites da computação.

Adquirir competências em análise e síntese, comunicação escrita, conhecimentos de informática relativos ao âmbito do estudo, resolução de problemas, raciocínio crítico, aprendizagem autónoma, aplicação prática de conhecimentos teóricos, criatividade.

Estágio(s)

Não

Programa

1. Introdução e definições básicas: linguagens, gramáticas, autómatos.

2. Autómatos finitos determinísticos e não-determinísticos e suas relações. Transdutores.

3. Linguagens regulares, gramáticas regulares, expressões regulares, autómatos finitos e suas relações.

4. Propriedades das linguagens regulares, lema da bombagem.

5. Linguagens livres de contexto não-regulares, parsing.

6 Simplificação das gramáticas livres de contexto, formas normais.

7. Autómatos de Pilha não-determinísticos e determinísticos.

8. Propriedades das linguagens livres de contexto (fecho, lemas da bombagem).

9. Máquinas de Turing padrão, tese de Turing,

10. Outros modelos de Máquinas de Turing, autómatos linearmente limitados.

11 Hierarquias de linguagens formais e autómatos.

12. Limites da computação algorítmica.

13. Outros modelos de computação (funções recursivas, Post, rescrita, cálculo-lambda).

14. Uma introdução à teoria da complexidade, problemas P e NP.

Docente(s) responsável(eis)

Pedro Manuel Henriques da Cunha Abreu

Métodos de Avaliação

Avaliação
Frequência: 100.0%

Avaliação Final
Exame: 100.0%

Bibliografia

An Introduction to Formal Languages and Automata, Peter Linz, 5th Ed., Jones and Bartlett Learing, 2012

Models of Computation and Formal Languages, R. Gregory Taylor, Oxford University Press, 1998.

Introduction to Automata Theory, Languages and Computation, 2nd   Ed., John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Addison Wesley, 2001.

Elements for the Theory of Computation, Harry Lewis and Christos Papadimitriou, 2nd Ed., Prentice Hall, 1998.

Introduction th the Theory of Computation, Michael Sipser, PWS Publishing Co, 1997.

Sítios web diversos a indicar nas aulas