Overview
Offerings
Rules
Contacts
Chief Examiner(s)
Unit Coordinator(s)
Notes
IMPORTANT NOTICE:
Scheduled teaching activities and/or workload information are subject to change in response to COVID-19, please check your Unit timetable and Unit Moodle site for more details.
Students who have not done one of the programming units specified are encouraged to consult the Chief Examiner regarding possible approval to enrol in this unit.
Learning outcomes
Use propositional logic, predicates and quantifiers to represent and analyse problems in the theory of computation;
Construct Finite Automata, Nondeterministic Finite Automata and Context-Free Grammars to describe languages;
Convert Regular Expressions into Finite Automata and vice versa;
Find a Regular Grammar for a Regular Language;
Find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
Use Turing Machines to describe languages and represent computable functions;
Demonstrate the limitations of the models of computation considered;
Show a language is not regular, or not context-free, or not decidable;
Show that a language is in P, or in NP, or NP-complete;
Write rigorous formal proofs, including proofs by construction, cases, contradiction and induction.
Teaching approach
Assessment
Scheduled and non-scheduled teaching activities
Workload requirements
Learning resources
Availability in areas of study
Computational science