Class Introduction to Computer Science

Use logic and set theory to model data and systems. Know the theoretical foundations of computing, the formal concept of algorithm and the existence of undecidable problems. Know the classes of formal languages, the associated computational models and their mutual relationship. Understand the universality principle of the Turing machine. Model system states with sets and 1st order logic. Distinguish between countable and non-countable sets. Model systems with finite automata (DFA and NFA). Build an automaton given a regular expression and its inverse. Build a DFA equivalent to an NFA. Define context-independent languages with grammars. Build LL and LR parsers.  

Not applicable

Description of contents: Modeling with Sets and Logic Review of sets, functions, relations and 1st order logic applied to systems modeling. Automata and Formal Languages Study of DFA, NFA, regular expressions, context-free grammars and stack automata. Computability Turing machines, decidable and undecidable problems, Church-Turing thesis and reductions. Complexity Classes P, NP, NP-completeness and analysis of the difficulty of computational problems.

Innovative methodologies are used that integrate interactive tools into the learning process, such as a state machine editor and the implementation of a state machine in JavaScript. These approaches allow students to experiment, simulate and validate formal models, promoting active learning and the link between theory and practice.

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