Libor Barto
 HOME POCOCOP RESEARCH FOR STUDENTS

ARCHIV 22/23 zimni semestr

[Zpet]

UNIVERSAL ALGEBRA (NMAG405)

Lecture: Thr 15:40 - 17:10 K5
Practicals run by Filippo Spaggiari: Thr 17:20 - 18:50 K5

• Practicals ("Z: Zapocet"): homeworks (60% from the sum of 4 best scores out of 5 homeworks)
• Lecture ("Zk: Zkouska"): written test + possible oral examination

Literature:

 topics (future topics may change) recommended reading lecture notes homework 29.9. Motivation. Algebra (signature, type). Examples. Pr.: Lattices vs. lattice ordered sets Bergman 1.1, 1.2 lecture 1 practicals 1 6.10. Lattices, complete lattices, closure operators. Pr.: Distributive and modular lattices. The lattice of equivalence relations. Bergman 2.1, 2.2, 2.3 lecture 2 practicals 2 13.10. Algebraic lattices and closure operators. Galois correspondences. Pr.: Complete lattices, closure operators, Galois correspondences. Bergman 2.4, 2.5 lecture 3 practicals 3 Homework 1 due 27.10. 17:20 20.10. Subalgebras, products, quotients. Pr.: Subalgebras, congruences. Bergman 1.3, 1.4, 1.5 lecture 4 practicals 4 corrected (lower quality) 27.10. H,S,P operators, variety. Homomorphisms. Pr.: Homomorphisms. Finite algebras generate locally finite varieties. Bergman 1.1, 1.3, 3.1, 3.5 lecture 5 practicals 5 Homework 2 due 10.11. 17:20 3.11. Direct and subdirect decomposition Pr.: Direct and subdirect decomposition. Bergman 3.2, 3.3 lecture 6 practicals 6 10.11. Subdirect decomoposition, SIs in congruence distributive vaieties Pr.: SIs in monounary algebras. Bergman 3.4, 3.5, (5.2) lecture 7 practicals 7 Homework 3 due 24.11. 17:20 17.11. --- --- 24.11. Terms, identities, free algebras. Pr.: Free algebras. Bergman 4.3, 4.4 lecture 8 practicals 8 1.12. The syntax-semantics Galois correspondence, Birkhoff's theorem. Pr.: Equational bases. Bergman 4.4, (4.6) lecture 9 practicals 9 Homework 4 due 15.12. 17:20 8.12. Clones. Free algebras as clones of term operations. Pr.: Clones. Bergman 4.1 lecture 10 practicals 10 15.12. The operations-relations Galois correspondence. Pr.: Algebraic and relational clones. Bergman 4.2 lecture 11 practicals 11 Homework 5 due 5.1. 17:20 22.12. Mal'cev conditions: Mal'cev, majority. Pr.: Mal'cev conditions Bergman 4.7 (part) lecture 12 practicals 12 5.1. Tame Congruence Theory Pr.: Tame Congruence Theory practicals 13

INTRODUCTION TO COMPLEXITY OF CSP (NMAG563)

Fri 10:40 K12

Problems

References (contain a lot of spoilers):

• survey (Barto, Krokhin, Willard): here
• shorter survey (Barto): here (see the complexity column)
• Krokhin's tutorial: available here
• Another Krokhin's tutorial, a bit different topics: available here
• My tutorial: PDF
• Paper Bulatov, Jeavons, Krokhin: Classifying the Complexity of Constraints Using Finite Algebras PDF

ARCHIV