Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [17.11.2022 07:05] – [Algorithmus] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [11.06.2024 13:21] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
 ====== 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:
@@ 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.
   * 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.
@@ Zeile 41: / Zeile 43: @@
 {{ :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.
-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 =====
@@ Zeile 205: / Zeile 207: @@
 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,
-aber eine Gruppe wurde nicht fertig.
+aber eine Gruppe wird nicht fertig.
 Die schlausten Schüler, Ada und Charles, haben die vier Gruppen analysiert.
@@ Zeile 234: / Zeile 236: @@
 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 ====
 {{simplefilelist>.:*}}