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
Alltagskompetenzen