faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [17.11.2022 07:03] – [Algorithmus] Frank Schiebelfaecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [11.06.2024 13:21] (aktuell) – Frank Schiebel
Zeile 1: Zeile 1:
 ====== Topologische Sortierung von Graphen ====== ====== Topologische Sortierung von Graphen ======
-{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausim.png?400|}}((Grafik(en): Warenverkehr bei einer Aufbausimulation (alle Bilder Pixabay-Lizenz - kein Nachweis notwendig) ))+
 Bei einem Aufbausimulationsspiel kann man verschiedene Gebäude bauen. Jedes Gebäude produziert eine bestimmte Ware. Damit das Gebäude arbeiten kann, benötigt es seinerseits Waren anderer Gebäude als Rohstoff: Bei einem Aufbausimulationsspiel kann man verschiedene Gebäude bauen. Jedes Gebäude produziert eine bestimmte Ware. Damit das Gebäude arbeiten kann, benötigt es seinerseits Waren anderer Gebäude als Rohstoff:
  
Zeile 8: Zeile 8:
   * Mit dem Getreide der Farm werden die Schweine gefüttert und in der Mühle das Mehl für den Bäcker gemahlen.    * Mit dem Getreide der Farm werden die Schweine gefüttert und in der Mühle das Mehl für den Bäcker gemahlen. 
   * Die Schweine werden vom Metzger geschlachtet.    * Die Schweine werden vom Metzger geschlachtet. 
 +
 +{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausim.png?400 |}}((Grafik(en): Warenverkehr bei einer Aufbausimulation (alle Bilder Pixabay-Lizenz - kein Nachweis notwendig) ))
  
 Diese Abhängigkeiten machen es schwer zu entscheiden, in welcher Reihenfolge man die Gebäude bauen sollte, damit sie nicht ungenutzt herumstehen.  Diese Abhängigkeiten machen es schwer zu entscheiden, in welcher Reihenfolge man die Gebäude bauen sollte, damit sie nicht ungenutzt herumstehen. 
Zeile 41: Zeile 43:
 {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph.png?600 |}} {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph.png?600 |}}
  
-Es gibt keine topologiosche Sortierung, weil es nicht möglich ist, einen Graph ohne Zyklus zu finden, der eine Reihenfolge für die Gebäude angibt. das Problem sind die Verbindungen vom Metzger und vom Bäcker zu den Minen, diese können nicht ersetzt werden, damit erhält man zwei Zyklen im Graphen, die man nicht vermeiden kann.+Es gibt keine topologische Sortierung, weil es nicht möglich ist, einen Graph ohne Zyklus zu finden, der eine Reihenfolge für die Gebäude angibt. das Problem sind die Verbindungen vom Metzger und vom Bäcker zu den Minen, diese können nicht ersetzt werden, damit erhält man zwei Zyklen im Graphen, die man nicht vermeiden kann.
  
 ++++ ++++
Zeile 84: Zeile 86:
 Du kannst das selbst ausprobieren, indem du die folgende Datei {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph-fischerhuette.zip |}} herunterlädst und auspackst. Du erhältst die Datei ''Aufbausimulation-Graph-Fischerhuette.excalidraw''. Diese kannst du in [[https://excalidraw.com/|Excalidraw]] öffnen, nun kannst du die Knoten des Graphen auf einer Achse anordnen, so dass es keine Kanten gibt, die von rechts nach links zeigen.  Du kannst das selbst ausprobieren, indem du die folgende Datei {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph-fischerhuette.zip |}} herunterlädst und auspackst. Du erhältst die Datei ''Aufbausimulation-Graph-Fischerhuette.excalidraw''. Diese kannst du in [[https://excalidraw.com/|Excalidraw]] öffnen, nun kannst du die Knoten des Graphen auf einer Achse anordnen, so dass es keine Kanten gibt, die von rechts nach links zeigen. 
  
-Zum Vergleich, ikannst du versuchen, dasselbe Ergebnis mit dem ursprünglichen Graphen (ohne Fischerhütte) zu erzielen: {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph.zip |}} - man kann sehr gut erkennen, wie ein Zyklus im Graph eine topologische Sortierung unmöglich macht. +Zum Vergleich, kannst du versuchen, dasselbe Ergebnis mit dem ursprünglichen Graphen (ohne Fischerhütte) zu erzielen: {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph.zip |}} - man kann sehr gut erkennen, wie ein Zyklus im Graph eine topologische Sortierung unmöglich macht. 
  
 ===== Algorithmus ===== ===== Algorithmus =====
Zeile 198: Zeile 200:
   * Verwende den Graphentester, um zu untersuchen, ob es eine Sortierung gibt. Gib, wenn möglich die Rangliste an.   * Verwende den Graphentester, um zu untersuchen, ob es eine Sortierung gibt. Gib, wenn möglich die Rangliste an.
   * Ist die Rangliste eindeutig?   * Ist die Rangliste eindeutig?
-  * +
 ---- ----
 {{:aufgabe.png?nolink  |}} {{:aufgabe.png?nolink  |}}
-=== (A8) Gruppenarbeit ===+=== (A7) Gruppenarbeit ===
  
 Für eine Gruppenarbeit bilden die Schüler einer Klasse vier Gruppen. Alle Gruppen teilten Für eine Gruppenarbeit bilden die Schüler einer Klasse vier Gruppen. Alle Gruppen teilten
 ihre Arbeit in einzelne Aufgaben auf. Drei Gruppen konnten alle ihre Aufgaben erledigen, ihre Arbeit in einzelne Aufgaben auf. Drei Gruppen konnten alle ihre Aufgaben erledigen,
-aber eine Gruppe wurde nicht fertig.+aber eine Gruppe wird nicht fertig.
  
 Die schlausten Schüler, Ada und Charles, haben die vier Gruppen analysiert. Die schlausten Schüler, Ada und Charles, haben die vier Gruppen analysiert.
Zeile 216: Zeile 218:
 Ein Kreis stellt eine Person dar. Ein Pfeil von Person 1 nach Person 2 bedeutet, Ein Kreis stellt eine Person dar. Ein Pfeil von Person 1 nach Person 2 bedeutet,
 dass Person 1 ihre Aufgabe erledigt haben musste, bevor Person 2 mit ihrer Aufgabe beginnen konnte. dass Person 1 ihre Aufgabe erledigt haben musste, bevor Person 2 mit ihrer Aufgabe beginnen konnte.
 +
 +**Welches Bild entspricht der Gruppe, die nicht fertig wurde?** (Begründe deine Antwort)
 +
 +{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:gruppenarbeit.png |}}
  
 ---- ----
Zeile 230: Zeile 236:
  
 Frage: **Wie viele Minuten benötigen sie für die Zubereitung der beiden Gerichte mindestens?** Frage: **Wie viele Minuten benötigen sie für die Zubereitung der beiden Gerichte mindestens?**
 +
 +
 +++++ Lösung | 
 +
 +{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:2024-03-19_15-44.png |}}
 +
 +++++
 ==== Dateien ==== ==== Dateien ====
  
 {{simplefilelist>.:*}} {{simplefilelist>.:*}}
  • faecher/informatik/oberstufe/graphen/zpg/topologische_sortierung/start.1668668596.txt.gz
  • Zuletzt geändert: 17.11.2022 07:03
  • von Frank Schiebel