StartseiteMathlog

Wie funktioniert ein Algorithmus?

Von / 5. Februar 2021 / 15 Kommentare
Mehr

Heute im neuen SPIEGEL:

Dem Wirtschaftsinformatiker Markus mussten wir einmal sogar erklären, wie ein Algorithmus funktioniert.

(Wirecard-Manager Jörn Leogrande über seinen Chef Markus Braun)

Da würde mich ja mal die Antwort interessieren. Bei Google erhält man auf die Frage „Wie funktioniert ein Algorithmus?“ die Antwort „Ein Algorithmus ist ein schrittweises Verfahren zum Lösen eines Problems durch ein spezielles Regelwerk. Algorithmen bestehen aus einer Folge von elementaren Anweisungen (z. B. Grundrechenarten, logischen Operationen), die nach endlich vielen Schritten die Lösung des gestellten Problems liefern.“ Aber ob es das war, was der Chef wissen wollte?

Mehr

Kommentare (15)

  1. #1 rolak
    5. Februar 2021

    was?

    Zwei Varianten zum Wochenende:
    1: Jörn hat seinen Chef falsch verstanden, der einen anderen falsch verstanden hatte und daraufhin analog zu ‘Wie ging nochmal Rumba?’ eigentlich gefragt hatte ‘Wie funktioniert ein AlgenRhythmus?’
    2: Der Chef träumte von etwas in der Art ‘Wir starten ihn, er ersetzt drei Mitarbeiter, wir machen noch mehr Kohle’.

  2. #2 Lercherl
    6. Februar 2021

    Und ich dachte, dieser hier wäre der originale Algorithmus? Jedenfalls hat Heinz Zemanek als IBM Fellow sich mit diesem Algorithmus beschäftigt, auch wenn seine Chefs sich vielleicht was anderes vorgestellt haben. Er ging auf Spurensuche nach Usbekistan, wurde dort ungeheuer populär, trat im Fernsehen auf und wurde zum “Held von Usbekistan” ernannt.

  3. #3 rolak
    6. Februar 2021

    dieser hier

    Ja schon, sicher.
    Aber das ist derart lange her, der funktioniert doch gar nicht mehr.

  4. #4 wereatheist
    Weit westlich von Usbekistan
    6. Februar 2021

    Ich dachte immer, der Ur-Algorithmus ist der Euklidsche.

  5. #5 user unknown
    https://demystifikation.wordpress.com/
    6. Februar 2021

    Ich würde ein Verfahren, von dem man nicht weiß, ob es wirklich zu einem Ende führt, wie einem Standardweg zur Berechnung der Collatz-Conjecture*), auch von einem Algorithmus sprechen.

    Für die, diese nicht kennen: Für eine Zahl x nimmt man, wenn x gerade ist, x/2 als nächstes Element. Ist sie ungerade, nimmt man 3x+1.

    Man sieht sofort, dass 2er-Potenzen wie 16 unweigerlich zur 1 führen (8, 4, 2, 1). Ungerade Zahlen werden qua 3x+1 im nächsten Schritt immer gerade und im übernächsten eventuell wieder ungerade. Teils wachsen die Zahlen gehörig an, aber für alle getesteten Zahlen endete die Folge bislang mit 1.

    Die 27 ist beispielsweise eine relativ kleine Eingabe, die sich gehörig wehrt, gegen 1 zu konvergieren. Die Folge erreicht zwischenzeitlich fast den Wert 10.000 aber dann geht es doch der 1 entgegen.

    Solche Fragen sind im Kontext des Halteproblems interessant, einer Problemstellung, für die Alan Turing beweisen konnte, dass es keinen Algorithmus gibt, der für alle Probleme und alle Eingaben entscheiden kann, ob sie zu einer Lösung führen.

    “Wie funktioniert ein Algorithmus” und “Was ist ein Algorithmus” sind auch m.E. keine identischen Fragen.

    Ich würde sagen, dass ein Algorithmus ein Verfahren ist, für das man für jeden Schritt der Verarbeitung deterministisch bestimmen kann, was der nächste Schritt ist. Ob er zu einem Halt führen wird, in eine Endlosrekursion gerät, oder immer weiter läuft mit ungewissem Ende ist nicht entscheidend – in den meisten Fällen erwarten wir aber, dass er in endlicher Zeit zu einem Ergebnis führt.

    Es gibt aber auch sehr populäre Endlosrekursionen, die gewollt sind, nämlich die Eventloop unseres Betriebssystems, die ewig auf neuen Input wartet. Der Input kann der Befehl sein, die Endlosschleife zu verlassen und runterzufahren, oder ein Stromausfall stoppt die Veranstaltung.
    Der Vollständigkeit seien auch Zufallszahlengeneratoren erwähnt und deren verbreitete Halbbrüder, die Pseudozufallszahlengeneratoren. Letztere erzeugen die Zahlen deterministisch, aber das Muster, nach dem sie diese erzeugen, ist so komplex, dass man als Mensch ohne Hilfsmittel keine Chance hat, die nächste vorherzusagen (außer durch Glück).
    Echte Zufallszahlengeneratoren können von nicht vorhersehbaren Ereignissen abhängig sein, etwa kleinsten Temperaturschwankungen oder radioaktivem Zerfall. Das ist dann aber wieder ein von außen kommender Input, wie eine Tastatur- oder Mauseingabe. Der Input ist hier unvorhersehbar, aber das Verfahren, nach dem der Algorithmus arbeitet, ist ansonsten bestimmt.

    Auf der Ebene der Logik könnte ich beschreiben, wie ein Algorithmus funktioniert, aber auf der elektrotechnischen Ebene halte ich mich lieber bedeckt. Irgendwas mit Strom, wahrscheinlich Spannung, aber auch Frequenzen kommen in Betracht oder auch Lichtimpulse.

    Es gibt aber auch rein analoge Algorithmen, etwa zur Bestimmung des längsten Pfads in einem Graphen.

  6. #6 hwied
    6. Februar 2021

    userunknown
    Die Collatz -Folge ist auch philosophisch von Bedeutung.
    Schafft sie doch einen Ereignisbaum, der vorwärts gerechnet deterministisch ist, rückwärts sich aber immer verzweigt und damit undeterministisch ist.

    Der Materialismus, der von der determinierten Welt träumt, der hat damit ausgeträumt. Der Geist in Form der Collatzfolge ist stärker.

  7. #7 Karl-Heinz
    Graz
    7. Februar 2021

    Was sind Algorithmen?
    Ein Algorithmus ist eine Folge von Anweisungen zur Lösung eines Problems. Diese Folge
    muss folgende fünf Bedingungen erfüllen:
    1. Allgemeingültigkeit
    Die Anweisungen besitzen Gültigkeit für die Lösung einer ganzen Problemklasse, nicht
    nur für ein Einzelproblem.
    2. Ausführbarkeit
    Die Anweisungen müssen verständlich formuliert sein für den Befehlsempfänger (Mensch
    oder Maschine) und für diesen ausführbar sein.
    3. Eindeutigkeit
    An jeder Stelle muss der Ablauf der Anweisungen eindeutig sein.
    4. Endlichkeit
    Die Beschreibung der Anweisungsfolge muss in einem endlichen Text möglich sein.
    5. Terminiertheit
    Nach endlich vielen Schritten liefert die Anweisungsfolge eine Lösung des gestellten
    Problems.

  8. #8 Joseph Kuhn
    7. Februar 2021

    @ Karl-Heinz:

    Zwei Fragen: Warum muss Bedingung 1 erfüllt sein? Und warum muss ein Algorithmus ein Problem in endlich vielen Schritten lösen (Bedingung 5)? Demnäch wäre eine Rechenvorschrift, die die Hinterkommastellen von Pi oder von 1/3 auflistet, kein Algorithmus? Oder habe ich nur den springenden Punkt nicht verstanden?

  9. #9 Karl-Heinz
    Graz
    7. Februar 2021

    @Joseph Kuhn

    Zu 1. Allgemeingültigkeit
    Beispiel:
    Jemand fragt mich, ob ich den Verkaufspreis für den Artikel
    “6(mehr)-kt. Kappe Edelstahl V4A IG 1/2 Zoll”
    ausrechnen könnte.

    geg.: Listenpreis: 0,66 €, Rabatt 30% und Aufschlag 160%.
    Ich berechne den VK wie folgt: Verkaufspreis (VK) = 0,66 € ⋅ (1-0,3) ⋅ (1+1,6) = 1,20 €.

    Das wäre jetzt ein Einzelproblem.

    Meistens sind die Fragesteller mit dieser Antwort nicht zufrieden und fordern mehr Variabilität.

    Für die Problemklasse: Verkaufspreis aus Listenpreis, Rabatt und Aufschlag zu berechnen
    würde der Algorithmus wie folgt aussehen:
    VK = Listenpreis ⋅ (1-Rabatt) ⋅ (1+Aufschlag)
    wobei gilt:
    Rabatt = Rabatt[in %]/[100%]
    Aufschlag = Aufschlag[in %] / [100%]

  10. #10 Karl-Heinz
    Graz
    7. Februar 2021

    @Joseph Kuhn

    Zu 5. Terminiertheit
    Wenn man von einem Algorithmus spricht, welches Pi berechnet, meint man im eigentlichen Sinne einen Algorithmus, das Pi auf n signifikante Stellen genau berechnet.

    Je größer die Anzahl der signifikanten Nachkommastellen ist, umso mehr Ressourcen (Zeit und Ausdruck) wird für die Ausführung des Algorithmus benötigt.

    Ich würde mich hüten zu behaupten, einen Algorithmus zu besitzen, welches Pi auf unendlich viele Stellen berechnet. 😉

    PS: In Pi ist ein Code enthalten, der alle bis jetzt geschriebene Bücher enthält. Und es kommt noch schlimmer, denn auch alle jemals in Zukunft geschriebene Bücher sind als Code in Pi enthalten. Pi ist eine transzendente Zahl.

  11. #11 rolak
    8. Februar 2021

    5. Terminiertheit

    Wenn Du (Laufzeit)Terminiertheit als generelle Eigenschaft eines Algorithmus voraussetzt, hast Du generell keine Möglichkeit, zu entscheiden, was ein Algorithmus ist und was nicht.

    In vielen Fällen ist insbesondere ‘spontane’ Terminiertheit sogar unerwünscht…

  12. #12 hwied
    8. Februar 2021

    Karl-Heinz denkt mehr an Computeralgorithmen. Im Algorithmus kann man allerdings eine Abbruchbedingung vorsehen, entweder zeitlich oder durch Mausklick.
    Die Allgemeingültigkeit zielt mehr auf die Struktur eines Algorithmus . Ein Algorithmus ist nur ein anderer Name für ein Programm mit einer bestimmten Aufgabe.

  13. #13 Karl-Heinz
    Graz
    8. Februar 2021

    @rolak, hwied und Joseph Kuhn

    Ich habe die oben genannten fünf Punkte aus einer Diplomarbeit reinkopiert, da sie mir sehr plausibel schienen.

    Bezüglich Terminiertheit habt ihr natürlich recht.
    Rein intuitiv würde ich für die Praxis eine Terminiertheit fordern (mit oder ohne Ergebnis).

    Ob jetzt bei der theoretischen Betrachtung des Begriffes Algorithmus eine Terminierung zwingend gefordert wird oder nicht, da muß ich zugeben, ich weiß es nicht, und hatte noch leider keine Zeit dazu, nachzugucken.

    Aber auf jedenfall Danke für das Feedback. 🙂

  14. #14 Karl-Heinz
    Graz
    8. Februar 2021

    Nachtrag zu Terminiertheit

    Algorithmus Definition: Diskussion
    ❖ Einer der fundamentalen Begriffe der Informatik ist nicht allgemein akzeptiert. Warum?
    – Die zweite Definition (“Ein Algorithmus muss terminieren.”) bezieht
    sich auf die Berechnung einer einzelnen Funktion, und da ist es schon
    besser, wenn wir für eine Eingabe auch eine Ausgabe bekommen.
    – Die erste Definition (“Ein Algorithmus muss nicht terminieren.”)
    bezieht auch andere interessante Informatik-Systeme ein, von denen
    wir erwarten, dass sie nicht terminieren (z.B. ein Betriebssystem oder
    ein Web-Server)
    ❖ Was sagt das über den Reifegrad der Informatik?

    – Informatik ist immer noch ein junges Gebiet.
    – Unterschiedliche Definitionen in vielen Bereichen der Informatik sind leider gang und gäbe.

  15. #15 hwied
    8. Februar 2021

    Karl-Heinz
    Ein Begriff ist erst vollständig definiert, wenn man eine Abgrenzung zu seinem Gegenteil findet. Also, was ist ein Nichtalgorithmus ?