Ficha Unidade Curricular (FUC)
Informação Geral / General Information
Carga Horária / Course Load
Área científica / Scientific area
Ciências e Tecnologias da Programação
Departamento / Department
Departamento de Ciências e Tecnologias da Informação
Ano letivo / Execution Year
2020/2021
Pré-requisitos / Pre-Requisites
Nenhum
Objetivos Gerais / Objectives
Aprendizagem de modelos computacionais (desde autómatos finitos às máquinas de Turing), sua utilização na resolução de problemas e estudo das suas limitações.
Objetivos de Aprendizagem e a sua compatibilidade com o método de ensino (conhecimentos, aptidões e competências a desenvolver pelos estudantes) / Learning outcomes
Concluída a disciplina o aluno deverá ser capaz de: 1. Interpretar e formular definições rigorosas; 2. Analisar consequências lógicas das definições; 3. Descrever vários modelos computacionais e assinalar as suas limitações. 4. Descrever linguagens através de gramáticas. 5. Resolver problemas computacionais utilizando os modelos computacionais aprendidos. 6. Manipular os formalismos aprendidos na construção de analisadores léxicos e sintácticos.
Conteúdos Programáticos / Syllabus
I Notação matemática e técnicas de demonstração Objectos matemáticos básicos: conjuntos, funções, relações e linguagens; Lógica, demonstrações e o princípio de indução matemática. II Autómatos Finitos e Linguagens Regulares Linguagens regulares e expressões regulares. Autómatos finitos deterministas e não deterministas. Reconhecimento de linguagens regulares. III Autómatos de Pilha e Linguagens Livres de Contexto Linguagens livres de contexto e gramáticas livres de contexto. Autómatos de pilha. Reconhecimento de linguagens livres de contexto. IV Máquinas de Turing e Linguagens Recursivamente Enumeráveis Linguagens Recursivamente Enumeráveis. Máquinas de Turing. Tese de Church-Turing.
Demonstração da coerência das metodologias de ensino e avaliação com os objetivos de aprendizagem da UC / Evidence that the teaching and assessment methodologies are appropriate for the learning outcomes
Objectivos de aprendizagem - Conteúdos programáticos 1 - I, II, III; 2 - I; 3 - II, III, IV; 4 - III; 5 - II, III, IV; 6 - III;
Avaliação / Assessment
I Avaliação periódica: 10 mini avaliações semanais online (10%) e duas frequências (90 %). Na avaliação periódica é obrigatório efetuar no mínimo 7 mini avaliações online. A presença nas aulas não é obrigatória. ou II Exame final. A presença nas aulas não é obrigatória.
Metodologias de Ensino / Teaching methodologies
Aulas teorico-práticas.
Demonstração da coerência das metodologias de ensino e avaliação com os objetivos de aprendizagem da UC / Evidence that the teaching and assessment methodologies are appropriate for the learning outcomes
As aulas teórico-práticas têm como objectivo desenvolver a capacidade de utilização, interpretação e análise dos modelos computacionais estudados, i.e. os objectivos de aprendizagem propostos. Começa-se por dar uma ideia intuitiva dos conceitos e discute-se a sua formulação. As consequências lógicas das definições são estudadas com a participação dos alunos. Segue-se um conjunto de exemplos e exercícios.
Observações / Observations
Devido à atual situação provocada pela COVID-19, o processo de avaliação poderá sofrer algumas adaptações, que serão comunicadas oportunamente, caso tal venha a ser necessário.
Bibliografia Principal / Main Bibliography
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.
Bibliografia Secundária / Secondary Bibliography
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.
Data da última atualização / Last Update Date
2024-02-16