(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
|
Projects
|
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, laboratory sessions, and project work.
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, a paper copy of the book without notes or additions can be brought into the final exam. 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 completed project work will be due at 23:59h on Friday 26th April 2024. Part-time students, or students taking CS605 as a one-off module, should discuss an alternative deadline with me.
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: you will be allowed to bring one paper copy of the Sipser book (without annotations, except to fix typos) into the exam with you.
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. An appropriate self-testing exercise would be: formulate the problem of sorting an arbitrary length list of integers as a language acceptance 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
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 make a choice/choices for your project topic using the appropriate channel on Teams. The project rules are available on the projects webpage. This project is worth 20% of the mark for the CS605 module.
The content of this year's module will be very similar to that taught in recent years.
(Summer 2023)
(Summer 2022)
(Summer 2020)
(Summer 2019)
(Summer 2018)
(Summer 2017)
(Summer 2016)
