To instill an appreciation of the importance of program complexity, and develop an ability to differentiate between alternative solutions to a given problem, to to reconise computationally intractable problems; to make the student cognisant of the parallels between finite automata and programs, and the ability to identify undecidable problems; to provide a grounding in formal specification languages, and an appreciation of their importance in software development.
Complexity Theory
Measures of complexity and asymptotic analysis. Recognising intractable problems and limits of Computation. Complexity classes P and NP. NP-Completeness and reducibility. Graph theory and graph algorithm applications.
Formal Specifications and Mathematical Techniques
Specification of Set operations, Relations and Functions; Mathematical proofs. Strings and languages. Propositional and predicate calculus;
Automata and Language Theory
Finite State Machines; Regular Languages and Expressions; The pumping lemma for regular languages. Context-free languages, pushdown automata. The Pumping Lemma for Context-free languages. Decidability: Decidable and undecidable languages.
Models of Computation
Turing Machines; Decision Problems; The Church-Turing Thesis and its implications; The recursion Theorem. Case Studies (example: the Halting Problem).
| Module Content & Assessment | |
|---|---|
| Assessment Breakdown | % |
| Other Assessment(s) | 40 |
| Formal Examination | 60 |