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

Arrays und Listen

Die Schülerinnen und Schüler vergleichen statische Arrays mit dynamischen Listen hinsichtlich ihrer Eigenschaften und Einsatzgebiete.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Strukturieren und Vernetzen
• KMK: Sekundarstufe II - Modellieren und Implementieren

Über dieses Thema

Die Algorithmenanalyse ist das mathematische Gewissen der Informatik. Schüler lernen hier die O-Notation kennen, um die Effizienz von Programmen unabhängig von der verwendeten Hardware zu bewerten. Dies ist ein zentraler Bestandteil der KMK-Standards im Bereich 'Darstellen und Interpretieren', da komplexe Zeit- und Platzverläufe in abstrakte Kategorien eingeordnet werden müssen. In der 12. Klasse verstehen die Lernenden, warum ein Algorithmus mit quadratischer Laufzeit bei großen Datenmengen unbrauchbar wird, selbst wenn er auf einem Supercomputer läuft.

Das Thema führt zu tiefgreifenden Erkenntnissen über die Grenzen der Berechenbarkeit und die Notwendigkeit von Optimierungen. Es geht nicht nur um Formeln, sondern um das Gespür für Skalierbarkeit. Wenn Schüler die Laufzeit ihrer eigenen Programme experimentell messen und mit theoretischen Vorhersagen vergleichen, wird die Mathematik dahinter lebendig. Dieser Bereich profitiert stark von forschendem Lernen, bei dem Schüler Hypothesen über das Verhalten von Algorithmen aufstellen und diese durch Belastungstests prüfen.

Leitfragen

1. Wann ist eine verkettete Liste einem Array in der Praxis überlegen?
2. Analysieren Sie die Zeitkomplexität von Operationen auf Arrays und verketteten Listen.
3. Begründen Sie die Wahl einer bestimmten Datenstruktur für ein gegebenes Problem.

Lernziele

• Vergleichen Sie die Speicherplatz- und Zeitkomplexität von Arrays und verketteten Listen für Einfüge-, Lösch- und Suchoperationen.
• Analysieren Sie die Eignung von Arrays und verketteten Listen für konkrete Anwendungsszenarien, wie z. B. die Implementierung eines Stacks oder einer Warteschlange.
• Begründen Sie die Wahl einer Datenstruktur (Array oder verkettete Liste) basierend auf den Anforderungen eines gegebenen Problems und den Eigenschaften der Datenstrukturen.
• Implementieren Sie grundlegende Operationen (Einfügen, Löschen, Suchen) für eine verkettete Liste in einer Programmiersprache.

Bevor es losgeht

Grundlagen der Programmierung (Variablen, Datentypen, Kontrollstrukturen)

Warum: Grundlegende Programmierkenntnisse sind notwendig, um die Konzepte von Arrays und Listen sowie deren Operationen zu verstehen und zu implementieren.

Einführung in Algorithmen und O-Notation

Warum: Ein Verständnis der O-Notation ist entscheidend, um die Effizienz von Operationen auf Arrays und Listen vergleichen zu können.

Schlüsselvokabular

Array	Eine Datenstruktur, die eine feste Anzahl von Elementen desselben Datentyps speichert. Der Zugriff auf Elemente erfolgt über einen Index, was einen schnellen direkten Zugriff ermöglicht.
Verkettete Liste	Eine lineare Datenstruktur, bei der Elemente (Knoten) nicht zusammenhängend im Speicher liegen. Jeder Knoten enthält Daten und einen Verweis (Zeiger) auf den nächsten Knoten in der Sequenz.
Statische vs. Dynamische Größe	Arrays haben eine feste, zur Kompilierzeit festgelegte Größe (statisch), während Listen ihre Größe zur Laufzeit dynamisch anpassen können.
Zeitkomplexität	Ein Maß dafür, wie sich die Laufzeit eines Algorithmus mit der Größe der Eingabe ändert. Wird oft mit der O-Notation ausgedrückt.
Speicherkomplexität	Ein Maß dafür, wie sich der Speicherbedarf eines Algorithmus mit der Größe der Eingabe ändert.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

O(n) bedeutet, dass der Algorithmus genau n Sekunden braucht.

Was Sie stattdessen lehren sollten

Die O-Notation beschreibt das Wachstum der Laufzeit, nicht die absolute Zeit. Durch den Vergleich von Programmen auf verschiedenen Rechnern erkennen Schüler, dass die Kurvenform gleich bleibt, auch wenn die absoluten Werte variieren.

Häufige Fehlvorstellung

Ein O(n²)-Algorithmus ist immer schlechter als ein O(n log n)-Algorithmus.

Was Sie stattdessen lehren sollten

