Algebra 2 (NMAI076) - Spring term 2024

Lecture: Thursday 14:00 - 15:30, lecture room S6
Exercises: Thursdays 15:40 - 17:10 on odd weeks, lecture room S6

Lecture notes Czech English
Algebra 1 alg1_cz alg1_en
Algebra 2 alg1_cz alg2_en

Evaluation:
To obtain the credit (Zápočet) for the course you need to score at least 54 out of 90 points. Points can be obtained from 3 homework assigments (3*30 points). The final grade will be determined by an oral exam, admission to the exam requires getting ''Zápočet'' first.

Syllabus: This course is a continuation of Algebra 1 and aims to introduce computer science students to some topics from abstract algebra:
  1. Homomorphisms (group homomorphism, quotient groups, ring homomorphisms, ideals, classification of finite fields)
  2. Number fields (ring and field extensions, algebraic elements, and finite degree extensions)
  3. Algorithms in polynomial arithmetic (fast polynomial multiplication and division, decomposition)
  4. Other algebraic structures (lattices and Boolean algebras)
Overview:

Date Topics Lecture notes Homework
22/02Repetition groups, group homomorphisms and isomorphisms, invariants
Ex: Examples 		Section 1.1-1.3
29/02 Group classifications; Normal subgroups, quotient groups Section 1.4, 2
06/03 The homomomorphism theorem and isomorphism theorems for groups; Ideals, PIDs
Ex: determining quotient groups, sums and intersections of ideas in Z		 Section 2, 3 HW1
due 21/03
13/03 Ring homomorphisms, quotient rings Section 4
20/03 Isomorphism theorems for rings, prime/maximal ideals, ring and field extensions
Ex:computing quotient rings, ring extensions		 Section 4,5.1
28/03 Algebraic and transcendental elements, the degree of a field extension, minimal polynomials Section 5.2,6.1,6.2
04/04 minimal polynomials, degrees of general extensions, algebraic numbers are a field
Ex: computing minimal polynomials, degrees of extensions, splitting fields		 Section 6.2, 6.3 HW2
due 18/04
11/04Problems solvable by ruler and compass
Uniqueness of rupture fields and splitting fields		Section 7, 8
18/04The classification of finite fields
Ex: Constructability of regular n-gons		Section 9
25/04Modular representations, Fast Fourier Transform Section 10
02/05 (self study) fast polynomial multiplication and division using FFT
Ex: primitive roots, FFT 		Section 11 HW3
due 16/05
09/05fast polynomial multiplication and division using FFT
square-free decomposition 		Section 11, 12.1
16/05 Berlekamp's algorithm
Ex: formal power series, discussion of 3rd homework		Section 12
23/05Examples of other algebraic structuresSection 13


Consultation:
If you have questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.

Spring term 2024
Algebra Proseminar (NMAG261)

See David Stanovský's website.

Winter term 2023/24
Convex Optimization (NMMB409)

The course was organized via the following Moodle course. The practicals were run by Mykyta Narusevych.

Winter term 2023/24
Practicals in Universal Algebra 1 (NMAG405)

See Libor Barto's website.

Spring term 2023
Algebra 2 (NMAI076)

Lecture: Monday 09:00 - 10:30, lecture room S6
Exercises: Monday 10:40 - 12:10 on odd weeks, lecture room S6, held by Filippo Spaggiari

Lecture notes Czech English
Algebra 1 alg1_cz alg1_en
Algebra 2 alg1_cz alg2_en

Evaluation:
To get ''Zápočet'' (i.e. to pass the exercise classes) you need to score at least 45 out of 70 points. Points can be obtained from 2 homework assigments (2*30 points), and in-class presentation (10 points). For more details see Filippo Spaggiari' website.
The final grade will be determined by an oral exam, admission to the exam requires passing the exercise class.

Syllabus: This course is a continuation of Algebra 1 and aims to introduce computer science students to some topics from abstract algebra:
  1. Homomorphisms (group homomorphism, quotient groups, ring homomorphisms, ideals, classification of finite fields)
  2. Number fields (ring and field extensions, algebraic elements, and finite degree extensions)
  3. Algorithms in polynomial arithmetic (fast polynomial multiplication and division, decomposition)
  4. Other algebraic structures (lattices and Boolean algebras)
Overview:

