Property Testing von Grapheigenschaften
| Talking persons: |
| Tobias Brunsch |
| Abstract: |
| Tobias Brunsch verteidigt seine Diplomarbeit zum Thema "Property Testing von Grapheigenschaften" In manchen Anwendungen sind die Eingaben eines Problems so groß, dass selbst Linearzeitalgorithmen zu langsam sind. Man möchte dann sogenannte Property Testing Algorithmen entwickeln, die mit hoher Wahrscheinlichkeit eine korrekte Aussage zur gegebenen Fragestellung liefern, und nur konstante Zeit benötigen. In der Diplomarbeit wurde untersucht, wie sich Färbbarkeit von Graphen mit Property Testing Algorithmen entscheiden lässt, und welche Querbezüge zu Konzepten wie Prädikatenlogik bestehen. |
| Times: |
| Wednesday 19th August 2009, 9.30 am - 10.30 am, room 1/205 |
