Search : Index : Faculty of Engineering : School of Electrical Engineering and Computer Science
Prev 433-313 Computer Design
Next 433-332 Operating Systems
433-330 Theory Of Computation | |
Credit Points | 12.5 |
Coordinator | Dr Harald Sondergaard |
Prerequisites | 433-253 and 433-255 |
Semester | 1 (view timetable) |
Contact | 24 hours of lectures and approximately 17 hours of practice classes |
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 | Project work (expected to take about 36 hours) during semester; and one written examination (not exceeding three hours) at the end of the semester. The project work must be completed satisfactorily to pass the subject. Weighting of assessment components will be advised at the commencement |
Search : Index : Faculty of Engineering : School of Electrical Engineering and Computer Science
Prev 433-313 Computer Design
Next 433-332 Operating Systems
Status: Official 1999 Last Modified: Tuesday October 20 11:50 SGML to HTML Conversion: Information Technology Services Authorised by: Academic Registrar Email Enquiries: Course_Information@registrar.unimelb.edu.au