Randomisierte Algorithmen (Lehrtext)

Neue Publikation (9/09)

Fachdidaktisches Review:
Juraj Hromkovic

Fachliches Review:
Juraj Hromkovic

Autorin
Sabrina Wiedersheim

Inhalt

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 Matrixmultiplika-
tionen auf.

Vorwissen

• 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.
  

Download

Daten zur Unterrichtseinheit