AlgoK and GDl Joint Research Seminar [S]

Dozentinnen/Dozenten:

Isolde Adler, Michael Mendler

Angaben:

Seminar

Termine:

Mi, 14:00 - 16:00, Raum n.V.
Das Seminar findet ab Mittwoch, den 24.04.2024 wöchentlich in Raum WE5/05.006 statt (Labor Mendler)

AlgoK-AK-B: Algorithmen und Komplexität

Dozentinnen/Dozenten:

Isolde Adler, Jakub Pekárek

Angaben:

Vorlesung, 4,00 SWS

Termine:

Mi, 10:00 - 12:00, WE5/04.004

Voraussetzungen / Organisatorisches:

Prerequisites: Algorithms and data structures, basic knowledge of computability theory, proof techniques. Good English language skills.

Inhalt:

Algorithms and problem solving lie at the heart of computer science. Given an algorithmic problem, such as the Traveling Salesperson Problem, how can we design an efficient algorithm? Once we found an algorithm that solves the problem correctly, can we be sure that the resources, such as running time, storage space (and related: energy), required by this algorithm are really necessary for solving the problem? Perhaps we can do better? These are the guiding questions that students will explore in this module. We will discuss the design and analysis of algorithms in depth, including algorithm design principles (such as greedy algorithms, divide and conquer algorithms and dynamic programming). We then discuss the classification of computational problems according to their resource complexity. This includes time and space complexity, complexity classes such as P, NP, PSPACE and the relationship between the classes, reductions, NP-completeness, the P versus NP problem, and lower bounds on resource requirements. Decision problems, search problems, and optimisation problems are introduced, and the students will encounter a variety of relevant problems from different fields, such as network flows, satisfiability, numerical problems (Knapsack), matching problems, geometrical problems, graph colouring, sequencing problems, linear programming and scheduling. We then move on to methods for dealing with computationally hard problems, discussing approximation algorithms and randomised algorithms. Further topics such as descriptive complexity, fixed-parameter algorithms and circuit complexity may be discussed if time permits.

Empfohlene Literatur:

Jon Kleinberg and Éva Tardos: Algorithm Design. Michael Sipser: Introduction to the Theory of Computation. Christos H. Papadimitriou: Computational Complexity. Michael Garey, David S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani: Algorithms. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Sanjeev Arora, Boaz Barak: Computational Complexity, A modern approach. Jörg Flum, Martin Grohe: Parameterized Complexity Theory.

AlgoK-Algo-M: Algorithmen

Dozent/in:

Isolde Adler

Angaben:

Vorlesung, 4,00 SWS

Termine:

Do, 14:00 - 16:00, WE5/04.004

AlgoK-Sem-B/M: Bachelor- und Masterseminar Algorithms and logic for data science and AI

Dozent/in:

Isolde Adler

Angaben:

Seminar, 2,00 SWS

Termine:

Einzeltermin am 19.4.2024, 12:00 - 14:00, WE5/02.020
Einzeltermin am 11.6.2024, 14:00 - 16:00, GU13/00.28
Einzeltermin am 28.6.2024, 12:00 - 14:00, WE5/02.020
Kick-off meeting (Meeting 1) 19.04., 12:00-14:00 in WE5/02.020; Meeting 2: 26.04.2024, 12:00-14:00 in WE5/02.020; Progress meeting (Meeting 3): 12.06.2024, in GU 13, 00.28, 10:00 - 14:00; two "block seminar" dates: 12.07.2024 and 19.07.2024, both from 8:00 -18:00 in GU13, 00.28

AlgoK-Sem-B/M: Bachelor- und Masterseminar Tree decompositions, algorithms and games

Dozent/in:

Isolde Adler

Angaben:

Seminar, 2,00 SWS

Termine:

Einzeltermin am 19.4.2024, 10:00 - 12:00, WE5/02.020
Einzeltermin am 11.6.2024, 14:00 - 16:00, GU13/00.28
Einzeltermin am 28.6.2024, 10:00 - 12:00, WE5/02.020
Kick-off meeting (Meeting 1) 19.04., 10:00-12:00 in WE5/02.020; Meeting 2: 26.04.2024, 10:00-12:00 in WE5/02.020; Progress meeting (Meeting 3): 12.06.2024, in GU 13, 00.28, 10:00 - 14:00; two "block seminar" dates: 12.07.2024 and 19.07.2024, both from 8:00 -18:00 in GU13, 00.28

AlgoK: Offenes Tutorium - mathematische Grundlagen

Dozentinnen/Dozenten:

Isolde Adler, Jakub Pekárek, Joseph Stimpson

Angaben:

Übung

Termine:

Mo, 10:00 - 14:00, WE5/02.020