University of Oxford Logo University of OxfordDepartment of Computer Science - Home

Foundations of Computer Science:  2009-2010

Information

Lecturer

Michael Benedikt

Degrees

Schedule A — MSc in Computer Science

MSc by Research

Term

Michaelmas Term 2009  (16 lectures)

Overview

Computer scientists need to understand what it means for a problem to be determinable by a computer, what it means for a problem to be efficiently determinable by a computer, and how to reason in a semi-automated and automated fashion about computer programs and the structures they manipulate. The purpose of this course is to introduce students to the theoretical foundations of computer science. It is intended both for students who have a degree in computer science and also for students with a good theoretical background (e.g. a degree in mathematics) but no exposure to theoretical computer science.

Students taking this course will gain background knowledge that will be useful in the course on:

Learning outcomes

At the end of this course, the student should be able to:

  1. Describe in detail what is meant by a finite state automaton, a context-free grammar, and a Turing machine, and calculate the behaviour of simple examples of these devices.
  2. Design machines of these types to carry out simple computational tasks.
  3. Reason about the capabilities of standard machines, and demonstrate that they have limitations.
  4. Describe precisely what it means for a problem to be in the classes P,NP, and PSPACE, and what it means to be complete for a class
  5. Classify problems into appropriate complexity classes, including P, NP and PSPACE, and use this information effectively.
  6. Understand the syntax and semantics of propositional logic.
  7. Understand the satisfiability problem for propositional logic and its connection with NP hardness.
  8. Understand first-order predicate logic, along with the complexity/computability of the associated satisfaction and satisfiability problems.

Syllabus

Finite state machines. Reduction of non-deterministic finite automata to deterministic finite automata. Regular languges and their closure properties. Regular expressions. Inter-translations between regular expressions and NFA. Context-free grammars and pushdown automata. Intuitive notion of computability. Church's Thesis. Turing machines and its expressive power. Universal Turing machines. Undecidable problems. Diagonalization and the Halting Problem.  Deterministic complexity classes. P, EXPTIME and the Hierarchy Theorem. NP and NP-completeness. Space complexity. Propositional logic. Truth tables. Propositional Logic and NP-completeness. Proof systems for Propositional Logic. Syntax and semantics of first-order logic.  Complexity of first-order logic.

Reading list