Foundations of Computer Science:  2019-2020

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 (but are missing some of this basic theory) 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:

• Theory of Data & Knowledge Bases
• Automata, Logics & Games
• Software Verification
• Categories, Proofs & Processes
• Game Semantics
• Computer-Aided Formal Verification
• Lambda Calculus & Types
• Logic of Multi-Agent Information Flow 

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

• M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, January 1997. (Primary text)
• M. Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, 2nd Editions. Cambridge University Press, 2004.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.