Posted on Leave a comment

Algorithmen Teil 2: Wichtige Anwendungsbeispiele

Graph mit gewichteten Kanten

Algorithmen Teil 2: Wichtige Anwendungsbeispiele

Im ersten Teil unseres Artikels zu den Algorithmen haben wir erklärt, was ein Algorithmus ist und welche Rolle dieser in der Informatik spielt. Dabei haben wir bereits ein Beispiel für einen sehr einfachen Algorithmus gegeben. In der modernen Informatik kommen jedoch viele weitere Algorithmen zum Einsatz, die dazu dienen, kompliziertere Probleme zu lösen. Zwei Beispiele hierfür sind der Dijkstra Algorithmus und der Luhn Algorithmus. Diese stellen wir Ihnen jetzt im zweiten Teil des Artikels mit Implementierung in Python vor.

Dijkstra Algorithmus

Der Dijkstra Algorithmus – benannt nach seinem Erfinder, dem niederländischen Informatiker Edsger W. Dijkstra – kommt zum Einsatz, um in einem Graphen den kürzesten Weg zwischen zwei Knoten zu berechnen. Man kann sich dies wie eine Landkarte vorstellen, auf der verschiedene Straßen mit Abzweigungen eingetragen sind. Wenn man von einem Punkt zu einem anderen gelangen will, stehen aufgrund dieser Abzweigungen verschiedene Kombinationen aus unterschiedlichen Teilstrecken zur Auswahl. Der Dijkstra Algorithmus dient dazu, herauszufinden, bei welcher dieser Kombinationen es sich um die kürzeste Verbindung handelt. Tatsächlich stellt die Routenplanung, um von einem Ort zu einem anderen zu gelangen, ein wichtiges Anwendungsgebiet dieses Algorithmus dar.

Python 3 Programmieren für Einsteiger 21.99 € Verfügbar In den Warenkorb

Darstellung der Graphen

Um den Dijkstra Algorithmus anwenden zu können, ist es wichtig, den Aufbau der Graphen zu beachten. Diese bestehen aus Knoten und Kanten. Jeder Punkt, an dem eine Abzweigung vorhanden ist oder bei dem es sich um einen Endpunkt handelt, wird als Knoten in den Graphen eingefügt. Er wird normalerweise als Kreis symbolisiert. Wenn eine Verbindung zu einem anderen Knoten besteht, wird hierfür eine Linie eingefügt. Diese bezeichnen wir als Kante. Die Kanten sind hierbei gewichtet. Das bedeutet, dass sie eine Zahl erhalten, die beispielsweise die Entfernung in Kilometern oder die benötigte Zeit für den entsprechenden Streckenabschnitt angibt.

Abbildung 1: Beispiel für einen Graph mit gewichteten Kanten

Bildquelle:

https://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Weighted_Graph.svg/320px-Weighted_Graph.svg.png

Beschreibung des Dijkstra Algorithmus

Um den Dijkstra Algorithmus zu beschreiben, muss man zunächst festlegen, welche Eigenschaften jeder einzelne Knoten aufweisen muss. Jeder Knoten muss zunächst einen eindeutigen Namen (oder eine Nummer) erhalten, über den er sich identifizieren lässt. Darüber hinaus müssen alle Kanten mit dem jeweiligen Zielknoten und der zugehörigen Entfernung aufgelistet sein. Das entspricht bislang der normalen Gestaltung eines gewichteten Graphen – so wie dies auch in der obigen Abbildung zu sehen ist.

Um den Dijkstra Algorithmus umzusetzen, muss jeder Knoten jedoch noch zwei zusätzliche Werte erhalten – einen Vorgängerknoten und eine Entfernung. Darüber hinaus ist eine Variable notwendig, die aussagt, ob Sie den Knoten bereits besucht haben oder nicht. Daraufhin müssen Sie nach folgendem Muster vorgehen:

1️⃣Weisen Sie allen Knoten für die Distanz den Wert „Unendlich“ zu (Da die meisten Programmiersprachen den Wert „Unendlich“ nicht unterstützen, ist es in der Praxis jedoch meistens notwendig, hierbei die Vorgehensweise anzupassen). Die einzige Ausnahme stellt der Startknoten dar. Da hier die Wegstrecke beginnt, erhält dieser den Wert 0. Bei allen Knoten müssen Sie außerdem vermerken, dass Sie diese noch nicht besucht haben. Ein Vorgänger wird vorerst nicht eingetragen.

