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) |
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) |
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) |
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) |
Implementation von Moore oder Dijkstra Arbeitsblatt: 04_kuerzesterpfad2.odt Graphentester Vorlage Tauschordner: |
x |
|
11+12 |
LF 3.2.2.2 (11) LF 3.2.2.2 (12) |
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 |
x |
|
| Ggf. hier Einschub: Backtracking-Algorithmen | ||||
12+13 |
BF+LF 3.x.1.2 (4) |
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) LF 3.2.1.2 (11) |
Traveling Salesman Problem (Aufgreifen aus IMP, Enaktiv mit Holzmodell) Implementation Greedy Arbeitsblatt: 06_repraesentation.odt Graphentester Ausblick: andere Strategien (z.B. Genetisch) Simulation im Graphentester |
o |
o
o o
|
16+17 |
LF 3.2.2.2 (12) |
Kartenfärbeproblem (Beschreibung des Algorithmus => händisches Durchführen) Arbeitsblatt: 07_kartenfaerben.odt Graphentester |
o |
|
18+19 |
LF 3.2.2.2 (10) |
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) |
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