Deutsch Intern
    Chair of Computer Science I - Algorithms, Complexity, and Knowledge-Based Systems

    Lehrveranstaltungen der Gruppe Komplexitätstheorie

    Das regelmäßige Lehrangebot umfasst folgende Veranstaltungen:

    • Theoretische Informatik (I-TI)
    • Kryptographie und Datensicherheit (I-KD)
    • Komplexitätstheorie (I-KT)
    • Komplexitätstheorie II (I-KT2)
    • Automatentheorie (I-AUT)
    • Berechenbarkeitstheorie (I-BER)
    • Mathematische Logik (I-ML)
    • Seminar (I-SEM)

    Die Tabelle zeigt die geplanten Lehrveranstaltungen. Wir bemühen uns diesen Zeitplan zu realisieren, einzelne Abweichungen sind jedoch möglich.

    I-TI I-SEM I-KT I-KD I-AUT I-BER I-ML I-KT2
    SS 2013 X
    WS 2013 X X X
    SS 2014 X
    WS 2014 X X X
    SS 2015 X
    WS 2015 X X X
    SS 2016 X
    WS 2016 X X X
    SS 2017 X
    WS 2017 X X X
    SS 2018 X
    WS 2018 X X X
    SS 2019 X
    WS 2019 X X X
    SS 2020 X
    WS 2020 X X X
    SS 2021 X
    WS 2021 X X X

    Theoretische Informatik (I-TI, 10 ECTS, 4V+2Ü, Bachelor)
    Diese Vorlesung vermittelt grundlegende Begriffe, Ideen, und Vorgehensweisen der gesamten Informatik. Dabei geht es um prinzipielle Möglichkeiten und Beschränkungen des algorithmisch Lösbaren. Dies umfasst Fragen wie: Was ist algorithmische Lösbarkeit? Welche Aufgaben sind durch Maschinen lösbar? Wie schnell können bestimmte Aufgaben gelöst werden? Die Vorlesung gibt eine Einführung in die Gebiete Berechenbarkeit, endliche Automaten, formale Sprachen sowie Komplexität.

    Komplexitätstheorie (I-KT, 5 ECTS, 2V+2Ü, Bachelor/Master1)
    Komplexitätstheorie II (I-KT2, 5 ECTS, 2V+2Ü, Master-Vorlesung)
    Die Komplexitätstheorie betrachtet algorithmisch lösbare Probleme und fragt, wie schwierig sie zu lösen sind. Beispielsweise untersucht man, welche Probleme innerhalb einer bestimmten Rechenzeit gelöst werden können. Solche Beschränkungen führen zur Definition von Komplexitätsklassen, die diejenigen Probleme zusammenfassen, die sich innerhalb einer bestimmten Rechenzeit lösen lassen. Bekannte Komplexitätsklassen sind beispielsweise P und NP. Die Vorlesung I-KT bietet eine umfassende Einführung in die Komplexitätstheorie, während die Vorlesung I-KT2 weiterführende Fragen betrachtet.  Die behandelten Themen umfassen Beziehungen zwischen Komplexitätsklassen, vollständige Probleme, Relativierbarkeit, Isomorphievermutung, Polynomialzeit-Hierarchie sowie probabilistische Berechnungen.

    Kryptographie und Datensicherheit (I-KD, 5 ECTS, 2V+2Ü, Bachelor/Master1)
    Die Vorlesung skizziert die Entwicklung von der klassischen zur modernen Kryptographie. Neben Verschlüsselungsverfahren werden auch interessante, kryptographische Protokolle vorgestellt. Die behandelten Themen umfassen symmetrische Kryptosysteme wie AES, perfekte Sicherheit, asymmetrische Kryptosysteme wie RSA, digitale Signaturen, Identifikation und Secure Multiparty Computation.

    Automatentheorie (I-AUT, 5 ECTS, 2V+2Ü, Master)
    Die Vorlesung untersucht die Klassen der Chomsky-Hierarchie, vor allem die regulären Sprachen und die sternfreien Sprachen. Neben den aus der Vorlesung Theoretische Informatik bekannten Konzepten wie endliche Automaten, reguläre Ausdrücke und Typ-3-Grammatiken betrachtet man weitere Begriffe wie endliche Monoide und Formeln der Logik erster Stufe über Wörtern. Die Vorlesung zeigt, dass sich die regulären Sprachen und die sternfreien Sprachen durch jedes dieser Konzepte charakterisieren lassen und stellt bis heute ungelöste Entscheidbarkeitsfragen im Zusammenhang mit regulären Sprachen vor.

    Berechenbarkeitstheorie (I-BER, 5 ECTS, 2V+2Ü, Master)
    Die Vorlesung untersucht verschiedene Formen der algorithmischen Beherrschbarkeit von Mengen, wobei es vor allem um die Frage geht, wie viel Berechenbarkeit in unentscheidbaren Mengen steckt. Die behandelten Themen umfassen berechenbare Funktionen, entscheidbare und aufzählbare Mengen, Reduzierbarkeit, relativierte Berechenbarkeit sowie die arithmetische Hierarchie.

    Mathematische Logik (I-ML, 5 ECTS, 2V+2Ü, Master)
    Die Vorlesung behandelt die Prädikatenlogik erster Stufe. Zunächst wird gezeigt, dass der Begriff des Folgerns mit dem Begriff des Beweisens übereinstimmt (Gödelscher Vollständigkeitssatz). Überdies geht die Vorlesung der Frage nach, welche mathematischen Theorien entscheidbar, axiomatisierbar bzw. vollständig sind. Wichtige Aussagen sind hier der Gödelsche Unvollständigkeitssatz und die Unentscheidbarkeit der Arithmetik.

    Seminar (I-SEM, 5 ECTS, Bachelor/Master)
    Das Seminar behandelt in der Regel das Thema Kryptographie.

    1 Die beiden Bachelor/Master-Vorlesungen können wahlweise im Informatik-Bachelor oder Informatik-Master eingebracht werden.

     

    Contact

    Lehrstuhl für Informatik I (Effiziente Algorithmen und wissensbasierte Systeme)
    Am Hubland
    97074 Würzburg

    Phone: +49 931 31-85054
    Email

    Find Contact

    Hubland Süd, Geb. Z8 Hubland Süd, Geb. M2