SFT3302

Formal methods 2

Not offered in 1998

H Schmidt

4 points
* 3 hours per week
* Second semester
* Caulfield
* Prerequisites: CSC2030

Objectives At the completion of this subject students should understand the principal data types used in computing, together with their associated algorithms; be able to use the main algorithm design, specification and analysis techniques; and have the skills to model, describe and reason about software artifacts and processes.

Synopsis The importance of formal methods and formal specifications in the development of software. Using predicate logic and set theory to codify statements about software properties. Varieties of formal specifications. Model-based formal specification, eg Z, LOTOS. Algebraic/logical specification, eg OBJ3. Object-oriented formal specifications. Case studies in formal specification. Specifying abstract data types using formal specification. Step-wise refinement - refining high-level specifications into algorithms and data structures. Reasoning. Information theory. Main algorithm design techniques. Analysing the complexity of algorithms. Using approximate algorithms. Review of important algorithms.

Assessment Examination: 50%
* Assignments: 50%
* Unit test: 10%

Recommended texts

Brassard G Algorithmics: Theory and practice Prentice-Hall, 1988
Cormen T H and others Introduction to algorithms MIT Press, 1990
Diller A Z: An introduction to formal methods 2nd edn, Wiley, 1994
Dorfman M and Thayer R H Guidelines and examples on systems and software requirement engineering IEEE Computer Society Press, 1990
Guttag H The algebraic specification of abstract data types Acta Informatica 10, pp 27-52, 1978
Harel D Algorithmics: The spirit of computing 2nd edn, Addison-Wesley, 1992
Horowitz E and Sahni S Fundamentals of computer algorithms Pitman, 1978
Potter B and others An Introduction to formal specifications and Z Prentice-Hall, 1991
Wordsworth J B Software development with Z Addison-Wesley, 1992