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

Ein Algorithmus ist ein allgemeines Verfahren mit einer endlichen Beschreibung welches mit auf Grundobjekten mit ausführbaren Verarbeitungsschritten ein Problem löst.

Warum ist Betriebssystem kein Algorithmus? Man kann doch allgemein beschreiben, wie bestimmte Ressourcen vergeben werden müssen, damit das Problem gelöst ist, dass beliebige Programme auf einem Computer laufen können.

"Das Betriebssystem" umfasst aber viel mehr als das. Ein Betriebssystem besteht aus einer (enormen) Vielzahl von verschiedenen Problem(instanzen), die ihrerseits algorithmisch gelöst werden.
Dein Begriff von Problem(instanz) ist zu naiv.

Ein Problem π ist formal eine Abbildung von einer Grundmenge Σ* in einen Lösungsraum Y.

Beispiel: Σ* ist die Menge aller endlichen Folgen mit Einträgen aus einer total geordneten Menge, Y die Menge aller bezüglich dieser Ordnung auf-/absteigend sortierten endlichen Folgen. Oder ganz klassisch: Σ* ist die Menge aller endlichen Zeichenketten über der Menge Σ = {a, b}, Y = {true, false} beschreibt das (hier triviale) Wortproblem aus der theoretischen Informatik.

Nicht zu verwechseln damit ist der Begriff der Probleminstanz, die zu einem gegebenen Problem eine Eingabe bereitstellt, im obigen ersten Fall beispielsweise (1, 2, 3, 4), (4, 4, 5, 6) oder im zweiten Fall aabbabab, bababababab oder ε.

Bei einem Betriebssystem kann man doch auch sagen, Grundmenge ist die Menge aller kombinationen von Programmen und Ressourcenzustände (sind auch endliche Zeichenketten) und der Lösungsraum ein neuer Ressourcenzustand. Oder darf es bei einem Algorithmus keine Rückkopplung zwischen Grundmenge und Lösungsraum geben?

Eigentlich sind Programme ja auch nur ein Ressourcenzustand.

Dann versuch mal, einen Algorithmus nach obiger Definition zu formulieren, der das Problem löst

otze

Wine wichtige Eigenschaft von Algorithmus ist Terminierung. Man muss also Beweisen können, dass ein Algorithmus immer mit endlich vielen Rechenschritten sein Ergebnis erzeugt.

Ich befürchte, dass trifft auf alles nicht mehr zu, was beliebige andere Programme ausführen kann, wie zum Beispiel Betriebssysteme.

@otze: Dann ist ein Verfahren zum Lösen des postschen Korrespondenzproblems kein Algorithmus, weil das PCP semientscheidbar ist?
Das ist zu kurz gedacht.
Was du meinst, ist partielle (terminiert manchmal) und totale (terminiert immer) Korrektheit, die aber speziell für den Algorithmus (bzw. seine Umsetzung in Code) nachgewiesen werden muss.

JFB schrieb:

Dann versuch mal, einen Algorithmus nach obiger Definition zu formulieren, der das Problem löst

Ich kann aber auch nicht einfach so mal einen Algorithmus formulieren der Gesichter erkennt. Gibt es jetzt keinen Gesichtserkennungsalgorithmus mehr?

knivil

Ein Algorithmus terminiert nach einer endlichen Zeit. Waere schlimm, wenn das ein Beriebssystem tun wuerde. Und ja, es gibt keinen Algorithmus, der das Halteproblem loest.

Ich kann aber auch nicht einfach so mal einen Algorithmus formulieren der Gesichter erkennt.

Aber andere koennen es.

otze schrieb:

Wine wichtige Eigenschaft von Algorithmus ist Terminierung. Man muss also Beweisen können, dass ein Algorithmus immer mit endlich vielen Rechenschritten sein Ergebnis erzeugt.

Und was ist mit z.B. einer Berechnung von PI? Die hört auch nie auf, ist das nun kein Algorithmus mehr?

knivil schrieb:

Ich kann aber auch nicht einfach so mal einen Algorithmus formulieren der Gesichter erkennt.

Aber andere koennen es.

Das kann ich von einem Betriebssystem auch behaupten.

gewünschter Benutzername schrieb:

otze schrieb:

Wine wichtige Eigenschaft von Algorithmus ist Terminierung. Man muss also Beweisen können, dass ein Algorithmus immer mit endlich vielen Rechenschritten sein Ergebnis erzeugt.

Und was ist mit z.B. einer Berechnung von PI? Die hört auch nie auf, ist das nun kein Algorithmus mehr?

Dann gibt es halt keinen Algorithmus zur Berechnung von PI, sondern nur Algorithmen die PI auf X-Stellen genau berechnen.

Das mit der Terminierung war bisher das einzige was Betriebssystem und Gesichtserkennung unterscheidet.

Zeus

funksteuerung schrieb:

knivil schrieb:

Ich kann aber auch nicht einfach so mal einen Algorithmus formulieren der Gesichter erkennt.

Aber andere koennen es.

Das kann ich von einem Betriebssystem auch behaupten.

Dadurch wird ein Betriebssystem nicht zum Algorithmus.

otze

funksteuerung schrieb:

Das mit der Terminierung war bisher das einzige was Betriebssystem und Gesichtserkennung unterscheidet.

Ein Punkt reicht ja auch aus.

LOL

Dann ist Windows 98 ein Algorithmus (Stürzt nach einer bestimmten Anzahl an Tagen wiederholbar wegen Überlauf einer Variablen der Zeitmessung ab, terminiert also) und Windows 7 ist kein Algorithmus mehr

Upps. Wieder was gelernt

Oder auch nicht...während Wikipedia zwar die Terminierung als Eigenschaft eines Algorithmus definiert, sagen Cormen, Leiserson, Rivest und Stein, dass die Terminierung einen korrekten von einem inkorrekten Algorithmus unterscheidet und nicht per so vorausgesetzt wird (wie ich oben geschrieben habe).

uch gut

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

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

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