Program Overview

Institute of Theoretical Computer Science

The Institute of Theoretical Computer Science is a leading research institution that focuses on the theoretical foundations of computer science. The institute offers a range of programs and courses that cover various aspects of theoretical computer science, including algorithms, data structures, and formal methods.

Teaching

The institute offers a variety of teaching programs, including:

• Lectures in Winter Semester 2025/2026
  • Algorithmen und Datenstrukturen
  • Introduction to Bioinformatics
  • Foundations of Theoretical Computer Science and Formal Foundations of Computer Science
• Archiv
  • Veranstaltungen im SS 2025
    • Algorithmen zur Sequenzanalyse
    • Algorithmische Spieltheorie
    • Kryptologie
    • SAT Solving
    • Zufallsmethoden in der Informatik
  • Veranstaltungen im SS 2024
    • Seminar Einführung in die Algorithmik: Algorithmen in der Aussagenlogik
    • Seminar Algorithmik: Algorithmen in der Aussagenlogik
    • Komplexitätstheorie
    • Algorithmische Spieltheorie
    • Datenkompression
    • Kryptologie
  • Veranstaltungen im WS 2024/2025
    • Algorithmen für schwierige Probleme
    • Algorithmen und Datenstrukturen
    • Einführung in die Bioinformatik
    • Grundlagen der Theoretischen Informatik und Formale Grundlagen der Informatik
  • Veranstaltungen im WS 2023/24
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Grundlagen der Theoretischen Informatik und Formale Grundlagen der Informatik
    • Quantum Computing
  • Veranstaltungen im SS 2023
    • Proseminar Algorithmen
    • Seminar Einführung in die Algorithmik: Algorithmen in der Aussagenlogik
    • Algorithmen für schwierige Probleme
    • Seminar Algorithmik: Algorithmen in der Aussagenlogik
    • Algorithmische Spieltheorie
  • Veranstaltungen im WS 2022/2023
    • Grundlagen der Theoretischen Informatik
    • Algorithmen und Datenstrukturen
    • Einführung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • SAT Solving
    • Zufallsmethoden in der Informatik
  • Veranstaltungen im SS 2022
    • Projekt: Algorithm Engineering
    • Seminar Algorithmik: Algorithmen in der Aussagenlogik
    • Seminar Einführung in die Algorithmik: Algorithmen in der Aussagenlogik
    • Algorithmen zur Sequenzanalyse
    • Kryptologie
    • Berechenbarkeit und Komplexität
    • Algorithmische Spieltheorie
  • Veranstaltungen im SS 2021
    • Algorithmische Spieltheorie
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Proseminar Algorithmen
    • Zufallsmethoden in der Informatik
  • WS 2020/2021
    • Formale Grundlagen der Informatik
    • Projekt Algorithm Engineering
    • Algorithmen und Datenstrukturen
    • SAT Solving
    • Algorithmen zur Sequenzanalyse
    • Einführung in die Bioinformatik
    • Quantum Computing
    • Seminar Algorithmik: (Computational) Group Theory
    • Proseminar Algorithmen: (Computational) Number Theory
  • WS 2020/2021
    • Formale Grundlagen der Informatik
    • Quantum Computing
    • Einführung in die Bioinformatik
    • Algorithmen zur Sequenzanalyse
    • SAT Solving
    • Algorithmen und Datenstrukturen
  • SS 2020
    • Algorithmische Spieltheorie
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Komplexitätstheorie
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Projekt Algorithm Engineering
    • Seminar Algorithmik: Computational (Algebraic) Topology
  • WS 2019/2020
    • Algorithmen und Datenstrukturen
    • Algorithmen für schwierige Probleme
    • Algorithmen zur Sequenzanalyse
    • Einführung in die Bioinformatik
    • Seminar Einführung in die Algorithmik: Themenkomplex Algorithmische Zahlentheorie
    • Seminar Algorithmik: Themenkomplex Algorithmische Zahlentheorie
    • Proseminar Algorithmen
    • Formale Grundlagen
    • Zufallsmethoden in der Informatik
  • SS 2019
    • Datenkompression
    • SAT Solving
    • Seminar Algorithmische Geometrie
    • Projekt Algorithm Engineering
    • Algorithmische Spieltheorie
    • Berechenbarkeit und Komplexität
    • Logik
    • Proseminar Algorithmen
    • Kryptologie: Algorithmen und Methoden
    • Seminar Algorithmik: Themenkomplex Kryptologie
    • Seminar Einführung in die Algorithmik: Themenkomplex Kryptologie
  • WS 2018/2019
    • Quantum Computing
    • Einführung in die Bioinformatik
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Formale Grundlagen der Informatik
    • Seminar (Einführung in die Algorithmik) & Seminar (Algorithmik): Themenkomplex Kryptologie
    • Proseminar (Algorithmen): Themenkomplex SAT-Solving
    • Highlights der Theoretischen Informatik
  • SS 2018
    • Algorithmen der Bioinformatik
    • Algorithmische Spieltheorie
    • Berechenbarkeit und Komplexität
    • Logik
    • Datenkompression
    • Kryptologie: Algorithmen und Methoden
    • Kryptologie: Mathematische Grundlagen
    • Scheduling
    • Projekt Algorithm Engineering
  • WS 2017/2018
    • Einführung in die Bioinformatik
    • Algorithmen für schwierige Probleme
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Formale Grundlagen der Informatik
    • Zufallsmethoden in der Informatik
    • Projekt Algorithmen Engineering
    • Seminar Algorithmik
    • Seminar Fun with Reductions
    • Proseminar Algorithmen
  • SS 2017
    • Algorithmische Spieltheorie
    • Berechenbarkeit und Komplexität
    • Komplexitätstheorie
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Scheduling
    • Proseminar Algorithmen
    • Seminar Algorithmik
    • Projekt Algorithm Engineering
  • WS 2016/2017
    • Algorithmen für schwierige Probleme
    • Einführung in die Bioinformatik
    • Einführung in die Informatik
    • Formale Grundlagen der Informatik
    • Highlights der Theoretischen Informatik
    • Proseminar Algorithmen
    • Seminar Algorithmik
  • SS 2016
    • Algorithmen der Bioinformatik
    • Algorithmische Spieltheorie
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Formal Foundtions of Computer Science
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Proseminar Klassiker der Informatik
    • Proseminar Algorithmen
    • Projekt Sequenzanalyse
  • WS 2015/2016
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Formale Grundlagen der Informatik
    • Einführung in die Bioinformatik
    • Quantum Computing
    • SAT Solving
    • Proseminar Parametrisierte Algorithmen
    • Proseminar Algorithmen
    • Seminar Modern C++ Style
    • Implementierung von Kompressionsverfahren
  • SS 2015
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Einführung in die Informatik
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Proseminar Algorithmen
  • WS 2014/2015
    • Algorithmen für schwierige Probleme
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Einführung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • Highlights der Theoretischen Informatik
    • Modern C++ Style
    • Algorithmische Geometrie
    • Proseminar Algorithmen
    • Algorithmen der Logik
  • SS 2014
    • Algorithmen der Bioinformatik
    • Algorithmische Spieltheorie
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Komplexitätstheorie
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Parametrisierte Algorithmen
    • Algorithmen der Logik
    • Algorithmen für Optimierungsprobleme
    • Implementierung von Bioinformatik-Algorithmen
  • WS 2013/2014
    • Algorithmen für schwierige Probleme
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Einführung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • SAT Solving
    • Proseminar Algorithmen
    • Algorithmische Geometrie
    • Natur-inspirierte Algorithmen
    • Neue Programmierkonzepte in C++11
    • Algorithmen der Logik
  • SS 2013
    • Datenkompression
    • Einführung in die Informatik
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Quantum Computing
    • Klassiker der Informatik
    • Algorithmen der Logik
  • WS 2012/2013
    • Algorithmen für schwierige Probleme
    • Algorithmen und Datenstrukturen
    • Boolesche Funktionen und Schaltkreise
    • Formale Grundlagen der Informatik
    • Proseminar Algorithmen
    • Algorithmen der Logik
  • SS 2012
    • Algorithmen zur Sequenzanalyse
    • Berechenbarkeit und Komplexität
    • Komplexitätstheorie
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Praktische Informatik
    • SAT Solving
    • Proseminar Informationsübertragung
    • Seminar Datenkompression
    • Unkonventionelle Algorithmen
    • Algorithmen der Logik
  • WS 2011/2012
    • Algorithmen der Bioinformatik
    • Algorithmen für schwierige Probleme
    • Algorithmen und Datenstrukturen
    • Einführung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • Highlights der Theoretischen Informatik
    • Proseminar Algorithmen
    • Seminar Algorithmische Geometrie
    • Projekt Bioinformatik
    • Implementierung von web-Suchmaschinen
  • SS 2011
    • Algorithmen der Bioinformatik
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • SAT Solving
    • Proseminar Algorithmen
    • Proseminar Informationsübertragung
    • Seminar Algorithmen in der Graphentheorie
    • Indexing and Compressing the Textual Web
    • Projekt SAT-Solving
  • WS 2010/2011
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Einführung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • Höhere Algorithmik
    • Quantum Computing
    • Proseminar Algorithmen
    • Seminar: Advanced Data Structures
    • Seminar: Probleme in NP
  • SoSe 2010
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Komplexitätstheorie
    • Kryptologie: Algorithmen und Methoden
    • Logik
    • Praktische Informatik
    • Proseminar Algorithmen
    • Seminar Algorithmen in der Graphentheorie
    • Seminar Bioinformatik
    • Seminar Search Engines
    • Projekt SAT-Solving
    • Projekt Sequenzanalyse
  • WS 2009/2010
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Einführung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • Highlights der Theoretischen Informatik
    • Höhere Algorithmik
    • Seminar Algorithmische Geometrie
    • Praktikum: Datenkompression
    • SAT-Solving
    • Kryptographie Projekt / Praktikum SS09
  • SoSe 2009
    • Algorithmen der Bioinformatik
    • Berechenbarkeit und Komplexität
    • Datenkompression
    • Kombinatorische Methoden der Informatik
    • Kryptologie
    • Logik
    • SAT Solving
    • Proseminar Ideen der Informatik
    • Seminar Sequenzanalyse
    • Kryptographie Projekt / Praktikum SS09
    • Praktikum: Datenkompression
    • SAT-Solving + CSP
  • WS 2008/2009
    • Algorithmen und Datenstrukturen
    • Algorithmen zur Sequenzanalyse
    • Einfuehrung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • Höhere Algorithmik
    • Quantenrechner
    • Meilensteine der Informatik
    • Funktionale Programmierung in Haskell
    • Hauptseminar Datenkompression
    • SAT-Solving + CSP (Projektarbeit)
  • SoSe 2008
    • Algorithmen I
    • Highlights der Theoretischen Informatik
    • Kolmogorov-Komplexität
    • Komplexitätstheorie
    • Kryptographie
    • Theoretische Informatik II
    • Proseminar Informationsübertragung
    • Hauptseminar Bioinformatik
    • Succinct Data Structures and Compressed Suffix Arrays
  • WS 2007/2008
    • Algorithmen II
    • Algorithmen der Bioinformatik
    • Einfuehrung in die Bioinformatik
    • Formale Grundlagen der Informatik
    • Formale Methoden der Informatik (WiWi)
    • Kryptographie Praktikum WS07/08
    • Quantum Computing
    • Theoretische Informatik I
    • Proseminar Graphalgorithmen

