(Lecturer: Thomas Naughton)
Maynooth University Department of Computer Science
|
|
(Lecturer: Thomas Naughton) Maynooth University Department of Computer Science |
Module Overview
This module is part of the M.Sc. Computer Science (Software Engineering). It can also be taken as a stand-alone module as part of other programmes. The purpose of this module 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
|
Past exam papers
|
For this academic year, the module will be taught by Tom Naughton.
The module will consist of a number of full days during the first week, followed by a number of Wednesdays during the following weeks, and comprising a mixture of lectures and laboratory sessions.
Lectures will closely follow the module textbook (Sipser, see below). Although very convenient, it is not necessary to have a copy of the book during lectures. I will also recommend specific sections in the book for self-study after lectures. Furthermore, you can, if you wish, bring a legal paper copy of the Sipser book (without notes/additions/annotations, except to fix typos) into the final exam with you. The book is available in the library (limited numbers), in the campus bookshop (limited numbers), bookshops in Dublin, and from national and international online booksellers.
The continuous assessment (CA) for this module is worth 20% and will be accrued by students through lab quizzes (short lab tests held during lab times under exam conditions and organised on an ad hoc basis as certain topics are covered in lectures and labs) and lab tests (longer tests held during lab times under exam conditions for which you will be given a day's notice).
The exam for this module will take place during the regular summer exam period (usually in May). It will be a limited form of open-book exam (see above for restrictions on the book).
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.
Preliminary 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. An appropriate self-testing exercise would be: formulate the problem of sorting an arbitrary length list of integers as a language recognition problem.
Each of the following sections corresponds to approximately a half day of lectures.
1: overview of the module, mathematical preliminaries, models of computation, equivalence of machines/functions/languages, regular languages
2: finite automata
3: context-free languages, pushdown automata
4: Turing machines, a brief history of computer science, Gödel's Incompleteness theorem, universality, Church-Turing thesis
5: Turing machines continued, unrestricted models of computation, Turing's 1936 paper
6: decidable languages, Turing-recognisable languages and their complements
7: proofs of undecidability
8: proofs of undecidability cont., measures of complexity, the Invariance thesis, the class P
9: the class NP, intractability
10: Cook-Levin theorem, NP-completeness, unconventional models of computation (time permitting)
While the Sipser book is sufficient for this module, any computer theory textbook should include the fundamental topics covered in this module. However, the syntax for their machines and assumptions made in their proofs will differ from Sipser and from each other. If you rely on a different textbook for one of your proofs, you will have to explain its unique machine syntax and state any assumptions made. Some well-known example textbooks that have stood the test of time include
The content of this year's module will be very similar to that taught in recent years.
(Summer 2024)
(Summer 2023)
(Summer 2022)
(Summer 2020)
(Summer 2019)
(Summer 2018)
(Summer 2017)
(Summer 2016)
