Wo fängt ein Algorithmus an und wo hört er auf?
-
Kann man eigentlich sagen, dass nichts, wo zwischendruch externe Ereignisse (Nutzereingabe, Hardwareinterrupt) den Ablauf beeinflussen, ein Algorithmus ist?
-
funksteuerung schrieb:
Kann man eigentlich sagen, dass nichts, wo zwischendruch externe Ereignisse (Nutzereingabe, Hardwareinterrupt) den Ablauf beeinflussen, ein Algorithmus ist?
Vielleicht kann man das als Parameter sehen, und dann quasi ein Template erstellen, das einen Algorithmus für jede Eingabekonfiguration erzeugt. (Das Template selbst wäre dann wieder ein Algorithmus?)
-
@cooky451: Was meinst du mit Template?
Der Algorithmusbegriff abstrahiert eben von solchen maschinennahen Problemen.
Deswegen ist es kein besonders aussichtsreiches Unterfangen, den Algorithmus "Betriebssystem" beschreiben zu wollen. Mehr Sinn macht es, die einzelnen Algorithmen, die in einem OS zusammenarbeiten zu sehen. Dann treten solche Fragen nach Interrupts gar nicht mehr auf.
-
Usereingabe kann man schon in einen Algorithmus integrieren.
"Sei s1...sn die endliche Nutzereingabe der Länge n". Fertig. Zwar kann der Algorithmus erst terminieren, wenn der Benutzer das letzte benötigte Zeichen (sn) eingegeben hat, tut er dies aber nicht, ist die Eingabe ungültig. Und auf ungültigen Eingaben braucht kein Algorithmus mehr irgendwelche Vorgaben erfüllen - außer, sie sind weiterhin angegeben.
-
Das ist nicht das, worauf funksteuerung hinauswollte, glaube ich.
Dass man eine Nutzereingabe vorschalten kann ist klar, aber eben keine (asynchronen?) Interrupts.
-
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?
-
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.
-
@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...)
-
(Zum letzten Abschnitt siehe auch dein edit :))
-
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ß.
-
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.
-
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.
-
dass die Terminierung einen korrekten von einem inkorrekten Algorithmus unterscheidet
Ist ein falscher Apfel immer noch ein Apfel?
-
.. nicht terminierender Algorithmus ist immer noch ein Algorithmus!
sei x = 0;
Solange x = 0 wiederhole:
gebe "Hallo" ausWill mir einer erzählen, dass das KEIN Algorithmus ist???
-
Ja, ich und viele andere in der Informatik.
-
Ein... schrieb:
.. nicht terminierender Algorithmus ist immer noch ein Algorithmus!
sei x = 0;
Solange x = 0 wiederhole:
gebe "Hallo" ausWill 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.
-
@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.
-
Lies n ein
Solange n!=1:
If n gerade
n=n/2
Else
n = 3n + 1Ist 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)
-
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?
-
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.