Algorithmen

Digitalisierung Okt. 18, 2019

ein Gastblog von Richard Krikler und Tobias RIgler.

HTL Rennweg Schüler.


Begriffserklärung:

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen in der Mathematik (Bsp.: Gleichungen lösen) und in der Informatik . Sie werden im Alltag, bei der Arbeit aber auch in der Freizeit verwendet. Sie bekommen eine immer größer werdende Bedeutung. Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.

Eigenschaften:

Algorithmen besitzen die folgenden Eigenschaften:

  • 1. Eindeutigkeit: ein Algorithmus darf keine widersprüchliche Beschreibung haben. Diese muss eindeutig sein.
  • 2. Ausführbarkeit: jeder Einzelschritt muss ausführbar sein.
  • 3. Endlichkeit: die Beschreibung des Algorithmus muss endlich sein.
  • 4. Terminierung: nach endlich vielen Schritten muss der Algorithmus enden und ein Ergebnis liefern.
  • 5. Determiniertheit: der Algorithmus muss bei gleichen Voraussetzungen stets das gleiche Ergebnis liefern.
  • 6. Determinismus: zu jedem Zeitpunkt der Ausführung besteht höchstens eine Möglichkeit der Fortsetzung. Der Folgeschritt ist also eindeutig bestimmt.
Ethik
Abbildung 1: Ethik

Diskussionen über die Einführung einer Algorithmus Ethik. Algorithmen erleichtern einerseits unseren Alltag, andererseits können sie auch unsere Verhaltensweise analysieren. Aus diesem Grund beeinflussen uns Algorithmen. Die Datenfirmen (Google, Facebook, Amazon, …) zeigen uns im Internet die Dinge, die wir sehen wollen bzw. dürfen. Beispielsweise erhalten zwei Personen bei derselben Eingabe in einer Suchmaschine ein ungleiches Ergebnis, da der Suchalgorithmus entscheidet.

Einsatzgebiete:
Abbildung 2: Navigationsgerät

Der Algorithmus ist in der Kommunikation aber auch in vielen technischen Geräten vorhanden.

  • Navigationsgeräte: zeigen immer den kürzesten Weg
  • Schachspiel gegen Computer
  • Rechtschreibkontrolle bei Word, etc.

Mit der Zeit gibt es immer weitere Bereiche, in denen man Algorithmen verwenden kann. Eine neue Dimension der Algorithmen ist der Bereich Big Data und Data Mining (dabei können große Datenmengen nach Mustern und Zusammenhängen ausgewertet werden).

Algorithmen gibt es schon ziemlich lange

Algorithmen sind nichts Neues, bereits im 9. Jahrhundert erklärt der arabische Mathematiker Al Chwarismi (der Namensgeber des Algorithmus) in seinem Buch den Gebrauch indischer Zahlenzeichen.

Unterschied von Algorithmen und Programmen
Abbildung 3: Algorithmus vs. Programm

Die Grenze zwischen einem Programm und einem Algorithmus ist fließend, aber trotzdem gegeben. Dies hängt je nach Definition ab. Der Algorithmus ist die Beschreibung eines Vorgangs oder eines Programms. Ein Programm ist die umgesetzte Version Algorithmus in Quelltext (Sourcecode). Der Algorithmus ist abhängig von seiner Programmiersprache, dabei wird das Programm allgemein beschrieben. Das Programm ist in seiner Programmiersprache umgesetzt. Beispielsweise bei einem Brettspiel ist die Anleitung der Algorithmus und das wirkliche Spielen das Programm.

Algorithmen darstellen
Abbildung 4: Darstellung eines PAP

Zur Darstellung von Algorithmen gibt es verschiedene Möglichkeiten:

  1. PAP (Programmablaufplan): Diese Darstellung wird häufig verwendet. Alle Elemente einer Programmiersprache sind in dieser Form vorhanden (If, Schleifen, Methoden in Formen).
  2. Eine einfache Beschreibung ist ein normaler Text indem ein bestimmter Ablauf mit Regeln beschrieben ist.
  3. Der Pseudocode ist ähnlich wie der Programmlaufplan. Bei dem quasi ein Algorithmus in einfachen Worten programmiert ist.
  4. Das Struktogramm ist auf ähnlich wie der Programmlaufplan, allerdings ist eine Erweiterung bei der Darstellung aufwendig.
  5. Das Programm ist eine Darstellung vom Algorithmus in einer Programmiersprache (z.B.: Java, PHP).

Geschichte des Algorithmus

Algorithmen von damals

