Foundations of the Theory of Machines.
Alan Turing developed his "Turing Machines" in the 1930s.
He asked and answered the question: What is a
computation? We now know that all answers to this
question proposed so far turn out to be equivalent.
This includes the answer:
"Something that can be done on a quantum computer, if they
ever exist". Turing showed that there were problems
which no machine or algorithm or computation
can solve. This is "The Year of Turing" -- he was born
100 years ago, the same year that the Titanic sank.
[We will cover some of this.]
Information and Coding Theory.
The term "information" is often misunderstood,
but in the theory due to
Claude Shannon, it refers to the amount of "surprise" upon the receipt of a
message. (No surprise means no information.)
The theory involves messages, their transmission, and the encoding of messages
for compression, for error handling, and for secrecy. To quote from Shannon:
The fundamental problem of communication is that of reproducing at one
point either exactly or approximately a message selected at another point.
Shannon (1948)
Shannon did an amazing job of presenting a fully-developed theory in the late 1940s;
since then an incredible number of refinements to the theory and
applications have emerged. Everything in the modern computer era depends on
this material as a foundation.
In particular Shannon introduced the ideas of Information
Entropy, and of Information Channels and their Capacity,
[Covered in electrical engineering departments.]
The Relational Model for Database Management.
An elegant way to handle information, deceptively simple and
easy to use, while powerful. Developed
by Edgar Codd in 1970. [Covered in our Database Management
course, which you should all take.]
NP-Complete Problems. These are intractable
optimization problems with astonishing properties.
Introduced by Cooke in 1971 and further developed by Karp in 1972.
[We will cover some of this.]
Public-key Cryptography and Digital Signatures.
Introduced by Diffie and Hellman in 1976. RSA Cryptosystem
in 1977. [Covered in our Cryptography course. The topic
is mathematical.]
Data Compression Algorithms. An offshoot of
Shannon's work and information theory. Significant parts
of our modern civilization rely on these. For example,
movies in mpeg format. [Covered in electrical
engineering departments.]
Programming Languages and Compilers. Includes
syntactic algorithms and many others. Much of the theory
of algorithms was developed in service of these areas.
Contributions by many people, particularly Backus, Knuth,
and Naur. (Peter Naur created the prototype of
most modern programming languages with Algol 60. Instead
of using a stack as the basis for a language and compiler,
Naur started with the idea of using a stack and developed
a language ideally suited to its utilization.)
[Covered in our required Programming Languages course
and in the elective Compilers course.]
Revision date:2012-02-22.
(Please use ISO 8601,
the International Standard Date and Time Notation.)