Algorithmen und komplexe Datenstrukturen · 1. Halbjahr

Listen und dynamische Daten

Die Schülerinnen und Schüler implementieren Listen und Arrays zur Verwaltung von Datenmengen und wenden grundlegende Operationen an.

Über dieses Thema

Listen und dynamische Daten bilden eine Grundlage für die effiziente Handhabung variabler Datenmengen in Programmen. Schülerinnen und Schüler der Klasse 9 implementieren zunächst statische Arrays mit fester Größe und lernen dann dynamische Listen, die Elemente zur Laufzeit hinzufügen, entfernen oder verändern können. Sie üben grundlegende Operationen wie das Anhängen von Elementen, das Löschen an bestimmten Positionen, das systematische Durchlaufen mit Schleifen und einfache Suchalgorithmen. Diese Fähigkeiten verbinden sich direkt mit den KMK-Standards zu Algorithmen und Datenstrukturen in der Sekundarstufe I.

Im Unterrichtsthema Algorithmen und komplexe Datenstrukturen fördert dieses Wissen algorithmisches Denken und das Verständnis von Zeit- und Speicherkomplexität. Dynamische Listen bieten Vorteile gegenüber Arrays, da sie flexibel auf wachsende Daten reagieren, wie in Anwendungen aus Datenbanken oder App-Entwicklung. Schüler analysieren, wie Algorithmen alle Listenelemente verarbeiten, und konstruieren Programme zur Datenspeicherung und -Manipulation. Dies schafft Brücken zur gesellschaftlichen Relevanz von Informatik, etwa bei Big Data.

Active Learning eignet sich hervorragend, weil Schüler durch hands-on Programmierung und kollaboratives Debugging abstrakte Konzepte erleben. Sie testen Grenzfälle wie Überlauf in Arrays oder dynamisches Wachstum, was Fehlerquellen aufdeckt und tiefes Verständnis schafft.

Lernziele

• Vergleichen Sie die Speicherplatzanforderungen und die Flexibilität von statischen Arrays und dynamischen Listen zur Laufzeit.
• Analysieren Sie die Schritte eines Suchalgorithmus (z. B. lineare Suche), um ein bestimmtes Element in einer unsortierten Liste zu finden.
• Konstruieren Sie ein Python-Programm, das Benutzereingaben in einer dynamischen Liste speichert und diese Liste nach bestimmten Kriterien filtert.
• Erklären Sie die Notwendigkeit von Schleifen zur systematischen Verarbeitung aller Elemente einer dynamischen Liste und demonstrieren Sie dies anhand eines Beispiels.

Bevor es losgeht

Grundlagen der Programmierung: Variablen und Datentypen

Warum: Schüler müssen verstehen, wie Variablen Werte speichern, bevor sie lernen, wie Listen mehrere Werte speichern.

Kontrollstrukturen: Schleifen (for, while)

Warum: Das systematische Verarbeiten von Listenelementen erfordert das Verständnis und die Anwendung von Schleifen.

Schlüsselvokabular

Array (statisch)	Eine Datenstruktur mit einer festen Anzahl von Elementen desselben Typs, deren Größe bei der Deklaration festgelegt wird und nicht mehr geändert werden kann.
Dynamische Liste	Eine Datenstruktur, deren Größe zur Laufzeit angepasst werden kann, indem Elemente hinzugefügt oder entfernt werden, ohne dass die Größe im Voraus festgelegt werden muss.
Element hinzufügen	Die Operation, ein neues Datenelement am Ende oder an einer bestimmten Position einer Liste anzufügen.
Element entfernen	Die Operation, ein Datenelement von einer bestimmten Position oder dem Ende einer Liste zu löschen.
Iteration (Schleife)	Der Prozess des wiederholten Durchlaufens aller Elemente einer Datenstruktur, typischerweise mit einer `for`- oder `while`-Schleife.

Ideen für aktives Lernen

Paarprogrammierung: Dynamische Liste bauen

In Paaren erstellen Schüler ein Programm, das eine dynamische Liste initialisiert, Elemente per Eingabe hinzufügt und die Liste ausgibt. Sie testen das Anhängen und Einfügen an Positionen. Abschließend vergleichen sie Laufzeiten mit statischen Arrays.

⏱ 30 Min.·Partnerarbeit

Mission erstellen

Stationenrotation: Listenoperationen

Richten Sie Stationen ein: Station 1 für Durchlaufen mit for-Schleife, Station 2 für Suchen und Löschen, Station 3 für Sortieren. Gruppen rotieren alle 10 Minuten und protokollieren Code-Beispiele. Plenum diskutiert Ergebnisse.

⏱ 45 Min.·Kleingruppen

Mission erstellen

Ganzer-Klasse-Challenge: Daten manipulieren

Präsentieren Sie ein reales Datenset, z. B. Schülernoten. Die Klasse entwickelt gemeinsam einen Algorithmus, der Duplikate entfernt und sortiert. Jeder Schüler trägt Code-Zeilen bei und testet.

