Informatik · Klasse 12 · Datenstrukturen und Algorithmen · 1. Halbjahr

Grundlagen der Algorithmen

Die Schülerinnen und Schüler definieren Algorithmen und analysieren ihre Eigenschaften wie Endlichkeit, Eindeutigkeit und Effektivität.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Modellieren und Implementieren
• KMK: Sekundarstufe II - Problemlösen und Handeln

Über dieses Thema

Datenstrukturen sind das Fundament effizienter Software. In diesem Modul vergleichen Schüler lineare Strukturen wie Listen, Stacks und Queues mit nicht-linearen Strukturen wie binären Bäumen. Das Verständnis dieser Unterschiede ist entscheidend für die KMK-Kompetenz 'Strukturieren und Vernetzen'. Die Lernenden analysieren, wie die Wahl einer Datenstruktur die Effizienz von Algorithmen beeinflusst, beispielsweise beim Suchen oder Einfügen von Elementen.

In der 12. Klasse geht es darum, über die reine Anwendung hinauszugehen und die internen Funktionsweisen (z.B. Zeigerstrukturen vs. Arrays) zu durchdringen. Schüler erkennen, dass es keine 'beste' Datenstruktur gibt, sondern nur die am besten geeignete für einen spezifischen Anwendungsfall. Dieses Thema wird besonders greifbar, wenn Schüler die abstrakten Strukturen physisch modellieren oder in Rollenspielen die Datenflüsse simulieren, um die Logik hinter 'Last-In-First-Out' oder hierarchischen Baumordnungen zu verinnerlichen.

Leitfragen

1. Erklären Sie die fundamentalen Eigenschaften eines Algorithmus.
2. Analysieren Sie den Unterschied zwischen einem Algorithmus und einem Programm.
3. Konstruieren Sie einen einfachen Algorithmus zur Lösung eines Alltagsproblems.

Lernziele

• Definieren Sie die fundamentalen Eigenschaften eines Algorithmus (Endlichkeit, Eindeutigkeit, Effektivität, Allgemeinheit) und begründen Sie deren Notwendigkeit.
• Analysieren Sie die strukturellen Unterschiede zwischen einem abstrakten Algorithmus und seiner konkreten Implementierung in Form eines Computerprogramms.
• Konstruieren Sie einen einfachen Algorithmus zur Lösung eines Alltagsproblems (z.B. Zubereitung eines Getränks) und dokumentieren Sie diesen schrittweise.
• Vergleichen Sie die Effektivität zweier verschiedener Algorithmen zur Lösung desselben Problems hinsichtlich ihrer Schrittzahl und Ressourcennutzung.

Bevor es losgeht

Grundlagen der Problemlösung

Warum: Schüler müssen bereits grundlegende Strategien zur Zerlegung von Problemen in kleinere Teile kennen, um Algorithmen entwickeln zu können.

Logische Operatoren und Bedingte Anweisungen

Warum: Das Verständnis von 'wenn-dann'-Strukturen ist essenziell, um die Eindeutigkeit und Ausführbarkeit von Algorithmenschritten nachvollziehen zu können.

Schlüsselvokabular

Algorithmus	Eine eindeutige, endliche und folgerichtige Handlungsanweisung zur Lösung eines Problems oder einer Klasse von Problemen.
Endlichkeit	Die Eigenschaft eines Algorithmus, nach einer endlichen Anzahl von Schritten zu einem Ergebnis zu gelangen oder abzubrechen.
Eindeutigkeit	Die Eigenschaft, dass jeder Schritt eines Algorithmus klar definiert ist und keine Interpretationsspielräume lässt.
Effektivität	Die Eigenschaft, dass jeder Schritt eines Algorithmus in endlich vielen Operationen ausführbar ist und das Problem mit vertretbarem Aufwand löst.
Programm	Eine konkrete Implementierung eines Algorithmus in einer bestimmten Programmiersprache, die von einem Computer ausgeführt werden kann.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Ein binärer Baum ist immer sortiert.

Was Sie stattdessen lehren sollten

Ein binärer Baum ist lediglich eine Struktur, bei der jeder Knoten maximal zwei Kinder hat. Erst ein binärer *Suchbaum* unterliegt einer Sortierordnung. Durch das manuelle Zeichnen unsortierter Bäume wird dieser Unterschied im Unterricht deutlich.

Häufige Fehlvorstellung

Arrays sind immer schlechter als verkettete Listen, weil sie eine feste Größe haben.

Was Sie stattdessen lehren sollten

Arrays bieten einen sehr schnellen Direktzugriff über den Index (O(1)), während Listen sequenziell durchlaufen werden müssen. In Performance-Experimenten können Schüler die Zugriffszeiten messen und die Vorzüge des Arrays bei statischen Datenmengen erkennen.

