Handbook 1996 : Faculty of Engineering (Volume 4 page 106)
Computer Science subject : Next:433-332 | Prev:433-325 | Search | Help
433-330 "Theory of Computation" appears differently in several places - choose the one you want:
1. Computer Science, Faculty of Engineering (v4, p106) : Next:433-332 | Prev:433-325
Credit points: 12.5
Coordinator: Assoc. Prof. E. Sonenberg
Prerequisite: Computer Science 433-241 or Electrical Engineering 431-204, Computer Science 433-242, 433-243, 433-244 and 433-245
Contact: 26 hours of lectures and approximately 17 hours of practice classes
Timetable: Second semester
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.
1. Computer Science, Faculty of Engineering (v4, p106) : Next:433-332 | Prev:433-325
2. Computer Science, Faculty of Science (v4, p183) : Next:433-332 | Prev:433-325
Credit points: 12.5
Coordinator: Assoc Prof E Sonenberg.
Prerequisite: Computer Science 433-241 or Electrical Engineering 431-204, Computer Science 433-242, 433-243, 433-244 and 433-245
Contact: 26 lectures and approximately 17 hours of practice classes
Timetable: Second semester
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.
* Note that CONTACT, COORDINATOR, OBJECTIVES differs from the maintainer's version above. A log of variations is available.
2. Computer Science, Faculty of Science (v4, p183) : Next:433-332 | Prev:433-325
Status: Official 1996 Date created: Oct 9 1995 Last modified: Oct 9 1995 Authorised by: Academic Registrar Email enquiries: Course_Information@registrar.unimelb.edu.au
Maintained by: Dept. of Computer Science, Faculty of Engineering.
Copyright © University of Melbourne 1995,1996.