Seminar zu Schwierigen Problemstellungen

Themenvergabe: Mi, 17.01., 12:20 Uhr, HS 2.

Vortragstermine: Die Termine werden in der ersten Vorlesungswoche des Semesters festgelegt, unter Umständen in einer gesonderten Vorbesprechung, die allen mit Themen vesehenen Teilnehmern per email mitgeteilt wird. In der Vergangenheit wurde mehrheitlich für Blöcke an den vorlesungsfreien Tagen votiert. Im SS 2018 sind das der 31.05., 05.06., 29.06. und 11.07. Den letzten Verfügungstag möchte ich ungern nehmen, da er als Ersatztermin in Frage kommt.

Sprache: Der Vortrag darf zur Teilnahmemöglichkeit für unsere internationalen Studierenden auch auf Englisch gehalten werden, was mit einem Pluspunkt in der Bewertung berücksichtigt wird.

Teilnehmerkreis: Es werden Vorträge an Bachelor- und Masterstudierende aller IT-Studiengänge vergeben. Von Masterstudierenden wird eine vertiefte wissenschaftliche Auseinandersetzung erwartet.

Thematik

Um es gleich vorwegzunehmen: Diese Vorträge sind nicht notwendigerweise schwieriger als andere. Es sind die vorzustellenden Probleme, welche schwierig sind.

Eine Problemstellung wird als schwierig empfunden, wenn es bisher nicht bekannt ist, wie man diese in einer Laufzeit polynomiell in der Eingabegröße löst, oder wenn es überhaupt nicht bekannt ist, wie man diese auf einem Computer löst. In vielen Fällen wurde die Schwierigkeit sogar schon mathematisch nachgewiesen.

Dennoch kommen diese Problemstellungen in praktischen Aufgaben vor, und daher muss man sie irgendwie lösen, zum Beispiel indem man sie etwas abwandelt oder indem man einen Algorithmus angibt, der im schlechtesten Fall zwar exponentiell ist, aber in der betreffenden Aufgabe für die dort vorherrschenden Eingabebedingungen doch in akzeptabler Laufzeit zu sinnvollen Ergebnissen führt.

In diesem Seminar werden verschiedene schwierige Probleme behandelt und teilweise auch Lösungsansätze für diese.

Ferner gibt es die Möglichkeit, ein Thema aus der Bioinformatik oder Musikinformatik vorzuschlagen. Dieses muss nicht notwendigerweise eine schwierige Problemstellung behandeln. Wer ein solches Thema haben möchte, sollte auf jeden Fall mit mir vor der Vergabe darüber sprechen. Als Ausgangspunkt können meine Seminare dienen, die es in früheren Semestern zu diesen Themen gab. Es dürfen davon verschiedene Problemstellungen behandelt werden oder auch dieselben Problemstellungen, aber dann mit Lösungsansätzen oder Aspekten, die im vergangenen Seminar nicht besprochen wurden. Im letzten Fall muss es eine klare Abgrenzung zum früheren Seminarvortrag geben.

Aufgrund der unterschiedlichen Problemstellungen kann keine einheitliche Literatur angegeben werden. In den meisten Fällen ist sie mir auch nicht bekannt. Die Erarbeitung geeigneter Quellen gehört zur wesentlichen Seminarleistung. Die bereits angegebene Literatur findet sich natürlich in unserer Bibliothek. Wenn Sie sich rechtzeitig darum bemühen, dann können wir von Ihnen als nützlich empfundene Literatur nachbestellen.

Eine Warnung sei vorausgeschickt: Auch wenn sich zu vielen Themen zahlreiche Internetreferenzen finden, so reicht es nicht aus, nur die ersten zu nehmen, die Google anzeigt (z.B. Wikipedia). Das würde zu oberflächliches Wissen generieren und häufig nicht den Kern der Fragestellungen treffen.

Vortragsthemen

1) Kryptographische Verfahren aufbauend auf der Schwierigkeit der Primzahlzerlegung (nur für B_TInf, B_ITE, B_STEC, B_CGT, B_IMCA)

