Kurt Mehlhorn

Schnellste Wege und Navigationssysteme

  • PRO
  • mandatory workload 3 h 30 min
  • language Deutsch
  • topics Informatik
  • purchase available 59
  • free certificate included mit Zertifikat

Worum geht es im Kurs?

Als Jugendlicher bin ich oft mit meinen Eltern in Urlaub gefahren. Mein Vater fuhr gerne Auto und mir oblag die Planung der Touren. Ich studierte Landkarten und Reiseführer und war mit einer anspruchsvollen Aufgabe gut beschäftigt.

Jetzt mache ich mir kaum noch Gedanken darüber, wie ich am besten von A nach B komme. Ich lasse mein Navigationssystem diese Aufgabe für mich erledigen.

Nur für Fahrradtouren bin ich sorgfältiger, weil neben der Entfernung auch die Höhenunterschiede eine wesentliche Rolle spielen.

Wie findet mein Navi in wenigen Sekunden den schnellsten Weg von meinem Haus zum Haus der Familie meiner Tochter in der Nähe von Stuttgart?
Wie beantwortet Google Maps Tausende solcher Anfragen parallel in Bruchteilen einer Sekunde?

Wir lernen zunächst Graphen als Abstraktion von Landkarten kennen.
Die wichtigste Komponente eines Navis ist ein effizienter Algorithmus zur Berechnung kürzester oder schnellster Wege. Wir lernen einen ersten solchen Algorithmus kennen und beobachten, dass seine Laufzeit im schlimmsten Fall exponentiell mit der Größe des zu durchsuchenden Graphen wächst.
Exponentielles Wachstum ist ein Killer: Auch die schnellsten Rechner könnten mit diesem Algorithmus niemals den schnellsten Weg zu meiner Tochter finden.

Edsger Dijkstra fand 1957 einen sehr viel besseren Algorithmus, dessen Laufzeit im Wesentlichen linear in der Größe des Graphen wächst. Dieser Algorithmus ist jetzt überall im Einsatz und Sie werden ihn verstehen.

Ich zeige Ihnen auch, wie Computer mit komplexen Strukturen wie Graphen umgehen können.

Inhalte:

  1. Einführung: kürzeste und schnellste Wege, Navigationssysteme, Landkarten und Graphen
  2. Der Grundalgorithmus zur Bestimmung schnellster Wege: Prinzip, Laufzeit, Korrektheit
  3. Dijkstras Algorithmus zur Bestimmung schnellster Wege: Funktionsweise, Implementierung und Darstellung vom Graphen in einem Rechner, Korrektheit
  4. Navigationssysteme

Bestandteile des Kurses:

  1. Videos
  2. Quizzes
  3. Aufgaben mit Lösungen
  4. Logbuchaufgaben
  5. Teilnahmebescheinigung

Danksagung

Ich danke meinen (ehemaligen und aktuellen) Mitarbeitern, mit deren Hilfe ich die Vorlesung Ideen und Konzepte der Informatik an der Universität des Saarlandes entwickelt habe:

Dr. Konstantinos Panagiotou, Dr. Adrian Neumann, Dr. Antonios Antoniadis, Dr. Corinna Coupette und Angelina Mansion.

Dieser Kurs und die gesamte Kursreihe bauen auf dieser Vorlesung auf.

Kursinhalt

Kapitel 1
Kürzeste Wege, Einführung
unit_video icon
Einführung
10 min
Vorschau
pdf icon
Negative Kanten und negative Zyklen
15 min
Kapitel 2
Grundalgorithmus
unit_video icon
Grundalgorithmus
15 min
unit_video icon
Grundalgorithmus-Laufzeit
15 min
unit_video icon
Grundalgorithmus-Korrektheit
15 min
Kapitel 3
Algorithmus von Dijkstra
unit_video icon
Algorithmus
25 min
unit_video icon
Implementierung und Laufzeit
15 min
unit_video icon
Korrektheit
15 min
image icon
Dijkstra-Algorithmus
40 min
pdf icon
Sinnhaftigkeit negativer Kantenkosten
30 min
Kapitel 4
Navigationssysteme
unit_video icon
Navigationssysteme
15 min

Was werden Sie lernen?

  1. Formulierung der Aufgabe: Berechnung schnellster bzw. kürzester Wege
  2. Abstraktion: Von der Landkarte zum Graphen
  3. Herleitung eines einfachen Algorithmus
  4. Korrektheit eines einfachen Algorithmus
  5. Laufzeitanalyse des einfachen Algorithmus. Exponentielle Laufzeit ist ein Killer
  6. Herleitung des raffinierteren Algorithmus
  7. Laufzeit und Korrektheit eines anspruchsvolleren Algorithmus
  8. Anwendung in Navigationssystemen

An wen richtet sich der Kurs?

Jede und jeder, die/der verstehen will, wie ihr bzw. sein Navigationssystem funktioniert.

Lehrende

  • PRO
  • mandatory workload 3 h 30 min
  • language Deutsch
  • topics Informatik
  • purchase available 59
  • free certificate included mit Zertifikat
individual track icon

Einzelpersonen

Kurszugang inklusive Zertifikat

Beinhaltet den Zugang zum Kurs und ein Teilnahmezertifikat als Download.

59 €*
organisation track icon

Organisationen & Gruppen

Bei Interesse am Kauf mehrfacher Kurszugänge für Ihre Angestellten oder eine Gruppe.

(Preis variiert in Abhängigkeit von der Anzahl der Teilnehmer)

Weiter zum Kauf
* Unsere Preise beinhalten MwSt.

Haben Sie Fragen?

Wir sind bereit, Ihnen zu helfen!

Plase choose your case and reach out to us

For corporate clients - B2B form

For questions regarding the course contents

Verwandte Kurse & Sets

Schnellste Wege und Navigationssysteme

Nicht überzeugt? Dann werfen Sie einen Blick auf unsere