2️⃣Wiederholen Sie nun die folgenden Anweisungen so lange, bis Sie alle Knoten des Graphen aufgesucht haben:

✅Wählen Sie aus allen bisher unbesuchten Knoten denjenigen mit der geringsten Entfernung aus. Diesen Knoten bezeichnen wir in den folgenden Anweisungen als Ursprungsknoten.

✅Suchen Sie nun nacheinander alle Nachbarknoten des Ursprungsknotens auf – also diejenigen Knoten, die direkt über eine Kante mit diesem verbunden sind. Führen Sie dabei jeweils die folgenden Aktionen durch:

✅Addieren Sie zur Entfernung, die für den Ursprungsknoten eingetragen ist, den Wert der Kante zum entsprechenden Nachbarknoten.

✅Ersetzen Sie die Entfernung, die bisher beim entsprechenden Nachbarknoten vermerkt ist, durch diese Summe, falls sie geringer als der bisherige Wert ist. Vermerken Sie in diesem Fall auch den Ursprungsknoten als Vorgänger.

✅Halten Sie fest, dass der Ursprungsknoten bereits besucht wurde.

Wenn Sie auf diese Weise alle Knoten des Graphen besucht haben, enthält jeder von ihnen die kürzeste Entfernung zum Startknoten. Über die Vorgänger, die in jedem einzelnen Knoten gespeichert sind, können Sie außerdem den Weg zu diesem zurückverfolgen. Sie sehen, dass Sie mit dem Dijkstra Algorithmus mit vergleichsweise einfachen Anweisungen ein sehr komplexes Problem lösen können.

Auf eine Implementierung des Algorithmus verzichten wir an dieser Stelle. Die Darstellung von Graphen in einem Computerprogramm ist nicht ganz einfach, sodass hierfür viele zusätzliche Erklärungen notwendig wären, die den Rahmen dieses Artikels sprengen würden.

Hacking und IT-Security für Einsteiger 26.99 € Verfügbar In den Warenkorb

Luhn Algorithmus

Ein weiterer Algorithmus, der eine sehr große Bedeutung hat, ist der Luhn Algorithmus. Diesen hat der Informatiker Hans Peter Luhn in den 1950er Jahren entwickelt. Er dient dazu, eine Prüfsumme zu erstellen. Wie bereits im ersten Teil unseres Beitrags zu Algorithmen ausgeführt, dient die Prüfsumme dazu, zu überprüfen, ob der Inhalt eines Dokuments korrekt ist. Der Luhn Algorithmus eignet sich allerdings nur für die Überprüfung von Zahlen. Textdokumente können Sie damit nicht kontrollieren. Außerdem stellt auch eine erfolgreiche Überprüfung mit dem Luhn Algorithmus nicht sicher, dass die Nummer tatsächlich fehlerfrei ist. Allerdings kann er viele häufige Fehler zuverlässig entdecken.

Anwendungsbereiche

Die Anwendungsbeispiele für den Luhn Algorithmus sind sehr vielfältig. Wenn Sie über eine Kreditkarte verfügen, dann tragen Sie eines davon stets bei sich. Bei der letzten Ziffer Ihrer Kreditkartennummer handelt es sich nämlich um eine Prüfsumme. Diese wird nach dem Luhn Algorithmus berechnet. Auch die Deutsche Bahn nutzt eine Prüfsumme auf Basis des Luhn Algorithmus für die Nummerierung ihrer Lokomotiven und Triebwagen. Viele Banken verwenden ihn auch für ihre Kontonummern. Darüber hinaus gibt es noch unzählige weitere Anwendungsbeispiele, bei denen dieser Algorithmus zum Einsatz kommt.

Prüfsumme berechnen

Um den Luhn Algorithmus anzuwenden, sind zwei Teilaufgaben zu erfüllen: Sie müssen bei einer gegebenen Zahl die Prüfsumme berechnen und Sie müssen bei einer Nummer, bei der die Prüfsumme bereits enthalten ist, kontrollieren, ob der Wert korrekt ist. Zunächst stellen wir Ihnen vor, wie Sie die Prüfsummen ermitteln:

1️⃣Setzen Sie die Prüfsumme auf 0.

2️⃣Wiederholen Sie die folgenden Anweisungen für alle Ziffern. Beginnen Sie dabei mit der letzten Ziffer und wählen Sie im nächsten Schritt immer die Ziffer, an der nächsthöheren Stelle:

