Informatik · Klasse 13 · Datenstrukturen und Algorithmen-Analyse · 1. Halbjahr

Grundlagen der Algorithmenanalyse

Die Schülerinnen und Schüler lernen die Notwendigkeit der Analyse von Algorithmen und grundlegende Metriken kennen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen

Über dieses Thema

Dynamische Datenstrukturen wie Bäume und Graphen sind die Werkzeuge, mit denen komplexe Beziehungen in der Informatik abgebildet werden. Während lineare Listen an ihre Grenzen stoßen, ermöglichen Bäume effizientes Suchen und Graphen die Modellierung von Netzwerken. In der 13. Klasse liegt der Fokus auf der Implementierung und der Wahl der richtigen Struktur für spezifische Probleme. Dies deckt die KMK-Standards zur Modellierung und Implementierung ab, wobei Schüler lernen, abstrakte Konzepte in funktionierenden Code zu übersetzen.

Diese Strukturen sind das Rückgrat moderner Anwendungen, von Dateisystemen bis hin zu sozialen Netzwerken. Schüler müssen verstehen, wie Zeiger und Referenzen im Speicher arbeiten, um diese Strukturen dynamisch zu verwalten. Das Thema profitiert massiv von visuellen und kollaborativen Ansätzen, bei denen Schüler Graphen physisch legen oder Suchalgorithmen in Gruppen 'durchspielen', bevor sie diese programmieren.

Leitfragen

1. Erklären Sie, warum die Effizienz von Algorithmen entscheidend für die Softwareentwicklung ist.
2. Vergleichen Sie verschiedene Ansätze zur Messung der Algorithmenleistung.
3. Analysieren Sie die Auswirkungen von Hardware- und Softwarefaktoren auf die Algorithmenperformance.

Lernziele

• Erklären Sie die Notwendigkeit der Algorithmenanalyse anhand konkreter Anwendungsbeispiele aus der Softwareentwicklung.
• Vergleichen Sie die Zeitkomplexität von Big-O-Notation für verschiedene Algorithmen (z. B. lineare Suche vs. binäre Suche).
• Berechnen Sie die Laufzeit von einfachen Algorithmen für gegebene Eingabegrößen.
• Identifizieren Sie die dominanten Terme in Laufzeitfunktionen zur Bestimmung der Big-O-Notation.
• Bewerten Sie die Effizienz eines gegebenen Algorithmus in Bezug auf Laufzeit und Speicherbedarf.

Bevor es losgeht

Grundlagen der Programmierung

Warum: Schüler müssen grundlegende Programmierkonzepte wie Variablen, Schleifen und bedingte Anweisungen verstehen, um Algorithmen implementieren und analysieren zu können.

Einfache Datenstrukturen (Arrays, Listen)

Warum: Ein Verständnis von grundlegenden Datenstrukturen ist notwendig, um zu verstehen, wie Algorithmen auf Daten zugreifen und diese verarbeiten.

Schlüsselvokabular

Algorithmenanalyse	Die Untersuchung der Effizienz von Algorithmen in Bezug auf die benötigte Rechenzeit (Zeitkomplexität) und den Speicherplatz (Speicherkomplexität).
Zeitkomplexität	Ein Maß dafür, wie sich die Laufzeit eines Algorithmus mit zunehmender Größe der Eingabe vergrößert. Wird oft mit Big-O-Notation ausgedrückt.
Speicherkomplexität	Ein Maß dafür, wie sich der Speicherbedarf eines Algorithmus mit zunehmender Größe der Eingabe vergrößert.
Big-O-Notation	Eine mathematische Notation, die das asymptotische Verhalten von Funktionen beschreibt und verwendet wird, um die obere Schranke der Komplexität eines Algorithmus anzugeben.
Laufzeit	Die tatsächliche Zeit, die ein Algorithmus benötigt, um eine Aufgabe auszuführen. Sie ist abhängig von der Hardware, dem Betriebssystem und der Implementierung.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Ein Baum ist nur eine kompliziertere Liste.

Was Sie stattdessen lehren sollten

Bäume ermöglichen logarithmisches Suchen, Listen nur lineares. Durch das Stoppen der Zeit beim 'Suchen' in physischen Modellen erleben Schüler den massiven Geschwindigkeitsvorteil bei großen Datenmengen.

Häufige Fehlvorstellung

Graphen und Bäume sind dasselbe.

Was Sie stattdessen lehren sollten

