Department of Computer Science, Unit Catalogue 2011/12 |
|
Credits: | 6 |
Level: | Intermediate (FHEQ level 5) |
Period: |
Semester 1 |
Assessment: | CW 25%, EX 75% |
Supplementary Assessment: | CM20217 Mandatory Extra Work (where allowed by programme regulations) |
Requisites: | Before taking this unit you must take CM10227 and take CM10228 and (take CM10196 or take MA10001) |
Description: | Aims: To introduce formal models of computation. To give students an appreciation of the complexity of different algorithms and problems and the limits of computation. To provide students with a basic understanding of formal computational models such as finite state automata and Turing machines. Learning Outcomes: On completion of this unit, students will be able to: 1. demonstrate an understanding of the fundamental models of computation. 2. explain the notion of complexity class, and establish what classes a range of well-known problems belong to. 3. demonstrate that some computational problems are undecidable. Skills: Use of IT (A), Application of Number (T/F, A), Problem Solving (T/F, A). Content: * Models of computation: for example, basic notions of finite state automata, Turing Machines, register machines. * Decidability. The undecidability of the Halting Problem. Reduction of other problems to the halting problem. * Complexity. Big-O notation and complexity of algorithms. The notion of complexity class as a measure of the difficulty of a problem. Reduction between problems. Hardness and completeness of a problem with respect to a complexity class. The hierarchy of complexity classes. The question of whether P=NP and its importance for computer science. |
Programme availability: |
CM20217 is Compulsory on the following programmes:Department of Computer Science
CM20217 is Optional on the following programmes:Department of Computer Science
|