Disciplina Introdução às Ciências da Computação

Usar a lógica e a teoria de conjuntos para modelar dados e sistemas. Conhecer os fundamentos teóricos da computação, o conceito formal de algoritmo e a existência de problemas indecidíveis. Conhecer as classes de linguagens formais, os modelos computacionais associadas e a sua relação mútua. Entender o princípio da universalidade da máquina de Turing. Modelar estados de sistemas com conjuntos e lógica de 1º ordem. Distinguir conjuntos contáveis de não contáveis. Modelar sistemas com autómatos finitos (DFA e NFA). Construir um autómato dada uma expressão regular e o inverso. Construir um DFA equivalente a um NFA. Definir linguagens independentes de contexto com gramáticas. Construir analisadores LL e LR. 

Não aplicável

Descrição dos conteúdos Modelação com Conjuntos e Lógica Revisão de conjuntos, funções, relações e lógica de 1ª ordem aplicadas à modelação de sistemas. Autómatos e Linguagens Formais Estudo de DFA, NFA, expressões regulares, gramáticas livres de contexto e autómatos de pilha. Computabilidade Máquinas de Turing, problemas decidíveis e indecidíveis, Tese de Church-Turing e reduções. Complexidade Classes P, NP, NP-completude e análise da dificuldade de problemas computacionais.

São utilizadas metodologias inovadoras que integram ferramentas interativas no processo de aprendizagem, como um editor de máquinas de estados e a implementação de uma máquina de estados em JavaScript. Estas abordagens permitem aos estudantes experimentar, simular e validar modelos formais, promovendo uma aprendizagem ativa e a ligação entre teoria e prática.

Wayne Goddard, "Introducing the Theory of Computation", 1st Edition, Jones & Bartlett Publishers, 2010, ISBN: 9789380108254