Introduction to the Theory of Computing 1

Synopsis

1-2. The basic notions of number theory: divisibility, prime numbers, the fundamental theorem of arithmetic, the cardinality of primes, the prime number theorem. The notion of congruence, operations on congruences.

3-4. Linear congruences, solution of simultaneous congruence systems. Euler-Fermat theorem, Fermat's little theorem. The notion of polynomial algorithm, the efficiency of number-theoretic algorithms.

5-6. Arithmetic algorithms: basic operations, exponentiation modulo m, Euclidean algorithm for computing the greatest common divisor and for solving linear congruences, primality testing. Public key cryptography, the RSA algorithm.

7-8. Coordinate geometry in the space: vectors in the space, coordinate system, scalar product. The equation of a plane. The (parametric and canonical) system of equations of a line. The notion of Rⁿ, operations on column vectors.

9-10. The notion of a subspace of Rⁿ, the property of being closed under operations. The notions of linear combination, generating system, spanned subspace. The notion of linear independence, the equivalence of the two definitions.

11-12. Relation between the sizes of linearly independent systems and generating systems in subspaces. The notions of basis and dimension, the clarity of the dimension. The clarity of representing a vector relative to a basis, the notion of the coordinate vector.

13-14. Solving systems of linear equations with the Gaussian elimination. The notions of row reduction, echelon form and reduced echelon form. Relation between the number of equations and the number of variables of uniquely solvable systems.

15-16. The definition of the determinant. The number of inversions in permutations. Basic properties of the determinant. Computing the determinant with the Gaussian elimination. Characterizing the unique solvability of (n x n) systems of linear equations with the determinant.

17-18. The (Laplace) expansion theorem for determinants.. The cross product of 3-dimensional vectors, its relation to the determinant. Operations on matrices, identity matrix, transposed matrix. The determinant of the product matrix.

19-20. Expressing systems of linear equations in the Ax=b form. Connection between the linear independence of the rows and the columns of square matrices and the determinant. The notion of the inverse matrix, necessary and sufficient condition on its existence. Computing the inverse. The notion of the rank of a matrix, the calculation of the rank.

21-22. Equality of the three types of rank notions. The notion of a linear map, necessary and sufficient condition on the linearity of a map. Composition of linear maps, addition formulas for the sine and cosine functions.

23-24. The kernel and the image of linear maps, the dimension theorem. Basis transformation, the matrix of a linear transformation with respect to a basis, its calculation.

25-26. The notions of the eigenvalue and the eigenvector of a square matrix, computing the eigenvalues, characteristic polynomial.

27-28. Repetition, summary, systematic review of the material studied. Description of the current list of exam questions for the oral exam and the detailed expectations related to each exam question.

Detailed topics of the exercises/labs

Same as the theme of the lectures from week to week.