Skip to main content
Unit of study_

COMP2022: Models of Computation

This unit provides an introduction to the foundations of computing. The main aims are to introduce and compare different models of computation based on state-machines, grammars and algebra, and logic.

Code COMP2022
Academic unit Computer Science
Credit points 6
Prerequisites:
? 
INFO1103 OR INFO1903 OR INFO1113
Corequisites:
? 
None
Prohibitions:
? 
COMP2922
Assumed knowledge:
? 
(MATH1004 OR MATH1904 OR MATH1064 OR MATH2069 OR MATH2969) AND (INFO1105 OR INFO1905 OR COMP2123 OR COMP2823)

At the completion of this unit, you should be able to:

  • LO1. demonstrate a knowledge of basic discrete mathematics, theorems and formal proofs
  • LO2. demonstrate an understanding of propositional logic
  • LO3. demonstrate an understanding of propositional logic as a model of facts and of reasoning
  • LO4. demonstrate an ability to use languages/tools for propositional logic
  • LO5. demonstrate an understanding of predicate logic
  • LO6. demonstrate an understanding of predicate logic as a model of facts and of reasoning
  • LO7. demonstrate an understanding of a formal language as a set of strings, and of operations on formal languages, in particular union, concatenation, and Kleene closure
  • LO8. demonstrate an ability to use regular languages and their representations by DFAs, NFAs, regular expressions, and regular grammars
  • LO9. demonstrate an ability to use context-free grammars or pushdown automata as a model of formal languages
  • LO10. demonstrate an awareness of the Chomsky hierarchy, and the notions of decidability and intractability
  • LO11. demonstrate an awareness of universal models of computation, e.g., Turing machines, the lambda calculus and its application to functional programming

Unit outlines

Unit outlines will be available 2 weeks before the first day of teaching for the relevant session.