CM50278: Foundations of computation
[Page last updated: 14 August 2024]
| Academic Year: | 2024/25 |
| Owning Department/School: | Department of Computer Science |
| Credits: | 6 [equivalent to 12 CATS credits] |
| Notional Study Hours: | 120 |
| Level: | Masters UG & PG (FHEQ level 7) |
| Period: |
|
| Assessment Summary: | CW 100% |
| Assessment Detail: |
|
| Supplementary Assessment: |
|
| Requisites: | This module is only available to apprentices on the Level 7 Digital and Technology Solution Specialist Apprenticeship |
| Learning Outcomes: |
On completion of this unit, students will be able to:
1. Demonstrate an understanding of the fundamental models of computation and the corresponding classes of formal languages, suitably expressed;
2. Design and apply algorithms for specific computational problems involving languages and computational models of appropriate types (e.g. automata);
3. Prove formally that some computational problems are undecidable within a particular class of computational models;
4. Demonstrate an understanding of the role of grammars in the context of parsing algorithms, by applying the theoretical knowledge to concrete cases.
5. Give upper bounds on complexities of some decidable computational problems. |
| Aims: | This unit will go back to the early days of computing, long before any physical machines existed which would be recognisable today as a computer. Do computational problems exist which have no possible `method' for solving? And when a `method' exists, on which resources does it rely upon, and what is its cost? In this unit, students will learn that to answer these questions they must investigate formally what a 'method' actually is, and appreciate its limits, as well as learning about some unsolvable problems, students will learn some techniques that are used in many modern systems, including the core component of how compilers are able to process source code when programming. This unit also covers how formal computation models can be used to reason about the relative speed or complexity of various algorithms without needing to write any actual code. |
| Skills: | Use of IT (A), Application of Number (T/F, A), Problem Solving (T/F, A), Critical thinking (T/F,A), communication (T/F,A) |
| Content: | Topics covered in this unit may include (but are not limited to) the following:
1. Basic mathematical notions and terminology. Deterministic and non-deterministic finite automata
2. Regular languages and their properties, regular expressions and relations to computational models.
3. Existence of non-regular languages via the pumping lemma. Context free grammars and languages, and their properties.
4. Pushdown automata. Parsing with context-free grammars, Chomsky Normal Form, application of theoretical knowledge to a concrete case.
5. Existence on non-context-free languages via the pumping lemma.
6. Turing machines and Church Turing Thesis.
7. Universal Turing machine, and undecidability of the halting problem.
8. Computational analysis and complexity: the classes P and NP. Decidable, semi decidable, undecidable properties. |
| Course availability: |
CM50278 is Compulsory on the following courses:Department of Computer Science
|
Notes:
|