Vorkurs Informatik WiSe 16/17 - Konzepte der …...Was steckt dahinter? – Brute-Force-Methode # Knoten Schritte 3 4 4 18 5 96 6 600 7 4.320 8 35.280 9 322.560 10 3.265.920 15 1.220.496.076.800

Vorkurs Informatik WiSe 16/17Konzepte der Informatik

Dr. Werner Struckmann / Stephan Mielke, Jakob Garbe, 12.10.2016

Technische Universität Braunschweig, IPS

Institut für Programmierungund Reaktive Systeme

Inhaltsverzeichnis

Schilda-Rallye

Was steckt dahinter?

Darstellung von Graphen

Zusammenfassung Datenstrukturen

12.10.2016 Dr. Werner Struckmann / Stephan Mielke, Jakob Garbe Seite 2Vorkurs Informatik WiSe 16/17 Institut für Programmierung

und Reaktive Systeme

Überblick

Schilda-Rallye






Schilda-Rallye – Stadtplan

Der Stadtrat hat vor kurzem beschlossen, alle Straßen zuEinbahnstraßen zu machen.



Schilda-Rallye – Problemstellung

Die Fahrzeuge von Schilda-Taxiwarten auf den Hotels Adler undGozo sowie auf dem Parkplatz derPension Kapitol:

Aufgrund der neuenVerkehrsführung benötigen dieFahrer einen Plan, wie sie auf demkürzesten Weg von ihrem Standortzu allen anderen Hotels kommen.

Eine Entfernungstabelle ist auchzur Berechnung der neuen Tarifenotwendig.



Schilda-Rallye – Markierung der Kreuzungen

Schilda-Rallye – Abstrakte Stadtplan

Schilda-Rallye – Erste Schritt

Schilda-Rallye – Fortsetzung (1)





















Schilda-Rallye – Ende

Schilda-Rallye – Entfernungstabelle

Hotel Entfernung (km)Adler 0,0Bogart 11,5Club 9,7Doge 8,1Emilio 3,7Fromm 6,5Gozo 6,2Holunder 7,6Iliona 11,4Jorge 9,8Kapitol 10,7Lundt 7,9



Überblick

Schilda-Rallye






Was steckt dahinter? – Einleitung

Die besprochenen Probleme gehören in das Umfeld der sogenannten Graphenalgorithmen.Ein Graph besteht hierbei aus einer Menge von Knoten und einerMenge von Kanten, die zwischen den Knoten verlaufen.Die Knoten (Vertices) werden oft als Kreise und die Kanten (Edges)als Linien oder Pfeile dazwischen dargestellt.Man unterscheidet ungerichtete Graphen (ohne Pfeil), bei denen dieVerbindung zweier Konten in beide Richtungen geht und gerichteteGraphen (mit Pfeil).Wozu ist aber ein Graph gut?Wie andere Modelle in der Informatik kann er ein Ausschnitt derWirklichkeit modellieren, um diese einfacher zu verstehen und zuanalysieren.



Was steckt dahinter? – Anforderungen

Aufgrund der vielfältigen Anwendungen gibt es auch eine Menge vonAlgorithmen auf Graphen. Der Dijkstra-Algorithmus ist hier ein sehrbekannter Vertreter.

Was zeichnet einen guten Algorithmus aus?

Er muss zuerst einmal die gestellte Aufgabe lösen.

Wichtiges Kriterium ist außerdem, dass dieser die Aufgabe möglichstschnell löst und auch bei großen Problemen nicht in die Knie geht.



Was steckt dahinter? – Zeitbedarfs

Wir betrachten wie stark der Zeitbedarf mit der Problemgrößeansteigt.

Am Beispiel der Landkarte kann dies sehr gut demonstriert werden.

Eine Problemgröße ist zum Beispiel die Anzahl der Städte auf derLandkarte.

Betrachten wir jetzt noch einmal den Brute-Force-Ansatz zurBestimmung des kürzesten Weges:

„Bestimme alle möglichen Wege vom Start zum Ziel und suche davonden kürzesten.“



Was steckt dahinter? – Brute-Force-Methode

Im schlechtesten Fall müssen also alle von einem Punktausgehenden Wege bestimmt werden.

Außerdem sind im schlechtesten Fall alle Knoten mit allen anderenKnoten verbunden (vollständiger Graph).

Für drei Knoten ist es noch kein Problem, die Anzahl möglicherWege vom Startpunkt S aus zu bestimmen.