Bei sehr kleinen Datenmengen kann der O(n²)-Algorithmus durch geringeren Verwaltungsaufwand schneller sein. In Kleingruppen-Diskussionen über 'Grenzfälle' wird dieses Verständnis für die Praxis geschärft.

Ideen für aktives Lernen

Experimentelle Untersuchung: Die Stoppuhr-Challenge

Schüler lassen zwei Algorithmen (z.B. lineare Suche vs. binäre Suche) gegen unterschiedlich große Datensätze laufen. Sie protokollieren die Zeiten, zeichnen Graphen und leiten daraus die jeweilige Komplexitätsklasse ab.

45 Min.·Partnerarbeit

Stationenrotation: O-Notation-Puzzle

An verschiedenen Stationen liegen Code-Schnipsel (Schleifen, geschachtelte Schleifen, Rekursionen). Schüler müssen die Anzahl der Elementaroperationen zählen und den Schnipsel der richtigen O-Klasse zuordnen.

50 Min.·Kleingruppen

Ich-Du-Wir (Denken-Austauschen-Vorstellen): Der Space-Time Trade-off

Schüler analysieren ein Problem, das entweder mit viel Speicher (Caching) oder viel Rechenzeit gelöst werden kann. Sie diskutieren in Paaren, in welcher Situation (z.B. eingebettetes System vs. Cloud-Server) welche Lösung vorzuziehen ist.

30 Min.·Partnerarbeit

Bezüge zur Lebenswelt

• In der Softwareentwicklung werden Arrays häufig für die Darstellung von Pixeldaten in Bildern oder für die Speicherung von Konfigurationsparametern verwendet, bei denen die Anzahl der Elemente bekannt ist. Datenbankindizes nutzen oft arrayähnliche Strukturen für schnellen Datenzugriff.
• Betriebssysteme verwenden verkettete Listen zur Verwaltung von Prozessen im Speicher oder zur Implementierung von Warteschlangen für Druckeraufträge. Dies ermöglicht eine flexible Anpassung an eine variable Anzahl von Elementen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie den Schülerinnen und Schülern ein kleines Code-Snippet, das entweder ein Array oder eine verkettete Liste verwendet. Bitten Sie sie, zu identifizieren, welche Datenstruktur verwendet wird, und zwei Gründe zu nennen, warum diese Wahl für das dargestellte Problem sinnvoll ist.

Diskussionsfrage

Stellen Sie die Frage: 'Stellen Sie sich vor, Sie entwickeln eine App zur Verwaltung von Musik-Playlists. Welche Datenstruktur würden Sie für die Speicherung der Songreihenfolge wählen und warum? Diskutieren Sie die Vor- und Nachteile von Arrays und verketteten Listen für dieses Szenario.'

Kurze Überprüfung

Zeigen Sie eine Tabelle mit verschiedenen Operationen (z. B. Element am Anfang einfügen, Element am Ende löschen, Element an Index i suchen) und bitten Sie die Schüler, die Zeitkomplexität (O-Notation) für Arrays und verkettete Listen einzutragen. Überprüfen Sie die Antworten gemeinsam.

Häufig gestellte Fragen

Warum ist die O-Notation für Informatiker so wichtig?

Sie ermöglicht es, die Effizienz eines Algorithmus objektiv zu vergleichen, ohne von der Geschwindigkeit des Prozessors oder der Programmiersprache abhängig zu sein. Es ist die universelle Sprache, um über Skalierbarkeit zu sprechen.

Wie kann man Schülern die logarithmische Laufzeit O(log n) anschaulich erklären?

Das beste Beispiel ist das Telefonbuch oder das Erraten einer Zahl. Wenn man den Suchraum mit jedem Schritt halbiert, wächst der Aufwand nur minimal, selbst wenn sich die Datenmenge verdoppelt. Aktives Ausprobieren dieses Prinzips macht den Logarithmus begreifbar.

Was bedeutet 'Worst-Case-Analyse'?

Man betrachtet das Szenario, in dem der Algorithmus am längsten braucht (z.B. Suche nach einem Element, das nicht existiert). Dies ist für die Sicherheit und Zuverlässigkeit von Systemen wichtiger als der Durchschnittsfall, da man Garantien über die maximale Laufzeit geben kann.

Wie hilft aktives Lernen beim Thema Komplexität?

Anstatt nur Formeln zu lernen, können Schüler durch das Messen von Laufzeiten und das Erstellen von Diagrammen eine intuitive Vorstellung von Wachstum entwickeln. Wenn sie selbst erleben, wie ein Programm bei 100.000 Elementen plötzlich 'einfriert', verstehen sie die Bedeutung von O(n²) besser als durch jede Theorie.