Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [17.11.2022 06:51] – [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 201: / Zeile 203: @@
 ----
 {{:aufgabe.png?nolink  |}}
-=== (A7) Kochplatten ===
+=== (A7) Gruppenarbeit ===
-((Aufgabe aus dem Informatik-Biber-Wettbewerb 2013. https://bwinf.de/biber/archiv/aufgabensammlung/ -- Copyright 2013 BWINF - GI e.V. (Lizenz CC-BY-SA 3.0)))
+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 wird nicht fertig.
+Die schlausten Schüler, Ada und Charles, haben die vier Gruppen analysiert.
+Sie fanden heraus, dass die meisten Gruppenmitglieder auf andere warten mussten,
+bevor sie mit ihrer eigenen Aufgabe beginnen konnten.
+Ada und Charles haben für jede Gruppe eine Skizze gezeichnet,
+die sich auf das Wesentliche konzentriert.
+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.
+**Welches Bild entspricht der Gruppe, die nicht fertig wurde?** (Begründe deine Antwort)
+{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:gruppenarbeit.png |}}
+----
+{{:aufgabe.png?nolink  |}}
+=== (A8) Kochplatten ===
+((Aufgabe aus dem Informatik-Biber-Wettbewerb 2013. https://bwinf.de/biber/archiv/aufgabensammlung/ -- Copyright 2013 BWINF - GI e.V. (Lizenz CC-BY-SA 3.0) ))
 Anna und Ben kommen hungrig nach Hause. Nun möchten sie möglichst schnell zu Abend essen. Im Kühlschrank sind Brokkoli, Fisch, Tomaten und Fleisch. Daraus wollen sie zwei Gerichte zubereiten. Die Zubereitung erfolgt in mehreren Schritten. Die meisten Schritte können Anna und Ben erst dann beginnen, wenn sie andere Schritte bereits erledigt haben.
-Im Bild sind die Schritte als Kreise und die Abfolge der Schritte mit Pfeilen dargestellt
+Im Bild sind die Schritte als Kreise und die Abfolge der Schritte mit Pfeilen dargestellt.
+{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:biberkochen.png |}}
+Annas und Bens Herd hat drei Herdplatten. Sie können also maximal drei Schritte gleichzeitig erledigen. Für jeden Schritt benötigen sie 5 Minuten.
+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>.:*}}