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