Untere Schranken für randomisierte und Quantenalgorithmen und Anwendung auf die lokale Suche
| Talking persons: |
| Dirk Winkler |
| Abstract: |
| Im Vortrag werden Methoden genauer vorgestellt, mit deren Hilfe es möglich ist, untere Schranken für die Laufzeit zu zeigen, die nötig ist, um mit Hilfe von Quantenalgorithmen und randomisierten Algorithmen bestimmte Probleme zu lösen. Als Beispielproblem, anhand dessen gezeigt wird, wie eine Anwendung aussehen kann, wird das Problem der "lokalen Suche" benutzt, das ist das Problem, in einem Knotengewichteten Graphen einen Knoten zu finden, dessen Wert höchstens so groß ist wie der Wert all seiner Nachbarn. |
| Times: |
| Tuesday 21st March 2006, 3.30 pm - 5.00 pm, room 1/336 |
