Page Areas:



Current Submenu:

Additional Information:

News

  • Prüfungstermin
    Am 15.01.2016 von 08:30 bis 11:45 Uhr ist Prüfungstermin für "Algebra für InformatikerInnen" (SS15), "Einführung in die Algebra" (SS15) und "Kommutative Algebra" (SS15). Prüfungsanmeldung über Kusss erforderlich!

Location

Science Park II, 3rd floor

Science Park II, 3rd floor, GPS: 48.335634,14.323747 ...  more of Location (Titel)


Position Indication:

Content

Vorlesung: Algorithmische Abstrakte Algebra (Computational Group Theory, Universal Algebra and CSPs, GAP)

LVA-Leiter: Peter Mayr
LVA-Nr.: 386.163

3,0 ECTS
2,0 SSt.


LVA-Termine

Montag, 10:15-11:45 Uhr, MT 130

1. Termin 21.10.2013, zusatzliche Termine Mittwoch, 23.10. und 30.10, 10:15-11:45 Uhr, SP2 416-2


Course Content

How can we solve Rubik's cube? How many moves are necessary? How can we represent and work with in nite groups on a computer? Is it possible to color a given map with four colors such that adjacent countries have distinct color? What is the connection between nding such a coloring, searching a database, and solving a system of linear equations? Which of these problems is hard, which one easy? In this course we will consider and formulate these questions as algebraic problems. In particular we study algorithms for computing with groups and more general algebraic structures. Our motivation for this comes from two areas:

  • Concrete questions about concrete algebras: For example, what is the size of a permutation group given by a list of generators?
  • Complexity theory: A number of classical decision problems like satis ability of Boolean formulas, graph colorability, solving systems of linear equations ... can be formulated as Constraint Satisfaction Problems (CSP). An open conjecture in theoretical computer science states that every such CSP is either solvable in polynomial time (like solving linear equations) or NP-complete (like coloring graphs). Some recent progress on this question is due to algebraic methods. For every CSP one can construct an algebraic structure such that solving the CSP amounts to determining the intersection of subalgebras. Hence algorithms for computing with general algebraic structures are then applicable to these decision problems.

Topics:

Computational Group Theory:

  • Permutation groups: Sims stabilizer chains, strong generators
  • Finitely presented groups: word problem, subgroup presentations, coset enumeration

Algebraic approach to CSP:

  • Formulating CSPs via algebraic structures
  • Polynomial time algorithms for CSPs: local consistency checking, bounded width, few subpowers

Literature


Schedule

The lectures will be blocked in order not to overlap with the workshops of the Special Semester on Applications of Algebra and Number Theory. The precise dates will be determined in the 1st meeting.