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

Unregistrierter

Würdet ihr sagen, es gibt eine Untergrenze, ab wann etwas ein Algorithmus ist?
Ist sowas ein Array-Ausgabe-Algorithmus?

Code:
foreach foo in foos print foo

Und gibt es eine Obergrenze für einen Algorithmus? Gibt es z.B. einen Gesichtserkennungs- oder Betriebssystem-Algorithmus? Oder ist ein Algorithmus immer nur eine kleine Aufgabe, also Sortier-Algorithmus usw.

knivil Mitglied 22:04:14 30.03.2012 Titel:

Zitat:

Ist sowas ein Array-Ausgabe-Algorithmus?

Ja.

Zitat:

Gesichtserkennungs-

Ja.

Zitat:

Betriebssystem-Algorithmus

Nein.

Ansonsten: Nutze die Suchfunktion oder schau bei Wikipedia vorbei.

Unregistrierter

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

Unregistrierter

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.

Unregistrierter

"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 ε.

Unregistrierter

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?

Unregistrierter

Eigentlich sind Programme ja auch nur ein Ressourcenzustand.

Unregistrierter

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

otze Mitglied 12:04:34 31.03.2012 Titel:

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.

Unregistrierter

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