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