Mathematics for Computer Science and Philosophy: 2019-2020
Degrees |
Overview
This is a second/third-year course for Computer Science & Philosophy students. They will attend a subset of the first-year lectures in Linear Algebra and Continuous Mathematics, and will so be equipped with the knowledge needed for courses in Machine Learning.Classes:
Colleges will arrange problem classes for their students, as with the corresponding first-year courses: three classes for Linear Algebra and two for Continuous Mathematics.
Examinations:
A two-hour exam at the end of the third year, with students answering two questions from a choice of three.
Synopsis
Linear Algebra. About 14 lectures in Michaelmas Term.
- Complex numbers.
- Vectors: Vectors and geometry in two and three space dimensions. Algebraic properties. Dot products and the norm of a vector. Important inequalities. Vector spaces, subspaces and vector space axioms. Complex vector spaces. Application examples.
- Independence and orthogonality: Linear independence of vectors. Basis and dimension of a vector space. Orthogonal vectors and subspaces. The Gram-Schmidt orthogonalisation, related algorithms and operation count. Application examples.
- Matrices: Matrix operations. Column, row and null space. Rank of a matrix. Inverse and transpose. Elementary matrices. The Gauss-Jordan method. Application examples: population growth and finite linear games.
- Systems of linear equations: Examples of linear systems. Geometry of linear equations. Gaussian elimination. Row echelon form. Homogeneous and nonhomogeneous systems of linear equations. Application examples: network analysis, global positioning systems and intersection of planes.
- Elementary matrix factorisations and determinants: LU factorisation, related algorithms and operation count. PLU factorisation. Calculating the determinant of a matrix. Properties of the determinant of a matrix. Application examples: area, volume and cross product; equations of lines and planes.
- Eigenvalues and eigenvectors: Definition. Similarity and diagonaliza-tion. Population growth revisited. Systems of linear differential equations.
Continuous Mathematics. About 9 lectures in Hilary Term.
- Derivatives, partial derivatives, differentiation with respect to a vector, gradient, Hessian and Jacobian. Taylor’s theorem in 1 dimension (Lagrange remainder), Taylor’s theorem in n dimensions (remainder only briefly). Examples.
- Optimization in 1 and n Classification of turning points via Taylor’s theorem. Convexity. Constrained optimization: Lagrange multipliers. Examples.
- Convergence rates of iterative methods.
- Numerical root finding in 1 dimension by bisection, Newton’s method, secant method. Root finding in n dimensions by Newton’s method, and briefly quasi-Newton methods. Complexity and error analysis. Examples.
Syllabus
Vector spaces and subspaces. Matrices. Inverse matrices. Solution of linear systems. Elementary matrix factorisations. Eigenvalues and eigenvectors.
Derivatives, partial derivatives, differentiation with respect to a vector; gradient, Hessian, Jacobian. Taylor’s theorem in 1- and n-dimensions, with Lagrange remainder. Optimization in 1- and n-dimensions, classification of stationary points. Constrained optimization and the method of Lagrange multipliers. Iterative numerical methods and rates of convergence. Methods for numerical root finding in 1- and n-dimensions, complexity and (simple cases of) error analysis.