Informatik-Logo
Fakultät für Informatik der Technischen Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Proseminar: Grundlagen lokal selbststabilisierender Strukturen

[Zusammenfassung] [Themenliste] [Amneldung] [Vorbesprechung] [Termine] [Hinweise] [Links]


Zusammenfassung

Sehr große Strukturen (wie das Internet oder höhere Organismen) sind von Natur aus dynamisch. Ständig finden Veränderungen in der Struktur statt, die diese idealerweise mit Hilfe geeigneter Regelungsverfahren so bewältigen sollte, dass sie immer wieder zu einem zulässigen Zustand zurückkehrt bzw. die Menge der zulässigen Zustände nie verlässt. Im Bereich lokal selbststabilisierender Strukturen beschäftigt man sich mit Verfahren, die rein lokal arbeiten (d.h. jeder Punkt dieser Struktur kann sich nur mit benachbarten Punkten koordinieren) und zusätzlich sicherstellen, dass für jeden Anfangszustand, von dem aus sich die Struktur im Prinzip erholen kann, in endlicher Zeit wieder ein zulässiger Zustand erreicht wird. Die Forschung im Bereich selbststabilisierender Strukuren ist noch relativ jung, hat aber faszinierende Anwendungen im Gebiet der Molekularbiologie, der Nanotechnologie und logischer Kommunikationsnetzwerke.

In diesem Seminar werden verschiedene Modelle und Verfahren für selbststabilisierende Strukturen betrachtet. Aufgabe der Seminarteilnehmer ist es, eines dieser Verfahren zu implementieren und auf seine Effektivität hin zu testen. Darüber soll ein kurzer Bericht verfasst werden und ein Vortrag vorbereitet werden, in dem das Verfahren beschrieben und demonstriert wird.


Termine



Themenliste:

    Externe Datenstrukturen
  1. Selbststabilisierender Kreis: Eine aktive Einheit soll aus einem beliebigen Graphen einen Kreis bauen. Wie macht man das am geschicktesten mit einer begrenzten Anzahl von Verbindungen der Einheit in den Graphen?
  2. Selbststabilisierendes Gitter: Wie kann eine einzelne aktive Einheit einen beliebigen Graphen in ein Gitter umwandeln?
    Interne Datenstrukturen
  3. Selbststabilisierender Heap: Wie können die Elemente einer Heapstruktur selbstädig durch Kommunikation mit benachbarten Elementen die Heapeigenschaft wieder herstellen?
  4. Selbststabilisierender AVL-Baum: Ein AVL-Baum ist ein Suchbaum. Wie kann ein beliebig entarteter AVL-Baum durch seine eigenen Elemente wieder in einen korrekten AVL-Baum verwandelt werden?
  5. Selbststabilisierende sortierte Liste: Wie können sich Knoten eines beliebigen Graphen mit eindeutigen Identifikationsnummern selbständig in eine sortierte Liste umorganisieren?
    Logische Netze für das Internet
  6. Dynamische de Bruijn Graphen: De Bruijn Graphen sind sehr gut für dynamische Peer-to-Peer Systeme geeignet, weil sie einen kleinen Grad und kleinen Durchmesser haben. Wie kann man entartete de Bruijn Graphen wieder in die korrekte Form zurückführen?
  7. Dynamische Hyperwürfel: s.o.
  8. Skipgraphen: s.o.
    Logische Netze für drahtlose Netze
  9. Nachbarschaftsgraphen: Nachbarschaftsgraphen sind spezielle Konstruktionen für drahtlose Netze, die Zusammenhang garantieren können. Wie kann man solche Graphen aus einer beliebigen Situation heraus bauen?
  10. Yao-Graphen: s.o.
  11. Gabriel-Graphen: s.o.
    Autonome Einheiten
  12. Selbststabilisierende Ausrichtung in eine Richtung ohne einen globalen Richtungssinn.
  13. Selbststabilisierende gleichmäßige Verteilung in einem beliebigen Raum.
    DNA Strukturen und Nanostrukturen
  14. Selbststabilisierende Rechtecke
  15. Selbststabilisierende Diamanten
  16. Nano-Origami

Thematische Fragen bitte an Christian Scheideler.

Anmeldung

* Interessentinnen/en können sich ab sofort per Email anmelden. In der E-Mail sollten folgende Informationen enthalten sein:

  • Name, Vorname
  • Studiengang und Studienfach
  • Semester
  • E-Mail (nur Adressen @in.tum.de)
  • bevorzugtes Thema

Vorbesprechung

* Die Vorbesprechung findet am

Donnerstag, 20.07.2006, 16:00 Uhr s.t.

im Raum

MI 03.11.018

statt.

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung) Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität) Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität) Die Endfassung der Seminarbeit ist spätestens 2 Wochen nach dem Votrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten).
Anwesenheit bei den Vorträgen Bei den einzelnen Vorträgen wird eine Anwesenheitsliste geführt.

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 5 Wochen vor dem Vortragerstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
bis 3 Wochen vor dem VortragGliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem VortragProbevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortragfertige Ausarbeitung abgeben.

Hinweise zur Anfertigung einer Seminararbeit

* Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  • Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden.
  • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
* Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Vorträge

* Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)

Interessante Links

* Eine Liste von interessanten Forschungsberichten im Bereich biologisch motivierter Modelle gibt es hier: The DNA and Natural Algorithms Group.
* Weitere Informationen werden hier eingefügt...

Weitere (thematische) Auskünfte bei: Christian Scheideler

Christian Scheideler Last modified: Tue Jul 11 13:55:37 CET 2006