Section : Seminar: Algorithmen | WS24: Seminar Algorithmik

Résumé de section

Umfang:	5 ECTS, 2 SWS
Zeit & Ort:	dienstags, 16:00–17:30 Uhr, Raum SE III (Informatikgebäude)
Voraussetzung:	Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmische Graphentheorie zum Einsatz, diese besucht zu haben ist deshalb sehr empfohlen. Für einige Theman kann Vorwissen aus einer der Masterveranstaltungen Visualisierung von Graphen, Algorithmische Geometrie oder Exakte Algorithmen hilfreich sein, ist aber nicht erforderlich.
Zielgruppe:	Master Informatik (empfohlen), Bachelor Informatik
Dozenten:	Alexander Wolff, Boris Klemz und Diana Sieper

Wenn Sie am Seminar teilnehmen möchten, kommen Sie zum ersten Termin am Dienstag, den 15.10.2024, um 16:00 Uhr – dieser wie auch das gesamte Seminar wird in Präsenzform stattfinden (sofern es keine anderslautende Regelung gibt). An diesem Termin bitten wir um vollständige Anwesenheit, da wir den Ablauf des Seminars besprechen und die Themenverteilung festlegen. Die Liste der Themen finden Sie bald weiter unten auf dieser Seite. Diese werden je nach Teilnehmerzahl jeweils alleine oder zu zweit bearbeitet. Machen Sie sich schon vorab Gedanken, welche Themen Sie gerne bearbeiten würden.

Bitte schreiben Sie sich schon jetzt in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen wollen. Melden Sie sich dazu bei WueCampus an (das haben Sie wahrscheinlich schon getan) und klicken in der "sekundären Navigationsleiste" (der Bereich unter dem Kurstitel) auf "Mich in diesen Kurs einschreiben" beziehungsweise "Enrol me in this course".

Thema in diesem Semester: Allgemeine Themen der Algorithmik

In diesem Semester deckt das Seminar einen weiten Bereich des Themenfelds Algorithmik ab. Die meisten Themen beziehen sich auf sehr aktuelle Forschungsergebnisse, einige sind ältere Klassiker. Betrachtet werden dabei hauptsächlich eher theoretische Erkenntnisse. Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmischer Graphentheorie zum Einsatz. Für einige Themen kann es hilfreich sein, eine der Vorlesungen Visualisierung von Graphen, Algorithmische Geometrie oder Exakte Algorithmen gehört zu haben, es ist aber nicht erforderlich. Manche Themen enthalten spannende offene Forschungsfragen. Wenn in der zweiten Hälfte des Seminars Zeit bleibt, kann daran gemeinsam geforscht werden. Dies kann auch zu Themen von Praktika, sowie Abschlussarbeiten im Anschluss an das Seminar führen.

Thema	Quellen (bei mehr als eine Quelle ist die Hauptquelle hervorgehoben)
Global and local edge-length ratios of planar straight line graph drawings	https://arxiv.org/abs/2311.14634, https://www.sciencedirect.com/science/article/pii/S0304397518306078?vi%3Dihub, https://jocg.org/index.php/jocg/article/view/3096, https://www.worldscientific.com/doi/abs/10.1142/S0218195921500072
Recognition Complexity of Subgraphs of 2- and 3-Connected Planar Cubic Graphs	https://arxiv.org/abs/2401.05892,
Revisting ILP Models for Exact Crossing Minimization in Storyline Drawings	https://submission.dagstuhl.de/collections/GD-2024/preliminary-proceedings/2Sx8Jdx8vzneFOKh5379
Boundary Labeling in a Circular Orbit	https://submission.dagstuhl.de/collections/GD-2024/preliminary-proceedings/Ee1PvVXvVq9EcTWZ5370
The Parameterized Complexity of Extending Stack Layouts	https://submission.dagstuhl.de/collections/GD-2024/preliminary-proceedings/F3eEJiVT189zsjiT5366
Parameterized Complexity of Simultaneous Planarity	https://arxiv.org/abs/2308.11401
Uncrossed Number of Graphs	https://submission.dagstuhl.de/collections/GD-2024/preliminary-proceedings/e4LUN88xq9hOL7SU536c
Computing the Enclosing Depth	https://arxiv.org/abs/2402.12371
Improving the Crossing Lemma	https://submission.dagstuhl.de/collections/GD-2024/preliminary-proceedings/iexgCm4EaZAsGbiD5377
The Density Formula	https://submission.dagstuhl.de/collections/GD-2024/preliminary-proceedings/nq647aiGOqwkJJDc5361
Paired Approximation Problems and Incompatible Inapproximabilities	https://arxiv.org/abs/0909.1870
Induced Matchings in Subcubic Graphs	https://arxiv.org/abs/1312.1110
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositionsy	https://link.springer.com/content/pdf/10.1007/s00453-009-9296-1.pdf
Solving 2-SAT in Linear Time	Wird im Seminar / per Email kommuniziert.
Kuratowski's Theorem	TBA

Lernziele

Ziel ist es, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen Kursteilnehmern und -teilnehmerinnen in einem Vortrag zu vermitteln.

Sie bekommen im Seminar einen Überblick über Techniken der Algorithmik und vertiefen ihre Kenntnisse über das Modellieren und Lösen von Problemen mithilfe von Graphen und Graphalgorithmen, sowie über parametrisierte Komplexität. Dieses Thema eignet sich übrigens auch gut für Abschlussarbeiten.

Module

Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik eingetragen.

Tim Hegemann

Boris Klemz

Marie Sieper

Samuel Wolf

Alexander Wolff

Résumé de section