Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar am 14.12.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 21.12.2017
Helmut Alt
zum Thema: Für manche Kunstgalerien lohnen sich irrationale Wächter
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 19.12.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 7.11.2017, 12 Uhr, SR 130 (Arnimallee 3)
Jonas Cleve
zum Thema: The Length of the Beacon Attraction Trajectory
==================================================================
Subject: Mittagsseminar am 14.12.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 14.12.2017
Boris Klemz
zum Thema: Paired Approximation Problems
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar 12.12.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 12.12.2017, 12 Uhr, SR 130 (Arnimallee 3)
Max Willert
zum Thema: Stabbing Disks and LP-type problems
==================================================================
Subject: Fwd: [all] Einladung zur Verteidigung meiner
Bachelorarbeit
Tomorrow.
-------- Forwarded Message --------
Subject: [all] Einladung zur Verteidigung meiner Bachelorarbeit
Liebe Institutsangeh=F6rige,
hiermit m=F6chte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit =
mit
dem Titel "Fast dynamic planar convex set maintenance using finger trees"=
einladen. Die Verteidigung findet am Dienstag, 5. Dezember, um 12:15 Uhr
in der Arnimallee 3, SR 130 statt. Betreut wurde die Arbeit von Prof. Dr.=
Wolfgang Mulzer.
Abstract:
Let a convex set in the plane be given by either a set of points or
half-spaces. The maintenance of it under insertion and deletion of
elements is a fundamental problem in computational geometry. This thesis
considers a data-structure which solves this problem. It was drafted by
the researchers Kaplan, Tarjan and Tsioutsiouliklis in a paper about
kinetic heaps (priority queues with linear functions as keys rather than
fixed values). However it was never written down in detail. We state thei=
r
construction explicitly. Its foundation is built by a deletion-only
structure which uses finger trees (height balanced trees with preferred
access points) to represent convex sets. With the semi-dynamic structure
at hand, a fully dynamic one may be constructed using given dynamization
transformations. The binary counting scheme transformation of Bentley and=
Saxe yields an insertion-and-deletion structure with $O(\log^2 n)$
worst-case vertical ray query time, $O(\log n)$ amortized insertion time
and $O(\log n \log \log n)$ amortized deletion time. A transformation of
Brodal and Jacob results in a structure with $O(\log n)$ worst-case
vertical ray query time, $O(\log n \log \log \log n)$ amortized insertion=
and $O(\log n \log \log n)$ amortized deletion time.
Viele Gr=FC=DFe,
Chris Hofer
==================================================================
Subject: Mittagsseminar am Donnerstag 30.11.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 30.11.2017
Günter Rote
über Kallus’s linear-time algorithm for the largest
triangle in a convex polygon
***************************************************
Ort: Takustraße 9, Seminarraum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar 28.11.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 28.11.2017, 12:00 Uhr s.t.
Bahareh Banyassady
zum Thema: Point location via violator spaces
*************************************
==================================================================
Subject: Mittagsseminar 28.11.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 28.11.2017, 12:00 Uhr s.t.
Bahareh Banyassady
zum Thema: Point location via violator spaces
*************************************
==================================================================
Subject: Mittagsseminar 21. 11. und 23. 11.
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 21.11.2017, 12 Uhr, A3, SR 130
Frank Hoffmann
zum Thema: Two Art Gallery Results for Orthogonal Simple Polygons
und am
Donnerstag, 23.11.2017, 12 Uhr, SR 055
Claudia Dieckmann
zum Thema: Voronoi Diagram in the Laguerre Geometry and its Applications
==================================================================
Subject: Mittagsseminar 14.11. und 16.11.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 13.11.2017, 12 Uhr, A3, SR 130
Katharina Klost
zum Thema: L. Stacho's proof for stabbing disks with 5 points
und am
Donnerstag, 16.11.2017, 12 Uhr, SR 055
Nadja Scharf
zum Thema: Online Square-into-Dynamic-Square Packing
==================================================================
Subject: Mittagsseminar am 7. und 9.11.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 7.11.2017, 12 Uhr, SR 055
Jonas Cleve
zum Thema: Covering Orthotrees with Beacons
und am
Donnerstag, 9.11.2017, 12 Uhr, SR 055
Max Willert
zum Thema: Cops, Robbers and Doughnuts
==================================================================
Subject: Mittagsseminar am 02.11.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 02.11.2017
Boris Klemz
zum Thema: Non-Crossing Connectors in Pseudodisks
and an Application: the Tube Problem
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar 24. und 26.10.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 24.10.2017, 12:00 Uhr s.t., SR 055
Helmut Alt
zum Thema: Not all bierdeckels can fit in a finite
finite container simultaneously
und am
Donnerstag, 26.10.2017, 12:00 Uhr s.t., SR 055
Günter Rote
zum Thema: Simulation of nondeterministic Turing machines
==================================================================
Subject: Mittagsseminar 17. und 19.10.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 17.10.2017, 12 Uhr, SR 055
Astrid Sturm
zum Thema: Bayesian Networks, Decision Graphs
and the ClimeFish project
Donnerstag, 19.10.2017, 12 Uhr, SR 055
Wolfgang Mulzer
zum Thema: Cap sets and the rank miracle
==================================================================
Subject: Miitagsseminar am 12.10.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 12.10.2017
Klaus Kriegel
zum Thema:
Bisecting masses with two cuts
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar 05.10.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 05. 10. 2017
Bahareh Banyassady
zum Thema: Palanar Directed Reachability Problem.
***************************************************
Ort: Takustra=C3=9Fe 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. (vielleicht 11:45 s.t!)
==================================================================
Subject: Mittagsseminar am 21.09
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 21.09.2017
Boris Klemz
zum Thema: Disk Obedient Drawings
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar 19.9.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 14.9.2017, 12 Uh, SR 055
Katharina Klost
zum Thema: Min-cuts and Shortest Cycles in Planar Graphs in O(n
log log n) Time
==================================================================
Subject: Mittagsseminar 14.9.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 14.9.2017, 12 Uhr, SR 055
Claudia Dieckmann
zum Thema:The Painter's Problem: covering a grid with colored
connected polygons
==================================================================
Subject: Mittagsseminar 12.9.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 12.09.2017, 12 Uhr, SR 055
Max Willert
zum Thema: The joy of SET
==================================================================
Subject: Mittagsseminar 5.9. + 7.9.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 5.9.2017, 12 Uhr, SR 055
Max Willert
zum Thema: Comparison Decision Trees
und
Donnerstag, 7.9.2017, 12 Uhr, SR 055
Frank Hoffmann
zum Thema: Collaborative Grid Searching
==================================================================
Subject: Mittagsseminar am 25.07.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 24.07.2017
Wolfgang Mulzer
zum Thema:
Covering Planar Graphs with a Fixed Number of Balls
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 22.08.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 22.08.2017
Nadja Scharf
zum Thema:
Packing Disks in 3D
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
--=20
Nadja Scharf
Freie Universit=C3=A4t Berlin
Institut f=C3=BCr Informatik
AG Theoretische Informatik
Takustra=C3=9Fe 9, Raum 122
14195 Berlin
==================================================================
Subject: Mittagsseminar 10.8 und 15.8
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 10. 8. 2017
Bahareh Banyassady
zum Thema:
General Sequential Time-Space Tradeoff for Finding Unique Elements
und am
Dienstag, 15. 8. 2017
Günter Rote
zum Thema: Majority colorings
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar (10.08 und 15.08)
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 10. 8. 2017
Bahareh Banyassady
zum Thema: General Sequential Time-Space Tradeoff for Finding
Unique Elements.
und am
Dienstag, 15. 8. 2017
Günter Rote
zum Thema: Majority colorings
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar (10.08 und 15.08)
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 10. 8. 2017
Bahareh Banyassady
zum Thema: General Sequential Time-Space Tradeoff for Finding
Unique Elements.
und am
Dienstag, 15. 8. 2017
G=C3=BCnter Rote
zum Thema: Majority colorings
***************************************************
Ort: Takustra=C3=9Fe 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Fwd: [i-prof] [i-studi] Einladung zur
Verteidigung meiner Bachelorarbeit
und um 12
-------- Forwarded Message --------
Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarb=
eit
Date: Fri, 4 Aug 2017 13:42:33 +0200
From: "Tobias Gro=C3=9F" <gross1989@zedat.fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de
Sehr geehrte Damen und Herren,
hiermit m=C3=B6chte ich Sie herzlich zur Verteidigung meiner Bachelorarbe=
it mit
dem Titel "Algorithmen und Anwendungen f=C3=BCr das Triangle Scheduling
Problem" einladen. Die Verteidigung findet am 08.08.2017 um 12 Uhr s.t. i=
m
Raum 055 in der Takustra=C3=9Fe 9 statt. Die Arbeit wurde von Dr. Claudia=
Dieckmann betreut.
Zusammenfassung:
Das Triangle Scheduling Problem, von D=C3=BCrr u.a. in [1] vorgestellt, i=
st ein
Spezialfall von Mixed-criticility Scheduling mit Jobs in Form
gleichschenkliger Dreiecke. Da es NP-schwer ist, kann der optimale
Zeitplan im Allgemeinen nur mittels Brute-Force-Algorithmus gefunden
werden, unter der Annahme P=E2=89=A0NP.
Der effiziente gierige Ansatz, jeweils das gr=C3=B6=C3=9Fte Dreieck in di=
e gr=C3=B6=C3=9Fte
L=C3=BCcke im Zeitplan zu setzen, kann in vielen F=C3=A4llen die optimale=
L=C3=B6sung
ermitteln, wie quantitative Tests mit gleich verteilt zuf=C3=A4lligen Job=
gr=C3=B6=C3=9Fen
zeigen. An den wenigen Beispielen mit nicht optimalem Ergebnis kann man
untersuchen, wann der gierige Algorithmus die falsche Entscheidung trifft=
=2E
Dar=C3=BCber hinaus kann mit Hilfe dynamischer Programmierung eine
(1+=CE=B5)-Approximation des optimalen Zeitplans gefunden werden. Indem d=
ie
Jobgr=C3=B6=C3=9Fen und Startzeiten vorher aufgerundet werden, reduziert =
sich die
L=C3=B6sung dabei auf die L=C3=B6sung von O(n^log(n)) vielen Teilprobleme=
n.
In dieser Arbeit entwerfe ich die drei Algorithmen in Pseudocode und
implementiere sie in der Programmiersprache Java.
Au=C3=9Ferdem ist das Triangle Scheduling Problem geometrisch betrachtet =
ein
Spezialfall des Packungsproblems in einem Rechteck und ich verallgemeiner=
e
den Brute-Force-Algorithmus auf andere Figuren wie gleichseitige Dreiecke=
,
Kreise etc.
Mit freundlichen Gr=C3=BC=C3=9Fen
Tobias Gro=C3=9F
[1] C. D=C3=BCrr, Z. Hanz=C3=A1lek, C. Konrad, R. Sitters, O. C. V=C3=A1s=
quez, and G. J.
Woeginger, =E2=80=9CThe triangle scheduling problem,=E2=80=9D CoRR, vol. =
abs/1602.04365,
2016. [Online]. Available: http://arxiv.org/abs/1602.04365
==================================================================
Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
Bachelorarbeit
Um 11.
-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Fri, 4 Aug 2017 13:32:31 +0200
From: Jakob K=F6hler <jakob.koehler@fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, Zentiks, Sera Renee
<serarenee.zentiks@fu-berlin.de>, Sch=FCler, Diana
<diana.schueler@fu-berlin.de>
Sehr geehrte Damen und Herren,
hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem
Titel "Optimale Orientierung eines 3D-Modells f=FCr den Metalldruck" ein.=
Die Pr=E4sentation findet am Di. 08.08.17, 11 Uhr s.t., im SR 055 der
Takustra=DFe 9 statt. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer
betreut. Zweitgutachter ist PD Dr. rer. nat. Klaus Kriegel.
Zusammenfassung:
Beim 3D-Druck dient die St=FCtzstruktur der Stabilisierung des Modells
w=E4hrend des Druckprozesses. Da die St=FCtzstruktur das Modell von unten=
abst=FCtzt, wirkt sich dessen Orientierung im Raum stark auf das Volumen
der notwendigen St=FCtzstruktur aus. Es l=E4sst sich zeigen, dass das
Problem der optimalen Orientierung eines 3D-Modells unter diesem
Gesichtspunkt in polynomieller Zeit l=F6sbar ist. Desweiteren wird ein
approximativer Algoritumus vorgestellt, welcher das Problem f=FCr konvexe=
Modelle in linearer Zeit l=F6st. In modifizierter Form l=E4sst sich der
Algorithmus auch auf nicht-konvexe Modelle anwenden, was allerdings in
einer quadratischen Laufzeit resultiert. In der Auswertung zeigt sich,
dass durch Anwendung des Algorithmus auf bestimmte Modelle signifikante
Einsparungen in den Materialkosten erzielt werden k=F6nnen.
Mit freundlichen Gr=FC=DFen
Jakob K=F6hler
==================================================================
Subject: Mittagsseminar am 27. Juli 2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 27.7.2017
Tillmann Miltzow
zum Thema:
Is area universality ∀∃R-complete? (forall-exists-Ⓡeals-complete)
(joint work with Michael G. Dobbins, Linda Kleist, Paweł Rzążewski)
***************************************************
Ort: Takustr. 9, Seminarraum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 25.07.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 25.07.2017
Wolfgang Mulzer
zum Thema:
Yet another proof of Chernoff's bound
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 20.07.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 20.07.2017, 12 Uhr, SR 055
Katharina Klost
zum Thema: Weighted girth in directed planar graphs
==================================================================
Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar am 18.07.2017
"das Wenden"
On 18.07.2017 10:21, Helmut Alt wrote:
>> Im Rahmen des Mittagsseminars der
>> Theoretischen Informatik der FU Berlin
>> spricht am
>>
>> Dienstag, 18.07.2017
>> Helmut Alt
>> zum Thema:
>> Über das Weneden eines konvexen Vielecks in einem ebensolchen
>>
>> ***************************************************
>> Ort: Takustr. 9, RM 055
>>
>> Uhrzeit: 12 Uhr s.t.
>> ***************************************************
>>
==================================================================
Subject: Mittagsseminar am 18.07.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 18.07.2017
Helmut Alt
zum Thema:
Über das Weneden eines konvexen Vielecks in einem ebensolchen
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar, 6.7.17
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 6. 7. 2017, 12:00 Uhr s.t., SR 055
Claudia Dieckmann
zum Thema: Maximum-Area Triangle in a Convex Polygon
==================================================================
Subject: Fwd: Einladung zur Verteidigung meiner
Bachelorarbeit
Mittagsseminar morgen.
-------- Forwarded Message --------
Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner
Bachelorarbeit
Sehr geehrte Damen und Herren,
hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit mit
dem Titel "Jump Point Search auf verallgemeinerten Spielbrettern" ein.
Die Verteidigung findet am Dienstag, den 4.7.2017, um 12:00 Uhr im
Raum 055 in der Takustra=C3=9Fe 9 statt.
Die Gutachter sind Prof. Dr. Wolfgang Mulzer und Dr. Claudia
Dieckmann. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut.
Abstrakt der Arbeit:
Jump Point Search (kurz JPS) ist ein neuer Algorithmus in der Wegfindung.=
Durch seine herausragenden Performance findet er, vor allem in der
Spiele-Entwicklung, viel Anwendung.
Leider beschr=C3=A4nkt sich die Definition dieses Algorithmus' auf
quadratische Gitter.
Meine Arbeit besch=C3=A4ftigte sich mit der Idee den Anwendungsbereich de=
s
JPS zu erweitern.
Hierf=C3=BCr abstrahierte und mathematisierte ich sowohl seine Entwicklun=
g,
als auch seine Handlungsweise,
adaptierte dieses Konzept auf regelm=C3=A4=C3=9Fige Dreiecks-tesselierte =
Fl=C3=A4chen
und arbeitete die Kriterien f=C3=BCr eine Verallgemeinerung heraus.
Den entstandenen Algorithmus analysierte ich stochastisch und testete
ihn gegen den "Jack of all trades"-Pathfinder A*.
Mit freundlichen Gr=C3=BC=C3=9Fen
Felix Wiener
==================================================================
Subject: Mittagsseminar heute 29. 6. 2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 29. 6. 2017, 12:00 Uhr s.t., SR 055
Günter Rote
zum Thema: Stable matching in a grid
==================================================================
Subject: Mittagsseminar 20.+22.06.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 20.06.2017, 12 Uhr, SR 055
Frank Hoffmann
zum Thema: Two classical graph coloring results
und
Donnerstag, 22.06.2017, 12 Uhr, SR 055
Max Willert
zum Thema: Distributed algorithm for maximal independet set
==================================================================
Subject: Mittagsseminar am 15.06.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 15.06.2017
Bahareh Banyassady
zum Thema:
A simple analysis of Rabin's algorithm for finding closest pairs
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 13.06.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 13.06.2017
Edouard Bonnet
zum Thema:
subexponential algorithms in non sparse classes of graphs
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 08.06.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 08.06.2017
Wolfgang Mulzer
zum Thema:
Joints and the Polynomial Method
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar 6.6. 2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 6.6.2017
Katharina Klost
zum Thema: Happy edge and vertex colorings
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
==================================================================
Subject: Mittagsseminar 30.5. und 1.6.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 30. 5. 2017
Günter Rote
zum Thema: Multidimensional divide and conquer: closest pairs
und am
Donnerstag, 1. 6. 2017
Klaus Kriegel
zum Thema: Closed meanders
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
==================================================================
Subject: Mittagsseminar 18. und 23.05.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 18.05.2017, 12 Uhr, SR 055
Wolfgang Mulzer
zum Thema: Adaptive Point Location in Planar Convex Subdivisions
Dienstag, 23.05.2017, 12 Uhr, SR 055
Katinka Wolter
zum Thema: Swimming with Fishes and Sharks: Beneath the Surface
of Queue-based Ethereum Mining Pools
==================================================================
Subject: Mittagsseminar 16.05.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 16.05.2017, 12 Uhr, SR 055
Max Willert
zum Thema: The Ice-cream Lemma
==================================================================
Subject: Mittagsseminar am 09. und 11.05.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 09.05.2017
Boris Klemz
zum Thema: Towards a Topology-Shape-Metrics Framework for
Ortho-Radial Drawings
und am
Donnerstag, 11.05.2017
Frank Hoffmann
zum Thema: The proper orientation number of undirected graphs
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 4.5.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 4.5.2017
Bahareh Banyassady
zum Thema: Find an area maximizing triangle inscribed in a given
convex polygon
***************************************************
Ort: Takustra=C3=9Fe 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
==================================================================
Subject: Mittagsseminar am 2.5.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 2.5.2017
Katharina Klost
zum Thema: Intersections of regular polygons with pairwise excluded centers
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar am 25. und 27. 4. 2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 25. 4. 2017
Günter Rote
zum Thema: Maximum induced matchings in convex bipartite graphs
und am
Donnerstag, 27. 4. 2017
Frank Hoffmann
zum Thema: The proper orientation number of undirected graphs
***************************************************
Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar 20.4.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 20.04.2017, 12 Uhr, SR 055
Claudia Dieckmann zum Thema:
The triangle scheduling problem
==================================================================
Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
Masterarbeit
-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: Tue, 28 Mar 2017 11:23:05 +0200
From: Jonas Cleve <jonascleve@mi.fu-berlin.de>
To: i-prof@inf.fu-berlin.de, i-wimi@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de
CC: diana.schueler@fu-berlin.de, SeraRenee.Zentiks@fu-berlin.de
Sehr geehrte Damen und Herren,
hiermit lade ich Sie zur Verteidigung meiner Masterarbeit mit dem Titel
=E2=80=9ECombinatorics of Beacon-based Routing and Guarding in Three Dime=
nsions=E2=80=9C
ein.
Die Pr=C3=A4sentation findet am
Donnerstag, den 30.03.2017 um 12:00 s.t. im Raum SR 055
im Rahmen des Mittagsseminars der Theoretischen Informatik statt.
Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitgutachter
ist Dr. Frank Hoffmann.
Mit freundlichen Gr=C3=BC=C3=9Fen
Jonas Cleve
*Abstract:*
A beacon is a point-like object which can be enabled to exert a magnetic
pull on other point-like objects in space.
Those objects then move towards the beacon in a greedy fashion until
they are either stuck at an obstacle or reach the beacon's location.
Beacons placed inside three-dimensional polytopes can be used to route
point-like objects from one location to another.
A second use case is to cover a polytope such that every point-like
object at an arbitrary location in the polytope can reach at least one
of the beacons once the latter is activated.
The topic of beacon-based routing and guarding was introduced by Biro et
al. [2] in 2011 and covered in detail by Biro in his PhD thesis [1].
Therein various aspects of beacons in the polygonal domain of two
dimensions were studied.
In this thesis we provide the first results for beacon-based routing and
guarding for three dimensions.
We first define the setting for three dimensions and look at
two-dimensional beacon-based routing which lays the groundwork for our
three-dimensional approach.
We then have a look at the complexity of certain three-dimensional
routing and guarding problems for which a smallest set of beacons should
be obtained.
We show that some of the problems are at least as hard as their
two-dimensional counterpart which makes them NP-hard and APX-hard.
For the problem of finding a smallest set of beacons to be able to route
between any pair of points in a polytope we show that it is always
sufficient and sometimes necessary to place floor((m+1)/3) beacons,
where m is the number of tetrahedra in a tetrahedral decomposition of
the polytope.
Finally, we show that there exists a polytope which cannot be covered by
placing a beacon at each vertex of the polytope.
[1] Michael Biro. =E2=80=9CBeacon-Based Routing and Guarding=E2=80=9D. Ph=
D thesis. State
University of New York at Stony Brook, 2013.
[2] Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph
S. B. Mitchell. =E2=80=9CBeacon-Based Routing and Coverage=E2=80=9D. In: =
21st Fall
Workshop on Computational Geometry (FWCG 2011). 2011.
==================================================================
Subject: Mittagsseminar 28.03.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 28.03.2017, 12 Uhr, SR 053 (!)
Wolfgang Mulzer zum Thema:
Growing Prioritized Disks and Rectangles
==================================================================
Subject: Mittagsseminar 28.03.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 28.03.2017, 12 Uhr, SR 055
Frank Hoffmann zum Thema:
The proper orientation number of undirected graphs
==================================================================
Subject: Mittagsseminar am 21. und 23. 3. 2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 21. 3. 2017
G=C3=BCnter Rote
zum Thema: Audioactive decay and the Conway sequence 1, 11,
21, 1211, 111221, 312211, 13112221, ....
und am
Donnerstag, 23. 3. 2017
Max Willert
zum Thema: Deformable Spanners
***************************************************
Ort: Takustra=C3=9Fe 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.
***************************************************
==================================================================
Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
Masterarbeit
-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: Tue, 14 Mar 2017 16:03:13 +0100
From: Katharina Klost <kathklost@zedat.fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de
CC: renee.zentiks@fu-berlin.de
Sehr geehrte Damen und Herren,
hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit
dem Titel "Complexity of recognizing generalized transmission graphs" ein=
=2E
Die Pr=C3=A4sentation findet am Donnerstag, den 16.03.2017 um 12:00 s.t. =
im
Rahmen des Mittagssemiars f=C3=BCr Theoretische Informatik in SR 055 stat=
t.
Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitkorrektor
ist PD Dr. Klaus Kriegel
Mit freundlichen Gr=C3=BC=C3=9Fen
Katharina Klost
*Zusammenfassung:*
Der allgemeine Transmissionsgraph einer Menge von geometrischen
Objekten, mit einem ausgezeichneten Punkt f=C3=BCr jedes Element der Men=
ge,
hat einen Knoten pro Element und eine gerichtete Kante /(u,v)/ genau
dann wenn der Punkt von /v/ in /u/ liegt. Diese Graphen sind ein
m=C3=B6gliches Modell f=C3=BCr Erreichbarkeit von Antennen.
Die Komplexit=C3=A4tsklasse ETR enth=C3=A4lt alle Sprachen, die in Polyno=
mialzeit
auf einen Satz der Form /=E2=88=83x_1,.,x_n:=CF=95(x_1,..., x_n) / reduzi=
ert werden
k=C3=B6nnen. Hierbei stammen/x_1,..., x_n/ aus den reelen Zahlen. Es ist
bekannt, dass ETR zwischen NP und PSPACE liegt.
F=C3=BCr viele geometrische Entscheidungsprobleme, wie zum Beispiel das
Erkennen von Kreisgraphen und Schnittgraphen von Strecken ist bekannt,
dass diese ETR-vollst=C3=A4ndig sind.
In dieser Arbeit werden /allgemeine Transmissionsgraphen/ formal
definiert und es wird gezeigt, dass das Erkennen von allgemeinen
Transmissionsgraphen von k-Kugeln, regelm=C3=A4=C3=9Figen Polygonen, Stre=
cken und
Kreissektoren ETR-vollst=C3=A4ndig ist.
*Abstract:*
Given an arrangement of geometric objects with one point of each object
singled out. The generalized transmission graph of this arrangement
consists of one vertex per element and a directed edge /(u,v)/ if and
only if the point of /v/ lies in /u/.
These graphs can serve as a generalized model of antenna reachability.
The complexity class ETR contains all problems that are polynomial time
reducible to a sentence of the form /=E2=88=83x_1,.,x_n:=CF=95(x_1,..., x=
_n)/ where
/x_1,..., x_n/ are interpreted over the real numbers. It aims to capture
the complexity of the existential theory of the reals. It is well known
that ETR lies between NP and PSPACE.
For many geometric decision problems, such as recognition of disk graphs
and of intersection graphs of lines, it is known that they are complete
for ETR.
In this thesis we formally introduce the class of /generalized
transmission graphs/ and show that the recognition problem of
generalized transmission graphs of k-spheres, regular polygons, line
segments and circular sectors is complete for the complexity class ETR.
==================================================================
Subject: Mittagsseminar 14.03.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 14.03.2017, 12 Uhr, SR 055
Nadja Scharf zum Thema:
=20
Symmetric Assembly Puzzles=20
--=20
Nadja Scharf
Freie Universit=C3=A4t Berlin
Institut f=C3=BCr Informatik
AG Theoretische Informatik
Takustra=C3=9Fe 9, Raum 122
14195 Berlin
==================================================================
Subject: Mittagsseminar am 28.02. und am 02.03.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 28.02.2017, 12 Uhr, SR 053 (Achtung: nicht 055)
Florian Hartmann
zum Thema: Computing Graph-Theoretic Similarity Scores Efficiently (Verteidigung der Bachelorarbeit)
und am
Donnerstag, 02.03.2017, 12 Uhr, SR 055
Klaus Kriegel
zum Thema: Rainbow Meanders an Cartesian Billiards
==================================================================
Subject: Mittagsseminar morgen Donnerstag, 23.02.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 23.02.2017, 12 Uhr, SR 055
G=FCnter Rote
zum Thema: Guess your own number! and Steiner triple systems!
==================================================================
Subject: Fwd: [i-prof] [i-studi] Einladung zur
Verteidigung meiner Bachelorarbeit
Tomorrow.
-------- Forwarded Message --------
Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarb=
eit
Date: Tue, 7 Feb 2017 10:13:53 +0100
From: Miro Baeten <miro.baeten@fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, Ren=E9e Zentiks <renee.zentiks@fu-berlin.de>
Sehr geehrte Damen und Herren,
hiermit m=F6chte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit =
mit
dem Titel "Erstellung eines GLL-Parsergenerators f=FCr kontextfreie
Grammatiken"
einladen. Die Arbeit entstand in der AG Theoretische Informatik und
wurde von Herrn
Prof. Dr. Wolfgang Mulzer betreut. Zweitgutachter ist Herr Prof. Dr.
Helmut Alt.
Die Verteidigung findet am Dienstag, den 14.02.2017 um 12:00 s.t. im
Seminarraum
055 in der Takustra=DFe 9 statt.
Mit freundlichen Gr=FC=DFen
Miro Baeten
Zusammenfassung:
Die Arbeit besch=E4ftigt sich mit der Erstellung eines Parsergenerators f=
=FCr
allgemeine kontextfreie Grammatiken unter Verwendung des GLL-Algorithmus,=
welcher mit ambigen Grammatiken in O(n^3) umzugehen wei=DF. Sein Einsatz
bietet sich unter anderem in der Computerlinguistik, dem Software
Reengineering
und in Compilern an. Die Laufzeit wird durch die Verwendung von als Graph=
en
strukturierten Stacks (GSS) sowie einem Shared Packed Parse Forest (SPPF)=
erreicht, der mehrerer valide Ableitungen zusammenfasst. Zun=E4chst wird
auf den
Algorithmus, danach auf den Generator und die Parser eingegangen. Der
Generator
abstrahiert die Grammatiken in einem Modell, analysiert dieses und erzeug=
t
daraus einen Parser, der sich an die asymptotische Laufzeit des Algorithm=
us
h=E4lt. Damit die Parser ambige Grammatiken schneller ableiten k=F6nnen,
wird der
Algorithmus um eine Parallelisierung erweitert. Abschlie=DFend wird
beleuchtet,
wie der Parsergenerator in Zukunft ausgebaut werden kann. Bedeutend ist
sowohl
der weitere Umgang mit den SPPFs als auch die Verbesserung des GSS.
==================================================================
Subject: Mittagsseminar 02.02.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 02.02.2017, 12 Uhr, SR 055
Max Willert
zum Thema: Subset-Sum ... most probably
==================================================================
Subject: Mittagsseminar 26.01.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 26.01.2017, 12 Uhr, SR 055
Nadja Scharf zum Thema:
=20
A PTAS for the Square Packing Problem =20
--=20
Nadja Scharf
Freie Universit=C3=A4t Berlin
Institut f=C3=BCr Informatik
AG Theoretische Informatik
Takustra=C3=9Fe 9, Raum 122
14195 Berlin
==================================================================
Subject: Mittagsseminar 24.01.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 24.01.2017, 12 Uhr, SR 055
Frank Hoffmann zum Thema:
Dominance in colored stochastic point sets
==================================================================
Subject: Mittagsseminar heute,
17.1.2017: The (Prouhet-)Tarry-Escott Problem
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 17.1.2017, 12 Uhr, SR 055
G=FCnter Rote
zum Thema: The Prouhet-Tarry-Escott problem about annihilation of=
polynomials
==================================================================
Subject: Mittagsseminar am 12.01.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 12.01.2017
Wolfgang Mulzer
zum Thema:
Stabbing Pairwise Intersecting Disks with Five Points
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar heute, 19.01.2017
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht
heute, Dienstag, 19.01.2017
Bahareh Banyassady
zum Thema: Higher-Order Voronoi Diagrams in Constrained memory
model.
***************************************************
*Ort: Takustr. 9, SR 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================
Subject: Mittagsseminar heute,
5.1.2017: Plane graph isomorphism
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Donnerstag, 5.1.2017, 12 Uhr, SR 055
G=FCnter Rote
zum Thema: Plane graph isomorphism testing
==================================================================
Subject: Mittagsseminar TI Dienstag, 02.01.17
Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
Dienstag, 03.01.2017
Boris Klemz
zum Thema:
Ordered Level Planarity
***************************************************
Ort: Takustr. 9, RM 055
Uhrzeit: 12 Uhr s.t.
***************************************************
==================================================================