⏱ 40 Min.·Ganze Klasse

Mission erstellen

Individuelle Übung: Liste vs. Array

Jeder Schüler programmiert dasselbe Szenario mit Array und Liste, misst Flexibilität bei wachsenden Daten. Sie dokumentieren Vor- und Nachteile in einem Bericht.

⏱ 20 Min.·Einzelarbeit

Mission erstellen

Bezüge zur Lebenswelt

Softwareentwickler, die mobile Apps erstellen, verwenden dynamische Listen, um z. B. die Kontaktdaten eines Nutzers zu speichern, die sich ständig ändern können, oder um eine Einkaufsliste zu verwalten, deren Elemente hinzugefügt und gelöscht werden.

Datenanalysten in der Marktforschung nutzen Listen, um Umfrageergebnisse zu sammeln und zu verarbeiten. Sie können dynamisch neue Antworten hinzufügen und später bestimmte Antworten filtern oder sortieren, um Trends zu erkennen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Arrays sind immer schneller und besser als Listen.

Was Sie stattdessen lehren sollten

Arrays haben feste Größe und sind bei konstanter Nutzung effizient, Listen flexibler für variable Daten. Pair-Programming-Aktivitäten lassen Schüler beide testen, z. B. bei Überlauf, und Vorteile durch Messung entdecken.

Häufige Fehlvorstellung

Dynamische Listen verbrauchen immer mehr Speicher.

Was Sie stattdessen lehren sollten

Listen wachsen nur bei Bedarf, Arrays verschwenden Platz bei Unterauslastung. Gruppenexperimente mit Speichervergleichen zeigen dies konkret, fördern Diskussion über Effizienz.

Häufige Fehlvorstellung

Man kann Listen nicht linear durchlaufen.

Was Sie stattdessen lehren sollten

Schleifen wie for-each ermöglichen einfaches Durchlaufen. Hands-on Codieren und Debugging-Sessions klären Syntax und Logik, machen den Prozess greifbar.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Stellen Sie den Schülern eine kurze Programmieraufgabe: 'Schreiben Sie Code, der 5 Zahlen in eine dynamische Liste einfügt und dann nur die geraden Zahlen ausgibt.' Bewerten Sie die Korrektheit der Listenerstellung und der Filterung.

Diskussionsfrage

Fragen Sie die Schüler: 'Stellen Sie sich vor, Sie entwickeln ein Spiel, das Punkte zählt. Wann würden Sie ein statisches Array verwenden und wann eine dynamische Liste? Begründen Sie Ihre Wahl anhand der Eigenschaften der Datenstrukturen.'

Lernstandskontrolle

Geben Sie jedem Schüler eine Karte mit einer der folgenden Operationen: 'Element hinzufügen', 'Element entfernen', 'Liste durchlaufen'. Bitten Sie die Schüler, eine kurze Erklärung zu schreiben, warum diese Operation für dynamische Listen wichtig ist, und ein Beispiel zu nennen, wo sie nützlich wäre.

Häufig gestellte Fragen

Was sind die Vorteile dynamischer Listen gegenüber Arrays?

Dynamische Listen passen ihre Größe automatisch an, ohne Neuzuweisung wie bei Arrays. Sie eignen sich für unbekannte Datenmengen, z. B. in Suchmaschinen. Schüler lernen durch Implementierung, dass Operationen wie Einfügen O(1) am Ende sind, und messen Unterschiede in Programmen. Dies stärkt Verständnis für reale Anwendungen in der Informatik.

Wie analysiert man Algorithmen zum Verarbeiten von Listen?

Schüler zerlegen Algorithmen in Schritte: Initialisierung, Schleife zum Zugriff auf jedes Element, Bedingungen für Aktionen. Zeitkomplexität O(n) für Durchlaufen wird durch Test mit großen Listen verdeutlicht. Kollaborative Codierung hilft, Edge-Cases wie leere Listen zu behandeln und Korrektheit zu prüfen.

Wie kann aktives Lernen das Verständnis von Listen fördern?

Aktives Lernen macht Konzepte durch Pair Programming und Stationen greifbar: Schüler coden, testen und debuggen gemeinsam, entdecken z. B. Indexfehler selbst. Solche Ansätze bauen Selbstwirksamkeit auf, da Erfolge sichtbar sind, und verbinden Theorie mit Praxis effektiver als reine Frontalvermittlung. Gruppenfeedback vertieft das Wissen nachhaltig.

Welche Programme konstruieren Schüler mit Listen?

Typisch: Notenlisten mit Mittelwertberechnung, Einkaufslisten mit Summierung oder Suchfunktionen in Wörterbüchern. Schüler speichern Daten, manipulieren sie und geben Ergebnisse aus. Solche Projekte verknüpfen mit KMK-Standards und zeigen gesellschaftliche Nutzung, z. B. in Apps für Datenmanagement.