Undergraduate Course: Computability and Intractability (INFR09008)
Course Outline
| School |
School of Informatics |
College |
College of Science and Engineering |
| Course type |
Standard |
Availability |
Available to all students |
| Credit level (Normal year taken) |
SCQF Level 09 (Year 3 Undergraduate) |
Credits |
10 |
| Home subject area |
Informatics |
Other subject area |
None |
| Course website |
http://www.inf.ed.ac.uk/teaching/courses/ci |
|
|
| Course description |
The course centres around the so-called Church-Turing Thesis which proposes that each one of a variety of different formal systems adequately captures the intuitive concept of (effective) computability. This thesis implies that by studying any one of these systems, for example Turing machines, we can learn about the inherent theoretical limitations of computers. If a problem cannot be solved by a Turing machine, then there is no computable solution to it at all.
Not all the computational problems which can be solved in principle can be solved in practice: the computational resources required (time or space) may be prohibitive. This observation motivates the study of resource-bounded computation. Having accepted an extended version of the Church-Turing thesis (that the computationally tractable problems are those which can be efficiently solved by a Turing machine) we are led inevitably to conclude the existence of natural problems which can be solved in principle but not within any reasonable resource bound.
The fundamental concepts and techniques encountered in this course resonate around the whole of Computer Science and indeed beyond: effective procedures and decidability, simulation methods, machine encodings and universality, diagonalization arguments, and reductions between problems. |
Entry Requirements
| Pre-requisites |
|
Co-requisites |
|
| Prohibited Combinations |
|
Other requirements |
Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School. This course also assumes that students are comfortable with mathematical notation, definitions, and proofs using basic techniques including induction.
|
| Additional Costs |
None |
Course Delivery Information
|
| Delivery period: 2010/11 Semester 1, Available to all students (SV1)
|
WebCT enabled: No |
Quota: None |
| Location |
Activity |
Description |
Weeks |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| Central | Lecture | | 1-11 | 09:00 - 09:50 | | | | | | Central | Lecture | | 1-11 | | | | 09:00 - 09:50 | |
| First Class |
Week 1, Thursday, 09:00 - 09:50, Zone: Central. Seminar Room 2, Chrystal Macmillan Building |
|
| Delivery period: 2010/11 Semester 1, Part-year visiting students only (VV1)
|
WebCT enabled: No |
Quota: None |
| Location |
Activity |
Description |
Weeks |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| Central | Lecture | | 1-11 | 09:00 - 09:50 | | | | | | Central | Lecture | | 1-11 | | | | 09:00 - 09:50 | |
| First Class |
Week 1, Thursday, 09:00 - 09:50, Zone: Central. Seminar Room 2, Chrystal Macmillan Building |
Summary of Intended Learning Outcomes
1 - Discuss the fundamental nature of computation as a process (Turing's Thesis).
2 - Discuss the limits to computing both in absolute terms (unsolvable problems) and practical terms (intractable problems).
3 - Distinguish different types of languages (recursively enumerable, recursive etc.).
4 - Demonstrate the solvability of a given problem both in informal as well as formal terms (use of Turing machines).
5 - Demonstrate the unsolvability of a given problem both in informal as well as formal terms (use of reductions).
6 - Discuss the classification of solvable problems into tractable versus intractable ones (P versus NP).
7 - Judge when a problem is likely to be intractable.
8 - Discuss the notion of polynomial time reduction and its relevance to classifying the relative complexity of problems.
9 - Demonstrate the likely intractability of a given problem by relating it to other known problems (use of polynomial time reductions). |
Assessment Information
Written Examination 100
Assessed Assignments 0
Oral Presentations 0
Assessment
via Written Examination.
If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year. |
| Please see Visiting Student Prospectus website for Visiting Student Assessment information |
Special Arrangements
| Not entered |
Contacts
| Course organiser |
Dr Marcelo Cintra
Tel: (0131 6)50 5118
Email: mc@inf.ed.ac.uk |
Course secretary |
Miss Tamise Totterdell
Tel: 0131 650 9970
Email: t.totterdell@ed.ac.uk |
|
copyright 2010 The University of Edinburgh -
1 September 2010 6:09 am
|
University Homepage