Members

The institute has a team of experienced researchers and professors, including:

• Prof. Dr. Jacobo Torán
• Prof. Dr. Enno Ohlebusch
• Prof. Dr. Uwe Schöning
• Christiane Halder-Schnell
• M.Sc. Lisa-Marie Jaser
• Jannik Olbrich
• Ehemalige Mitarbeiter / Doktoranden
  • Dr. Thomas Büchler
  • Dr. Florian Wörz
  • Dr. Julian Nickerl
  • Dr. Jan-Hendrik Lorenz
  • M.Sc. Bogdan Adrian Dina
  • Dr. Uwe Baier
  • Dr. Gunnar Völkel
  • Dipl.-Inf. Helmut Sedding
  • Dipl.-Phys. Stefan Arnold
  • Dr. Martin Bader
  • Dipl. Inf. Adrian Balint
  • Dipl.-Inf. Timo Beller
  • Dipl.-Inf. Marcus Bombe
  • Dipl.-Inf. Sebastian Doern
  • Dr. Tobias Eibach
  • Dr. Oliver Gableske
  • Dr. Simon Gog
  • Dr. Thanh Minh Hoang
  • Dr. Dominikus Krüger
  • Dipl.-Inf. Adrian Kügel
  • Dr. Markus Maucher
  • Dr. Thomas Schnattinger
  • Dr. Simon Straub
  • Dr. Fabian Wagner
  • Dr. Henning Wunderlich
  • Dr. Patrick Scharpfenecker
  • Waltraud Fromm

