Algebra DSBA 2019/2020

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск


Teachers and assistants

Группа 191 192 193
Lecturer Dima Trushin
Teacher Dima Trushin Sergey Gayfullin Galina Kaleeva
Assistant Arina Yunying Timur

Consultations schedule

Teacher/Assistant Monday Tuesday Wednesday Thursday Friday
Dima Trushin zoom since 16:00
Sergey Gayfullin 16:30–18:00
Galina Kaleeva 16:30–18:00 пароль: algebra 16:40–18:00 (June, 5th) пароль: algebra

Grading system

The cumulative grade is computed as follows:

C = 0,6 * H + 0,4 * T,

where H is the grade for the home assignments and T is the written test grade.

The final course grade is given by

F = 0,5 * C + 0,5 * E = 0,3 * H + 0,2 T + 0,5 E

where E is the final exam grade.

Only the final grade is rounded in the final formula according to the standard rule.

Lecture abstracts

Lecture 1 (06.04.2020). Binary operations. Associativity, neutral element, inverse element, commutativity. Definition of a group. Additive and multiplicative notations. Subgroups and cyclic subgroups. The order of an element of a group.

Lecture 2 (13.04.2020). Subgroups of the group of integers. Left and right cosets, examples. Normal subgroups. The Lagrange theorem and its 5 corollaries.

Lecture 3 (20.04.2020). Homomorphisms and Isomorphisms of groups. Image and kernel of a homomorphism. Normal subgroups. Direct product of groups. Finite Abelian Groups. The Chinese Remainder Theorem. Structure of a finite abelian group.

Lecture 4 (27.04.2020). Second version of the Chinese Remainder Theorem. Structure of Z_{p^n}^*. Cryptography. Exponentiation by squaring (fast raising to a power algorithm). The discrete logarithm problem. Diffie-Hellman key exchange.

Lecture 5 (07.05.2020). Rings, commutative rings, fields, subrings. Invertible elements, zero divisors, nilpotent and idempotent elements. Ideals. Description of ideals in Z and Z_n. Homomorphisms and isomorphisms of rings. The Chinese remainder theorem for rings. The kernel and the image of a homomorphism, their properties.

Lecture 6 (12.05.2020). Polynomials in one variable. Euclidean algorithm, greatest common divisor, ideals of F[x]. Irreducible polynomials and unique factorization of polynomials in F[x]. Ring of remainders, the Chinese Remainder Theorem for polynomials.

Lecture 7 (18.05.2020). Characteristic of a field. Field extensions, an extension by a root. Finite fields: number of elements in a finite field, multiplicative group of a finite field is cyclic, classification of finite fields (without proof). How to produce finite fields. Galois random generator. Stream cipher.

Lecture 8 (25.05.2020). Polynomials in several variables. Lexicographical orders, stabilization of strictly descending chains of monomials. An elementary reduction, a reduction with respect to a set of polynomials, remainders, Groebner basis.

Lecture 9 (01.06.2020). Stabilization of reduction. S-polynomials and the Buchberger criterion. Ideals in a polynomial ring, the Buchberger algorithm to produce a Groebner basis of an ideal. A ring of remainders. Membership problem and variable elimination.

Problem sheets

The solutions should be sent to your teaching assistant via email before the beginning of the next seminar.

Seminar 1 (06.04.2020). Problems

Seminar 2 (13.04.2020). Problems

Seminar 3 (20.04.2020). Problems

Seminar 4 (27.04.2020). Problems

Seminar 5 (07.05.2020). Problems

Seminar 6 (12.05.2020). Problems

Seminar 7 (18.05.2020). Problems

Seminar 8 (25.05.2020). Problems

Seminar 9 (01.06.2020). Problems



  • Homework
191 192 193
  • Summary Statement
191 192 193