Ein Baum ist ein spezieller Graph ohne Zyklen. Das Identifizieren von Zyklen in verschiedenen Netzwerkdiagrammen hilft Schülern, die hierarchische Struktur von Bäumen von der freien Vernetzung in Graphen abzugrenzen.

Ideen für aktives Lernen

Museumsgang: Graphen im echten Leben

Schüler erstellen Poster zu verschiedenen Anwendungsfällen (U-Bahn-Netz, Stammbaum, Internet-Routing) und analysieren im Rundgang, welche Graphen-Eigenschaften (gerichtet, gewichtet) jeweils vorliegen.

45 Min.·Ganze Klasse

Forschungskreis: Der perfekte Suchbaum

Gruppen erhalten ungeordnete Datensätze und müssen manuell einen balancierten binären Suchbaum erstellen. Danach vergleichen sie die Suchtiefe mit einer unsortierten Liste.

40 Min.·Kleingruppen

Ich-Du-Wir (Denken-Austauschen-Vorstellen): Baum oder Graph?

Schüler bewerten verschiedene Szenarien (z.B. Ordnerstruktur vs. Freundschaften bei Instagram) und entscheiden paarweise, welche Datenstruktur effizienter ist, inklusive Begründung der Speicherkomplexität.

30 Min.·Partnerarbeit

Bezüge zur Lebenswelt

• Bei der Entwicklung von Suchmaschinen wie Google ist die Algorithmenanalyse entscheidend, um Suchanfragen in Millisekunden zu beantworten. Ein ineffizienter Suchalgorithmus würde die Benutzererfahrung stark beeinträchtigen.
• Im Finanzwesen werden Algorithmen für den Hochfrequenzhandel eingesetzt. Hier zählt jede Mikrosekunde, weshalb die Optimierung der Algorithmen auf Geschwindigkeit und Effizienz absolute Priorität hat, um profitable Handelsentscheidungen treffen zu können.
• Die Analyse von Algorithmen ist für die Entwicklung von Betriebssystemen unerlässlich. Beispielsweise muss der Scheduler eines Betriebssystems effizient entscheiden, welche Prozesse als Nächstes ausgeführt werden, um eine reibungslose Systemleistung zu gewährleisten.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie den Schülern die Beschreibung eines einfachen Algorithmus (z. B. Summe der Elemente einer Liste). Bitten Sie sie, die Anzahl der Operationen für jede Zeile zu zählen und die dominante Operation zu identifizieren. Fragen Sie: 'Warum ist es wichtig, die Anzahl der Operationen zu kennen?'

Kurze Überprüfung

Zeigen Sie auf dem Whiteboard zwei Code-Snippets, die unterschiedliche Ansätze zur Lösung desselben Problems darstellen (z. B. iterative vs. rekursive Fakultät). Bitten Sie die Schüler, die Big-O-Notation für beide Ansätze zu bestimmen und zu begründen, welcher Ansatz unter welchen Umständen (z. B. große Eingaben) effizienter ist.

Diskussionsfrage

Stellen Sie die Frage: 'Stellen Sie sich vor, Sie entwickeln eine App für die Routenplanung. Welche Faktoren beeinflussen die Wahl des Algorithmus für die Routenberechnung, und wie würden Sie die Effizienz verschiedener Algorithmen vergleichen, bevor Sie eine Entscheidung treffen?'

Häufig gestellte Fragen

Wann sollte man einen binären Suchbaum verwenden?

Immer dann, wenn Daten häufig sortiert ausgegeben werden müssen oder schnelle Suchvorgänge in dynamischen Mengen erforderlich sind, bei denen sich die Daten oft ändern.

Wie fördert aktives Lernen das Verständnis von Datenstrukturen?

Indem Schüler Graphen mit Seilen legen oder Bäume mit Karteikarten bauen, wird die abstrakte Zeiger-Logik begreifbar. Fehler in der Struktur werden visuell sofort offensichtlich, was die Fehlersuche im Code später erleichtert.

Was ist der Unterschied zwischen Tiefensuche und Breitensuche?

Die Tiefensuche geht erst in die Tiefe eines Pfades, die Breitensuche erkundet erst alle Nachbarn. Beide haben unterschiedliche Einsatzgebiete, etwa bei der Wegfindung oder in KI-Systemen.

Warum sind Graphen für soziale Medien wichtig?

Sie erlauben es, Beziehungen (Kanten) zwischen Nutzern (Knoten) effizient zu speichern und komplexe Abfragen wie 'Freunde von Freunden' performant durchzuführen.