goto UNSW home page  
Contacts Library myUNSW WebCT
Theory of Computation - COMP4141
PRINT THIS PAGE
UNSW Computing
 
Faculty: Faculty of Engineering
 
 
School:  School of Computer Science and Engineering
 
 
Course Outline: http://www.cse.unsw.edu.au/~cs4141
 
 
Campus: Kensington Campus
 
 
Career: Postgraduate
 
 
Units of Credit: 6
 
 
EFTSL: 0.125 (more info)
 
 
Contact Hours per Week: 4
 
 
Enrolment Requirements:
 
 
Prerequisite: COMP9024 or enrolment in MIT program 8684 or GradCert program 7344.
 
 
Fee Band: 2 (more info)
 
 
Further Information: See Class Timetable
 
 

Description

Computability: formal languages and problems, Turing Machines (TMs), computability, (semi-)decidability, universal TMs, Church-Turing thesis, halting problem, reduction and undecidability proofs, examples; Complexity: run time, space, complexity classes, non-determinism and NP, polynomial reductions and NP completeness, optimisation problems and approximation, randomisation; Languages and Automata: regular expressions and languages, finite automata, determinisation, context-free grammars and languages (CFLs), Chomsky normal form, word problems, pumping lemma, push-down automata, decidability problems for CFLs; Semantics and Correctness: while programs, assertions and program correctness, Hoare logic, loops and loop invariants, relative completeness of Hoare logic (and its role in a proof of Goedel's incompleteness result).

Further Information

URL for this page:

© The University of New South Wales (CRICOS Provider No.: 00098G), 2004-2011. The information contained in this Handbook is indicative only. While every effort is made to keep this information up-to-date, the University reserves the right to discontinue or vary arrangements, programs and courses at any time without notice and at its discretion. While the University will try to avoid or minimise any inconvenience, changes may also be made to programs, courses and staff after enrolment. The University may also set limits on the number of students in a course.