Wo fängt ein Algorithmus an und wo hört er auf?
-
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?
-
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.
-
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.
-
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?
-
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.