Lectures

Because of the corona pandemic, there won't be any lectures in the standard sense.

Instead the current plan is to proceed as follows (subject to change):

• We will publish slides accompanied by written notes every week or every second week (this depends on the amount of information contained in the slides/notes).
• The lecture notes are still work in progress and thus certainly contain typos, errors, awkward formulations, and may --- at least sometimes --- be difficult to understand: they will thus be a perfect replacement for the usual lectures ...
• For corrections, clarifications, etc, we will thus
  • setup a forum via the moodle page (please take your time to formulate your questions are precise as possible; we won't/can't answer questions that are incomprehensible), and
  • offer -- at least in the beginning -- a chat/video conference on one of the two official lecture dates in order to answer questions posted in the forum or asked via the chat (this will be an experiment, we will only continue offering this, if we have the impression that is of any use).
• Currenlty (15.04.2020) we do not know how we have to handle the endterm (there will be no retake) because of the corona pandemic. For this reason,
  • we do not know how many students we can really handle in the exam, and thus
  • we have closed the registration for the course for now, and
  • we will restrict the access to the lecture material via mandatory exercises. That is, we will e.g. ask you to take some test via moodle or implement one of the algorithms discussed in the current lecture; only if you/your code passes the test, you will get access to the the material for the next lecture. In order to keep things simple, we will dictate the programming language(s) you have to use (probably Python).
  • you will get a bonus of 0.3, if you successfully complete all mandatory exercises/tests/tasks, in order to make up for the added work load.

Original dates for the lectures and tutorials:

• Tuesdays: 14:00-15:30, 15:45-17:15 (Room 03.09.014)
• Wednesdays: 14:00-15:30 (Room 03.09.014)

Lecture start: 29.04.2020 (this gives us a little bit more time to proof-read the lecture notes etc).

Expected previous knowledge

Basics of graph theory, formal language theory, probability theory, logics, linear algebra and calculus as taught in the courses IN0015, IN0011, IN0018, MA0901, and MA0902.

Note that, although the course is open to bachelor students, we assume that you have already passed these courses.

Courses IN2041 (automata and formal languages), IN2049 (logics), and IN2239 (algorithmic game theory) can be of help, but are not required.

Content (Outline)

We study games which occur frequently in theoretical computer science (verification, synthesis, logics), and mathematics (topology, operations research) and how they interact with each other.

• Qualitative winning conditions:
  • Gale-Stewart games
  • Reachability and Safety Games
  • Büchi Games
  • Concurrent reachability games
  • Muller/Rabin/Strett/Parity/LTL Games
• Quantitative winning conditions:
  • Markov Chains
  • Markov Decision Processes
  • Stocastic Games with discounted and limit-average payoff
  • Mean-Payoff Games
• Applications:
  • Controller synthesis
  • Strix
  • (PRISM)