✅Multiplizieren Sie den Wert der Ziffer mit zwei, falls deren Position – von hinten beginnend – ungerade ist.

✅Ziehen Sie den Wert 9 ab, falls diese Zahl größer als 9 ist.

✅Addieren Sie den Wert (also je nach Position entweder die ursprüngliche Ziffer oder den bearbeiteten Wert) zur bisherigen Prüfsumme.

3️⃣Subtrahieren Sie die letzte Ziffer der Prüfsumme von der Zahl 10 und legen Sie das Ergebnis als endgültige Prüfsumme fest.

Nummern kontrollieren

Der zweite Teil des Luhn Algorithmus besteht darin, zu kontrollieren, ob eine Nummer korrekt ist. Dabei gehen wir davon aus, dass die letzte Ziffer der Nummer die Prüfsumme darstellt. Der eigentliche Wert besteht daher nur aus den übrigen Ziffern. In vielen Anwendungsbeispielen wird die Prüfsumme jedoch auch nach einem Bindestrich angegeben.  Für unser Anwendungsbeispiel verwenden wir die Nummer jedoch als Ganzes – also inklusive der Prüfsumme am Schluss. Bei Nummern, bei denen diese mit Bindestrich angegeben ist, müssen Sie diesen einfach entfernen und die Zahl zusammenschreiben (bei der Nummer 152323-3 müssten Sie dann beispielsweise die Zahl 1523233 überprüfen).

Der Algorithmus für die Überprüfung sieht wie folgt aus:

1️⃣Setzen Sie die Prüfsumme auf 0.

2️⃣Wiederholen Sie die folgenden Anweisungen für alle Ziffern. Beginnen Sie dabei mit der letzten Ziffer und wählen Sie im nächsten Schritt immer die Ziffer, an der nächsthöheren Stelle:

✅Multiplizieren Sie den Wert der Ziffer mit zwei, falls deren Position – von hinten beginnend – gerade ist.

✅Ziehen Sie den Wert 9 ab, falls diese Zahl größer als 9 ist.

✅Addieren Sie den Wert zur bisherigen Prüfsumme.

3️⃣Wenn die letzte Ziffer der Prüfsumme 0 ist, ist die Zahl korrekt. In allen anderen Fällen ist ein Fehler aufgetreten.

Wenn Sie die oben genannte Zahl 152323-3 überprüfen, erhalten Sie beispielsweise 21 als Ergebnis. Sie letzte Ziffer ist daher ungleich 0. Das bedeutet, dass diese Nummer nicht korrekt ist. Sollten Sie mit diesem Algorithmus jedoch Ihre Kreditkartennummer überprüfen, ist die letzte Ziffer der Prüfsumme stets eine 0.

Implementierungsbeispiel in Python

Um aufzuzeigen, wie Sie einen solchen Algorithmus in die Praxis umsetzen können, haben wir zwei kleine Python-Programme entwickelt. Das erste Beispiel berechnet die Prüfsumme. Dabei richtet es sich im Prinzip genau am obigen Algorithmus aus. Die einzige Anpassung, die wir hierbei vorgenommen haben, bezieht sich auf die Auswahl der Ziffern. In einem Computerprogramm ist es nicht ganz so einfach, auf eine beliebige Ziffer einer Zahl zuzugreifen. Deshalb berechnen wir in jedem Durchgang die letzte Ziffer der Zahl mit dem Modulo-Operator. Anschließend passen wir die Zahl so an, dass wir diese letzte Ziffer entfernen. So können wir im nächsten Schritt wieder die letzte Ziffer heranziehen:

zahl = int(input("Geben Sie eine Zahl ein: "))
summe = 0
ungerade = True
while zahl >= 1:
	ziffer = zahl % 10
	if ungerade:
		ziffer = ziffer * 2
	if ziffer > 9:
		ziffer -= 9
	summe += ziffer
	ungerade = not ungerade
	zahl = (zahl - zahl % 10) / 10
print("Prüfsumme:", int(10 - summe % 10))
Abbildung 2: Die Berechnung der Prüfsumme nach dem Luhn Algorithmus
Python Kompendium 26.99 € Verfügbar In den Warenkorb

Das zweite Beispielprogramm überprüft, ob eine Nummer korrekt ist. Dabei setzt es den zweiten Teil des Luhn Algorithmus um:

zahl = int(input("Geben Sie eine Zahl ein: "))
summe = 0
ungerade = False
while zahl >= 1:
	ziffer = zahl % 10
	if ungerade:
		ziffer = ziffer * 2
	if ziffer > 9:
		ziffer -= 9
	summe += ziffer
	ungerade = not ungerade
	zahl = (zahl - zahl % 10) / 10
