Algebra DSBA 2019/2020 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(консультации)
(Results)
 
(не показана одна промежуточная версия 3 участников)
Строка 1: Строка 1:
 
= Schedule =
 
= Schedule =
  
* [https://zoom.us/j/491446502 Lecture] Monday 12:10–13:30
+
* [https://zoom.us/j/98706972969 Lecture] Monday 12:10–13:30
  
* [https://zoom.us/j/695983454 Seminar 191] Monday 13:40–15:00
+
* [https://zoom.us/j/92828388875 Seminar 191] Monday 13:40–15:00
  
 
= Teachers and assistants =
 
= Teachers and assistants =
Строка 26: Строка 26:
 
| <center>1</center> || Dima Trushin ||  ||  || [https://us04web.zoom.us/j/5515049969 zoom since 16:00] ||  ||
 
| <center>1</center> || Dima Trushin ||  ||  || [https://us04web.zoom.us/j/5515049969 zoom since 16:00] ||  ||
 
|-
 
|-
| <center>2</center> || Sergey Gayfullin ||  || [ https://us02web.zoom.us/j/89143777345 16:30&ndash;18:00] ||  ||  ||
+
| <center>2</center> || Sergey Gayfullin ||  || [https://us02web.zoom.us/j/89143777345 16:30&ndash;18:00] ||  ||  ||
 
|-
 
|-
| <center>3</center> || Galina Kaleeva || [https://us04web.zoom.us/j/79877329363 16:30&ndash;18:00] ||  ||  ||  ||  
+
| <center>3</center> || Galina Kaleeva || [https://us04web.zoom.us/j/75909851166?pwd=MzQ2MmpQZTFiaUs5cEd0c1NxekpSdz09 16:30&ndash;18:00] пароль: algebra||  ||  ||  || [https://us04web.zoom.us/j/75909851166?pwd=MzQ2MmpQZTFiaUs5cEd0c1NxekpSdz09 16:40&ndash;18:00] (June, 5th) пароль: algebra
 
|-
 
|-
 
| <center>4</center> || Arina || || ||  || ||
 
| <center>4</center> || Arina || || ||  || ||
Строка 58: Строка 58:
  
 
'''Lecture&nbsp;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&nbsp;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&nbsp;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&nbsp;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&nbsp;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&nbsp;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&nbsp;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&nbsp;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&nbsp;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 =
 
= Problem sheets =
Строка 68: Строка 82:
  
 
'''Seminar&nbsp;3''' (20.04.2020). [https://yadi.sk/i/UkSrO9JhNa14sg '''Problems''']
 
'''Seminar&nbsp;3''' (20.04.2020). [https://yadi.sk/i/UkSrO9JhNa14sg '''Problems''']
 +
 +
'''Seminar&nbsp;4''' (27.04.2020). [https://yadi.sk/i/A9JjBjJfsHL9_Q '''Problems''']
 +
 +
'''Seminar&nbsp;5''' (07.05.2020). [https://yadi.sk/i/xWV0DbYfPG9qiQ '''Problems''']
 +
 +
'''Seminar&nbsp;6''' (12.05.2020). [https://yadi.sk/i/jdg96r9XChrFkA '''Problems''']
 +
 +
'''Seminar&nbsp;7''' (18.05.2020). [https://yadi.sk/i/JzwF9Rd5Ycn6dA '''Problems''']
 +
 +
'''Seminar&nbsp;8''' (25.05.2020). [https://yadi.sk/i/qWymXdWqGB9KzA '''Problems''']
 +
 +
'''Seminar&nbsp;9''' (01.06.2020). [https://yadi.sk/i/H0QLPDojzbQVXQ '''Problems''']
 +
 +
= Exam =
 +
 +
* [https://yadi.sk/i/oY_3ADtOrqxWww The lists of definitions and statements]
 +
 +
* [https://yadi.sk/i/Zb7RvwpECu8-3A The list of statements to prove]
  
 
= Results =
 
= Results =
 +
 +
* Homework
  
 
{| class="wikitable" style="text-align:center"
 
{| class="wikitable" style="text-align:center"
 
|-
 
|-
 
! [https://docs.google.com/spreadsheets/d/1HUJ-WoTtWmpYSNq2okUr99AKX2MmVlC3pnctCMsSEEI/edit#gid=0 191] !! [https://docs.google.com/spreadsheets/d/1HUJ-WoTtWmpYSNq2okUr99AKX2MmVlC3pnctCMsSEEI/edit#gid=1992163396 192] !! [https://docs.google.com/spreadsheets/d/1HUJ-WoTtWmpYSNq2okUr99AKX2MmVlC3pnctCMsSEEI/edit#gid=83275050 193]
 
! [https://docs.google.com/spreadsheets/d/1HUJ-WoTtWmpYSNq2okUr99AKX2MmVlC3pnctCMsSEEI/edit#gid=0 191] !! [https://docs.google.com/spreadsheets/d/1HUJ-WoTtWmpYSNq2okUr99AKX2MmVlC3pnctCMsSEEI/edit#gid=1992163396 192] !! [https://docs.google.com/spreadsheets/d/1HUJ-WoTtWmpYSNq2okUr99AKX2MmVlC3pnctCMsSEEI/edit#gid=83275050 193]
 +
|}
 +
 +
* Summary Statement
 +
 +
{| class="wikitable" style="text-align:center"
 +
|-
 +
! [https://docs.google.com/spreadsheets/d/1ULykRTOgC79vjbaE7hXnVsmEzO2fnWcVwCPrff-IICU/edit#gid=0 191] !! [https://docs.google.com/spreadsheets/d/1ULykRTOgC79vjbaE7hXnVsmEzO2fnWcVwCPrff-IICU/edit#gid=17634846 192] !! [https://docs.google.com/spreadsheets/d/1ULykRTOgC79vjbaE7hXnVsmEzO2fnWcVwCPrff-IICU/edit#gid=1828997773 193]
 
|}
 
|}
  

Текущая версия на 22:12, 14 июня 2020

Schedule

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
1
Dima Trushin zoom since 16:00
2
Sergey Gayfullin 16:30–18:00
3
Galina Kaleeva 16:30–18:00 пароль: algebra 16:40–18:00 (June, 5th) пароль: algebra
4
Arina
5
Yunying
6
Timur

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

Exam

Results

  • Homework
191 192 193
  • Summary Statement
191 192 193

Links