Formal methods II
4 points * Two 1-hour lectures per week * First semester * Clayton * Prerequisites: CSC2030 and CSC2040
Objectives On completion of the subject students will have an understanding of intractability and its practical implications, elementary information theory and computer simulation techniques and will have the ability to prove that simple programs meet their formal specification.
Synopsis The topics covered include the following. Intractable problems: P, NP, and P-Space complexity classes; lower bound analysis; proving NP-completeness and approximate solutions to intractable problems. Information theory, in particular coding, together with a review of probability theory. Introduction to simulation of discrete stochastic processes and Monte Carlo methods, foundations for performing computer simulations. Formal specifications and proofs of correctness.
Assessment Examination (2 hours): 60% * Practical work: 40%
Recommended texts
Ross S M A course in simulation Macmillan, 1990
Hopcroft J E and Ullman J D Introduction to automata theory, languages and computation Addison-Wesley, 1979
| Published by Monash University, Clayton, Victoria
3168 Copyright © Monash University 1996 - All Rights Reserved - Caution Authorised by the Academic Registrar December 1996 |