Randomisierte Algorithmen (Lehrtext)

Main content

Autorin
Sabrina Wiedersheim

Akkordeon. Mit Tab zu Einträgen navigieren, dann Inhalt mit Enter auf und zuklappen.

 

Inhalt und Lernziele

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.

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

Weitere Informationen zur Unterrichtseiheit

Schlagwörter Sortieralgorithmen, Deterministischer Quicksort Algorithmus, Randomisierter Quicksort Algorithmus, Matrixmultiplikationstest 22, Matrizen, Matrixmultiplikationen
Fachgebiet Algorithmen und Datenstrukturen
Schultyp, Schulstufe Gymnasium
Sprache deutsch
Entstehung der Unterrichtseinheit Juli 2008
Publikation auf EducETH
September 2009
 
 
URL der Seite: http://www.educ.ethz.ch/unterrichtsmaterialien/informatik/randomisierte-algorithmen.html
26.05.2017
© 2017 Eidgenössische Technische Hochschule Zürich