Mathematical Foundations of Computer Science
- Professor Cristian S. Calude,
room 303-427, Science Building, course coordinator.
- Professor Fred Kroon,
room 443 Arts 1.
Tutor and marker:
Yan Kolezhitskiy. Office hours:
- Taught: First semester 2019, three hours of lectures and a tutorial repeated twice) a week
(see 2019 Academic Dates).
Timetable: Lectures: Monday, Wednesday, Friday 3.00pm - 4.00pm, OGHLecTh/102-G36. Tutorials: TThursday and Friday, 1:00pm 2:00pm ClockT029/105-029, starting the second
- Short Description:
The aim of this paper is to present mathematical models for computers and computation, and derive results about what can and cannot be computed. It deals with idealised computers (automata) which operate on idealised input and output (formal languages). For example, we prove that it is impossible to write a computer program that takes as input any computer program and tells us whether or not that program will end up in an endless loop (the halting problem). Quantum computing will also be briefly described and the Church-Turing Thesis will be critically discussed. In addition we will discuss some problems in algorithmic complexity. We assume you are comfortable with formal mathematical proofs and can write them properly.
- Mathematical backgrgound refresh
- Automata and regular languages
- Computability and decidability
- Algorithmic complexity
- Church-Turing Thesis
- Quantum computing
- Expected learning outcomes: On completion, students will be able to
- explain the theoretical limits on computational solutions of undecidable and inherently complex problems
- describe concrete examples of computationally undecidable or inherently infeasible problems from different fields
- understand formal definitions of machine models, classical and quantum
- prove the undecidability or complexity of a variety of problems
- understand the issue of whether there are limits of computability
- understand the basic principles of quantum computing
Introduction to the Theory of
PWS Publishing Company, Boston, 2013, third edition.
- Software: Register machine simulation
- Assessment: Tutorial work: 5%. Three assignments: 15%, Test: 30%, Exam: 50%.
- Assignments (sumitted via Canvas):
due on 7 April 2019,
due on 19 May 2019,
worth 5%; assignment 3:
due on 2 June 2019,
worth 5%. All assignments must be prepared using an appropriate word-processing application [diagrams may be hand-drawn], converted to PDF format, and uploaded in Canvas before 23.55 of the due date.
- Any problem
related to marking should be addressed to the tutor and/or marker.
1 April 2019, in class, time: 15:00-16:00 in OGHLecTh/102-G36 and OCH1/104-G53. Room distribution will be announced by 29 March 2019.
- Canvas: COMPSCI350.
- Handouts: In Canvas.
- Other relevant sites: