Randomisierte Algorithmen

In dieser mentorierten Arbeit sollen die Schüler in das Themengebiet der randomisierten Algorithmen eingeführt werden und anhand von Beispielen die Stärke des Zufalls für Algorithmen entdecken. Dabei werden vor allem zwei Typen von randomisierten Algorithmen erarbeitet: Die Methode des Überlistens von Gegnern und die Methode der Fingerabdrücke (Grundlage: Entwurfsmethoden von zufallsgesteuerten Systemen, Prof. Dr. Juraj Hromkovič). Die erste Methode wird über ein Codeknackerproblem und über das Themengebiet der Sortieralgorithmen (Quicksortalgorithmus) erklärt. Der zweite Teil baut auf dem Problem der Verifikation von Matrixmultiplikationen auf.

Ziel der Arbeit ist auch vor allem die Anwendung der Wahrscheinlichkeitstheorie in der Informatik.