Wo fängt ein Algorithmus an und wo hört er auf?
-
natürlich sind es unterschiedliche Begriffe, sonst könnte ja nicht der eine unscharf und der andere exakt definiert sein
-
und der zweite Teil? Dein Begriff ist über den unscharfen anderen Definiert.
-
Er hat nur von Turingberechenbarkeit geredet, nicht von Berechenbarkeit. Turingberechenbarkeit ist ganz einfach zu definieren, dafür braucht man nicht den Algorithmenbegriff.
-
otze schrieb:
Das ist offensichtlich kein Algorithmus.
Finde ich schon, so offensichtlich kann es also nicht sein. Aber was ist es denn eigentlich dann, wenn es kein Algorithmus ist? Wie heißt das Ding?
Klar ist das alles Definitionssache, aber ich sehe den Sinn nicht das Terminieren mit aufzunehmen. Wenn ich meine Sprache in eure übersetzetn möchte, dann muß ich manchmal halt noch "terminierender" vor Algorithmus schreiben. Das ist recht praktisch und ich kann damit leicht beide Konzepte formulieren und beschreiben; das was eine gute Definition eben leistet.
Also, wie übersetzt man in die andere Richtung und was ist dann besser als vorher?
-
!rr!rr_. schrieb:
der Begriff "Algorithmus" ist nicht eindeutig definiert.
Falsch, der Algorithmusbegriff wird beispielsweise exakt in "The Art of Computer Programming" definiert.
Wie heißt das Ding?
Programm!
-
knivil schrieb:
!rr!rr_. schrieb:
der Begriff "Algorithmus" ist nicht eindeutig definiert.
Falsch, der Algorithmusbegriff wird beispielsweise exakt in "The Art of Computer Programming" definiert.
Eindeutigkeit verlangt aber, daß entweder alle die selbe Definition verwenden, oder alle in Verwendung befindlichen Definitionen nachweislich äquivalent sind.
-
knivil schrieb:
!rr!rr_. schrieb:
der Begriff "Algorithmus" ist nicht eindeutig definiert.
Falsch, der Algorithmusbegriff wird beispielsweise exakt in "The Art of Computer Programming" definiert.
Wie heißt das Ding?
Programm!
Und wenn es terminiert ist es ein Algorithmus? Also ist ein Algorithmus ein Programm das terminiert? Insbesondere ist ein Algorithmus also ein Programm. Das klingt ist glaub ich ziemlich weit weg vom üblichen Sprachgebrauch.
Naja, ich denke wir können es dabei belassen. Mir war nur wichtig, dass hier nicht das bild entsteht, das sei völlig festgelegt (so wie das leider bei der deutschen wikipedia passiert ist).
-
http://www.cs.uni-potsdam.de/ti/lehre/04-Lehrer/slides-0-anim.pdf auf Folie 1: schrieb:
Algorithmen: abstrakte Losungsmethoden
Programme: konkrete LosungsvorschriftenTeilen sowenige hier diesen Ansatz? XD
-
Ich glaube alle sind sich einig, außer darin ob terminieren nun eine eigenschaft eines algorithmus ist, die er haben kann oder nicht bzw. Eine, die er eben haben muß. Letzteres handhaben verschiedene Leute und Quellen offensichtlich unterschiedlich.
-
!rr!rr_. schrieb:
Eindeutigkeit verlangt aber, daß entweder alle die selbe Definition verwenden, oder alle in Verwendung befindlichen Definitionen nachweislich äquivalent sind.
Nein, Einheitlich != Eindeutig!
-
Und was hast du damit gewonnen, knivil? Die Definition von Knuth ist nicht allgemeingültig, wie hier vielfach offengelegt wurde. Und daher ziemlich nutzlos.
-
knivil schrieb:
Nein, Einheitlich != Eindeutig!
eindeutig!
-
knivil schrieb:
!rr!rr_. schrieb:
Eindeutigkeit verlangt aber, daß entweder alle die selbe Definition verwenden, oder alle in Verwendung befindlichen Definitionen nachweislich äquivalent sind.
Nein, Einheitlich != Eindeutig!
langsam wirds lächerlich
-
Ich verstehe nicht, was ihr fuer ein Problem habt. Die meisten Argumente gegen Knuths Definition sind sehr subjektiver Natur. Beispielsweise: "... schraenkt die Algorithmen unnoetig ein" oder versuchen mittels Zufall zu tricksen.
Woher kommt das? Na weil kaum ein Buch sich festlegt. Viele reden ueber Algorithmen, (habe kurz in "Algorithmen in C" als auch das schon angesprochene Buch von Rivest "Algorithmen - Eine Einführung"). Grob: Ding das Probleme loest. Suuuper. Leider hoert es bei den meisten dann auf. Welche Eigenschaften hat denn nun ein Algorithmus? Welche Probleme loest er? Knuth macht darueber konkrete Aussagen, die beiden anderen nicht. Die "Definition" bleibt sehr schwammig und ungewiss. Klar kann die Definition aufgeweicht werden, aber das ist Ansichtssache. Und genau darum geht es hier, um Ansichten. Ich persoenlich moechte diesen konkreten Algorithmusbegriff ungern gegen einen schwammigen eintauschen, da formale Gruende einfach dagegen sprechen.
Und fuer alle, die einen Begriff suchen: Semi-Algorithmus.
-
Die argumente für knuths definition sind ja genauso subjektiv, wobei hier außer "Knuth hat aber gesagt" ja nicht besonders viel geliefert wurde. wir hätten gern den anderen konkreten Algorithmenbegriff, der "terminiert" als mögliche Eigenschaft von Algorithmen auffasst und diese nicht zwingend voraussetzt, die Gründe mögen subjektiv sein, das sind sie bei in sich konsistenten Alternativen von Definitionen aber immer. Auch wenn du versuchst anderes zu suggerieren ist keiner der beiden Begriffe schwammiger als der andere.
tatsächlich kann man sich oft das geeier ja auch sparen. Sobald man über laufzeiten reden will ist Terminieren ja Generalvoraussetzung. Erst wenn man Aussagen der Form "es gibt keinen Algorithmus, der..." beweisen will, muß man sich da wirklich festlegen -- und das passiert dann ja auch, meist über turingmaschinen. Das ist auch der Grund, warum sich deine anderen Bücher da nicht festlegen.
-
Hi,
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.
Ich befürchte, dass trifft auf alles nicht mehr zu, was beliebige andere Programme ausführen kann, wie zum Beispiel Betriebssysteme.
irgendwie wird hier aus meiner Sicht das Betriebssystem nicht ganz richtig betrachtet. Ein Betriebssystem ist ja kein Endlosfilm, der immer weiter im kreis läuft. Es macht ja im (aus heutiger Sicht) optimalen Fall selber nichts. Es führt einfach nur einzelne im Normalfall eindeutig terminierende Aufgaben aus.
Die erste Aufgabe die ausgeführt wird ist es, das System in den Betriebsbereiten Zustand zu versetzen. Ist nach einer nachvollziehbaren zeit erledigt. Danach reagiert es lediglich auf verschiedene Anforderungen von "außen", (auch wenn in dem Fall außen auch mal der Zeitgeber der eingebauten Quarzuhr ist). Wenn ein Benutzer eine Taste drückt, oder ein Programm eine Anforderung an das System stellt, dann erst wird das System tätig und reagiert nachvollziehbar darauf. Und am Schluss schreibt es alles zwischengespeicherte wieder auf die Platte.
Aus meiner Sicht ist ein Betriebssystem ein Algorithmus der auf Anforderungen unterschiedlicher (aber begrenzter) Art jeweils mit einer entsprechenden endlichen Leistungserbringung reagiert. also lässt sich der Allgorithmus des Betriebssystems letztlich auf einen ganz einfachen Nenner bingen:Wenn eine Anforderung eintrifft erfülle die Anforderung.Anders könnte es sein, wenn sich das System in der Zwischenzeit selbst beschäftigt. Zum Beispiel freie Zeitscheiben nutzen würde um die Platte generell defragmentiert zu halten. (Warum moderne Betriebssysteme das nicht machen ist mir schleierhaft).
Gruß Mümmel
-
Ein Betriebssystem ist ja kein Endlosfilm
Doch, oder was meinst du was der Leerlaufprozess unter Windows ist?
-
Hi,
knivil schrieb:
Ein Betriebssystem ist ja kein Endlosfilm
Doch, oder was meinst du was der Leerlaufprozess unter Windows ist?
eine Abfrage der diversen ...-quellen obs was neues gibt. Zumindest theoretisch könnte man den Computer auch statt dessen so lange anhalten bis irgend eine Nachricht eintrifft.
Gruß Mümmel
-
und wie merkt ein angehaltener Computer, daß eine Nachricht eintrifft?
ich kann ja auch nicht feststellen, ob eine email angekommen ist, wenn der Computer aus ist.