Das wichtigste Verfahren ist das berühmte RSA-Verfahren, welches auch in den Veranstaltungen IT-Sicherheit oder Kryptographie-Workshop von Prof. Beuster behandelt wird. Ein weiteres ist der Blum-Blum-Shub-Generator, von dem mir aber keine praktische Anwendung bekannt ist.

Wegen der Behandlung in Prof. Beusters Vorlesungen darf sich um dieses Thema nur bewerben, wer in seinem Studiengang diese Veranstaltungen nicht besucht.

 

2) Effiziente Primzahlbestimmung

Es soll ein Algorithmus vorgestellt werden, mit dem man in polynomieller Zeit bestimmen kann, ob einer Zahl eine Primzahl ist oder nicht. Gerne können hierzu auch historische Bemerkungen gemacht werden. Neben der Originalarbeit von Agrawal und seinen indischen Absolventen wurde das auch in meiner nicht mehr angebotenen Vorlesung Computer-Algebra behandelt. Das Vorlesungsmaterial findet sich weiterhin auf meiner Vorlesungs-Webseite.

Ferner gibt es das Rabin-Müller-Verfahren, das immer noch der Stand der Technik ist, aber nicht mit letzter Sicherheit Primzahlen bestimmt. Auch dieses wurde in meiner Vorlesung Computer-Algebra behandelt.

Dieser Vortrag ist vor allem für Masterstudierende geeignet und setzt ein gutes Verständnis der Algorithmik oder Komplexitätstheorie voraus.

 

3) Versuche der effizienten Primzahlzerlegung

Es handelt sich hierbei um ein Problem, zu dem kein effizienter Algorithmus bekannt ist, weswegen es in der Kryptographie eingesetzt werden kann. Allerdings ist auch die Schwierigkeit des Problems noch nicht bewiesen. Es gibt verschiedene Verfahren dafür, die zum Beispiel in dem Buch von Kaplan beschrieben sind:

Michael Kaplan: Computeralgebra, Springer 2005, ISBN 3-540-21379-1

 

4) Effizienzverbesserungen bei der Berechnung eines Fahrplans (z.B. für die Bahn)

Die Berechnung eines Fahrplans ist mit dem Stundenplanproblem bekannt und als polynomiell schwierig zu lösen bewiesen (es ist NP-vollständig).

Dieses Thema sollte idealerweise jemand bearbeiten, der sich besonders für Fahrpläne interessiert und möglicherweise in diesem Gebiet schon erste berufliche Erfahrungen gesammelt hat (zum Beispiel in einem Praktikum).

Das Thema kann mit verschiedener Tiefe behandelt werden abhängig ob von einem Bachelor- oder Masterstudierenden.

 

5) Praktische Ansätze zur Lösung des Rucksackproblems (Knapsack)

Auch dieses Problem ist als NP-vollständig bekannt. Es ist eine in der Wissenschaftsgemeinde als Knapsack bekannte Problemstellung, welche in verschiedenen Varianten in vielen Beladungsproblemen eine Rolle spielt, in denen es darum geht, möglichst viele Güter auf engem Raum zu bepacken.

Das Thema kann mit verschiedener Tiefe behandelt werden abhängig ob von einem Bachelor- oder Masterstudierenden.

 

6) Vorstellung eines Problems mit exponentieller unterer Laufzeitschranke

Mir ist persönlich kein Problem bekannt, von dem das explizit bewiesen wurde. Aber es soll so etwas geben, zum Beispiel im Kontext des Schachspiels.

Dieses Thema eignet sich eher für Masterstudierende.

 

7) Unentscheidbare Probleme in der Praxis

Unentscheidbar heißt, dass man das Problem überhaupt nicht lösen kann (auch nicht ineffizient). Es gibt hierfür einen einführenden Artikel im Spektrum der Wissenschaft 09/17 (S. 72 ff.), der als Grundlage für weitere Recherchen dienen kann.

Das Thema kann mit verschiedener Tiefe behandelt werden abhängig ob von einem Bachelor- oder Masterstudierenden.

 

8) Problemstellung und dessen Lösung aus der Bioinformatik

Hier müssen Sie selbst einen Vorschlag machen.

 

9) Problemstellung und dessen Lösung aus der Musikinformatik

Hier müssen Sie selbst einen Vorschlag machen.