Randomisierte Algorithmen (Lehrtext)

Autorin
Sabrina Wiedersheim

In dieser mentorierten Arbeit sollen die Schüler in das Themengebiet der randomisierten Algorithmen eingeführt werden und anhand von Beispielen die Stäke 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 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.

  • Gute Grundlagen in der Wahrscheinlickeitstheorie und Kombinatorik
  • Gewisse erste Erfahrungen in der Informatik: Was ist ein Algorithmus? Notation von Algorithmen (if- und for-Schleifen, input, output, . . . ) und erste Erfahrungen mit Laufzeitanalysen (O(n), O(log(n)), O(n2 ), . . . )
  • Analysis: Die Notation von Summen  über das Summenzeichen sollte den Schülern bekannt sein. Die Kenntis der Harmonischen Zahl Hn wäre von Vorteil. 
  • Die Themengebiete der Sortieralgorithmen und der Matrizen werden in dieser Arbeit zwar eingeführt, aber nur sehr knapp. Es ist deshalb von Vorteil, wenn die Schüler dabei schon gewisse Kentnisse mitbringen oder wenn sie bei diesen Einführungsabschnitten zusätzliche Unterstüzung erhalten.
JavaScript wurde auf Ihrem Browser deaktiviert