As an alternative, excellent description of this course I strongly recommend the preface of Computers Ltd.: What They Really Can't Do (Oxford University Press) by David Harel. This lovely little book by one of Computer Science's best expositors is highly recommended reading. (See the review of this book in Plus magazine.)
As supplementary reading on the science of computing as a whole, I also strongly recommend the books:
Note: The above exercises are not really
part of this
course. How many you attempt to solve depends only upon
your level of
confidence with the mathematics that will be used as
the course
progresses.
Our working language for the course
will be English.
In general, I shall give you more exercises than you might conceivably
be able to solve during one exercise class. The exercises marked with
a star are those that I consider more important for your
understanding. All the exercises will be "doable", and working them
out will greatly increase your understanding of the topics covered in
the course. The best advice I can give you is to work them all out by
yourselves, and to make sure you understand the solutions if the other
members of your group (or me) gave you the solutions on a golden
plate. Above all, don't give up if you cannot find the key to the
solutions right away. Problem solving is often a matter of mental
stamina as much as creativity.
Above all, try to be critical of your solutions to the exercises. You
may not need (some of) the material covered in this course in your
future careers, but having an analytical and critical attitude will
always help you.
For further advice on how to learn this material (and, in fact, the
material in any course) I strongly recommend that you look at the
slides for the talk Psychologists'
tips on how and how not to learn by Wilfrid Hodges. In
particular, try to reflect upon the hints he gives, and ask yourselves
how much you practice what he preaches. You might also wish to read How
to Read Mathematics by Shai Simonson and
Fernando Gouveau --- a collection of useful, down-to-earth tips on how
to read, and learn from, mathematical texts
The list of exam questions for this part of the course is
as follows:
This page will be actively modified over the autumn term
2004, and is currently undergoing heavy restructuring. You are invited
to check it regularly during the autumn term. The page is dormant in
the spring term.
Prerequisites
The course assumes knowledge of basic
discrete mathematics, such as
the one that you have been using in
the course Matematik 2B
and in Algorithms and
Data
Structures. Those of you who would like to refresh their
memory,
or who are not confident about their understanding of the
basic
mathematics used in this course, are strongly encouraged to
read,
e.g., Chapter 0 of Sipser's book and/or Chapter 1 of the
book
Elements of the Theory of Computation (2nd edition) by
Lewis
and Papadimitriou. As
practice makes perfect, I also recommend that you work out some of
the
exercises to be found in those references. Try, for example,
exercises
0.2-0.5, 0.7, 0.10-0.11 in Sipser's book and/or exercises
1.1.1-1.1.4,
1.5.1-1.5.2 in the book by Lewis and
Papadimitriou.Course Material and
Lecture Plan
The course will consist of a series of 5 lectures, which will take
place at 10:15 (new
time) on Wednesdays in the period 8 September-8 October 2004. The
location of the
lectures will be room A4-108. Look at
the semester calendar
(inactive at the moment) for updated
information on the schedule for this (and all other)
courses. Lecture Plan
[Overview of the lecture (PDF file with hyper-references)]
[Slides for the lecture (PDF file with hyper-references)]
You might wish to read the introductory sections of On computable
numbers, with an application to the Entscheidungsproblem published
by Alan Turing in 1936. This is the classic, original paper that introduced the notion
of Turing machine.
[Overview of the lecture (PDF file with
hyper-references)]
[Slides for the lecture
(PDF file with hyper-references)]
[A Poetic
Undecidability Proof by Geoffrey K. Pullum]
[Another
Poetic Undecidability Proof courtesy of Harry Mairson]
[For
theatre buffs, here is where you can read more about the play Infinities
by John D. Barrow
that I mentioned during the lecture. Here is a review of the
play.]
[Overview of the lecture (PDF file
with hyper-references)]
[Slides for the lecture
(PDF file with hyper-references)]
[A site with some classic logical paradoxes.]
[Overview of the lecture (PDF file with
hyper-references)]
[Slides for the lecture (PDF file with hyper-references)]
[Overview of the lecture (PDF file with
hyper-references)]
[Slides for the lecture (PDF file with hyper-references)]
The so-called "P versus NP" problem is one the Millennium Prize
Problems announced by the Clay
Mathematics Institute, and carries a $1 million reward. You might
wish to read the popular article Million-Dollar
Minesweeper by Ian Stewart.
Exercise
Classes and Advice on Modus Operandi
As usual, each lecture will have an associated exercise class. The
exercises mentioned on the web page for a lecture should be solved
during the exercise class that precedes the following lecture. For
example, the exercises listed on the web page for lecture 1 should be
solved before lecture 2. There will be no exercise class preceding the
first lecture. The exercise classes will take place in room E3-109 from about 8:15 till 10:00.
Exam
The exam will be individual and oral. Each student will be examined
for at most 20 minutes on one of the topics listed in the exam
prospectus that will be distributed during the last lecture. The topic
will be selected randomly by each student. The student will be
informed of his/her mark (on the standard 13-scale) after the oral
exam. The student can choose to hold the exam in either Danish or
English.