Research

The institute is involved in various research areas, including:

• EDACC
• Sequence Analysis
• SAT Solving
• Dichte Packung von Garnrollen auf Paletten

Zufallsmethoden in der Informatik

Inhalt

Methoden der Wahrscheinlichkeitstheorie und Statistik: Zufallsvariablen, Verteilungen, erzeugende Funktionen, Abschätzungen, Zentraler Grenzwertsatz, statistische Tests, stochastische Prozesse. Randomisierte Datenstrukturen und Algorithmen, Markovketten und Zufallsirrfahrten, Entropie und Information, Monte Carlo Methode, paarweise Unabhängigkeit und Hashing, Zufallsgraphen, probabilistischer Existenznachweis. Simulated Annealing und Ising-Modell. Pseudozufallszahlengeneratoren.

Literatur

• Ross: Probability Models for Computer Science. Academic Press, 2002.
• Mitzenmacher, Upfal: Probability and Computing. Cambridge, 2005.
• Schickinger, Steger: Diskrete Strukturen, Band 2. Springer, 2001.
• Häggström: Finite Markov Chains and Algorithmic Applications. Cambridge, 2002.
• Alon, Spencer: The Probabilistic Method. Wiley, 2015.
• Durrett: Random Graph Dynamics. Cambridge, 2007.
• Luby, Wigderson: Pairwise Independence and Derandomization. now Publ., 2006.
• Givens, Hoeting: Computational Statistics. Wiley, 2005.
• Mari, Schott: Probabilistic and Statistical Methods in Computer Science. Springer, 2001.
• Brémaud, Pierre: Discrete Probability Models and Methods, 2017.

Dozent

Prof. Dr. Uwe Schöning Prof. Dr. Hans Kestler

Vorlesungszeiten

Dienstag 12:00 - 14:00 Uhr
in O27/123 Mittwoch 12:00 - 14:00 Uhr
in O27/2202

Sonstiges

LSF-Eintrag Moodle Klausur "Zufallsmethoden in der Informatik" Dauer: 90 Minuten. Erlaubte Hilfsmittel an beiden Terminen sind ein beidseitig beschriebenes DIN A4-Blatt sowie ein Taschenrechner. Zur Verfügung gestellt wird ein Blatt mit der Tabelle der Standardnormalverteilung.