Mathematical Foundations of Computer Science
- Lecturers:
- Professor Cristian S. Calude,
room 303-575, Science Building,
- Professor Bakhadyr Khoussainov,
room 303-581, Science Building, course coordinator,
- A/Professor Fred Kroon,
Arts 2,
18 Symonds St.,
Level 2,
Room 202.
-
Tutor:
Alastair Abbott. Office hours:
Friday 11-12 noon or by appointment, room 576. Any problem
related to marking should be addressed to the tutor.
-
Class representative:
To be nominated
- Taught: First semester 2012, three hours of lectures and a tutorial a week (see 2012 Academic Dates).
-
Timetable: Lectures: Monday 15-16, Arts 1, room 209, Tuesday 14-15, Arts 1 Building, 203, Friday 14-15, 29 Engineering Block 3, room 403. Tutorials: Tuesday 15-16, Owen Glenn Building, CaseRoom2, starting the second
week.
- 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.
- Content:
- Automata and regular languages
- Context-free languages
- Computability and decidability
- Algorithmic complexity
- Church-Turing Thesis
- Quantum computing and beyond Turing
- 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 unconventional
- prove the undecidability or complexity of a variety of problems
- understand the issue of whether there are limits of computability
- Textbook:
M. Sipser.
Introduction to the Theory of
Computation,
PWS Publishing Company, Boston, 2006, second edition.
- Software: Register machine simulation
- Recommended Reading:
- J. E. Hopcroft, R. Motwani, J. D. Ullman.
Introduction to
Automata Theory, Languages, and Computation, Addison Wesley, Boston,
2001, second edition.
- John C. Martin.
Introduction
to Languages and the Theory of Computation
Mc Graw-Hill, Boston, 2003, third edition.
- Tutorials: Tutorial handouts & solutions
- Assessment: Three assignments worth 20% in total, Test: 30%, Exam: 50%
- Assignments (the assignment dropbox will be outside the room 303-576): Assignment 1:
due Friday 16 March, before 4.00pm,
worth 7%;
assignment 2:
due Friday 6 May, before 4.00pm,
worth 7%;
assignment 3:
due Friday 25 May, before 4.00pm, worth 6%.
Sample solutions:
-
Test:
23 March, in class.
Sample Solutions.
-
Exam:
- Handouts: Prof. Calude's lectures.
- Policy on
Cheating
- Other relevant sites: