Computational Discrete Mathematics

• Explain how to explicitly represent and compute with very large integers, finite fields, and with polynomials over finite fields.
• Describe a fast multiplication algorithm and applications for other computations.
• Apply modular methods and chinese remaindering to algebraic computations.
• Efficiently factor a polynomial over a finite field.
• Perform multivariate polynomial division with remainder and describe the role of monomial orders.
• Compute a Gröbner basis and describe its relevance for ideal membership and related problems.
• Represent real-world problems as non-linear equations and the relation to ideals of multivariate polynomial rings.
• Use a computer algebra system to experimentally work with algebraic problems.
• Determine the asymptotic complexity of algorithm for algebraic problems in a realistic computational model.
• Prove the correctness of algebraic algorithms.

Exact algebraic computation. Arithmetic in finite fields, with polynomials over finite fields and over integers, and with matrices over finite fields and over integers. Algorithms for factoring. Ideals in Noetherian rings, especially multivariate polynomial rings, Gröbner bases and Buchberger’s algorithm.

01018, Understanding of concepts from abstract algebra: linear algebra, rings, ideals, quotient rings, the isomorphism theorem, finite fields. Some experience with programming and algorithms.
Students that have not taken 01018 but have 01017 and 01426 should be able to follow the course but should expect reading up on the mentioned algebra.

Lectures, exercises, assignments

Minimum: 5.

Please be aware that this course will only be held if the required minimum number of participants is met. You will be informed 8 days before the start of the course, whether the course will be held.