2019-20（CST）剑桥大学计算机科学与技术教学大纲.pdf

Computer Science Tripos

Syllabus and Booklist 2019–20

Contents

Introduction to Part IA 4

Entry to the Computer Science Tripos . . . . . . . . . . . . . . . . . . . . . . . . 4

Computer Science Tripos Part IA . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Natural Sciences Part IA students . . . . . . . . . . . . . . . . . . . . . . . . . . 4

The curriculum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Michaelmas Term 2019: Part IA lectures 6

Scientific Computing Practical Course . . . . . . . . . . . . . . . . . . . . . . . . 16

Lent Term 2020: Part IA lectures 18

Paper 1: Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Paper 2: Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Paper 3: Machine Learning and Real-world Data . . . . . . . . . . . . . . . . . . 21

Easter Term 2020: Part IA lectures 23

Paper 1: Introduction to Probability . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Paper 2: Software and Security Engineering . . . . . . . . . . . . . . . . . . . . 24

Paper 3: Interaction Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Preparing to Study Computer Science 28

Foundations of Data Science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Paper 7: Further Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2

Further Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Group Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Programming in C and C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Semantics of Programming Languages . . . . . . . . . . . . . . . . . . . . . . . 45

Unix Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Lent Term 2020: Part IB lectures 48

Compiler Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Artificial Intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Complexity Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Paper 7: Concepts in Programming Languages . . . . . . . . . . . . . . . . . . . 61

Paper 7: Formal Models of Language . . . . . . . . . . . . . . . . . . . . . . . . 62

Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Introduction to Part II 66

Michaelmas Term 2019: Part II lectures 68

Unit: Advanced Graphics and Image Processing . . . . . . . . . . . . . . . . . . 68

Bioinformatics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Business Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Unit: Natural Language Processing . . . . . . . . . . . . . . . . . . . . . . . . . 82

Principles of Communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Lent Term 2020: Part II lectures 87

Unit: Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Comparative Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

E-Commerce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Machine Learning and Bayesian Inference . . . . . . . . . . . . . . . . . . . . . 95

Quantum Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

3

Unit: Topics in Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Business Studies Seminars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Hoare Logic and Model Checking . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4 University of Cambridge

Introduction to Part IA

Entry to the Computer Science Tripos

The only essential GCE A level for admission to Cambridge to read for the Computer

Science Tripos is Mathematics. Further mathematics should be taken if available, and a

physical science (Physics, Chemistry or Geology) is desirable.

Computer Science Tripos Part IA

Part IA students taking the 75% Computer Science option will attend all lectures for

Papers 1, 2 and 3. In addition they attend the Mathematics course offered for Part IA of the

Natural Sciences Tripos (NST).

Computer Science Tripos as well as the Mathematics course offered for Part IA of the

Natural Sciences Tripos (NST).

An A level in a science subject is desirable for students taking an NST option. Computer

Science students taking an NST option are expected to undertake practical work on the

same basis as for the Natural Science Tripos.

Natural Sciences Part IA students

There is a Computer Science option in the first year of the Natural Sciences Tripos,

counting as one quarter of the year’s work. Students taking this option should take the

pre-arrival course and attend all the lectures and practicals for Paper 1.

The curriculum

For most of the courses listed below, a list of recommended books is given. These are

roughly in order of usefulness, and lecturers have indicated by means of an asterisk those

books which are most recommended for purchase by College libraries.

Computer Science Tripos Part IA 5

The Computer Laboratory Library aims to keep at least one copy of each of the course

texts in “The Booklocker” (see http://www.cl.cam.ac.uk/library/).

For further copies of this booklet and for answers to general enquiries about Computer

Science courses, please get in touch with:

Teaching Administrator

University of Cambridge

Computer Laboratory

William Gates Building

J J Thomson Avenue