if int(summe % 10) == 0:
	print("Die Nummer ist korrekt.")
else:
	print("Die Nummer weist einen Fehler auf.")
Abbildung 3: Die Überprüfung mit einer korrekten und mit einer falschen Nummer

Mit diesem Programm können Sie nun beispielsweise Ihre Kreditkartennummer überprüfen. Diese wird immer zu einem korrekten Ergebnis führen. Wenn Sie jedoch eine falsche Ziffer eingeben, wird das Programm diesen Fehler (fast immer) bemerken.

Welche Fehler erkennt der Luhn Algorithmus?

Ein erster Ansatz, um die Korrektheit einer Nummer zu ermitteln, bestand darin, ihre Quersumme zu bilden – also einfach alle Ziffern zusammenzuzählen. Der Luhn Algorithmus verfolgt einen ganz ähnlichen Ansatz. Ein erster Unterschied besteht jedoch darin, dass er nur die letzte Ziffer der Quersumme zu verwendet. Das sorgt für eine einheitliche Darstellung, bei der die letzte Ziffer der Nummer stets die Prüfsumme darstellt.

Darüber hinaus kann die einfache Quersumme keine Zahlendreher erkennen. Die Nummern 1423 und 1243 haben beispielsweise genau die gleiche Quersumme. Indem der Luhn Algorithmus jede zweite Zahl verdoppelt, führt hierbei ein solcher Zahlendreher jedoch zu einem anderen Ergebnis. Auf diese Weise kann er deutlich mehr Fehler erkennen als die normale Quersumme. Die einzige Ausnahme stellen hierbei Zahlendreher mit den Ziffern 0 und 9 dar.

Da die Verdopplung der Zahl 0 ebenfalls 0 ergibt, spielt die Position hierbei keine Rolle. Bei der Verdopplung der Zahl 9 ist das Ergebnis 18. Da dieses größer als 9 ist, müssen wir hier 9 abziehen, sodass wir als Ergebnis wieder die ursprüngliche Zahl erhalten. Daher spielt auch hierbei die Verdopplung keine Rolle. Das führt dazu, dass beispielsweise die Zahlen 39024 und 30924 bei der Überprüfung genau zum gleichen Ergebnis kommen. Das stellt eine gewisse Schwäche dieses Algorithmus dar. Da solche Fälle jedoch nur selten auftreten, hat er sich dennoch als praxistauglich erwiesen. 

Selbstverständlich gibt es noch viele weitere Fehler, die der Luhn Algorithmus nicht erkennt – beispielsweise wenn man bei zwei Ziffern, die sich beide an einer geraden oder ungeraden Position befinden, eine entgegengesetzte Änderung vornimmt. Wenn wir beispielsweise von der Zahl 415273 ausgehen, könnten wir bei der ersten Ziffer den Wert 2 addieren und an bei der dritten Ziffer den gleichen Wert abziehen: 613273. Auch das führt zum gleichen Ergebnis. Solche Veränderungen sind jedoch normalerweise auf eine bewusste Manipulation zurückzuführen. Der Luhn Algorithmus ist jedoch nicht dafür vorgesehen, diese zu erkennen. Er dient lediglich dazu, Übertragungsfehler zu erkennen. Zu der Zeit, zu der er entwickelt wurde, wurden viele Nummern noch händisch übertragen. Dabei kam es häufig zu ungewollten Fehlern. Der Luhn Algorithmus konnte diese jedoch stark reduzieren.

Algorithmen haben eine große Bedeutung

Diese beiden Beispiele haben gezeigt, welch enorme Bedeutung Algorithmen bei alltäglichen Anwendungen haben. Dabei handelt es sich jedoch nur um zwei recht einfache Beispiele. Wenn Sie beispielsweise ihr Smartphone oder einen Computer verwenden, werden dabei meistens viele Hundert verschiedene Algorithmen ausgeführt, die häufig wesentlich komplizierter sind. Auch wirtschaftlich haben Algorithmen eine große Bedeutung. Manche von ihnen sind patentiert und ihnen wird ein Wert von vielen Millionen Euro beigemessen. Aus diesen Gründen ist es sehr lohnenswert, Algorithmen zu verstehen und sie später auch selbst zu entwickeln.

Ähnliche Produkte

Schreibe einen Kommentar