Modulcode:	Inf-MPAlgKombSeq
Englische Bezeichnung:	Master Project - Algorithmics and Combinatorics for Sequential Structures
Modulverantwortliche(r):	Prof. Dr. Dirk Nowotka
Turnus:	unregelmäßig (WS17/18 SS18 WS18/19 SS20 WS20/21 SS21 WS21/22 SS24)
Präsenzzeiten:	4PÜ
ECTS:	10
Workload:	300 Std. Projektarbeit, davon 60 Std. betreut
Dauer:	ein Semester
Modulkategorien:	MSc-Inf-Proj (MSc Inf (21)) 2F-MSc-Proj (2F-MA Inf (21)) Proj (MSc Inf (15))
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

In diesem Praktikum werden wechselnde Themenstellungen aus dem Bereich der Kombinatorik und Algorithmus auf Sequenzen behandelt. Dabei werden Inhalte aus den Vorlesungen Combinatorics on Words und Algorithms on Sequences praktisch vertieft.

Lernziele:

Die Studierenden sind in der Lage theoretische Fragestellungen über Sequenzen zu identifizieren sowie zu lösen und die Lösungsstrategien praktisch zu implementieren (bspw. in Python).

Lehrinhalte:

Die Untersuchung kombinatorischer und algorithmischer Eigenschaften von Wörtern ist ein zentrales Thema der Theoretischen Informatik, das sowohl in der Gebieten der Datenkompression, Kryptographie und Sprachtheorie, als auch in der Theorie algorithmischen Lernens, Datenbanktheorie und Bioinformatik zur Anwendung kommt. Ursprünglich motiviert durch zwei der zentralen Probleme der Wortkombinatorik und Wortalgorithmik, besonders Pattern Matching (Suche nach Mustern) sowie die Lösung von Wortgleichungen, schlagen wir darauf aufbauend die Untersuchung einer Reihe von neuen kombinatorischen und algorithmischen Fragen vor. Zum Beispiel: effizientes Suchen von Übereinstimmungen bei verschiedenen Typen von Mustern zweiter Ordnung (Mustern, die neben Konstanten-Symbolen auch Wort- und Funktionsvariablen enthalten); Identifizieren relevanter Klassen von Wortgleichungen, deren Erfüllbarkeit effizient entschieden werden kann; Verständnis, woraus die Schwierigkeiten beim Lösen von Wortgleichungen anderer Klassen resultieren.

Weitere Voraussetzungen:

• Programmierkenntnisse
• Interesse an Wortkombinatorik und Algorithmen

Prüfungsleistung:

Präsentation der Projektergebnisse

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Individuell zu den zu bearbeitenden Themen.

Verweise:

Kommentar: