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

Jester

@otze: du erklärst also den Fall P=1, welcher eine Nullmenge ist, zum allgemeinen Fall und den Fall P!=1 zum Sondefall? kann man natürlich machen, wirkt aber eher wie eine Verzweiflungstat.

mal was anderes, wenn Algortihmen immer terminieren, wie heißen dann die Dinger, die nicht immer terminieren? Also auf welcher Menge von Objekten ist terminieren" definiet? Pseudo-Algorithmen?

P.S.: bei meiner Mini-Umfrage gestern haben alle Wert darauf gelegt, dass die Handlungsbeschreibung eines Algorithmus endlich ist. auch auf Nachfrage wollte keiner fordern, dass es terminiert. (ich habe zuerst gefragt "was ist ein algorithmus?" und dann "würdest du noch fordern, dass das stets terminiert?", ich glaube es ist mir gelungen nicht zu suggestiv zu fragen).

Jester

Btw, mal in die englische Wikipedia geschaut? Das deckt sich dort ziemlich genau mit meinem Verständnis.

otze

Jester schrieb:

@otze: du erklärst also den Fall P=1, welcher eine Nullmenge ist, zum allgemeinen Fall und den Fall P!=1 zum Sondefall? kann man natürlich machen, wirkt aber eher wie eine Verzweiflungstat.

Glaube ich nicht. Das Problem ist, dass die Definition von Las-Vegas-Algorithmen so wie hier verwendet erlaubt, dass

while(true){}

Die Definition erfüllt. Das ist offensichtlich kein Algorithmus. Und ich denke auch, dass es nicht im Sinne desjenigen war, der die Las-Vegas-Algorithmen eingeführt hat, dass so ein Programm erlaubt ist. Es deckt sich auch mit keiner Beschreibung, die ich finde. Es passt nur einfach in die Definition so wie sie formuliert wurde. Je nach Definitionsformulierung findet man auch, dass Monte-Carlo-Algorithmen normale Algorithmen sind, bei denen die Laufzeit eine Zufallsvariable ist. Jetzt ist natürlich die Frage, ob die Zufallsvariable Zeit auch den Wert unendlich annehmen darf.

In dem Sinne glaube ich wirklich, dass die "Nullmenge" der Normalfall ist.

Warum genau ist das kein Algorithmus?

weil otze das sagt

das ganze ist ein Streit um des Kaisers Bart.

der Begriff "Algorithmus" ist nicht eindeutig definiert. Alternativen sind exakt definierte Berechenbarkeitsbegriffe a la "Turing-berechenbar".

otze

!rr!rr_. schrieb:

der Begriff "Algorithmus" ist nicht eindeutig definiert. Alternativen sind exakt definierte Berechenbarkeitsbegriffe a la "Turing-berechenbar".

Das sind unterschiedliche Begriffe. Turing-Berechenbarkeit sagt nur: "Es gibt ein Programm, das das Problem auf einer Turing-Maschine lösen kann."

Oder wie es Wikipedia sagt:
"In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar (auch rekursiv), wenn es einen Algorithmus gibt, der die Funktion berechnet."

natürlich sind es unterschiedliche Begriffe, sonst könnte ja nicht der eine unscharf und der andere exakt definiert sein

otze

und der zweite Teil? Dein Begriff ist über den unscharfen anderen Definiert.

Michael E.

Er hat nur von Turingberechenbarkeit geredet, nicht von Berechenbarkeit. Turingberechenbarkeit ist ganz einfach zu definieren, dafür braucht man nicht den Algorithmenbegriff.

Jester

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?

knivil

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

Jester

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

Zeus

http://www.cs.uni-potsdam.de/ti/lehre/04-Lehrer/slides-0-anim.pdf auf Folie 1: schrieb:

Algorithmen: abstrakte Losungsmethoden
Programme: konkrete Losungsvorschriften

Teilen sowenige hier diesen Ansatz? XD

Jester

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.

knivil

!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!

Jester

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

knivil

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.