CSC3050

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 elementary information theory and computer simulation techniques, intractability and its practical implications, and will have the ability to prove that simple programs meet their formal specification.

Synopsis Information theory: in particular coding, together with a review of probability theory. Introduction simulation of discrete stochastic processes and Monte Carlo methods, foundations for performing computer simulations. Intractable problems: P, NP, and P-Space complexity classes; lower bound analysis; proving NP-completeness and approximate solutions to intractable problems. Formal specifications and proofs of correctness.

Assessment Examination (2 hours): 60%
* Assignments: 40%

Recommended texts

Ross S M A course in simulation 2nd edn Academic Press, 1997
Hopcroft J E and Ullman J D Introduction to automata theory, languages and computation Addison-Wesley, 1979