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

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

  • K

    dass die Terminierung einen korrekten von einem inkorrekten Algorithmus unterscheidet

    Ist ein falscher Apfel immer noch ein Apfel?

    0
  • ?

    .. nicht terminierender Algorithmus ist immer noch ein Algorithmus!

    sei x = 0;
    Solange x = 0 wiederhole:
    gebe "Hallo" aus

    Will mir einer erzählen, dass das KEIN Algorithmus ist???

    0
  • K

    Ja, ich und viele andere in der Informatik.

    0
  • Z

    Ein... schrieb:

    .. nicht terminierender Algorithmus ist immer noch ein Algorithmus!

    sei x = 0;
    Solange x = 0 wiederhole:
    gebe "Hallo" aus

    Will mir einer erzählen, dass das KEIN Algorithmus ist???

    Einige von Uns nennen es auch Schwachfug anstelle einer Endlosschleife :p Es ist kein Verfahren, dass ein Problem löst, deswegen ist es auch kein Algorithmus. Nicht alles was im Pseudocode darstellbar ist, ist ein Algorithmus.

    0
  • ?

    @knivil: Komischer Vergleich. Das "falsch" hört sich an als wolltest du auf ein Imitat hinaus. So wie in "Falschgeld". Besser: Ist ein angefaulter Apfel immer noch ein Apfel? Ich denke schon.

    @Zeus: Das hängt wieder stark von der Definition von Problem ab. Wenn man die nimmt, die ich oben gegeben habe, könnte man beispielsweise einen leeren Lösungsraum annehmen.

    0
  • J

    Lies n ein

    Solange n!=1:
    If n gerade
    n=n/2
    Else
    n = 3n + 1

    Ist das nun ein Algorithmus? ich würde sagen ja, leider ist offen, ob das stets terminiert. deswegen weiß knivil nicht ob es ein Algorithmus ist. Das scheint mir den Algorithmenbegriff unnötig einzuschränken. (ich bin auch Informatiker und kenne viele Informatiker, die das auch so sehen)

    0
  • J

    knivil schrieb:

    dass die Terminierung einen korrekten von einem inkorrekten Algorithmus unterscheidet

    Ist ein falscher Apfel immer noch ein Apfel?

    Sind Las Vegas-Algorithmen Algorithmen?

    0
  • M

    Jester: Selber Ort, die gleichen Personen 😉

    http://www.c-plusplus.net/forum/294795-38

    Vielleicht sollte ich mich wirklich mal mit dem Thema befassen. Denn es gibt immer jemanden, der Wissen aus Büchern nachplappert, aber nicht überzeugend auf meine/unsere Fragen eingehen kann.

    0
  • ?

    Muss man den Begriff überhaupt so präzise abgrenzen (mir ist klar, dass das Mathematiker gerne tun)?
    Wenn sich schon Leute wie Rivest und Knuth nicht einig sind, was denn nun einen Algorithmus genau ausmacht, dann ist es vielleicht gar nicht so wahnsinnig wichtig? Solange im Kontext klar ist, was gemeint ist, ist doch alles in bester Ordnung.

    0
  • K

    Jester schrieb:

    Lies n ein

    Solange n!=1:
    If n gerade
    n=n/2
    Else
    n = 3n + 1

    Und die Ausgabe?

    Das scheint mir den Algorithmenbegriff unnötig einzuschränken.

    Darueberhinaus gibt es ja noch mehr als Algorithmen und nicht Algorithmen um zu differenzieren, beispielsweise Programme. Warum eine Definition aufweiten oder verwaessern, wenn doch so viele andere Begriffe zur Auswahl stehen.

    (ich bin auch Informatiker und kenne viele Informatiker, die das auch so sehen

    Wo kommen wir denn hin, wenn Mathematik zukuenftig durch Mehrheitsentscheid betrieben wird.

    Zu Las-Vegas-Algorithmen: Nur weil Algorithmus draufsteht, muss noch lange nicht Algorithmus drin stecken. Ist ein falscher Hase auch ein Hase, aber schauen wir doch mal bei Wikipedia:

    In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure.

    vs.

    Ein Las-Vegas-Algorithmus ist ein randomisierter Algorithmus, der immer ein korrektes Ergebnis liefert, wenn er terminiert.

    Tja, was denn nun? Ab diesem Punkt kann man sich beispielsweise fuer eine Seite entscheiden, terminiert oder eben nicht. D.h. man geht den Schritt von Definition zu Meinung, und Meinungen sind wie ... Genauso kann man dann auch diskutieren, ob die Null zu den natuerlichen Zahlen zaehlt.

    nachplappert

    Formal anwenden ist also fuer dich negativ belegt. Naja, was verstehst du an der Definition von Algorithmus nicht? Wo bin ich nicht ueberzeugt. Das ich Jester nicht ueberzeugen kann, ist mir schon klar.

    Rivest und Knuth

    Ich schaue mir kurz die ersten Seiten von "Algorithmen - Eine Einführung" an und sehe grob keinen Widerspruch zu Knuth.

    0
  • J

    knivil schrieb:

    (ich bin auch Informatiker und kenne viele Informatiker, die das auch so sehen

    Wo kommen wir denn hin, wenn Mathematik zukuenftig durch Mehrheitsentscheid betrieben wird.

    Naja, Du hast oben mit "ich und viele andere Informatiker" angefangen. Aber Du hast recht, das geht natürlich jicht nach Mehrheit, deshalb erlaube ich mir näher zubspezifizieren, dass es sich dabei um Algorithmiker handelt. und ganz genau genommen läuft es natürlich doch nach Mehrheit, nämlich nach der Mehrheit der Publikationen in einem Gebiet.Dadurch etabliert sich ein gemeinsames Grundverständnis, von dem man auch dann nur schwer anweichen kann, wenn man selbst eine andere Nomenklatur für besser erachtet.

    Achja, die Ausgabe des obigen Algorithmus soll einfach immer 17 sein. -- Wenn's hilft!? Oder wenn das nicht reichen sollte bau noch nen Durchlaufzähler ein, der mitzählt und gib den aus. Wie würdest Du das Ding nennen?

    Edit: ich mach wenn ich drann denke nachher mal ne kleine Umfrage bei uns.

    0
  • O

    Las-Vegas-Algorithmen terminieren mit Wahrscheinlichkeit 0 nicht. Also "fast immer". Das reicht mir aus um das einen Algorithmus zu nennen.

    //edit also mit Wahrscheinlichkeit 0 bei jeder Eingabe im Suchraum natürlich.

    0
  • J

    otze schrieb:

    Las-Vegas-Algorithmen terminieren mit Wahrscheinlichkeit 0 nicht. Also "fast immer". Das reicht mir aus um das einen Algorithmus zu nennen.

    //edit also mit Wahrscheinlichkeit 0 bei jeder Eingabe im Suchraum natürlich.

    Ja, aber das geht doch an der Frage vorbei. sagen wir ich würfle erst, bei 6 lasse ich den Algorithmus laufen, sonst gehe ich in ne Endlosschleife. Algorithmus oder nicht? Bleib doch mal beim großen Ganzen anstatt zu glauben, dass du hier leute mit randfällen aufs Glatteis führen kannst.

    0
  • ?

    otze schrieb:

    Las-Vegas-Algorithmen terminieren mit Wahrscheinlichkeit 0 nicht. Also "fast immer". Das reicht mir aus um das einen Algorithmus zu nennen.

    und was ist, wenn in dieser Ausnahmemenge vom Maß 0 alle praxisrelevanten Eingaben stecken?

    0
  • O

    Jester schrieb:

    Ja, aber das geht doch an der Frage vorbei. sagen wir ich würfle erst, bei 6 lasse ich den Algorithmus laufen, sonst gehe ich in ne Endlosschleife. Algorithmus oder nicht? Bleib doch mal beim großen Ganzen anstatt zu glauben, dass du hier leute mit randfällen aufs Glatteis führen kannst.

    Ich sehe jetzt nicht, dass mein Argument einen Randfall beschreibt, sondern im Gegenteil den Normalfall. Es wird dir in der Realität niemals passieren, dass ein shaker-sort für kleine Eingaben nicht terminiert. Und genau das ist, was die Theorie auch besagt: Wahrscheinlichkeit 0. Es kann dir niemand sagen wie lange es dauern wird und manchmal wird es sehr sehr sehr lange dauern, aber genauso dauern exponentiell-zeit Algorithmen sehr sehr lange. Also ist selbst "dauert wahrscheinlich länger als unser Universum existiert" kein Kriterium, denn das trifft auf die meisten komplexen Probleme zu.

    Also frage ich jetzt umgekehrt: warum sollte dein Algorithmus zusammen in einer Kategorie mit Las-Vegas-Algorithmen liegen?

    !rr!rr: Aus deinen Annahmen folgt p(treffer) = 0 -> nicht im Suchraum -> algorithmus muss nicht termineiren. Aber mal ehrlich: wenn ich hier von Randfällen reden soll, was ist DEIN Punkt dann erst? Maß 0 an einem Computer. Das ist gleichbedeutend mit: Ein Algorithmus, der pi auf unendliche Genauigkeit berechnet.

    0
  • J

    otze schrieb:

    Also frage ich jetzt umgekehrt: warum sollte dein Algorithmus zusammen in einer Kategorie mit Las-Vegas-Algorithmen liegen?

    ernst gemeint? na weil er die Definition erfüllt, nirgendwo steht dass Las Vegas Algorithmen nur mi WK 0 nicht terminieren.

    0
  • ?

    @Jester: Würdest du sagen, ein Betriebssystem ist auch ein Algorithmus?

    0
  • O

    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.

    0
  • J

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

    0
  • J

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

    0
Anmelden zum Antworten