c++.de :: Wo fängt ein Algorithmus an und wo hört er auf?

Unregistrierter

uch gut

Zitat:

Was du meinst, ist partielle (terminiert manchmal) und totale (terminiert immer) Korrektheit

Windows 98 ist total Korrekt, Windows 7 nicht mal mehr partiel

Unregistrierter

Kann man eigentlich sagen, dass nichts, wo zwischendruch externe Ereignisse (Nutzereingabe, Hardwareinterrupt) den Ablauf beeinflussen, ein Algorithmus ist?

cooky451 Mitglied 16:36:46 31.03.2012 Titel:

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?)

Unregistrierter

@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.

otze Mitglied 18:08:27 31.03.2012 Titel:

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.

Unregistrierter

Das ist nicht das, worauf funksteuerung hinauswollte, glaube ich.
Dass man eine Nutzereingabe vorschalten kann ist klar, aber eben keine (asynchronen?) Interrupts.

cooky451 Mitglied 19:00:46 31.03.2012 Titel:

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 Mitglied 19:03:19 31.03.2012 Titel:

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.

Unregistrierter

@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...)

Unregistrierter

(Zum letzten Abschnitt siehe auch dein edit

)