Computer Science

ECM3422 - Computability and Complexity (2016)

Back | Download as PDF
MODULE TITLEComputability and Complexity CREDIT VALUE15
MODULE CODEECM3422 MODULE CONVENERDr Antony Galton (Coordinator)
DURATION: TERM 1 2 3
DURATION: WEEKS 11 weeks
Number of Students Taking Module (anticipated) 13
DESCRIPTION - summary of the module content

It is popularly supposed that there is no limit to the power of computers to perform any task, so long as it is sufficiently well defined, and to do so quickly and efficiently. In fact this is not so, and it can be proved mathematically that there are well-defined computational tasks which cannot, in principle, be performed by computers as we know them; and other tasks which, while they can be performed, cannot be completed in a feasible amount of time (e.g., to find the shortest round tour of 30 cities requires a computation which would take even the fastest computers longer than the age of the universe). This module will introduce you to the Turing Machine model of computation which underpins the fundamental theories of computability (concerned with what can be computed at all) and complexity (concerned with how efficiently things which can be computed can be computed).

Pre-requisites: ECM1414, ECM2418

AIMS - intentions of the module

To introduce the Mathematical basis and practical implications of the classical theory of computability and to consider the extent to which this is still relevant to modern developments in computing.
 

INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)

On successful completion of this module, you should be able to:
Module Specific Skills and Knowledge:
1 manipulate formal languages and create abstract automata to a given specification;
2 explain what is meant by a general model of computation and work with some specific examples of such models;
3 describe the mathematical basis of the theory of computability;
4 appreciate the relationship between the theory of computation and practical computing.
Discipline Specific Skills and Knowledge:
5 appreciate the power of abstraction to support a general understanding of some subject matter;
6 appreciate the role of theoretical understanding in underpinning disciplined and responsible practice.
Personal and Key Transferable / Employment Skills and Knowledge:
7 approach problems analytically at an appropriate level of abstraction.

 

 

SYLLABUS PLAN - summary of the structure and academic content of the module

- regular languages and regular expressions, context-free languages and grammars, pumping lemmas and other methods of proof;
- finite-state automata, elimination of non-determinism, Kleene's theorem, push-down automata;
- Turing machines, the universal Turing machine;
- recursive and recursively enumerable functions;
- recursive insolubility of the halting problem for Turing machines; variants of the halting problem; other recursively insoluble problems;
- the Church-Turing thesis and its variants; other models of computation; the quest for hypercomputation;
- time complexity vs space complexity; overview of the complexity class landscape;
- recapitulation of the P vs NP problem; more rigorous presentation of P vs NP in terms of Turing machine model; proof of Cook’s Theorem.

LEARNING AND TEACHING
LEARNING ACTIVITIES AND TEACHING METHODS (given in hours of study time)
Scheduled Learning & Teaching Activities 34.00 Guided Independent Study 116.00 Placement / Study Abroad
DETAILS OF LEARNING ACTIVITIES AND TEACHING METHODS
Category Hours of study time Description
Scheduled learning and teaching 22 Lectures
Scheduled learning and teaching 12 Tutorials
Guided Independent Study 30 Coursework
Guided Independent Study 86 Independent study

 

ASSESSMENT
FORMATIVE ASSESSMENT - for feedback and development purposes; does not count towards module grade
Form of Assessment Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
Class test 1 hour 1, 2 In class
       
       
       
       

 

SUMMATIVE ASSESSMENT (% of credit)
Coursework 20 Written Exams 80 Practical Exams
DETAILS OF SUMMATIVE ASSESSMENT
Form of Assessment % of Credit Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
Written exam – closed book 80 2 hours 2, 3, 4, 5, 6, 7 None
Coursework assignment 20 20 hours 1, 2, 7 Written
         
         
         

 

DETAILS OF RE-ASSESSMENT (where required by referral or deferral)
Original Form of Assessment Form of Re-assessment ILOs Re-assessed Time Scale for Re-reassessment
All above Written exam (100%) All August Ref/Def
       
       

 

RE-ASSESSMENT NOTES

Referred and deferred assessment will normally be by examination. For referrals, only the examination will count, a mark of 40% being awarded if the examination is passed. For deferrals, candidates will be awarded the higher of the deferred examination mark or the deferred examination mark combined with the original coursework mark.
 


 

RESOURCES
INDICATIVE LEARNING RESOURCES - The following list is offered as an indication of the type & level of
information that you are expected to consult. Further guidance will be provided by the Module Convener

ELE-http;//vle.exeter.ac.uk

Reading list for this module:

Type Author Title Edition Publisher Year ISBN Search
Set Martin, John C. Introduction to Languages and the Theory of Computation McGraw-Hill 2003 [Library]
Set Parkes, Alan P A Concise Introduction to Languages and Mechanics Springer Verlag 2008 978-1-84800-120-6 [Library]
CREDIT VALUE 15 ECTS VALUE 7.5
PRE-REQUISITE MODULES ECM1414, ECM2418
CO-REQUISITE MODULES
NQF LEVEL (FHEQ) 3 (NQF level 6) AVAILABLE AS DISTANCE LEARNING No
ORIGIN DATE Wednesday 11 November 2015 LAST REVISION DATE Thursday 20 October 2016
KEY WORDS SEARCH Formal languages; automata; Turing machine; computability; computational complexity.