Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| talit:algorithmen [2025-03-03 20:37] – [Visualisierung] hof | talit:algorithmen [2025-03-03 21:01] (aktuell) – [Aufgabe 4 - Graph Walk] hof | ||
|---|---|---|---|
| Zeile 12: | Zeile 12: | ||
| Alle diese Probleme lassen sich mit mit Graphen formulieren und mit Graphenalgorithmen lösen. Graphen sind eine wichtige Datenstruktur in der Informatik. In der Talit kümmern wir uns erst einmal darum, wie wir einen Graph effizient beschreiben können; anschliessend schreiben wir Code, um verschiedene Eigenschaften von Graphen zu untersuchen - und vielleicht schneller nach Rom zu gelangen. | Alle diese Probleme lassen sich mit mit Graphen formulieren und mit Graphenalgorithmen lösen. Graphen sind eine wichtige Datenstruktur in der Informatik. In der Talit kümmern wir uns erst einmal darum, wie wir einen Graph effizient beschreiben können; anschliessend schreiben wir Code, um verschiedene Eigenschaften von Graphen zu untersuchen - und vielleicht schneller nach Rom zu gelangen. | ||
| - | |||
| ### Graphen repräsentieren | ### Graphen repräsentieren | ||
| Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen: | Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen: | ||
| + | <figure graph_romis> | ||
| {{: | {{: | ||
| + | < | ||
| + | </ | ||
| Aus was besteht ein Graph? Aus **Knoten** (en. _nodes_ oder _vertices_) und **Kanten** (_edges_). In unserem Fall haben die Kanten **Gewichte**, | Aus was besteht ein Graph? Aus **Knoten** (en. _nodes_ oder _vertices_) und **Kanten** (_edges_). In unserem Fall haben die Kanten **Gewichte**, | ||
| Zeile 111: | Zeile 113: | ||
| </ | </ | ||
| ++++ | ++++ | ||
| - | |||
| ### Tiefensuche | ### Tiefensuche | ||
| Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen: | Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen: | ||
| + | |||
| + | <figure graph_romis2> | ||
| + | [[http:// | ||
| + | < | ||
| + | </ | ||
| - | [[http:// | ||
| #### Aufgabe 2 | #### Aufgabe 2 | ||
| Zeile 255: | Zeile 260: | ||
| ++++ | ++++ | ||
| </ | </ | ||
| - | |||
| #### Aufgabe 4 - Graph Walk | #### Aufgabe 4 - Graph Walk | ||
| Zeile 262: | Zeile 266: | ||
| **Aufgabe**: | **Aufgabe**: | ||
| * Die Ausgabe kann mit `print()` erfolgen oder eine Liste zurückgeben. | * Die Ausgabe kann mit `print()` erfolgen oder eine Liste zurückgeben. | ||
| - | * Herausforderung: | + | * Herausforderung: |
| <nodisp 1> | <nodisp 1> | ||
| Zeile 578: | Zeile 582: | ||
| ++++ | ++++ | ||
| </ | </ | ||
| - | #### Visualisierung | + | ### Visualisierung |
| Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf [[https:// | Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf [[https:// | ||
hof