Algorithmen

Stand: 07.01.2007

Zeitrichtwert: 8 Unterrichtsstunden

Inhaltliche Schwerpunkte Bemerkungen

Klärung des Algorithmusbegriffs (2)

  • Anforderungen an Algorithmen
  • historische Bedeutung

Ausgangspunkt für die neuen Fragestellungen bilden die mit Hilfe des Rechners durchgeführten Simulationen von Spielen. Diskutiert werden soll jetzt die Frage, welche Spiele sich mit dem Rechner simulieren lassen bzw. welche Anforderungen solche Spiele erfüllen müssen. Als Ergebnis ergibt sich, dass man die "Spielausführung" so genau beschreiben können muss, dass sie von einem Rechner durchgeführt werden kann. Wichtige Anforderungen für solche Beschreibungen sind: Endlichkeit, Eindeutigkeit, Ausführbarkeit, Allgemeinheit.

Im Anschluss wird der Algorithmus-Begriff eingeführt und anhand verschiedener Beispiele verdeutlicht bzw. abgegrenzt. Die zentralen Anforderungen "Endlichkeit", "Eindeutigkeit", "Ausführbarkeit", "Allgemeinheit" werden dabei besonders herausgestellt. Es wird geklärt, dass man den Begriff "Algorithmus" auch dann benutzt, wenn der "Prozessor" kein Bestandteil eines Rechners ist. Beispiele aus der Mathematik zeigen, dass es Algorithmen schon sehr lange gab, bevor die ersten Rechner bzw. automatischen Rechenmaschinen entwickelt wurden.

Analyse und Implementierung von Standardalgorithmen (6)

  • Korrektheit
  • Laufzeitverhalten
  • Problemlösen mit Standardalgorithmen

Zur Vertiefung algorithmischer Strukturen wird ein klassisches Beispiel aus der Mathematik betrachtet: Bestimmung des größten gemeinsamen Teilers (ggT) von zwei natürlichen Zahlen. Einfache Algorithmen werden erst selbst entwickelt und umgangssprachlich formuliert; z. B.: "Bestimme die kleinere der beiden Zahlen und speichere den Wert als Hilfszahl ab. Solange die Division beider vorgegebener Zahlen durch die Hilfszahl einen Rest ungleich Null ergibt, vermindere die Hilfszahl um Eins." Anschließend werden diese Algorithmen strukturell mit Struktogrammen dargestellt. Mit Hilfe von Ablaufprotokollen wird ihre Korrektheit getestet.

Die sich als korrekt erweisenden Algorithmen werden implementiert. Hierdurch soll eine intensivere Auseinandersetzung mit den Algorithmen erfolgen und zudem die Übersetzung der algorithmischen Bausteine in die gewählte Programmiersprache geübt werden. Weitere systematische Tests der lauffähigen Programme sollen dann die Korrektheit der Algorithmen bestätigen.

Eine Recherche zum Thema "ggT-Algorithmus" liefert Standardalgorithmen, siehe z. B. bei Wikipedia. Zunächst müssen diese Algorithmen verstanden werden. Hierzu werden wieder Ablaufprotokolle angefertigt und ggf. die Algorithmen implementiert. Interessant ist nun der Vergleich verschiedener Algorithmen. Es zeigt sich bereits anhand ausgewählter Ablaufprotokolle, dass unterschiedlicher Aufwand zur Berechnung des ggT betrieben wird. Dieser wird jetzt etwas genauer untersucht. Mit Hilfe von Laufzeitmessungen und Zählern, die in die erstellten Programme eingefügt werden, wird der Berechnungsaufwand abgeschätzt.

Zusammenfassend werden die wichtigen Eigenschaften "Korrektheit" und "Effizienz" von Algorithmen noch einmal herausgestellt. Anhand weiterer Beispiele (z. B. schnelles Potenzieren) werden die Konzepte und Verfahren vertieft.

Valid XHTML 1.0 Strict Valid XHTML 1.0