Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
lehre:ss19:projektgruppe-computational-geometry [2019/04/05 14:59]
langetepe [Inhalt]
lehre:ss19:projektgruppe-computational-geometry [2019/04/05 22:33]
hjhaverkort [Vorgestellte Themen im SS19]
Zeile 30: Zeile 30:
  
 1. Sortieralgorithmen:​ "Sound des Speicherzugriffs"​\\ 1. Sortieralgorithmen:​ "Sound des Speicherzugriffs"​\\
-  * Wenn Algorithmen größere Datenmengen verarbeiten,​ werden die Daten während der Berechnungen blockweise zwischen Festplatte, Hauptspeicher und Zwischenspeicher übertragen. Damit geht am wenigsten Zeit verloren, wenn in jedem beschränkten Zeitraum meistens nur auf Speicherzellen zugegriffen wird, die im Speicher mehr oder weniger gebündelt sind. Oft haben verschiedene Algorithmen für ein Problem, z.B. Sortieren, die gleiche theoretische Zeitkomplexität aber sehr unterschiedliche Speicherzugriffstrukturen und somit praktische Effizienz. In diesem Projekt wollen wir die Struktur der Speicherzugriffe von Sortieralgorithmen (und vielleicht auch von anderen einfachen Algorithmen) nicht nur anschaulich machen, ​sonder ​auch hörbar. Etwas ähnliches hat [[https://​panthema.net/​2013/​sound-of-sorting/​|Timo Bingmann]] gemacht: er hat die Datenwerte die verglichen werden sonifiziert---wir wollen aber ihre Adressen im Speicher sonifizieren. Dazu sollen die Algorithmen so implementiert werden, dass sie nur ein Array als Speicher benutzen, wobei wir die Operation auf dem Array so modifizieren,​ dass dabei auch Klang erzeugt wird. Das kann z.B. mit Java oder C++ gemacht werden, oder mit Supercollider:​ eine Programmiersprache die speziell für Klangerzeugung entworfen wurde.+  * Wenn Algorithmen größere Datenmengen verarbeiten,​ werden die Daten während der Berechnungen blockweise zwischen Festplatte, Hauptspeicher und Zwischenspeicher übertragen. Damit geht am wenigsten Zeit verloren, wenn in jedem beschränkten Zeitraum meistens nur auf Speicherzellen zugegriffen wird, die im Speicher mehr oder weniger gebündelt sind. Oft haben verschiedene Algorithmen für ein Problem, z.B. Sortieren, die gleiche theoretische Zeitkomplexität aber sehr unterschiedliche Speicherzugriffstrukturen und somit praktische Effizienz. In diesem Projekt wollen wir die Struktur der Speicherzugriffe von Sortieralgorithmen (und vielleicht auch von anderen einfachen Algorithmen) nicht nur anschaulich machen, ​sondern ​auch hörbar. Etwas ähnliches hat [[https://​panthema.net/​2013/​sound-of-sorting/​|Timo Bingmann]] gemacht: er hat die Datenwerte die verglichen werden sonifiziert---wir wollen aber ihre Adressen im Speicher sonifizieren. Dazu sollen die Algorithmen so implementiert werden, dass sie nur ein Array als Speicher benutzen, wobei wir die Operation auf dem Array so modifizieren,​ dass dabei auch Klang erzeugt wird. Das kann z.B. mit Java oder C++ gemacht werden, oder mit Supercollider:​ eine Programmiersprache die speziell für Klangerzeugung entworfen wurde.
  
 2. Underground Maps: Platzierung der Labels\\ 2. Underground Maps: Platzierung der Labels\\
Zeile 39: Zeile 39:
    
 4. Multiple Robot Routing mit Nebenbedingungen\\ 4. Multiple Robot Routing mit Nebenbedingungen\\
-  * Eine effiziente Bewegung modularer Angenten auf engstem Raum ist eine wichtige Aufgabe. In einer Gitterwelt sollen einzelne aus Gitterzellen bestehende Agenten von einer Startkonfiguration zu einer Endkonfiguration effizient kollisionsfrei bewegt werden. Dazu soll eine interaktive Applikation programmiert werden. Ausgangspunkt ist dabei eine Arbeit, bei der die Aufgabe für ein komplett gefülltes Grid mit einzelnen Agenten algorithmisch quasi optimal gelöst wird. Dieser Algorithmus besteht aus kleinen Bewegungsblöcken und soll zunächst in 2D umgesetzt und animiert dargestellt werden und dann ggf. mit Nebenbedingungen (z.B. Ruheplätze oder ausgedehnte Agenten) erweitert werden. Ein effiziemter ​2D-Algorithmus wird in folgender Arbeit beschrieben:​ https://​arxiv.org/​abs/​1801.10465+  * Eine effiziente Bewegung modularer Angenten auf engstem Raum ist eine wichtige Aufgabe. In einer Gitterwelt sollen einzelne aus Gitterzellen bestehende Agenten von einer Startkonfiguration zu einer Endkonfiguration effizient kollisionsfrei bewegt werden. Dazu soll eine interaktive Applikation programmiert werden. Ausgangspunkt ist dabei eine Arbeit, bei der die Aufgabe für ein komplett gefülltes Grid mit einzelnen Agenten algorithmisch quasi optimal gelöst wird. Dieser Algorithmus besteht aus kleinen Bewegungsblöcken und soll zunächst in 2D umgesetzt und animiert dargestellt werden und dann ggf. mit Nebenbedingungen (z.B. Ruheplätze oder ausgedehnte Agenten) erweitert werden. Ein effizienter ​2D-Algorithmus wird in folgender Arbeit beschrieben:​ https://​arxiv.org/​abs/​1801.10465
 5. Terrain Guarding in Dimension 1.5 (oder 2.5)\\ 5. Terrain Guarding in Dimension 1.5 (oder 2.5)\\
   * Die Platzierung von Wächtern zur Beobachtung eines Gebietes kommt in vielen Anwendungen vor. Gegeben ​ ist hier ein 1.5 dimensionales Terrain als Polygonzug und es soll eine minimale Anzahl an Agenten gefunden werden, die das ganze Gebiet //sehen//. Dieses Problem ist NP-schwer im allgemeinen,​ es gibt aber Algorithmen mit guten Laufzeiten für Spezialfälle und zur Approximation der Anzahl der minimal notwendigen Agenten. Hierfür soll eine interaktive Applikation programmiert werden, bei der das Terrain editiert werden kann und verschiedene Algorithmen animiert dargestellt werden. Als Ausgangspunkt und Anhalt dienen die u.a. Arbeiten. Bei erweitertem Interesse kann auch das //​Hochschießen//​ eines Satellitens in einem 2.5 dimensionalen Terrain betrachtet werden. Dabei soll ein Online-Algorithmus zur Kernsuche erweitert werden. Literatur dazu wird dann bei Interesse angefügt.  ​   * Die Platzierung von Wächtern zur Beobachtung eines Gebietes kommt in vielen Anwendungen vor. Gegeben ​ ist hier ein 1.5 dimensionales Terrain als Polygonzug und es soll eine minimale Anzahl an Agenten gefunden werden, die das ganze Gebiet //sehen//. Dieses Problem ist NP-schwer im allgemeinen,​ es gibt aber Algorithmen mit guten Laufzeiten für Spezialfälle und zur Approximation der Anzahl der minimal notwendigen Agenten. Hierfür soll eine interaktive Applikation programmiert werden, bei der das Terrain editiert werden kann und verschiedene Algorithmen animiert dargestellt werden. Als Ausgangspunkt und Anhalt dienen die u.a. Arbeiten. Bei erweitertem Interesse kann auch das //​Hochschießen//​ eines Satellitens in einem 2.5 dimensionalen Terrain betrachtet werden. Dabei soll ein Online-Algorithmus zur Kernsuche erweitert werden. Literatur dazu wird dann bei Interesse angefügt.  ​
lehre/ss19/projektgruppe-computational-geometry.txt · Zuletzt geändert: 2019/04/05 22:33 von hjhaverkort

Benutzer-Werkzeuge