Wo fängt ein Algorithmus an und wo hört er auf?

[cooky451]

Soweit ich das verstehe kann man halt einen Algorithmus erstellen der für eine unendliche Menge an Eingaben/Eingabezeitpunkten eine endliche Menge von Übergängen/Ergebnissen beschreibt.

Edit: Was übrigens dazu führen würde, dass man Betriebssysteme als Algorithmen beschreiben kann, weil diese ja bei bestimmten Eingaben anhalten?

[otze]

Wer sagt, dass man Nutzereingaben in einem Algorithmus über Interrupts realisieren muss? Es gibt so viele gute Abstraktionen, die genau solche Probleme umgehen. Linux Datenströme führen Beispielsweise genau zu einer Abstraktion wie: "Die menge aller Nutzereingaben über stdin ist ein Datenstrom s1...sn"

//edit funktionale Sprachen machen exakt dieselbe Abstraktion, da sie aufgrund der funktionalen Einschränkungen formal keine Interrupts realisieren können.

Eine Eingabeoperation ließt von deinem Datenstrom s1...sk die ersten m zeichen. Dass wenn m > k die Laufzeitumgebung den Nutzer nach Eingaben fragen muss, ist aber für den Algorithmus völlig unerheblich.

[JFB]

@cooky451: Ich weiß nicht genau was du meinst, aber "unendliche Menge an Eingabezeitpunkten" wird, wenn du von einem Zeitkontinuum ausgehst, zum Problem, weil die Menge der Algorithmen abzählbar unendlich ist.

@otze: Ja, eben. Aber irgendwer muss sich auf irgendeiner Ebene mit Interrupt handling auseinandersetzen. Dass sich das so abstrahieren lässt, um es sauber beschreiben zu können ist klar. Nur das ist ja genau der Punkt: Lässt sich auch die "tiefe" Ebene sauber beschreiben?

Ich glaube nicht, dass das ordentlich möglich ist. Alleine schon deswegen, weil sich jede berechenbare Funktion auch im Lambda-Kalkül beschreiben lässt, und da ist das mit der Zeitlichen Anordnung von Anweisungen so eine Sache (siehe auch das Verarbeiten von Nutzereingaben in Haskell...)

[JFB]

(Zum letzten Abschnitt siehe auch dein edit :))

[funksteuerung]

otze schrieb:

Wer sagt, dass man Nutzereingaben in einem Algorithmus über Interrupts realisieren muss? Es gibt so viele gute Abstraktionen, die genau solche Probleme umgehen. Linux Datenströme führen Beispielsweise genau zu einer Abstraktion wie: "Die menge aller Nutzereingaben über stdin ist ein Datenstrom s1...sn"

//edit funktionale Sprachen machen exakt dieselbe Abstraktion, da sie aufgrund der funktionalen Einschränkungen formal keine Interrupts realisieren können.

Eine Eingabeoperation ließt von deinem Datenstrom s1...sk die ersten m zeichen. Dass wenn m > k die Laufzeitumgebung den Nutzer nach Eingaben fragen muss, ist aber für den Algorithmus völlig unerheblich.

Die Menge aller Nutzereingaben über stdin ist aber nicht "s1...sn", sondern theoretisch unendlich groß.

[Andreas XXL]

Wie wird denn die Tatsache modelliert, das die Eingaben am Anfang noch nicht feststehen?
Die Eingaben des Anwenders hängen doch von seinen vorherigen eingaben und den Ausgaben die der Algorithmus (falls es mit dieser Definition einer ist) in der zwischenzeit gemacht hat ab.

[otze]

funksteuerung schrieb:

Die Menge aller Nutzereingaben über stdin ist aber nicht "s1...sn", sondern theoretisch unendlich groß.

unendliche Eingaben müssen von keinem Algorithmus verarbeitet werden können. Geht ja auch gar nicht in endlicher Zeit. Aber für jede beliebige endliche Eingabe findest du ein n, sodass der Formalismus zutrifft.

@AndreasXXL Siehe haskell-Eingabemonaden. Ich erklär mir hier jetzt nicht nen Wolf.

[knivil]

dass die Terminierung einen korrekten von einem inkorrekten Algorithmus unterscheidet

Ist ein falscher Apfel immer noch ein Apfel?

[Ein...]

.. nicht terminierender Algorithmus ist immer noch ein Algorithmus!

sei x = 0;
Solange x = 0 wiederhole:
gebe "Hallo" aus

Will mir einer erzählen, dass das KEIN Algorithmus ist???

[knivil]

Ja, ich und viele andere in der Informatik.

[Zeus]

Ein... schrieb:

.. nicht terminierender Algorithmus ist immer noch ein Algorithmus!

sei x = 0;
Solange x = 0 wiederhole:
gebe "Hallo" aus

Will mir einer erzählen, dass das KEIN Algorithmus ist???

Einige von Uns nennen es auch Schwachfug anstelle einer Endlosschleife :p Es ist kein Verfahren, dass ein Problem löst, deswegen ist es auch kein Algorithmus. Nicht alles was im Pseudocode darstellbar ist, ist ein Algorithmus.

[JFB]

@knivil: Komischer Vergleich. Das "falsch" hört sich an als wolltest du auf ein Imitat hinaus. So wie in "Falschgeld". Besser: Ist ein angefaulter Apfel immer noch ein Apfel? Ich denke schon.

@Zeus: Das hängt wieder stark von der Definition von Problem ab. Wenn man die nimmt, die ich oben gegeben habe, könnte man beispielsweise einen leeren Lösungsraum annehmen.

