Subject: Fwd: [Ml-iwimi-mi] Einladung zur Verteidigung
meiner Bachelorarbeit
This thesis defense is tomorrow in the noon seminar (the talk will be in
German)
-------- Weitergeleitete Nachricht --------
Betreff: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit
Datum: Thu, 14 Dec 2023 16:32:57 +0100
Von: "Yagmur Dönmez" <yagmud01@zedat.fu-berlin.de>
An: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, maria.koekenhoff@fu-berlin.de
Sehr geehrte Damen und Herren,
ich lade Sie hiermit herzlich zu Verteidigung meiner Bachelorarbeit mit
dem Titel "Vergleich der Streaming und Online Algorithmen für das
Kantenfärbungsproblem" ein.
Der Vortrag wird am 21.12.23 um 12:00 Uhr in der Takustraße 9 Raum 051
stattfinden.
Erstgutachter: Dr. rer. nat. Katharina Klost
Zweitgutachter: Prof. Dr. László Kozma
Mit freundlichen Grüßen
Yagmur Dönmez
Abstract
Die Kantenfärbung zählt zu den fundamentalsten Problemen innerhalb der
Graphentheorie. Im Streaming Modell werden die Kanten des Eingabegraphen
dem Algorithmus einzeln präsentiert. Hierbei ist der zur Verfügung
stehende Speicher kleiner als die Größe des Eingabegraphen, weshalb nicht
alle Kanten des Graphen gespeichert werden können. Da die Ausgabe genauso
groß ist wie die Eingabe selbst, müssen auch die Farben der Kanten als
Stream ausgegeben werden, das sogenannte W-Streaming. In der Vergangenheit
wurden schon einige Lösungen für dieses Problem in verschiedensten
Modellen vorgestellt. In dieser Arbeit werden wir uns die Entwicklung und
Fortschritte dieser genauer anschau- en. Zuletzt lieferten zwei
randomisierte Algorithmen im gegnerischen Kantenan- kunftsmodell, aus ESA
2019, SOSA 2021 und ESA 2022, die besten Ergebnisse. Hierbei färbt der
neueste jeden Graphen mit 2∆t Farben in O(n∆/t) Platz für jedes n ≤ ∆,
wobei ∆ der maximale Grad des Graphen ist. Diese Lösung bietet den
einzigen bekannten Online-Kantenfärbungsalgorithmus mit sublinearem
Platzbedarf. Unser Ziel ist es die verschiedenen Ergebnisse mit einander
zu vergleichen, um potenzielle Verbesserungen zu identifizieren.
==================================================================
Subject: Mittagsseminar am Dienstag, 19.12.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin spricht am
Dienstag, 19.12.2023, 12:00 Uhr, SR 051, Takustra=C3=9Fe 9
Benjamin Berendsohn
zum Thema: Fast and simple unrooted dynamic forests.
==================================================================
Subject: Mittagsseminar am Dienstag, 12.12.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 05.12.2023, 12:00 Uhr, SR 051, Takustraße 9
Günter Rote
zum Thema: Counting polyominoes up to 70 cells.
==================================================================
Subject: Mittagsseminar Donnerstag 07.12.2023
Das Mittagsseminar wird heute bestreikt.
==================================================================
Subject: Mittagsseminar am Dienstag, 05.12.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 05.12.2023, 12:00 Uhr, SR 051, Takustraße 9
Aruni Choudhary
zum Thema: About Funk and Hilbert geometry.
==================================================================
Subject: Mittagsseminar am Donnerstag, 30.11
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 30.11.2023, 12:00 Uhr, SR 051, Takustraße 9
Helena Bergold
zum Thema: Rafla's conjecture for convex drawings
==================================================================
Subject: Mittagsseminar am Dienstag, 28.11.2023
Das Mittagsseminar wird heute bestreikt.
==================================================================
Subject: Mittagsseminar am Donnerstag, 23.11
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 23.11.2023, 12:00 Uhr, SR 051, Takustraße 9
Michaela Krüger
zum Thema: About Feedback
==================================================================
Subject: Mittagsseminar am Dienstag, 21.11.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 21.11.2023, 12:00 Uhr s.t., SR 051, Takustraße 9
Franz J. Brandenburg (Passau)
zum Thema: Defining graphs by geometric objects
Zusammenfassung:
We consider graphs whose vertices are geometric objects in the plane,
such that there is an edge if and only if the objects
intersect, touch, are close, or are visible and see one another.
We emphasize fundamental results for the respective classes of graphs,
e.g., the complexity of the recognition problem,
and state open problems, in particular, for object visibility graphs.
==================================================================
Subject: Mittagsseminar 16.11.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 16.11.2023, 12:00 Uhr, SR 051, Takustraße 9
László Kozma
zum Thema: Verification through randomness.
==================================================================
Subject: Fwd: [i-prof] [i-studi] Invitation Master's
thesis defense
Reminder: this thesis defense is in today's noon seminar.
-------- Forwarded Message --------
Subject: [i-prof] [i-studi] Invitation Master's thesis defense
Date: Thu, 9 Nov 2023 12:09:54 +0100
Dear all,
I hereby invite you to the upcoming defense of my master's thesis, titled
"On Erdős-Szekeres Problem".
The defense will be held in room SR051 (Takustraße 9) on Tuesday, November
14th, 2023 at 12:00, and will be held in English.
Advisor and first reviewer: Prof. Dr. László Kozma
Second reviewer: Dr. rer. nat. Katharina Klost
Best regards，
Fang Lin
Abstract:
The Erdős-Szekeres theorem, established in the 1930s, posits that for a
sufficiently large set of points in the plane in general position, it is
guaranteed to contain n points forming a convex polygon. In other words,
there exists a quantity denoted as N(n) such that any set of N(n) points
contains a convex n-gon. This problem is colloquially referred to as the
"happy ending problem."
The exact value of N(n) remains elusive, motivating efforts to establish
both lower and upper bounds as accurately as possible. Over the course of
more than 90 years, extensive research has been dedicated to refining the
bounds. For general n, Erdős and Szekeres demonstrated in 1935that N(n) <=
\binom{2n-4}{n-2}+1 = 4^{n-o(n)}, while in 1961, they confirmed that
N(n)>= 2^{n-1}+1. Over the course of these 90 years, there have been eight
improvements to the original upper bound, albeit the majority of these
remain within the limit of 4^{n-o(n)}. A noteworthy development occurred
in 2016 when Andrew Suk improved the upper bound to 2^{n +o(n)}. The best
upper bound till today is 2^{n +O(\sqrt{nlogn)}}.
Recently, a pertinent question has arisen in an article by G.Damasdi et
al. concerning the Erdős-Szekeres problem. The question is to determine
the smallest value, denoted as S(n), for which a set of S(n) points in
general position in the plane does not form a convex n-gon initially, but
the addition of any arbitrary point results in the formation of a convex
n-gon. This question is of recent origin, with an unestablished upper
bound, and it remains unresolved, even in relatively simple cases.
This thesis will commence with an introduction to foundational concepts
and provide a historical perspective on the problem's evolution.
Subsequently, it will survey the existing upper and lower bounds from the
literature concerning the core Erdős-Szekeres problem, along with simpler
instances. Following this, the thesis will shift its focus to an
investigation of the open question, offering explanations for simple cases
and formulating a conjecture regarding its bounds. Finally, it will
introduce two interactive tools, namely, the saturation game and the
extremal game, both rooted in the Erdős-Szekeres theorem and the open
question.
==================================================================
Subject: Mittagsseminar am Dienstag, 09.11.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 09.11.2023, 12:00 Uhr, SR 051, Takustraße 9
Katharina Klost
zum Thema: Dynamic compressed quadtrees
==================================================================
Subject: Mittagsseminar am Dienstag, 07.11.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin sp=
richt am
Donnerstag, 07.11.2023, 12:00 Uhr, SR 051, Takustra=DFe 9
Mahmoud Elashmawi
zum Thema: Translational Packing of Convex Polygons
==================================================================
Subject: Mittagsseminar am Donnerstag, 2.11.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 2.11.2023, 12:00 Uhr, SR 051, Takustraße 9
Helmut Alt
zum Thema: About Space
==================================================================
Subject: Fwd: [i-prof] Invitation to my bachelor thesis
defence
Tomorrow's Mittagsseminar.
Please note the unusual time and location.
Cheers
Wolfgang
-------- Forwarded Message --------
Subject: [i-prof] Invitation to my bachelor thesis defence
Date: Tue, 24 Oct 2023 20:26:18 +0200
Dear all,
I would like to invite you to my bachelor thesis defence, titled
"Persistent Binary Search Trees and Their Practical Applications."
The defence will be held in room SR053 (Takustraße 9) on Tuesday,
October 31st, 2023 at 14:30. English will be the language of the defence.
Advisor and first reviewer: Prof. Dr. Wolfgang Mulzer
Second reviewer:Prof. Dr. László Kozma
Best regards,
Chao Zhan
Abstract:
Ephemeral data structures retain only the most recent version of the
data structures, while persistent data structures maintain a full history
of the data structures. Fortunately, several methods can be employed
to make any pointer-based ephemeral data structure persistent. This
thesis aims to clarify and analyse classical approaches and apply them
to the implementation of persistent binary search trees. Subsequently,
we evaluate the efficiency of these approaches by conducting several
benchmark tests. Furthermore, a partially persistent binary search tree
is employed to address the traditional planar point location problem.
This approach offers a solution with O(n) space cost, O(logn) query
time, and O(nlogn) preprocessing time.
==================================================================
Subject: Mittagsseminar - 26.10.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 26.10.2023, 12:00 Uhr, SR 051, Takustraße 9
Max Willert
zum Thema: Orthogonal guarding a 1.5d terrain
==================================================================
Subject: Mittagsseminar am Dienstag, 24.10.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der
FU Berlin spricht am
Dienstag, 24.10.2023, 12:00 Uhr, SR 051, Takustraße 9
Oskar Besler
zum Thema: Vergleich von kernbasierten Routing-Algorithmen
in Straßennetzwerken (B.Sc.-Verteidigung, auf Deutsch/in German)
Hintergrund: Das effiziente Finden eines kürzesten Pfades in einem
Straßennetzwerk zwischen zwei Positionen ist eine wichtige Aufgabe für
Echtzeitanwendungen wie Navigationssysteme, um flexibel auf dynamische
Veränderungen im Straßennetzwerk, wie Änderungen von Start- und
Endpositionen, reagieren zu können. In der Literatur gilt der
Highway-Hierarchies-Star-Algorithmus als einer der effizientesten
Algorithmen zur Ermittlung des kürzesten Pfades zwischen zwei Knoten in
einem Straßennetzwerk.
Ziele: In dieser Arbeit soll überprüft werden, ob der
Highway-Hierarchies-Star-Algorithmus tatsächlich effizienter ist als
verschiedene etablierte Algorithmen zum Finden des kürzesten Pfades, wie
in der Literatur beschrieben.
Methoden: Dafür werden verschiedene Algorithmen zur Berechnung des
kürzesten Pfades implementiert und anhand unterschiedlicher Suchanfragen
in deutschen Straßennetzwerken bewertet.
Ergebnisse: Die Experimente zeigen, dass der
Highway-Hierarchies-Star-Algorithmus die besten Ergebnisse bei den
Suchanfragen erzielt und dabei auch eine annehmbare Vorverarbeitungszeit
aufweist.
Schlussfolgerungen: Der Highway-Hierarchies-Star-Algorithmus bietet
schnelle Anfragezeiten in statischen Graphen, sodass verschiedene Anfragen
mit unterschiedlichen Start- und Endpositionen in Millisekunden berechnet
werden können. Dies bestätigt weitgehend die Bewertung in der Literatur.
Dennoch sind weitere Tests auf dynamischen Graphen erforderlich, um eine
komplette Beurteilung vornehmen zu können.
==================================================================
Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar 19.10.2023
Muss krankheitsbedingt leider ausfallen...
> Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
> spricht am
>
> Donnerstag, 19.10.2023, 12:00 Uhr, SR 055, Takustraße 9
> Max Willert
> zum Thema: Orthogonal guarding a 1.5d terrain
>
> _______________________________________________
> agti-Mittagsseminar mailing list
> agti-Mittagsseminar@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/agti-mittagsseminar
> _______________________________________________
> Automatischer Mailverteiler an Gruppe 'ml-ti-mi'.
> Hinweise dazu siehe Hilfeseite:
> https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler
>
==================================================================
Subject: Mittagsseminar 19.10.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 19.10.2023, 12:00 Uhr, SR 055, Takustraße 9
Max Willert
zum Thema: Orthogonal guarding a 1.5d terrain
==================================================================
Subject: Mittagsseminar am 21.09.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 26.09.2023, 12:00 Uhr, SR 055, Takustraße 9
Kristin Knorr
zum Thema: Cops and robbers on 1-planar graphs
==================================================================
Subject: Mittagsseminar am 21.09.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 21.09.2023, 12:00 Uhr, SR 055, Takustraße 9
Helena Bergold
zum Thema: Fliples in Signotopes
==================================================================
Subject: Mittagsseminar am 19.09.2023
Attention: Note the changed room SR 051 (instead of the usual SR 055)!
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 19.09.2023, 12:00 Uhr, SR 051 (!), Takustraße 9
Jonas Cleve
zum Thema: Patrolling Grids With a Bit of Memory
==================================================================
Subject: Mittagsseminar am 14.09.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 14.09.2023, 12:00 Uhr, SR 055, Takustraße 9
Michaela Krüger
zum Thema: Grid USO to Cube USO - Part 1
==================================================================
Subject: Noon Seminar 12.9.2023
In the Noon Seminar on
Tuesday 12th Sept, Location: SR 55 (or 53), Takustraße 9,
László Kozma
will talk about: Finding saddle-points faster than sorting.
==================================================================
Subject: Mittagsseminar am 07.09.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 07.09.2023, 12:00 Uhr, SR 055, Takustraße 9
Katharina Klost
zum Thema: Balanced Separators in Polygonal Domains
==================================================================
Subject: Mittagsseminar Dienstag, 05.09.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin sp=
richt am
Dienstag, 05.09.2023, 12:00 Uhr, SR 053, Takustra=DFe 9
Mahmoud Elashmawi
zum Thema: Complete Colorings of Planar Graphs
==================================================================
Subject: Mittagsseminar am Donnerstag, 31.08.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 31. August 2023, 12:00 Uhr, SR 055, Takustraße 9
Wolfgang Mulzer
zum Thema: Card-based cryptography
==================================================================
Subject: Mittagsseminar Dienstag, 29.8.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 29. August 2023, 12:00 Uhr, Seminarraum 055
Helmut Alt
zum Thema: Restricted Knapsack
==================================================================
Subject: Mittagsseminar 24.8.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 24.08.2023, 12:00 Uhr, SR 055, Takustraße 9
Max Willert
zum Thema: Approximating the burning number
==================================================================
Subject: Mittagsseminar Dienstag, 22.8.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin spricht am
Dienstag, 22. August 2023, 12:00 Uhr, Seminarraum 053
Benjamin Berendsohn
zum Thema: Twin-width of binary structures
==================================================================
Subject: Mittagsseminar Dienstag,
15.8.2023 und Donnerstag, 17.8.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 15. August 2023, 12:00 Uhr, Seminarraum 053
Helena Bergold
zum Thema: k-intersecing pseudoconfiguration of points
und am
Donnerstag, 17. August 2023, 12:00 Uhr, Seminarraum 053
Günter Rote
zum Thema: Packing and tiling a Square with squares and with
rectangles
==================================================================
Subject: Mittagsseminar Dienstag,
08.08.2023 und Donnerstag, 10.08.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 8. August 2023, 12:00 Uhr, Seminarraum 053(?)
Helena Bergold
zum Thema: k-intersecing pseudoconfiguration of points
und am
Donnerstag, 10. August 2023, 12:00 Uhr, Seminarraum 053
Günter Rote
zum Thema: Packing and tiling a Square with squares and with
rectangles
==================================================================
Subject: Fwd: [Ml-iwimi-mi] Einladung zur Verteidigung
meiner Bachelorarbeit
Tommorow in the noon seminar, potentionally in German.
-------- Weitergeleitete Nachricht --------
Betreff: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit
Datum: Sun, 16 Jul 2023 22:15:16 +0200
Von: Philipp Walter <zuramm@zedat.fu-berlin.de>
An: i-studi@inf.fu-berlin.de
Kopie (CC): i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
maria.koekenhoff@fu-berlin.de
Sehr geehrte Damen und Herren,
hiermit lade ich Sie zu der Verteidigung meiner Bachelorarbeit
mit dem Titel "Experimental Evaluation of Algorithms for Long Plane Trees"
ein.
Die Verteidigung findet am Donnerstag, den 20.07.2023, um 12:00 Uhr im
Seminarraum 055, Takustr. 9 statt.
Erstgutachterin: Dr. Katharina Klost
Zweitgutachter: Prof. Dr. Wolfgang Mulzer
Mit freundlichen Grüßen
Philipp Walter
Abstract: Longest planar spanning trees are thought to be an NP-hard task.
One approach to such problems is to relax the solution’s criteria. This
can be achieved by identifying solutions that are not necessarily the
longest spanning tree but are planar. This paper investigates the lower
bound of the approximation factor of algorithms producing planar spanning
trees. We analyze the algorithm proposed in Cabello et al. (2021). The
algorithm finds AB trees that improve star graphs. The star is a simple
graph proposed by Alon et al. (1993), where one point is connected to
every other point. The AB tree algorithm attempts to improve the star by
adding zig-zag edges, which increases the total length. To analyze the
approximation factors, we implement four algorithms: the aforementioned AB
tree algorithm, a brute force algorithm for the longest planar spanning
tree, a longest spanning tree algorithm, and a specialized algorithm for
convex point sets. A genetic algorithm was used to find point sets with
low approximation factors programmatically. The brute force algorithm
implementation performed poorly and was only utilized for point sets of no
more than 10 points. We analyzed point sets with approximation factors of
less than 0.9. The genetic algorithm’s output has an approximation factor
of 0.9 as well. The sets with low approximation factors are very elongated
point sets, particularly ellipsoid forms. In this work, the lowest
approximation factor determined is 0.877. Our analysis finds a more overly
stretched graph results in an even lower approximation factor.
==================================================================
Subject: Mittagsseminar Donnerstag,
06.07.2023 und Dienstag, 11.07.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 18. Juli 2023, 12:00 Uhr, SR 053, Takustraße 9
Felix Schröder (TU Berlin)
zum Thema: Linear Size Universal Point Sets for Classes of Planar Graphs
==================================================================
Subject: Mittagsseminar Donnerstag, 13.07.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 13. Juli 2023, 12:00 Uhr, SR 055, Takustraße 9
Kristin Knorr
zum Thema: Short flip sequences to untangle segments in the plane
==================================================================
Subject: Mittagsseminar Donnerstag,
06.07.2023 und Dienstag, 11.07.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 6. Juli 2023, 12:00 Uhr, SR 055, Takustraße 9
Jonas Cleve
zum Thema: Pattern Formation with Fat Robots
und am
Dienstag, 11. Juli 2023, 12:00 Uhr, SR 053, Takustraße 9
Anand Srivastav (Universität Kiel)
zum Thema: The Chromatic Number of Randomly Augmented Graphs
==================================================================
Subject: noon seminar 4th July
Dear all,
in the noon seminar on Tuesday, 4th July, I will talk about saddle points.
Best regards,
Laszlo
==================================================================
Subject: Noon Seminar today
Dear all,
today in the noon seminar a thesis defense (MSc):
Claas Frederic Fandré
"Bounds on the mixing time of Catalan structures"
Best regards,
Laszlo
==================================================================
Subject: Mittagsseminar Dienstag, 27.06.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin spricht am
Dienstag, 27.06.2023, 12:00 Uhr, SR 053, Takustraße 9
Katharina Klost
zum Thema: Planar Obstacle Number
==================================================================
Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
Masterarbeit
Tomorrow's noon seminar will be a Master defense, see below.
Cheers
Wolfgang
-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: Fri, 16 Jun 2023 12:23:43 +0200
Sehr geehrte Damen und Herren,
hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit dem
Titel „Optimierung des Konfigurationsprozesses von Retail-Geräten durch
Entwicklung einer domänenspezifischen Sprache” ein.
Die Verteidigung findet am 22.06.23 um 12 Uhr im Rahmen des
Mittagsseminars der AG Theoretische Informatik im Raum SR 055 statt.
Erstgutachter und Betreuer der Arbeit ist Prof. Dr. Wolfgang Mulzer,
Zweitgutachter ist Dr. Sönke Kannapinn.
Die Arbeit wurde ebenfalls von Denis Kuniß von der Diebold Nixdorf Systems
GmbH betreut.
Mit freundlichen Grüßen
Sebastian Kuzniarz
Zusammenfassung:
Die vielschichtige Komplexität in der Entwicklung, Pflege und
Konfiguration von Software verlangt eine kontinuierliche
Prozessoptimierung zur Effizienzsteigerung und Fehlerminimierung. Aus
diesem Grund wird innerhalb dieser Arbeit eine domänenspezifische
Konfigurationssprache für die Bibliothekssoftware ProBase Store des
Unternehmens Diebold Nixdorf entwickelt, um den aktuellen
Konfigurationsprozess von Retail-Geräten zu optimieren.
Im theoretischen Teil dieser Arbeit wird ein fundiertes Verständnis für
formale Sprachen, Grammatiken und Compilerbau geschaffen, welches als
Basis für die Entwicklung einer domänenspezifischen Sprache dient.
Anschließend werden domänenspezifische Sprachen (DSLs) als Schnittstellen
zwischen Mensch und Maschine definiert, was eine Bewertung hinsichtlich
Usability ermöglicht. Diese Definition dient der Entwicklung einer dem
Entwicklungsprozess folgenden Nutzerstudie zur Evaluation der
Konfigurations-DSL hinsichtlich Effektivität, Effizienz sowie
Benutzerzufriedenheit.
Auf Basis der theoretischen Grundlagen wird eine DSL unter Verwendung des
Xtext-Frameworks entwickelt. Die Entwicklung beruht auf einer umfassenden
Analyse der Konfigurationsdomäne und der dem vorherigen
Konfigurationsprozess zugrundeliegenden Sprache, welche es ermöglicht,
eine die DSL beschreibende kontextfreie Grammatik zu definieren. Darauf
aufbauend werden sämtliche Bestandteile der DSL, einschließlich
Validierungs- und Scoping-Mechanismen sowie die Abbildung auf die
ursprüngliche Sprache, implementiert und in einen für den
Konfigurationsprozess optimierte Web-basierten Editor integriert.
In einer Nutzerstudie mit 12 Teilnehmer:innen wird die entwickelte
domänenspezifische Sprache (DSL) mit dem bisherigen Prozess verglichen.
Die Ergebnisse der Studie zeigen, dass Teilnehmer:innen im Vergleich zum
alten Prozess bei der Bearbeitung von Testaufgaben durchschnittlich 46,88
% weniger Zeit benötigen sowie 16,66 % weniger Fehler mit der
DSL-basierten Lösung machen. Dies sorgt für eine signifikante Verbesserung
in Bezug auf Effektivität (von 80,13 % auf 96,79 %) und Effizienz (von
76,91 % auf 93,59 %). Hinsichtlich Usability wird mit Hilfe der
System-Usability-Scale (SUS) für den DSL-basierten Prozess ein
durchschnittlicher Score von 87,71 ermittelt, was eine deutliche
Steigerung im Vergleich zum alten Prozess (SUS-Score: 30,21) darstellt. Im
Allgemeinen gelten Systeme mit einem SUS-Score von über 68 als
überdurchschnittlich gut. Die Ergebnisse verdeutlichen das Potenzial von
DSLs, um Entwicklungs- und Konfigurationsprozesse in Softwareprojekten zu
optimieren, insbesondere wenn diese mit Toolunterstützung für Nutzer:innen
zur Verfügung stehen.
==================================================================
Subject: Mittagsseminar Dienstag 20.06.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin spricht am
Dienstag, 20.06.2023, 12:00 Uhr, SR 053, Takustraße 9
Michaela Borzechowski
zum Thema: Necklace Splitting with Unique Solutions
==================================================================
Subject: Mittagsseminar 15.06.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin spricht am
Donnerstag, 15.06.2023, 12:00 Uhr, SR 053, Takustraße 9
Benjamin Berendsohn
zum Thema: Twin-width and Arborially Satisfied Supersets
==================================================================
Subject: Mittagsseminar 13.06.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 13.06.2023, 12:00 Uhr, SR 053, Takustra=DFe 9
Mahmoud Elashmawi
zum Thema: Lower Bounds of Longest Monotone Paths in Line Arrangements
==================================================================
Subject: Mittagsseminar am Donnerstag, 08.06
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 07. Jui 2023, 12:00 Uhr, SR 055, Takustraße 9
Wolfgang Mulzer
zum Thema: Follow the leader
==================================================================
Subject: Mittagsseminar 6.62023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 06.06.2023, 12:00 Uhr, SR 053, Takustraße 9
Max Willert
zum Thema: Moores Bound
==================================================================
Subject: noon seminar Thursday, 1st June
Dear all,
tomorrow in the noon seminar a talk by Arash Pourdamghani (TU Berlin)
with details below.
(afterwards some spicy candy I brought from Finland ;)
Best,
Laszlo
*Title:*
SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree (Paper
<https://pourdamghani.net/_pages/INFOCOM23SeedTree.pdf>)
*Abstract:*
The vision of developing self-adjusting networks is now a reality. For
example, programmable optical networking switches are already being used
in big tech companies such as Googleand Microsoft. However, theoretical
foundations are lagging behind in this area: previous methods have been
designed by having fixed and limited networking resources in mind. In
this talk, I detail the background and explain a novel model of the
problem inspired by data center networking needs. I will show how online
and randomized algorithms are being used to develop a more efficient
technique that is optimized toward and match the traffic workload they
serve, proving the dynamic optimality of the algorithm.
*About:*
Arash Pourdamghani is a direct Ph.D. student at the INET
<https://www.linkedin.com/company/inet-tuberlin/> group at the Technical
University of Berlin, Germany, and also an associated researcher at the
Weizenbaum Institute <https://www.weizenbaum-institut.de/en>. Previously
he was a researcher at the University of Vienna and completed research
internships at IST Austria and CUHK. He got his B.Sc. from the Sharif
University of Technology. He is interested in algorithm design and
analysis with applications in networks, distributed systems, and
blockchains. His particular focus is on self-adjusting networks
<https://self-adjusting.net/>.
==================================================================
Subject: Mittagsseminar am 30.5.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 30.5.2023, 12:00 Uhr, SR 053, Takustraße 9
Helena Bergold
zum Thema: 41 NP-hard sign mappings
==================================================================
Subject: Mittagsseminar am 23.05.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 23.05.2023, 12:00 Uhr, SR 053, Takustraße 9
Kristin Knorr
zum Thema: Obstacle Numbers of Graphs
==================================================================
Subject: Mittagsseminar am 16.5.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 16.5.2023, 12:00 Uhr, SR 053, Takustraße 9
Günter Rote
zum Thema: The length of the grid parabola, and
how the zeta function comes about
==================================================================
Subject: Mittagsseminar am 09.05.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 09.05.2023, 12:00 Uhr, SR 053, Takustraße 9
Jonas Cleve
zum Thema: Voronoi Diagrams of Rotating Rays
==================================================================
Subject: NO Mittagsseminar today
Dear TIs,
I apologize for the short notice, but I will not be able to give the
Mittagsseminar today.
Jonas
==================================================================
Subject: Fwd: [all] Einladung zur Verteidigung meiner
Bachelorarbeit
Noon Seminar today, note that the room is 055 (normal noon seminar room)
-------- Weitergeleitete Nachricht --------
Betreff: [all] Einladung zur Verteidigung meiner Bachelorarbeit
Datum: Thu, 27 Apr 2023 00:04:58 +0200
Von: Konstantin Jaehne <konstijaehne@zedat.fu-berlin.de>
An: all@mi.fu-berlin.de, maria.koekenhoff@fu-berlin.de
Sehr geehrte Angehörige des Informatik-Instituts,
hiermit lade ich zur Verteidigung meiner Bachelorarbeit mit dem Titel
"Analyse und experimenteller Vergleich von Suchalgorithmen für sortierte
Matrizen" am 27.04. um 12:00 ein (T9 SR055).
Betreuerin: Dr. Katharina Klost
Zweitkorrektor: Prof. Dr. Wolfgang Mulzer
Mit freundlichen Grüßen
Konstantin Jaehne
-----------------------
Zusammenfassung:
In dieser Arbeit geht es um Suchalgorithmen in spalten- und zeilenweisen
sortierten Matrizen. Neben der herkömmlichen Zeitkomplexität soll ein
besonderes Augenmerk auf dem asymptotischen Verhalten der Anzahl der
Vergleiche eines Elements (der Matrix) mit dem gesuchten Objekt liegen. Es
wird ein Suchalgorithmus für endliche n×m-Matrizen vorgestellt und eine
detaillierte Komplexitätsanalyse vorgenommen. Zudem werden alternative
Algorithmen präsentiert und miteinander verglichen.
==================================================================
Subject: thesis defense
today in the noon seminar, talk starting in a few minutes..
-------- Forwarded Message --------
Subject: [i-prof] Invitation to the defense of my Bachelor's thesis
Date: Mon, 17 Apr 2023 18:05:34 +0200
Dear all,
I hereby invite you to the defense of my Bachelor's thesis with the title:
"Algorithms for optimal search trees on trees".
The defense will take place on Thursday, 20.04.2023 at 12:00 in room
T9/053(Takustr. 9). The defense presentation will be held in English.
First examiner: Prof. Dr. László Kozma
Second examiner: Prof. Dr. Wolfgang Mulzer
Supervisor: Prof. Dr. László Kozma
Best regards,
Johannes Voderholzer
Abstract:
Finding optimal binary search trees in terms of minimal search cost for a
sequence of key queries is a well studied problem in computer science. An
important theorem over the combinatorial structure of the problem found by
Knuth in 1971 can be used to speed up a dynamic program for the problem to
O(n^2) time, where n is the number of keys. Recently, Berendsohn and Kozma
gave a 2-approximation algorithm for a generalization of optimal binary
search trees to search trees on trees, which runs in O(n^3) time. We show,
that Knuth theorem also holds in this setting and use it to improve the
running time of the algorithm to O(min(D^2*L^2, n^3)), where D denotes
the diameter and L the number of leaves of the search space tree. We give
a full implementation of both algorithms and verify the correctness and
running time on randomly generated trees of different types. Further, we
show that a bound given by Mehlhorn for binary search trees can be
generalized to search trees on trees.
==================================================================
Subject: Mittagsseminar am 18.04.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 18.04.2023, 12:00 Uhr, SR 055, Takustra=C3=9Fe 9
Alexander Kauer
zum Thema: Quadforests on the real RAM in our dynamic disk =
connectivity data structure=20=
==================================================================
Subject: NO Mittagsseminar am 13.04.2023
Hello everybody,
Unfortunately, it seems that I caught a cold over easter=E2=80=94there =
will be no noon seminar today.
Have a nice day,
Alexander=
==================================================================
Subject: Mittagsseminar am 10.04.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 11.04.2023, 12:00 Uhr, SR 055, Takustraße 9
Katharina Klost
zum Thema: Classification of bichromatic points with outliers
==================================================================
Subject: Mittagsseminar 6.4.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin
spricht am
Donnerstag, 06.04.2023, 12:00 Uhr, SR 055, Takustraße 9
Benjamin Berendsohn
zum Thema: k-server with pattern-avoiding input
==================================================================
Subject: Mittagsseminar 4.4.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 04.04.2023, 12:00 Uhr, SR 055, Takustraße 9
Johannes Obenaus
zum Thema: Induced Paths
==================================================================
Subject: Mittagsseminar 16.3.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 16.03.2023, 12:00 Uhr, SR 055, Takustra=DFe 9
Mahmoud Elashmawi
zum Thema: Upper bounds for Deterministic online b-matching on (k,d)-gr=
aphs
==================================================================
Subject: Noon Seminar Tuesday 14.3.2023
Dear all,
today in the noon seminar an online talk (via Webex).
Tan Junqi, a master student at Harbin Institute of Technology (China)
will give the talk:
"The Shapley Value of Maximum Independent Set in perfect graphs"
Webex Link:
https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=m54d9759049fd72e8ba8c6a4189884582
Best regards,
Laszlo
==================================================================
Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar am Donnerstag 09.02.
und Dienstag 14.02.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 09. März 2023, 12:00 Uhr, SR 055, Takustraße 9
Helmut Alt
zum Thema: On online packing
==================================================================
Subject: Mittagsseminar 7.3.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 07.03.2023, 12:00 Uhr, SR 055, Takustraße 9
Max Willert
zum Thema: TSP (... not what you think :-D)
==================================================================
Subject: Fwd: Einladung Verteidigung Bachelorarbeit
Today in the noon seminar.
Best,
Laszlo
-------- Forwarded Message --------
Subject: [i-prof] Einladung Verteidigung Bachelorarbeit
Date: Wed, 1 Mar 2023 13:32:45 +0100
Sehr geehrte Damen und Herren,
ich lade Sie hiermit zur Verteidigung meiner Bachelorarbeit mit
dem Titel ""An Algorithm for Hierarchical Clustering - Experiments and
Analysis" ein. Der Vortrag wird am 02.03.2023 um 12:00 Uhr in der
Takustraße 9 Raum 055 auf Englisch stattfinden.
Erstgutachter: Prof. Dr. László Kozma
Zweitgutachter: Prof. Dr. Helmut Alt
Betreuer: Prof. Dr. László Kozma
Viele Grüße,
Arman Durmus
***
Dear Sir or Madam,
I hereby invite you to the defense of my bachelor thesis titled "An
Algorithm for Hierarchical Clustering - Experiments and Analysis". The
presentation will take place on 02.03.2023 at 12:00 am in Takustraße 9
room 055 in english.
First examiner: Prof. Dr. László Kozma
Second examiner: Prof. Dr. Helmut Alt
Supervisor: Prof. Dr. László Kozma
Best regards,
Arman Durmus
***
Zusammenfassung(Abstract):
We present and analyze a new algorithm idea to hierarchically cluster data,
and show that it performs well compared to other established hierarchical
clustering methods when evaluated based on Dasgupta’s cost function. We
prove that in one iteration, our algorithm finds the optimal hierarchical
clustering tree for the given order of the points, when limited to
hierarchical clustering trees the leaves of which have the same ordering
as said points.
Additionally, we show that the cost of the found tree can only improve or
remain the same with each iteration. Thus, the presented algorithm can be
used for hierarchical clustering tasks, or on the results of other
hierarchical clustering algorithms to improve those, and
leaves room for theoretical improvements and experimentation.
==================================================================
Subject: Mittagsseminar am Dienstag, 28.02
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 28. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Wolfgang Mulzer
zum Thema: Nabil Mustafa's proof of the eps-net theorem
==================================================================
Subject: Mittagsseminar am Donnerstag 23.02.2023
Jetzt nochmal mit korrektem Datum...
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 23. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Kristin Knorr
zum Thema: Crossing-free Matchings in Geometric Graphs Part Two
==================================================================
Subject: Mittagsseminar am Dienstag 21.02.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 21. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Kristin Knorr
zum Thema: Crossing-free Matchings in Geometric Graphs Part Two
==================================================================
Subject: Mittagsseminar am Dienstag 21.02.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 21. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Helena Bergold
zum Thema: Strong Erdős-Hajnal properties in chordal graphs
==================================================================
Subject: Mittagsseminar am Donnerstag 16.02.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 16. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Jonas Cleve
zum Thema: Minimum color number for gap-less nearest neighbor
graphs in 1d
==================================================================
Subject: Mittagsseminar am Donnerstag 09.02. und
Dienstag 14.02.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 09. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Michaela Borzechowski
zum Thema: On Phases of USOs - Part 1: Definitions & a small proof
Dienstag, 14. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Michaela Borzechowski
zum Thema: On Phases of USOs - Part 2: More proofs
==================================================================
Subject: Mittagsseminar am Dienstag, 07.102
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 07. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
Wolfgang Mulzer
zum Thema: Lower Bounds for Selection (results from the 80s)
==================================================================
Subject: Mittagsseminar am Donnerstag, 02.02.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 02.Februar 2023, 12:00 Uhr, SR 055, Takustraße 9
JKatharina Klost
zum Thema: Shortest Paths with Multiple Edge-Cost Estimates
Please observe the current safety constraints (FFP2 masks recommended),
seehttps://www.fu-berlin.de/sites/coronavirus/
==================================================================
Subject: Mittagsseminar am Dienstag, 24.01.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 24. Januar 2023, 12:00 Uhr, SR 053, Takustraße 9
Johannes Obenaus
zum Thema: Flip Graphs for Arrangements of Pseudocircles
Please observe the current safety constraints (FFP2 masks recommended),
see https://www.fu-berlin.de/sites/coronavirus/
Mittagsseminar schedule: <https://mycampus.imp.fu-berlin.de/x/PjuUIf>
==================================================================
Subject: [Mittagsseminar T
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 19.01.2023, 12:00 Uhr, SR 055, Takustraße 9
Helmut Alt
zum Thema: Online Sorting
==================================================================
Subject: Mittagsseminar am Dienstag, 17.01.
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 17. Januar 2023, 12:00 Uhr, SR 053, Takustra=DFe 9
Mahmoud Elashmawi
zum Thema: Crossing-Free Matchings in Geometric Graphs
Please observe the current safety constraints (FFP2 masks recommended),
see https://www.fu-berlin.de/sites/coronavirus/
Mittagsseminar schedule: <https://mycampus.imp.fu-berlin.de/x/PjuUIf>
==================================================================
Subject: Mittagsseminar 12.1.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 12.01.2023, 12:00 Uhr, SR 055, Takustraße 9
Max Willert
zum Thema: Cantor vs. Kronecker
==================================================================
Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
Bachelorarbeit
Today's mittagsseminar (in German).
Cheers
Wolfgang
-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Thu, 29 Dec 2022 22:35:18 +0100
Sehr geehrte Damen und Herren,
hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem Titel
"Analyse und Vergleich verschiedener Sortieralgorithmen" ein.
Die Verteidigung findet am Donnerstag, den 05.01 um 12:00 Uhr im SR 055
statt.
Erstgutachter: Prof. Dr. Wolfgang Mulzer
Zweitgutachter: Dr. rer. nat. Max Willert
Mit freundlichen Grüßen,
Glenn Schneider
Zusammenfassung:
Sortierverfahren sind ein großes Thema in der Informatik und über die
Jahre werden immer wieder neue Sortieralgorithmen entwickelt.
Sortieralgorithmen sind außerdem oft Themen von wissenschaflichen Arbeiten
und es wird heute noch erforscht, wie man sie verbessern kann.
Es stellt sich die Frage, warum es so viele verschiedene Algorithmen gibt,
was deren Vor- und Nachteile sind und in welchen Situationen man welchen
Algorithmus verwenden sollte. Gibt es einen ”besten” Sortieralgorithmus
den man immer verwenden soll oder ist es eher sinnvoll, basierend auf den
gegebenen Daten einen bestimmten Algorithmus auszuwählen?
Das Ziel dieser Arbeit ist die Implementierung von ausgewählten
Sortieralgorithmen und die Erstellung verschiedener Testfälle, mit denen
die Algorithmen in unterschiedlichen Situationen getestet und verglichen
werden können. Damit soll experimentell die Frage beantwortet werden, wie
sehr es sich lohnt, je nach Situation verschiedene Sortieralgorithmen zu
verwenden.
==================================================================
Subject: Mittagsseminar am Dienstag, 03.01.2023
Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU
Berlin spricht am
Dienstag, 03. Januar 2023, 12:00 Uhr, SR 055, Takustraße 9
Jonas Cleve
zum Thema: The (geometric) goat problem
Please observe the current safety constraints (FFP2 masks recommended),
see https://www.fu-berlin.de/sites/coronavirus/
==================================================================