Obwohl der Begriff Algorithmus aus Arabien kommt, entstanden die ersten Algorithmen im antiken Griechenland. Algorithmen sind schon sehr lange im Gebrauch. Seit der Entwicklung der Sprache lebten Menschen in größeren Gruppen. Dafür brauchten sie Verhaltensregeln, Gebote, Gesetze. Das sind bereits einfache Algorithmen. Durch die Sprache ist es möglich Verfahren und Fertigkeiten an andere Menschen weiterzugeben. Das sind dann komplexere Algorithmen. Dadurch konnten sich die ersten Berufe bilden. Der Begriff Algorithmus trat zuerst im Rahmen der Mathematik, Logik und Philosophie. Ein Beispiel für einen mathematischen Algorithmus aus dem Altertum ist der Euklidische Algorithmus.

Begriffsherkunft:
Abbildung 5: Al-Khwarizmi

Die Bezeichnung „Algorithmus“ kommt vom Namen Al-Khwarizmi (Muḥammad ibn Mūsā al-Khwārizmī). Al-Khwarizmi lebte von 780 bis 850 n. Chr. und war ein Universitätsprofessor im damaligen Choresmien in Zentralasien. Er beschäftigte sich mit Verfahren zu Lösung von Gleichungen, welche aus heutiger Sicht auch Algorithmen sind. Aus diesem Grund bekamen Algorithmen ihren Namen.

Vorteile bei Nutzung von Algorithmen

Informatik und Mathematik:

Algorithmen sind eines der zentralen Themen der Informatik und Mathematik. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern Algorithmen Computer und andere Maschinen. Ebenfalls werden sie verwendet um komplexe Rechnungen berechnen zu lassen.

Algorithmen-Analyse:

Die Erforschung und Analyse von Algorithmen ist eine Hauptaufgabe der Informatik. Zur Analyse in eine stark formalisierte Form gebracht und mit den Mitteln der formalen Semantik1 untersucht.

Algorithmen heute:
Abbildung 6: Aktienmarkt Frankfurt

Algorithmen sind überall vertreten. Vom Rechtschreib- und Satzbau- Kontrolle in einer Textverarbeitung bin hin zur Analyse von Aktienmärkten. Zusammengefasst sind Algorithmen also heutzutage sehr hilfreich, denn sie nehmen uns viel Arbeit ab indem sie viele kleine Aufgaben übernehmen, welche uns viel wichtige Zeit kosten würde.

Beispiele für Algorithmen

Berühmte Algorithmen:
  • Euklidischer Algorithmus
  • Algorithmus von Trémaux: zeigt ein Vorgehen, um aus einem Labyrinth oder
  • Irrgarten hinauszukommen
  • Google Algorithmus: Dieser Beschreibt wie Google beurteilt welche Seiten relevant sind
  • Kochrezepte
  • Bauanleitungen
Euklidische Algorithmus:

Dieser Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er ist der älteste bekannte Algorithmus (300 v. Chr.) zur Bestimmung des größten gemeinsamen Teilers. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen. Der Algorithmus ist nach dem griechischen Mathematiker Euklid benannt.

Alltagsformen von Algorithmen:
Rechenvorschriften:

Sie sind eine Untergruppe der Algorithmen. Sie beschreiben Handlungsanweisungen in der Mathematik bezüglich Zahlen. Also man rechnet zuerst was in Klammen steht, Punkt vor Strich….

Body-Mass-Index:

Ein weiteres Beispiel wäre der Body-Mass-Index. Hierfür benötigt man Daten über seinen Körper (Gewicht, Körpergröße) und kann sich nach einer gewissen Vorgehensweise ein Ergebnis errechnen. Die Formel um sich seinen Body-Mass-Index zu berechnen lautet:
𝐵𝑀𝐼 = 𝐺𝑒𝑤𝑖𝑐ℎ𝑡 / 𝐾ö𝑟𝑝𝑒𝑟𝑔𝑟öß𝑒^2

Mathematik Beispiel:
Abbildung 7: Mathematik Tafel

In der Mathematik werden des Öfteren Algorithmen benötigt, um Ergebnisse zu berechnen. Ein Beispiel hierzu wäre die Lösung zu einem Gleichungssystem mit drei Gleichungen. Zum Beispiel hat man folgende drei Gleichungen gegeben:

Schritt 1: Man bringt alle Variablen auf eine Seite und alle Zahlen auf die andere Seite
𝐼: 3𝑥 − 7𝑦 + 8𝑧 = 4
𝐼𝐼: 𝑥 + 𝑦 − 3𝑧 = −1
𝐼𝐼𝐼: 2𝑥 + 3𝑦 − 9𝑧 = −4

