Sie sind hier:

Stoffverteilungsplan

Datenstrukturen (3.x.1.2)

Algorithmen auf Datenstrukturen (3.x.2.2)

Dieser Stoffverteilungsplan stellt einen möglichen Unterrichtsgang durch das Thema Graphen dar. Er setzt voraus, dass die Schülerinnen und Schüler vorher verkettete Datenstrukturen und Breiten- und Tiefensuche in Bäumen kennengelernt und im Leistungsfach auch das Thema Laufzeitanalyse schon behandelt haben. Gegebenenfalls kann das Thema Backtracking in die Unterrichtseinheit Graphen integriert werden.

Die einzelnen Stunden sollten in der Art des Zugangs variiert werden. Ein Vorschlag ist jeweils in Klammer angegeben. Näheres dazu im Unterrichtsverlauf.

x = sollte auf jeden Fall gemacht werden
o = optional

Std.	Inhaltsbezogene Kompetenzen	Inhalt / Material	BF	LF
1+2	BF + LF 3.x.1.2 (5) Begriffe aus der Graphentheorie (unter anderem Knoten, Kanten, Knotengrad,[...] Kreis/Zyklus) [...] verwenden	Einführung Graphen: Euler-Zug Anzahl der Knoten einer Zusammenhangskomponente mit Breiten- und/oder Tiefensuche bestimmen (Simulation => Algorithmus) Arbeitsblatt: 01_eulerzug.odt Präsentation: 02_eulerzug.odp Graphentester	x	x
3+4	BF + LF 3.x.1.2 (5) Begriffe aus der Graphentheorie (unter anderem [...] Kreis/Zyklus) und Eigenschaften von Graphen (unter anderem gerichtet / ungerichtet,[...], zyklisch / azyklisch) verwenden LF 3.2.1.2 (11) einen Algorithmus auf Graphen implementieren (unter Verwendung geeigneter Bibliotheken [...])	*Topologische Sortierung* (Quelltext des Algorithmus => Nachvollziehen => Quelltext kommentieren) Arbeitsblatt: 02_topologischesortierung.odt		o
5+6	BF+LF 3.x.2.2 (10) einen Algorithmus zur Lösung des Problems des kürzesten Pfades (zum Beispiel Dijkstra) beschreiben und an Beispielen von Hand durchführen	Kürzester Pfad: *Moores Algorithmus A* (Selbstentdeckend mit gestuften Hilfen) Wdh. Breitensuche Arbeitsblatt: 03_kuerzesterpfad.odt Graphentester	x	x
7+8	3.x.1.2 (5) Begriffe aus der Graphentheorie (unter anderem [...] Kreis/Zyklus) und Eigenschaften von Graphen (unter anderem [...], gewichtet / ungewichtet, [...]) verwenden BF+LF 3.x.2.2 (10) einen Algorithmus zur Lösung des Problems des kürzesten Pfades (zum Beispiel Dijkstra) beschreiben und an Beispielen von Hand durchführen	Kürzester Pfad: *Dijkstra oder Bellman-Ford* (Pseudocode => Nachvollziehen => Unterschiede zu Moore herausarbeiten) Arbeitsblatt: 04_kuerzesterpfad2.odt	x	x
9+10	LF 3.2.1.2 (11) einen Algorithmus auf Graphen implementieren (unter Verwendung geeigneter Bibliotheken oder Frameworks)	Implementation von *Moore* oder *Dijkstra* ggf. Verwendung des selbst implementierten ADT Queue Arbeitsblatt: 04_kuerzesterpfad2.odt Graphentester Vorlage Tauschordner: Klassendokumentation		x
11+12	LF 3.2.2.2 (11) erläutern, dass nicht bekannt ist, ob für jedes Problem eine in Polynomialzeit berechenbare Lösung existiert, und können dafür Beispiele angeben LF 3.2.2.2 (12) Strategien (zum Beispiel Greedy) zur Bestimmung von Näherungslösungen in polynomieller Laufzeit beschreiben und an geeigneten Problemstellungen (zum Beispiel 4-Farben-Problem, Dominating Sets) von Hand durchführen	Dominierende Mengen Erkenntnis: Optimale Lösung zu finden ist schwierig, da es sehr viele Möglichkeiten gibt Berechnung der Anzahl Greedy: Grundprinzip verschiedene Heuristiken bewerten und ausprobieren Arbeitsblatt: 05_dominierendemenge.odt Graphentester (Algorithmen DominatingSetGreedyX bereitstellen)		x
Ggf. hier Einschub: Backtracking-Algorithmen
12+13	BF+LF 3.x.1.2 (4) Graphen in den Repräsentationsformen Adjazenzmatrix und Adjazenzliste beschreiben	Repräsentation von Graphen Effizienzanalyse (Motivation Laufzeitanalyse der Algorithmen ohne sie explizit durchzuführen) Arbeitsblatt: 06_repraesentation.odt	x	x x
14+15	LF 3.2.2.2 (12) Strategien (zum Beispiel Greedy) zur Bestimmung von Näherungslösungen in polynomieller Laufzeit beschreiben und an geeigneten Problemstellungen (zum Beispiel 4-Farben-Problem, Dominating Sets) von Hand durchführen LF 3.2.1.2 (11) einen Algorithmus auf Graphen implementieren [...]	Traveling Salesman Problem (Aufgreifen aus IMP, Enaktiv mit Holzmodell) Implementation Greedy Arbeitsblatt: 06_repraesentation.odt Graphentester Beispielgraphen: im Ordner 06_travelingsalesman Ausblick: andere Strategien (z.B. Genetisch) Simulation im Graphentester	o	o o o
16+17	LF 3.2.2.2 (12) Strategien (zum Beispiel Greedy) zur Bestimmung von Näherungslösungen in polynomieller Laufzeit beschreiben und an geeigneten Problemstellungen (zum Beispiel 4-Farben-Problem, Dominating Sets) von Hand durchführen	*Kartenfärbeproblem* (Beschreibung des Algorithmus => händisches Durchführen) Arbeitsblatt: 07_kartenfaerben.odt Graphentester		o
18+19	LF 3.2.2.2 (10) einen Algorithmus (zum Beispiel Prim, Kruskal) zur Bestimmung eines Minimum Spanning Tree und einen zur Lösung des Problems des kürzesten Pfades (zum Beispiel Dijkstra, Bellman-Ford) beschreiben und an Beispielen von Hand durchführen	Minimal spannende Bäume (Kruskal oder Prim) (Analyse der Simulation eines fertigen Algorithmus => Händisches Durchführen) Arbeitsblatt: 08_minimalspanningtree.odt Graphentester		x
19+20	LF 3.2.1.2 (10) Datenstrukturen zur Modellierung und Lösung ausgewählter Anwendungsfälle [...] nutzen	Vermischte Übungen Arbeitsblätter 11_1 bis 19_1 (AB 1x_... passt thematisch zu AB 0x_...)	o	x

Stoffverteilungsplan: Herunterladen [odt][104 KB]

Weiter zu Installation: Graphentester