Date Topics Lecture notes Homework
13/02Group homomorphisms and isomorphisms, invariants, classifications
Ex: Examples 		Section 1
20/02Normal subgroups, quotient groups, homomophism theorem,
1st isomorphism theorem 		Section 2
27/02Ideals and divisibility, PIDs, ideals in fields
Ex: quotient groups, intersection and sum of ideals 		Section 3
06/03Quotient rings, homomorphism theorem,
1st and 2nd isomorphism theorem for rings		Section 4.1,4.2
13/03 prime and maximal ideals; Ring and field extensions, degree
Ex:quotient rings, ring and field extensions 		Sections 4.3, 51st HW
due 27.3
20/03Algebraic and transcendental numbers
Minimal polynomials of algebraic numbers 		Section 6
27/03Extensions by more than one element, constructability, ruler-and-circle constructions
Ex: minimal polynomials and algebraic numbers		Section 6.3, 7
03/04 Uniqueness of splitting fields (up to isomorphism),
Classification of finite fields		Sections 8, 9
10/04Easter Monday
17/04Modular representations of rings, Fast Fourier TransformationSection 10
24/04Fast polynomial multiplication and division, formal power series
Ex: general field extensions and their degree 		Section 11
01/05International Workers' Day
08/05V-Day2nd HW
due 24.5
15/05Square-free factorizations of polynomials
Berlekamp's algorithm for decomposition into irreducibles		Section 12
22/05Berlekamp's algorithm; algebraic structures, substructures, homomorphisms
Ex: ordered sets, lattices and Boolean algebras		Sections 12, 13


Consultation:
If you have questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.

Spring term 2023
Practicals in Universal Algebra II (NMAG450)

See Libor Barto's website.

Spring term 2022
Universal Algebra II (NMAG450)

Lecture: Monday 10:40 - 12:10, lecture room K7
Exercise classes: even weeks, Monday 12:20 - 13:50, lecture room K7, given by Kevin Berg

Lecture notes

Syllabus:This course discusses selected topics from Universal Algebra. This includes
  1. Equational logic: the equational completeness theorem, term rewriting systems, Knuth-Bendix algorithm
  2. Commutator theory: Abelianness, the term condition commutator, applications
  3. Finitely based algebras: McKenzie's theorem on algebras with DPC
  4. Maltsev conditions: Taylor terms, polymorphism clones and CSPs, absorption theory
Evaluation:
Exercises: there will be 3 homework assignments, on which you need to score 60% to get ''Zápočet''
Lecture: oral examination (appointment by mail: michael@logic.at).


Date Topics Lecture notes Exercises Homework
14/02Equational theories, fully invariant congruences;
completeness theorem for equational logic.		 Section 1.1
21/02term rewrite systems, convergence, Knuth-BendixSection 1.2, 1.3 1.2,1.3,1.4
28/02Abelian and affine algebras
Herrmann's fundamental theorem		Section 2.1, 2.2
07/03The term conditions commutator,
Examples (groups and lattices)		 Section 2.3 1.2,1.3,1.4
2.12, 2.13		HW1: 1.6, 1.8 (first point) 2.10, 2.14
14/03A characterization of CD varieties
by the commutator		Section 2.4
21/03Birkhoff's theorem on Id_n
a non-finitely based algebra		Chapter 3 2.19,2.20HW1 due
28/03Park's conjecture
McKenzie's DPC theorem		Section 3.1
04/04Jonsson's lemma
DPSC varieties		Section 3.2 3.2,3.3, 3.11HW2: 3.4, 3.5, 3.6, and 4.1
11/04Baker's theorem
CSPs: Definition and Examples		Section 3.2, 4.1
18/04Easter holiday
25/04Pol-Inv revisited, clone homomorphismsSection 4.1., 4.2. HW2 due
02/05Minion homomorphisms, Taylor's theoremSection 4.2. 4.3, 4.13HW3: 4.6,4.7,4.8 and 4.12
09/05Loop lemma (for triangles)
Siggers terms		Section 4.3
16/05only Exercise class today! HW3 due


Consultation:
If you have questions on the material, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but personal meetings can be arranged. Please make also use of the exercise classes to discuss your questions.

Further reading:

Winter term 2021/22
Algebra 1 (NMAI062)

Please register to the !! Moodle course !!

Lecture notes

Lecture: Wednesday 10:40 - 12:10, lecture room S4
Exercise classes: Tuesdays 15:40 - 17:10, lecture room S10, given by Kevin Berg
(current covid regulations)

Evaluation:
To get ''Zápočet'' (i.e. to pass the exercise classes) you need to score at least 60/100 points. These can be obtained from 3 homework assignments (3*30 points), or weekly quizzed (10 points), which will be posted on the Moodle course
The final grade will be determined by a written exam. Admission to the exam requires passing the exercise class.