Schritt 2: Hauptdeterminante berechnen:
𝐷 = 𝑑𝑒𝑡
[1] 3 −7 8 [2] 1 1 −3 [3] 2 3 −9 𝐷 = −27 + 42 + 24 − 16 − (−27) − (−63) = −13

Schritt 3: Einzelne Determinanten (Dx wurde ausführlich gerechnet) berechnen:
𝐷𝑥 = 𝑑𝑒𝑡
[1] 4 −7 8 [2] −1 1 −3 [3] −4 3 −9 𝐷𝑥 = −36 + (−44) + (−24) − (−32) − (−36) − (−63) = −13
𝐷𝑦 = 𝑑𝑒𝑡
[1] 3 4 8 [2] 1 −1 −3 [3] 2 −4 −9 𝐷𝑦 = −13
𝐷𝑧 = 𝑑𝑒𝑡
[1] 3 −7 4 [2] 1 1 −1 [3] 2 3 −4 𝐷𝑧 = −13

Schritt 4: Berechnen der einzelnen Variablen:
𝑥 = 1

Spezielle Algorithmen Beispiele
Algorithmus der über Straftäter entscheidet:

Der Gesetzgeber des US-Bundesstaats Pennsylvania hat vor Jahren entschieden, dass künftig ein Computerprogramm Richtern dabei helfen soll zu entscheiden, welches Strafmaß ein verurteilter Straftäter bekommen soll. Der Algorithmus soll vorhersagen, wie hoch das Risiko ist, dass ein Delinquent in den kommenden drei Jahren wieder straffällig wird und damit eine Gefahr für die öffentliche Sicherheit darstellt. Diese Bewertung fließt seit 2019 in Urteile ein. Dafür nutzt das Programm Variablen wie das Alter des Verurteilten, sein Geschlecht, Informationen zu seinem Verbrechen und zu früheren Verurteilungen bis zurück ins Jugendalter.

Faktoren für Kindeswohl:

In Pittsburgh, Pennsylvania, verwendet für Kinderfürsorge seit 2016 einen Algorithmus, welcher bewertet, ob in Kind misshandelt wird. 14000 Anrufe gehen bei der Fürsorge jedes Jahr wegen Kindermisshandlungen ein. Oft ist es ein Fehlalarm, aber manchmal sind Kinder in Lebensgefahr. In Pittsburgh überprüft der Algorithmus Daten aus zahlreichen Registern. Waren die Eltern des Kindes in medizinischer Behandlung wegen Drogensucht, sind sie vorbestraft oder wurde ihnen schon ein Kind abgenommen. All diese Informationen fließen in eine Risikobewertung ein. Stuft das Programm die Gefahr als hoch ein, muss binnen 24 Stunden die Jugendwohlfahrt die Familie aufsuchen. Andere Fälle werden aussortiert.

Ex-Sträflinge:

In Philadelphia wird ein anderer Algorithmus genutzt, um Straftäter, welche auf Bewährung entlassen werden, zu beurteilen. Das Programm stuft ein, wie hoch die Wahrscheinlichkeit ist, dass ein Ex-Sträfling wieder ein Verbrechen begeht. Je nach Einschätzung wird der Betroffene mehr oder weniger engmaschig überwacht.

Quellenverzeichnis:

  • https://www.infschule.de/algorithmen/algorithmen
  • https://de.wikipedia.org/wiki/Algorithmus
  • https://jobify.net/glossar/algorithmus/
  • https://www.datenschutzbeauftragter-info.de/was-ist-ein-algorithmus-definition-undbeispiele/
  • http://www.mrknowing.com/2014/03/06/was-ist-ein-algorithmus/
  • https://derstandard.at/2000090555530/Formt-der-Algorithmus-unser-Leben

Bildquellen:

  • Abbildung 1: Ethik https://ceai.univie.ac.at/2016/06/11/3580/
  • Abbildung 2: Navigationsgerät https://www.preisvergleich.at/tag/Navigationsgeraete-178268.html
  • Abbildung 3: Algorithmus vs. Programm http://www.mrknowing.com/2014/03/06/was-ist-ein-algorithmus/
  • Abbildung 4: Darstellung eines PAP http://www.mrknowing.com/2014/03/06/was-ist-ein-algorithmus/
  • Abbildung 5: Al-Khwarizmi https://www.pinterest.at/pin/312437292870973674/
  • Abbildung 6: Aktienmarkt Frankfurt https://www.faz.net/aktuell/finanzen/thema/aktienmarkt
  • Abbildung 7: Mathematik Tafel https://unicheck.unicum.de/hochschulranking-informatik-und-mathematik

Tobias Rigler

Member of VUCA-Technical-Team.