Ideen für aktives Lernen

Planspiel: Der menschliche Stack und die Queue

Schüler stellen sich in einer Reihe auf und simulieren Datenoperationen. Für den Stack dürfen Elemente nur 'oben' (vorne) hinzugefügt und weggenommen werden, für die Queue wird hinten angestellt und vorne bedient, um die Zugriffsregeln haptisch zu verstehen.

20 Min.·Ganze Klasse

Forschungskreis: Baum-Strukturen im Alltag

In Kleingruppen suchen Schüler nach hierarchischen Daten in ihrer Umgebung (Dateisysteme, Stammbäume, Turnierpläne). Sie zeichnen diese als binäre Bäume und diskutieren, wie man effizient einen bestimmten Knoten finden kann.

40 Min.·Kleingruppen

Ich-Du-Wir (Denken-Austauschen-Vorstellen): Array vs. Verkettete Liste

Lernende erhalten ein Szenario (z.B. eine Playlist, in der oft Lieder eingefügt werden). Sie überlegen einzeln, welche Struktur effizienter ist, vergleichen ihre Argumente mit einem Partner und präsentieren das Ergebnis.

25 Min.·Partnerarbeit

Bezüge zur Lebenswelt

• Navigationssysteme wie Google Maps oder Waze verwenden Algorithmen, um die schnellste Route zwischen zwei Punkten zu berechnen, wobei sie Faktoren wie Verkehrsdichte und Straßenbedingungen berücksichtigen.
• Rezepturen in Kochbüchern oder Online-Plattformen sind im Grunde Algorithmen für die Zubereitung von Speisen. Sie definieren eine Schritt-für-Schritt-Anleitung mit spezifischen Zutaten und Handlungsweisen.
• Automatisierte Sortieranlagen in Logistikzentren, wie sie beispielsweise von Amazon eingesetzt werden, verarbeiten und sortieren Pakete basierend auf vordefinierten Algorithmen, um Lieferungen effizient zu verteilen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie den Lernenden eine Karte mit der Aufgabe: Beschreiben Sie einen Alltagsprozess (z.B. Zähneputzen) und formulieren Sie ihn als Algorithmus mit mindestens drei Schritten. Nennen Sie für jeden Schritt, welche Eigenschaft (Endlichkeit, Eindeutigkeit, Effektivität) hier besonders wichtig ist.

Kurze Überprüfung

Stellen Sie folgende Frage an die Tafel: 'Ist jede Schritt-für-Schritt-Anleitung ein Algorithmus? Begründen Sie Ihre Antwort mit einem Beispiel, das die Unterschiede zwischen einer einfachen Anleitung und einem formalen Algorithmus aufzeigt.'

Diskussionsfrage

Diskutieren Sie im Plenum: 'Warum ist es wichtig, dass ein Algorithmus endlich ist?' Sammeln Sie verschiedene Szenarien, in denen ein nicht-endlicher Prozess zu Problemen führen würde, und diskutieren Sie die Konsequenzen für die Softwareentwicklung.

Häufig gestellte Fragen

Warum lernt man in der Schule noch verkettete Listen, wenn es in Java 'ArrayList' gibt?

Die ArrayList in Java nutzt intern ein Array. Das Verständnis der verketteten Liste ist essenziell, um zu begreifen, wie dynamische Speicherverwaltung und Zeiger funktionieren. Es schult das Verständnis für die zugrunde liegenden Mechanismen der Informatik.

Wie hilft aktives Modellieren beim Verständnis von Datenstrukturen?

Abstrakte Zeigeroperationen in verketteten Listen oder Bäumen sind oft schwer vorstellbar. Wenn Schüler diese Operationen mit Schnüren oder auf Papier physisch 'umhängen', werden die logischen Schritte beim Einfügen oder Löschen sichtbar und Fehler in der Logik sofort korrigiert.

Was ist ein praktisches Beispiel für einen Stack im Computeralltag?

Die 'Rückgängig'-Funktion (Undo) in Textverarbeitungsprogrammen oder der 'Zurück'-Button im Browser nutzen Stacks. Die zuletzt ausgeführte Aktion liegt obenauf und wird als erste wieder rückgängig gemacht (LIFO-Prinzip).

Wann sollte man einen binären Baum statt einer Liste verwenden?

Bäume sind ideal für hierarchische Daten oder wenn man sehr schnell suchen muss. In einem balancierten binären Suchbaum reduziert sich die Suchzeit dramatisch gegenüber einer linearen Liste, da man mit jedem Schritt die Hälfte der Daten ausschließen kann.