433-255 Models of Computation

Note

When taken from School of Electrical Engineering and Computer Science, Faculty of Engineering: 7.1. When taken from Computer Science, Faculty of Science: 6.25

Credit Points

Coordinator

Prerequisites

433-141 and 433-142 or 433-162

Semester

Contact

Subject Description

The objective of this subject is for students: to be able to reason formally about the properties of simple specifications and programs; to be able to reason formally about simple models of computation; and to appreciate the variety of applications of discrete mathematical techniques in computer science.

Topics covered include: Sets and set operations, relations and functions. Logic, propositional and predicate calculus, and proof structures. Formal specification, refinement and program proof. Formal languages, grammars and recognisers. Models of computation: finite state machines, pushdown automata and Turing machines.

Assessment

One written examination not exceeding three-hours at the end of the subject. Project work, which is expected to take about 30 hours must be completed satisfactorily to pass the subject. Weighting of assessment components will be made known at the commencement of the subject