Search | Previous : 433-325 | Next : 433-332
Handbook 1997 : Faculty of Engineering : School of Electrical Engineering and Computer Science

433-330 Theory of Computation

Credit Points:

12.5

Coordinator:

Assoc. Professor E. Sonenberg

Prerequisite/s:

Computer Science 433-242, 433-243, 433-244 and 433-245 (from 1998: 433-253 and 433-255.)

Pre/Corequisite/s:

431-204 or 433-241 (From 1998: nil.)

Timetable:

Semester 1

Contact:

26 hours of lectures and approximately 17 hours of practice classes

Objectives:

On successful completion of this subject students should:

  • understand the limitations of computing, the relative power of formal languages and the inherent complexity of computational problems of practical importance;

  • 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.

Content:

A selection from: computability: recursive functions; Turing machines. Logic: clausal form; unification; resolution; Herbrand models; soundness and completeness of resolution; links with logic programming. 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.

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.
Search | Previous : 433-325 | Next : 433-332
Handbook 1997 : Faculty of Engineering : School of Electrical Engineering and Computer Science 
Status:                   OFFICIAL 1997
Last Modified:            Wednesday March 12 3:36 pm
SGML to HTML Conversion:  Information Technology Services
Authorised by:            Academic Registrar
Email Enquiries:          Course_Information@registrar.unimelb.edu.au
Copyright © University of Melbourne 1997.