433-255 Logic and Computation

From 2007 this subject will be offered in Semester 2 only.

433-172 Algorithmic Problem Solving or 433-152 Algorithmic Problem Solving (Advanced) or equivalent (prior to 2003, 433-141 Computing Fundamentals A).

The objectives of this subject are for students to be able to reason formally about the properties of simple specifications and programs; to be able to reason formally about simple models of computation; to appreciate the variety of applications of discrete mathematical techniques in computer science; and to gain working experience with a logic programming language.

Topics include logic: propositional and predicate calculus, proof structures; logic programming languages (Prolog); formal specification, refinement and program proof; and selected topics from the Chomsky hierarchy of languages, computability, and computational complexity.

• ability to apply knowledge of basic science and engineering fundamentals

• in-depth technical competence in at least one engineering discipline

• ability to undertake problem identification, formulation and solution

• capacity for independent critical thought, rational inquiry and self-directed learning

Project work during semester, expected to take about 36 hours (30%); and a 2-hour end-of-semester written examination (70%). To pass the subject, students must obtain at least 50% overall, 15/30 in project work, and 35/70 in the written examination.