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

otze Mitglied 07:42:19 06.04.2012 Titel:

Jaster: Ich bin bereit dein "Gegenbeispiel" für einen las-Vegas-Algorithmus als Untermenge anzusehen, der kein Algorithmus ist. Und fordere daher: Las-Vegas-Algorithmen mit P(terminieren) != 1 gehören in die Klasse "Rumreiten auf schwächen der formalen Definition" und sind damit nicht in der Klasse Algorithmen alle anderen schon.

Jester Moderator 11:20:30 06.04.2012 Titel:

@funksteuerung: nein, im wesentlichen fehlt mir dabei noch das definierte Ein-/Ausgabe-Verhalten, das liegt bei einem Betriebssystem in der Form nicht wirklich vor. Das lebt auf einer anderen granularitätsstufe. Außerdem verbindet man mit einem Betriebssystem normalerweise eine konkrete Implementierung, während ein Algorithmus ein Lösungsverfahren bezeichnet, nicht dessen Implementierung.

Jester Moderator 11:31:26 06.04.2012 Titel:

@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 Moderator 11:34:19 06.04.2012 Titel:

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

otze Mitglied 12:03:08 06.04.2012 Titel:

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

C++:
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.

Unregistrierter

Warum genau ist das kein Algorithmus?

Unregistrierter

weil otze das sagt :eek:

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 Mitglied 17:03:04 06.04.2012 Titel:

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

Unregistrierter

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

otze Mitglied 17:09:26 06.04.2012 Titel:

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