[Jester]

Lies n ein

Solange n!=1:
If n gerade
n=n/2
Else
n = 3n + 1

Ist das nun ein Algorithmus? ich würde sagen ja, leider ist offen, ob das stets terminiert. deswegen weiß knivil nicht ob es ein Algorithmus ist. Das scheint mir den Algorithmenbegriff unnötig einzuschränken. (ich bin auch Informatiker und kenne viele Informatiker, die das auch so sehen)

[Jester]

knivil schrieb:

dass die Terminierung einen korrekten von einem inkorrekten Algorithmus unterscheidet

Ist ein falscher Apfel immer noch ein Apfel?

Sind Las Vegas-Algorithmen Algorithmen?

[Michael E.]

Jester: Selber Ort, die gleichen Personen

http://www.c-plusplus.net/forum/294795-38

Vielleicht sollte ich mich wirklich mal mit dem Thema befassen. Denn es gibt immer jemanden, der Wissen aus Büchern nachplappert, aber nicht überzeugend auf meine/unsere Fragen eingehen kann.

[JFB]

Muss man den Begriff überhaupt so präzise abgrenzen (mir ist klar, dass das Mathematiker gerne tun)?
Wenn sich schon Leute wie Rivest und Knuth nicht einig sind, was denn nun einen Algorithmus genau ausmacht, dann ist es vielleicht gar nicht so wahnsinnig wichtig? Solange im Kontext klar ist, was gemeint ist, ist doch alles in bester Ordnung.

[knivil]

Jester schrieb:

Lies n ein

Solange n!=1:
If n gerade
n=n/2
Else
n = 3n + 1

Und die Ausgabe?

Das scheint mir den Algorithmenbegriff unnötig einzuschränken.

Darueberhinaus gibt es ja noch mehr als Algorithmen und nicht Algorithmen um zu differenzieren, beispielsweise Programme. Warum eine Definition aufweiten oder verwaessern, wenn doch so viele andere Begriffe zur Auswahl stehen.

(ich bin auch Informatiker und kenne viele Informatiker, die das auch so sehen

Wo kommen wir denn hin, wenn Mathematik zukuenftig durch Mehrheitsentscheid betrieben wird.

Zu Las-Vegas-Algorithmen: Nur weil Algorithmus draufsteht, muss noch lange nicht Algorithmus drin stecken. Ist ein falscher Hase auch ein Hase, aber schauen wir doch mal bei Wikipedia:

In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure.

vs.

Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert.

Tja, was denn nun? Ab diesem Punkt kann man sich beispielsweise fuer eine Seite entscheiden, terminiert oder eben nicht. D.h. man geht den Schritt von Definition zu Meinung, und Meinungen sind wie ... Genauso kann man dann auch diskutieren, ob die Null zu den natuerlichen Zahlen zaehlt.

nachplappert

Formal anwenden ist also fuer dich negativ belegt. Naja, was verstehst du an der Definition von Algorithmus nicht? Wo bin ich nicht ueberzeugt. Das ich Jester nicht ueberzeugen kann, ist mir schon klar.

Rivest und Knuth

Ich schaue mir kurz die ersten Seiten von "Algorithmen - Eine Einführung" an und sehe grob keinen Widerspruch zu Knuth.

[Jester]

knivil schrieb:

(ich bin auch Informatiker und kenne viele Informatiker, die das auch so sehen

Wo kommen wir denn hin, wenn Mathematik zukuenftig durch Mehrheitsentscheid betrieben wird.

Naja, Du hast oben mit "ich und viele andere Informatiker" angefangen. Aber Du hast recht, das geht natürlich jicht nach Mehrheit, deshalb erlaube ich mir näher zubspezifizieren, dass es sich dabei um Algorithmiker handelt. und ganz genau genommen läuft es natürlich doch nach Mehrheit, nämlich nach der Mehrheit der Publikationen in einem Gebiet.Dadurch etabliert sich ein gemeinsames Grundverständnis, von dem man auch dann nur schwer anweichen kann, wenn man selbst eine andere Nomenklatur für besser erachtet.

Achja, die Ausgabe des obigen Algorithmus soll einfach immer 17 sein. -- Wenn's hilft!? Oder wenn das nicht reichen sollte bau noch nen Durchlaufzähler ein, der mitzählt und gib den aus. Wie würdest Du das Ding nennen?

Edit: ich mach wenn ich drann denke nachher mal ne kleine Umfrage bei uns.

[otze]

Las-Vegas-Algorithmen terminieren mit Wahrscheinlichkeit 0 nicht. Also "fast immer". Das reicht mir aus um das einen Algorithmus zu nennen.

//edit also mit Wahrscheinlichkeit 0 bei jeder Eingabe im Suchraum natürlich.

[Jester]

otze schrieb:

Las-Vegas-Algorithmen terminieren mit Wahrscheinlichkeit 0 nicht. Also "fast immer". Das reicht mir aus um das einen Algorithmus zu nennen.

//edit also mit Wahrscheinlichkeit 0 bei jeder Eingabe im Suchraum natürlich.

Ja, aber das geht doch an der Frage vorbei. sagen wir ich würfle erst, bei 6 lasse ich den Algorithmus laufen, sonst gehe ich in ne Endlosschleife. Algorithmus oder nicht? Bleib doch mal beim großen Ganzen anstatt zu glauben, dass du hier leute mit randfällen aufs Glatteis führen kannst.