Inf11 - Lernbereich 1: Graphen (ca. 10 Std.)

Kompetenzerwartungen: Die Schülerinnen und Schüler ...

modellieren im Rahmen praktischer Fragestellungen vernetzte Strukturen als Graphen und klassifizieren diese anhand ihrer Eigenschaften.
implementieren mithilfe einer objektorientierten Programmiersprache und unter Verwendung einer Adjazenzmatrix die Datenstruktur Graph.
erläutern allgemein die Idee der Breitensuche, formulieren den zugehörigen Algorithmus und wenden diesen an konkreten Beispielen an.
implementieren den Breitensuche-Algorithmus und modifizieren diesen in geeigneter, vom Anwendungskontext abhängiger Weise, z. B. bei der Auswahl oder Bearbeitung aller erreichbaren Knoten mit bestimmten Eigenschaften.
analysieren und erläutern die Funktionsweise des Dijkstra-Algorithmus und wenden diesen an konkreten Beispielen an; dabei erkennen sie, dass Algorithmen ihren Alltag mitbestimmen.

Inhalte zu den Kompetenzen:

Graph: Knoten, Kanten, Pfad, Erreichbarkeit von Knoten, Zyklus
Eigenschaften von Graphen: gerichtet, (stark/schwach) zusammenhängend, bewertet/gewichtet, zyklenfrei
Adjazenzmatrix
Breitensuche, Dijkstra-Algorithmus

Ergänzendes Unterrichtsmaterial