Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [15.11.2022 11:03] – [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 37: / Zeile 39: @@
 ++++ Lösung |
 {{ :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 59: / Zeile 62: @@
 ++++
-====== Definition: Topologische Sortierung, Reihenfolge ====
+===== Definition: Topologische Sortierung, Reihenfolge =====
 <WRAP center round important 96%>
@@ Zeile 83: / 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 ======
+===== Algorithmus =====
 {{:aufgabe.png?nolink  |}}
@@ Zeile 136: / Zeile 139: @@
 === (A5) ===
-Implementiere den Algorithmus selbst in einer eigenen Klasse unter "eigene Algorithmen".
+Implementiere den Algorithmus selbst in einer eigenen Klasse unter "eigene Algorithmen". Teste deinen Algorithmus an den Beispielen ''03_beispiel_obst.csv'' und  ''04_beispiel_obst2.csv''.
+++++ Lösungsvorschlag Algorithmus |
+<code java>
+// Reihenfolge
+String Reihenfolge = "";
+// Hole alle Knoten vom Graph g
+List<Knoten> alleKnoten = g.getAlleKnoten();
+// Schleife über alle Knoten
+for(Knoten k: alleKnoten) {
+    int Eingangsgrad = g.getEingehendeKanten(k).size();
+    k.setWert(Eingangsgrad);
+    k.setFarbe(7);
+}
+step();
+boolean sort=true;
+while(alleKnoten.size() > 0 && sort) {
+    Collections.sort(alleKnoten);
+    Knoten k = alleKnoten.remove(0);
+    if (k.getIntWert() == 0) {
+        k.setFarbe(4);
+        Reihenfolge += k.getInfotext() + " ";
+        for(Knoten n: g.getNachbarknoten(k)) {
+            n.setWert(n.getIntWert()-1);
+        }
+     } else {
+        sort=false;
+     }
+     step();
+}
+if (! sort) {
+    System.out.println("Keine Sortierung möglich!");
+} else {
+    System.out.println(Reihenfolge);
+}
+</code>
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A6) Rangliste ===
+Im Tennisclub "Blau-Weiß" wird normalerweise im Laufe des Jahres eine Rangliste der Spieler
+ausgespielt. Dazu spielt jeder gegen jeden. In diesem Jahr mussten aber umfangreiche
+Bauarbeiten am Platz durchgeführt werden. Die Saison neigt sich nun dem Ende, es haben aber
+noch nicht alle Paarungen stattgefunden. Die Tabelle gibt Auskunft, wie die Spiele nach Sätzen
+ausgegangen sind. Der Eintrag in der dritten Spalte der zweiten Zeile bedeutet z.B., dass Albert
+mit 1:3 gegen Boris verloren hat.
+{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:tabelle.png?600 |}}
+  * Modelliere die Situation als Graph. Was sind die Knoten? Was wird durch die Kanten beschrieben? Wäre es möglich die Situation durch einen ungerichteten Graphen zu modellieren?
+  * Verwende den Graphentester, um zu untersuchen, ob es eine Sortierung gibt. Gib, wenn möglich die Rangliste an.
+  * Ist die Rangliste eindeutig?
+----
+{{:aufgabe.png?nolink  |}}
+=== (A7) Gruppenarbeit ===
+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.
+{{ :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>.:*}}