Syllabus:This course aims to give an introduction to algebra for computer science students. It will cover the following topics:
  1. Number theory: prime factorization, congruences, Euler's theorem and RSA, the Chinese remainder theorem
  2. Polynomials: rings and integral domains, polynomial rings, irreducibility, GCD, the Chinese remainder theorem and interpolation, the construction of finite fields and applications (error correcting codes, secret sharing,...)
  3. Group theory: permutation groups, subgroups, Langrange's theorem, group actions and Burnsides's theorem, cyclic groups, discrete logarithm and applications in cryptography
Literature:The course has its own lecture notes, which are based on David Stanovsky's material from last year, and will be constantly updated during the semester. Complementary resources are for instance Consultation:
If you have open questions, do not hesitate to ask (either in person or via e-mail)! I have no official office hours, but if required, a personal meeting can be arranged. Please make also use of the exercise classes to discuss your questions.

Spring term 2020
Universal Algebra II (NMAG450)

Lecture notes


Grading:
Exercises: homeworks (you need to score 60% on the 3 best out of 4 homeworks)
Lecture: oral examination (appointment by mail: michael@logic.at).
Not available from 17.07.-27.07, 17.08-28.08

Additional literature:
Date Topics Lecture notes Exercises Homework
24/02Equational theories, fully invariant congruences;
completeness theorem for equational logic.		 Section 1.1 1.1-1.3
02/03Convergent term rewriting systems Section 1.2
09/03Critical pairs, Knuth-Bendix algorithm;
Affine algebras 		Section 1.2, 1.3
Section 2.1		 1.4, 1.8,1.9 1.5,1.6,1.7
due on 24/03
16/03Abelian algebras
Herrmann's fundamental theorem 		Section 2.1, 2.2 2.1-2.9;
in particular 2.2, 2.6
23/03Centralizer relation and commutator
Example: groups		 Section 2.3 2.11, 2.12 2.10, 2.13, 2.14
due on 07/04
30/03Properties of the commutator
Characterization of CD varieties		 Section 2.3, 2.4 2.15-2.20;
in particular 2.18,2.19
06/04Nilpotent algebras
and open questions		 Section 2.5 Section 2.5
20/04Birkhoff's theorem on Id_n(A)
Example of a non-finitely based algebra 		Chapter 3 3.1-3.4
27/04McKenzies DPC theorem Section 3.1 3.5-3.8
04/05CSPs, pp-definable relations
Pol-Inv 		Section 4.1 4.1-4.5 3.5,3.6,4.3 due on 19/05
11/05 Clone and minion homomorphisms
 Section 4.2 4.6-4.8
18/05Taylor operations
the CSP dichotomy conjecture/theorem		 Section 4.3 4.9-4.11 4.6,4.7,4.8
until your exam


Winter term 2019/20
Practicals in Universal Algebra I (NMAG405)

See Libor's website.

Spring term 2019
Universal Algebra II (NMAG450)

The course will roughly follow Libor Barto's lecture from 17/18.

Lecture: Thurday 9:00 - 10:30 Seminar room of KA
Exercises: Thurday 10:40 - 12:10 Seminar room of KA (only odd semester weeks = even calendar weeks)

Grading:
Exercises: homeworks (60% from 3 best scores out of 4 homeworks)
Lecture: oral examination (appointment by mail: michael@logic.at).
next available dates 27/05-07/06; 17/06-20/06; 04/07-

Literature:
Date Topics Recommended reading Exercises Homework
28/02Abelian and affine algebras, Fundamental theorem. Bergman 7.3 Ex. 1
07/03Checking identities, Relational description of Abelianness;
Centralizer relation (in general and in groups) 		Bergman 7.4
14/03Properties of the commutator
Characterization of CD varieties		 Bergman 7.4 Ex. 2 HW 1
due 28/03
21/03Equational theories, fully invariant congruences;
completeness theorem for equational logic.		Bergman 4.6
Jezek 13
28/03Reduction order, critical pairs
Knuth-Bendix algorithm		Jezek 13Ex. 3
04/04Examples of finitely based and non finitely based algebrasBergman 5.4HW 2
due 25/04
11/04 McKenzie's result on definable principal congruencesBergman 5.5Ex. 4
18/04Constraint satisfaction problems over finite templates
Pol-Inv revisited 		BKW
25/04(h1-)clone homomorphisms
Taylor terms		BKWEx. 5HW 3
due 09/05
02/05Taylor's theoremBergman 8.4.
09/05Smooth digraphs, algebraic length 1,absorptionBK
16/05Absorption, transitive termsBKEx. 6HW 4
23/05Absorption theorem, LLL (loop lemma 'light', for linked digraphs)BK


Winter term 2018/19
Practicals in Universal Algebra I (NMAG405)

see David Stanovsky's website.