Currículo
Teoria da Computação L5103
Contextos
Groupo: EI PL - 2020 > 1º Ciclo > Unidades Curriculares Obrigatórias
ECTS
6.0 (para cálculo da média)
Objectivos
Concluída a disciplina o aluno deverá ser capaz de: O1. Interpretar e formular definições rigorosas; O2. Analisar consequências lógicas das definições; O3. Descrever vários modelos computacionais e assinalar as suas limitações. O4. Descrever linguagens através de gramáticas. O5. Resolver problemas computacionais utilizando os modelos computacionais aprendidos. O6. Manipular os formalismos aprendidos na construção de analisadores léxicos e sintácticos.
Programa
CP1. Notação matemática e técnicas de demonstração CP2. Autómatos Finitos e Linguagens Regulares CP3. Autómatos de Pilha e Linguagens Livres de Contexto CP4. Máquinas de Turing, Linguagens Recursivamente Enumeráveis e Tese de Church-Turing.
Método de Avaliação
Avaliação ao longo do semestre: 10 mini avaliações semanais online individuais (10%) e dois testes escritos (90 %), o primeiro a meio do semestre e o segundo coincidindo com o exame de 1ª época. Não existem notas mínimas de aprovação nos testes escritos. A presença nas aulas não é obrigatória. ou Exame final individual(100%) – 1ª época, 2ª época e Época Especial
Carga Horária
Carga Horária de Contacto -
Trabalho Autónomo - 95.0
Carga Total -
Bibliografia
Principal
- F. Santos, Teoria da Computação - Exercícios, ISCTE-IUL, 2015. F. Santos, Teoria da Computação - Folhas de Apoio, ISCTE-IUL, 2013. J. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, (3ª edição)2003, (4ª edição) 2011.:
Secundária
- D. Mandrioli e C. Ghezzi, Theoretical Foundations of Computer Science, John Wiley, 1987 J. Hopcroft, R. Motwani e J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley, 2001. N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge University Press, 1980. :