433-330 Theory of Computation

Credit Points

Coordinator

Prerequisites

433-253 and 433-255

Semester

Contact

Subject Description

The objective of this subject is for students: to understand the limitations of computing, the relative power of formal languages and the inherent complexity of computational problems of practical importance; and to be familiar with standard tools and notation for formal reasoning about computational models such as propositional logic, first order predicate logic, fixpoint theory, and lambda calculus.

Topics covered include: A selection from: Computability: recursive functions; Turing machines. Logic: clausal form; unification; resolution; Herbrand models; soundness and completeness of resolution; links with logic programming; modal logics for computer science applications. Formal languages; Chomsky hierarchy; theory of lexical analysers and parsers. Complexity: the classes P and NP; NP-complete problems. Other topics: lattices; operators and fixpoints; information and coding theory; cryptography; lambda calculus.

Assessment

Up to three-hours of written examinations at the end of the subject. Project work, which is expected to take about 36 hours, must be completed satisfactorily to pass the subject. Weighting of assessment components will be made known at the commencement of the subject