Einführung in Graph- und Flussalgorithmen
Feuer löschen mit der Informatik?
Feuer löschen mit der Informatik3
Das haben wir heute vor…
3
Feuer löschen mit der Informatik4
Auf zum ersten Brand
4
Von der Feuerwache zum Feuer
• Kürzesten Weg finden
• Algorithmen mit Struktogrammen
Wasserversorgung herstellen und löschen
• Wasserversorgung optimieren mit Flussnetzwerken
Verletzte Person im Haus suchen und finden
• Suchalgorithmen auf dem Grundriss des Hauses
Feuer löschen mit der Informatik5
Auf zum ersten Brand - Stadtplan
5
Feuer löschen mit der Informatik6
Auf zum ersten Brand – Struktogramm6
Sequenzblock:
Auswahlblock:
Feuer löschen mit der Informatik7
Auf zum ersten Brand – Struktogramm
7
Schleifenblock:
Auswahlblock:
Feuer löschen mit der Informatik8
Auf zum ersten Brand – Abschluss
8
Feuer löschen mit der Informatik9
Was bisher geschah…
9
Von der Feuerwache zum Feuer
• Kürzesten Weg finden
• Algorithmen mit Struktogrammen
Wasserversorgung herstellen und löschen
• Wasserversorgung optimieren mit Flussnetzwerken
Verletzte Person im Haus suchen und finden
• Suchalgorithmen auf dem Grundriss des Hauses
Feuer löschen mit der Informatik10
Erarbeitung Netzwerke
10
Feuer löschen mit der Informatik11
Stichpunkte
11
Feuer löschen mit der Informatik12
Film
Film
12
Feuer löschen mit der Informatik13
Flussnetzwerke
13
Feuer löschen mit der Informatik14
Flussnetzwerke
14
Feuer löschen mit der Informatik15
Arbeitsphase
15
Schreibe alle maximale Kapazitäten in die Schläuche.
Solange es noch einen Weg zu einem Feuer gibt
Suche einen beliebigen Weg von einem Hydranten zu einem Feuer
Suche die niedriste Kapazität deines Weges.
Addiere die niedrigste Kapazität in al le Schläuche des Weges
mit der aktuel len Durchflussmenge.
Feuer löschen mit der Informatik16
Lösungsvorschlag
16
Feuer löschen mit der Informatik17
Notizseite
17
Feuer löschen mit der Informatik18
Was bisher geschah…
18
Von der Feuerwache zum Feuer
• Kürzesten Weg finden
• Algorithmen mit Struktogrammen
Wasserversorgung herstellen und löschen
• Wasserversorgung optimieren mit Flussnetzwerken
Verletzte Person im Haus suchen und finden
• Suchalgorithmen auf dem Grundriss des Hauses
Feuer löschen mit der Informatik19
Personensuche
19
Feuer löschen mit der Informatik20
Personensuche
Ihr seid gefragt! Helft dem Feuerwehrmann die verletzte Person zu finden!
20
Feuer löschen mit der Informatik21
Personensuche
Vergleich der Algorithmen:
21
Algo Gr. 1 Gr. 2 Gr. 3 Gr. 4 Gr. 5 ⌀
BS
TS
EA
BS: BreitensucheTS: TiefensucheEA: Eigener Algorithmus
Feuer löschen mit der Informatik22
Personensuche – Platz für Notizen
22
Feuer löschen mit der Informatik23
Personensuche
23
Von der Feuerwache zum Feuer
• Kürzesten Weg finden
• Algorithmen mit Struktogrammen
Wasserversorgung herstellen und löschen
• Wasserversorgung optimieren mit Flussnetzwerken
Verletzte Person im Haus suchen und finden
• Suchalgorithmen auf dem Grundriss des Hauses
Feuer löschen mit der Informatik24
Personensuche
24
Von der Feuerwache zum Feuer
• Kürzesten Weg finden
• Algorithmen mit Struktogrammen
Wasserversorgung herstellen und löschen
• Wasserversorgung optimieren mit Flussnetzwerken
Verletzte Person im Haus suchen und finden
• Suchalgorithmen auf dem Grundriss des Hauses