Themenvergabe: war am Mi, 17.01., 12:20 Uhr, HS 2. Es wurden zwei Vorträge vergeben (siehe unten).

Vortragstermine: 05.06., HS 3, 09:00 Uhr - 11:30 Uhr, genaue Termine siehe unten

Sprache: Alle Vorträge sind auf Deutsch.

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

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.

Die im Folgenden verlinkten Ausarbeitungen und Vortragsunterlagen sind im Original dargestellt und ausschließlich von den Verfassern bearbeitet worden. Daher kann der Lehrveranstalter keine Gewähr für die Qualität und Richtigkeit geben.

1) Versuche der effizienten Primfaktorzerlegung

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

Vortragender: Alexander Stein

05.06.2018, 09:00 Uhr, HS 3

Vortrag   Ausarbeitung

2) 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.

Vortragender: Clemens Rawald

05.06.2018, 10:15 Uhr, HS 3

Vortrag   Ausarbeitung