Blockseminar
Sublineare Algorithmen: Property Testing
und sublineare Approximationsalgorithmen
Wintersemester 2005/2006
| Veranstalterin: |
Beate Bollig
beate.bollig uni-dortmund.de
|
|
| Voraussetzung: |
Komplexitätstheorie und Effiziente Algorithmen (wünschenswert) |
| Termin: |
in der ersten Woche nach Ende der Vorlesungszeit |
| Raum: |
steht noch nicht fest |
Inhalt:
Da in vielen Anwendungen heutzutage derartig große Datenmengen entstehen,
dass selbst Linearzeitalgorithmen keine effiziente Verarbeitung
ermöglichen, stellt sich die Frage, welche Aufgaben sublineare
Algorithmen lösen können.
Property Testing ist ein Teilgebiet des Entwurfs und der Analyse sublinearer
Algorithmen. Es wird eine Relaxation des herkömmlichen
Entscheidbarkeitsbegriffs untersucht: die Aufgabe eines randomisierten Algorithmus
besteht darin mit hinreichender Wahrscheinlichkeit zu entscheiden, ob die
zu untersuchende Eingabe eine vorgegebene Eigenschaft erfüllt oder ob
sie weit davon entfernt ist, über die Eigenschaft zu verfügen.
Eingaben, für die beides nicht zutrifft, dürfen beliebig
klassifiziert werden.
Property Testing Algorithmen können als Approximationsalgorithmen
für Entscheidungsprobleme betrachtet werden.
Ein weiterer inhaltlicher Schwerpunkt des Seminars sind sublineare Approximationsprobleme
für Optimierungsprobleme.
Literatur:
Einen guten Überblick über das Gebiet Property Testing findet man
in:
- Fischer, E. (2001).
(Eldar Fischers Publikationen
)
The art of uninformed decisions. A primer to property testing.
Bulletin of the European Association for Theoretical Computer Science,
75:97-126.
- Ron, D. (2001).
(Dana Rons Publikationen
)
Property testing.
In Handbook of Randomized Algorithms. Kluwer Academic Publishers.
Themenliste als PS-File
Der weitere Ablauf ist der folgende:
- Interessierte können sich ab sofort bei der Veranstalterin melden.
Anmeldeschluß ist der
15.12.2005.
-
Die Vorträge sollen anhand der angegebenen Literatur vorbereitet werden.
Die Einarbeitung in die vorgeschlagene und bei Bedarf auch
weitere Literatur erfolgt
selbstständig, d.h.
nicht im Rahmen einer Vorlesung o.Ä.
Die Veranstalterin steht aber
für inhaltliche Fragen und Fragen zur Vortragsgestaltung zur Verfügung.
Nützliche Hinweise zur Vortragsgestaltung finden sich hier:
Hinweise als PS-File
-
Spätestens 4 Wochen vor dem Vortrag findet
eine Zwischenbesprechung statt.
Die Teilnehmer und Teilnehmerinnen sollten
jeweils ein schlüssiges Konzept vorstellen, d.h. die
wesentlichen Aussagen der zugrundeliegenden Literatur sollte verstanden sein.
-
Eine in Latex erstellte Zusammenfassung
des Vortragsthemas von ca 3 Seiten ist bis spätestens 3 Wochen vor dem Vortrag
bei der Veranstalterin abzugegeben.
Die Zusammenfassungen werden anschließend
an alle Seminarteilnehmerinnen und -teilnehmer verteilt.
14.11.2005 - Beate
Bollig