(Lecturer: Thomas Naughton)
Department of Computer Science,
National University of Ireland Maynooth, Ireland.
|
|
(Lecturer: Thomas Naughton) Department of Computer Science, National University of Ireland Maynooth, Ireland. |
Module Overview
This module is part of the M.Sc. in Computer Science (Software Engineering), of the Postgraduate Diploma in Science (Software Engineering), and of the new Erasmus Mundus MSc in Dependable Software Systems. It can also be taken as a stand-alone module by occasional students. The purpose of this course is to explain the fundamental and practical limits of computers. Students will learn how to identify problems that cannot be solved with a computer, how to identify problems that should not be solved (but only approximated) with a computer, and how to proceed in both cases.
Organisation
|
Module Structure
|
Reading Material
|
Lab Work
|
Projects
|
Past exam papers
|
For this academic year, the module will be taught by Tom Naughton.
The course will run over a period of two weeks.
Lectures will closely follow the course text (Sipser, see below). It is not necessary to have a copy of the book during lectures, but it will be a useful study aid, and I will recommend specific sections in the book for self-study before the final exam. Furthermore, a copy of the book without notes or additions can be brought into the final exam. The book is available in the library, in the campus bookshop, bookshops in Dublin, and from international online booksellers.
The assigned practical work will be due at 23:59h on the Friday of your assignment week. This is to ensure that you have a full weekend to rest and read the introductory material before your next week of lectures. Part-time students, or students taking CS605 as a one-off module, should discuss an alternative deadline with me.
The exam for this course is likely to take place in January 2013.
Outline
The emphasis is placed on mathematical foundations and theory of computability and computational complexity
The purpose of this course is to explain the limits of computers, what they can and cannot do, both in terms of their fundamental limitations and their practical application. You will learn about the theoretical foundations on which computer science is built. You will learn how to design a simple theoretical computer with a minimal instruction set and prove that it has equal computational power to this year's fastest supercomputer, or next year's. You will learn how to tell if a problem is not worth tackling using a computer, and if it is to be tacked, whether an exact solution can be sought or whether it should only be approximated. In the case of the latter scenario, you will learn how it can be much more efficient to transform an unseen problem into a suitable form for off-the-shelf approximation packages, rather than write the code from scratch.
Monday morning reading and exercises. Please read the following mathematical preliminaries (linked here) that recap what you should already know from your undergraduate degree. For example, the concepts of set, tuple, relation, string (also referred to as a word), and language should be familiar to you by the end of the morning. Please answer the following past exam questions when you have read and understood that mathematical preliminaries: Past exam paper December 2002 Q1(a)i-v, Sample exam layout paper 2002-2003 Q1, Past exam paper December 2001 Q1(a) and Q1(b), Sample exam paper 2003-2004 Q3(a) (see exam papers below). Finally, answer the following: formulate the problem of sorting an arbitrary length list of integers as a language acceptance problem.
Monday (afternoon): Overview of the course, mathematical preliminaries, models of computation, equivalence of machines/functions/languages, regular languages, finite automata
Tuesday: finite automata continued, context-free languages, pushdown automata, Turing machines, a brief history of computer science, Gödel's Incompleteness theorem, universality, Church-Turing thesis, unrestricted models of computation
Wednesday: Turing machines continued, Turing's 1936 paper, decidable languages, Turing-recognisable languages and their complements
Thursday: proofs of undecidability, Measures of complexity, Invariance thesis, the class P
Friday: the class NP, intractability, Cook-Levin theorem, NP-completeness, coping with NP-complete problems, unconventional models of computation (time permitting)
Please print, complete, and return to me the following self-assessment sheets after you have attempted the lab sheets above. They will not accrue any marks, but they will allow both you and I to assess how well you are progressing in the module.
You must choose your project topic. By way of example, these were the projects in previous years: 2011, 2010, and 2009. This project will account for 20% of the mark for the CS605 module.
The content of this year's course will be very similar to that taught in the following previous years.
