Teoria da Computação
2
2012-2013
01000142
Informática
Português
Presencial
Semestral
6.0
Obrigatória
1º Ciclo - Licenciatura
Conhecimentos de Base Recomendados
Lógica, estruturas discretas, álgebra, análise matemática, programação;Inglês.
Métodos de Ensino
Aulas teóricas (2h semanais): apresentação e discussão, com meios audiovisuais e recurso a demonstrações computacionais quando apropriado. Resolvem-se também exemplos.
Aulas Teórico-práticas (1 h semanal): resolução de exercícios, extraídos de uma folha de problemas fornecida cada semana.
Aulas Práticas Laboratoriais (2h semanais): apoio complementar na resolução de exercícios e para a resolução de desafios temáticos.
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 torna da noção de Turing-computabilidade, para mostrar os atuais limites da computação.
Aquisição de competências em análise e síntese, comunicação escrita, conhecimentos de informáticar elativos 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ãoPrograma
Cap.1.Introdução e definições básicas: linguagens, gramáticas, autómatos.
Cap.2.Autómatos finitos determinísticos e não-determinísticos e suas relações. Transdutores.
Cap.3.Linguagens regulares, gramáticas regulares, expressões regulares, autómatos finitos e suas relações.
Cap.4.Propriedades das linguagens regulares, lema da bombagem.
Cap.5.Linguagens livres de contexto não-regulares, parsing.
Cap.6 Simplificação das gramáticas livres de contexto, formas normais.
Cap.7.Autómatos de Pilha não-determinísticos e determinísticos.
Cap.8 Propriedades das linguagens livres de contexto (fecho, lemas da bombagem).
Cap.9 Máquinas de Turing padrão, tese de Turing,
Cap.10 Outros modelos de Máquinas de Turing, autómatos linearmente limitados.
Cap.11 Hierarquias de linguagens formais e autómatos.
Cap.12. Limites da computação algorítmica.
Cap.13. Outros modelos de computação (funções recursivas, Post, rescrita, cálculo-lambda).
Cap.14. Uma introdução à teoria da complexidade, problemas P e NP.
Docente(s) responsável(eis)
António Dourado Pereira Correia
Métodos de Avaliação
Avaliação
- 4 Questionários (facultativos): 2,5% (cada) (contribuindo para a nota dos testes) - 2 Testes: 20% (cada) - 1 Exame: 60% (mínimo: 50% ou 9,5/20): 100.0%
Bibliografia
An Introduction to Formal Languages and Automata, Peter Linz, 3rd Ed., Jones and Bartelett Computer Science, 2001
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 the Theory of Computation, Michael Sipser, PWS Publishing Co, 1997.