Mit jedem zusätzlichen Knoten steigt die Anzahl der möglichenWege stark an. Zeichnerisch die Lösung zu bestimmen ist dann nichtmehr praktikabel.Man kann die Anzahl der Knoten auch rechnerisch bestimmen.Für den Graphen mit vier Knoten gilt, dass man ihn aus zweiKomponenten zusammensetzen kann: ein einzelner Knoten S plusein Graph mit drei Knoten.Da der bekannte Graph drei Knoten besitzt, kann vom neuen KnotenS auf drei Arten ein Weg zum bekannten Graphen begonnen werden.




Im 3er-Graphen wird dann auf die bereits ermittelte Weise ein Weggesucht.Daher ist die Anzahl möglicher Wege im 4er-Graphen 3 · 2 = 6.Für einen 5er-Graphen gibt es vier Möglichkeiten, Wege vom neuenKnoten zum 4er-Graphen zu beginnen. Die Anzahl der Wege beträgtdaher 4 · 6 = 24.Auf diese Weise kann man ableiten, dass in einem vollständigenGraphen mit n Knoten (n − 1)! verschiedene Wege von einemgesetzten Startpunkt ausgehen.Da für jeden der Wege n − 1 Streckenabschnitte eingerechnetwerden müssen, bedarf es für die Brute-Force-Methode ungefähr(n − 1)(n − 1)! Berechnungen, um den kürzesten Weg zu finden.




# Knoten Schritte3 44 185 966 6007 4.3208 35.2809 322.56010 3.265.92015 1.220.496.076.80020 2.311.256.907.767.808.00050 29805811337679110482740356002743473467490088737581301760000000000




Für 100 Knoten sind im schlimmsten Fall bereits

923929532895047111548822464677040334858088085817378052539070342562654239932976164552852049336394953103391160941618951520668673358807695360000000000000000000000

Berechnungen nötig.

Wenn auch nur alle 12.903 Gemeinden Deutschlands als Knoten in dieSuche einbezogen werden, sind 9, 88 · 1047438 Berechnungen nötig.



Überblick

Schilda-Rallye






Darstellung von Graphen – Überlegung

Computer kennt keine graphische Darstellung

Insbesondere keine Kanten und Knoten

Abstraktion notwendig

Überführung der graphischen Darstellung in eine Datenstruktur



Darstellung von Graphen – Adjazenzmatrix

Idee für ungerichtete Graphen:Sei n die Anzahl der Knoten.Benutze eine n × n Matrix.Wenn eine Kante zwischen Knoten a und b existiert, dann trage inZeile a und Spalte b eine 1 ein, andernfalls eine 0.Verfahre ebenso mit Zeile b und Spalte a.

0 1 1 0 11 0 0 1 01 0 0 1 10 1 1 0 11 0 1 1 0




Beispiel für ungerichteten Graphen mit Gewichten:

Symmetrie bleibt erhalten.

Anstelle von einer 1 trage das Kantengewicht ein.

0 7 8 0 57 0 0 1 08 0 0 2 60 1 2 0 95 0 6 9 0




Beispiel für gerichteten Graphen mit Gewichten:

Keine Symmetrie mehr.

0 7 8 0 50 0 0 0 00 0 0 2 00 1 0 0 90 0 6 0 0




Anstatt einer Matrix wird eine verkettete Liste benutzt.Besonders geeignet für gerichtete GraphenDie Basisstruktur bildet die Liste aller Knoten.Für jeden Knoten wird eine Liste der Nachfolger entlang gerichteterKanten abgespeichert.



Darstellung von Graphen – Inzidenzmatrix

Anstatt Verbindungen von Knoten zu Knoten darzustellen, wird hier dieNachbarschaft der Kanten zu den Knoten dargestellt.Jede Spalte enthält 2 von Null verschiedene Einträge

e1 e2 e3 e4 e5 e6 e71 1 1 0 0 0 0 1-1 0 0 0 -1 0 0 20 -1 0 1 0 0 -1 30 0 0 -1 1 1 0 40 0 -1 0 0 -1 1 5



Überblick

Schilda-Rallye







Listen

Array’s (zusammenhängender Speicher)

(doppelt) Verkettete Listen

Stapel



Zusammenfassung DatenstrukturenGraphen

Bäume



Zusammenfassung

Graphentheorie

Brute-Force-Methode vs. Greedy-Algorithmen


Datenstrukturen (Zusammenfassung)

Morgen:

Codierungen



Danke

Vielen Dank für Ihre Aufmerksamkeit!



Documents

Vorkurs Informatik WiSe 16/17 - Konzepte der …...Was steckt dahinter? – Brute-Force-Methode # Knoten Schritte 3 4 4 18 5 96 6 600 7 4.320 8 35.280 9 322.560 10 3.265.920 15 1.220.496.076.800