# Algorithmen und Eigenschaften



## Wang (11. Nov 2009)

Hallo, JAVA-Freunde! :toll:

Ich bitte um etwas Unterstützung bei der folgenden Aufgabe:



> Stellen Sie sich einen Karteikasten vor, in dem Sie nach allen Karteikarten mit einem bestimmten Titel suchen.
> Hierfür stellen wir Ihnen fünf unterschiedliche Algorithmen vor:
> 
> Suchverfahren 1:
> ...



Meine Lösung:

Suchverfahren 1:
- terminierend (Alorithmus kommt nach endlich vielen Arbeitsschritten zum Ende)
- deterministisch (Wirkung und Reihenfolge der Einzelschritte ist eindeutig festgelegt)
- determiniert (da deterministisch und das Ergebnis der Verarbeitung ist für jede einezelne Anwendung eindeutig bestimmt)
- total korrekt (der Algorithmus ist partiell korrekt und terminiert für alle gültigen Eingaben)

Falls das soweit richtig ist, präsentiere ich noch meine anderen Lösungen.

Vielen Dank!


----------



## Der Müde Joe (11. Nov 2009)

>terminierend

nicht zwingend. zB du hast 2 Karten und nimmst immer die erste, brauchst aber die 2te


----------



## diggaa1984 (11. Nov 2009)

was passiert wenn man NIE die richtige Karte erwischt, dann is das ding endlos, also nicht-terminierend???:L


----------



## Marco13 (11. Nov 2009)

Entweder, diese Fragen sind sehr verbreitet und "Standard", oder du hörst eine Vorlesung bei dem, der letzteren früher vielleicht gelegentlich gelesen hat, in dem Land, wo er herkommt. (TUD?).

Irgendwie hab ich bei den Worten "deterministisch<->zufällig" ein komisches Gefühl, müßte aber nochmal auf den Folien die genauen Definitionen davon nachlesen....


----------



## Der Müde Joe (11. Nov 2009)

>aber nochmal auf den Folien die genauen Definitionen davon nachlesen.... 

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Anders gesprochen heißt das, auf eine Anweisung im Algorithmus folgt unter den gleichen Voraussetzungen immer die gleiche Anweisung. WIKI


----------



## diggaa1984 (11. Nov 2009)

ich kenne deterministisch auch in dem sinne das es nur eine möglichkeit gibt weiter zu arbeiten, nicht-deterministisch hat dann mehrere alternativen bei der selben eingabe.


----------



## Marco13 (11. Nov 2009)

@Der Müde Joe: Zufällig war es (wenn ich mich recht erinnere) genau diese Vorlesung, in der sinngemäß gesagt wurde: "Namen sind Schall und Rauch, es geht darum, sich im abstrakten Gerüst der Definitionen zu bewegen" - verbindlich ist, was der Prof auf seine Folien schreibt  
Aber ja, das kann schon richtig sein, von daher wäre das Beispiel wegen des zufälligen Wählens aber nicht deterministisch...


----------



## Wang (11. Nov 2009)

Der Müde Joe hat gesagt.:


> >terminierend
> 
> nicht zwingend. zB du hast 2 Karten und nimmst immer die erste, brauchst aber die 2te



Danke müder Joe und danke auch an alle anderen.

Bezüglich der Eigenschaft "rekursiv" war ich mir nicht ganz sicher, aber ich habe das so gesehen, dass ich keine Funktion habe, die durch sich selbst definiert wird. Seht ihr das genauso?


----------



## Marco13 (11. Nov 2009)

Das erste Verfahren ist nicht rekursiv *wink*


----------



## HansPaulKlaus (11. Nov 2009)

Du meinst es gibt keine Funktion die sich selbst aufruft.Also 1 ist nicht rekursiv.Das ist richtig.

Der Fall den Müder Joe beschrieben hat kann eigentlich nicht eintreten.Man kann aufgrund der Aufgabenstellung von einem "Laplace Experiment" ausgehen.D.h. die Ergebnismenge ist endlich und jedes Ergebnis ist gleich wahrscheinlich.Daraus folgt dass der Algorithmus 1 terminiert und zwar immer.Je grösser allerdings die Anzahl der Karteikarten in der Box desto grösser natürlich die Laufzeit.

Und als Faustregel - Sobald irgendwas mit "Zufall" im Spiel ist kannst du in aller Regel Determinismus vergessen.


----------



## Wang (11. Nov 2009)

Marco13 hat gesagt.:


> Das erste Verfahren ist nicht rekursiv *wink*



Danke, Marco13! 

Kann es sein, dass dann für das Suchverfahren 1 keine der angegebenen sechs Eigenschaften zutreffen?

EDIT:
Also doch ein terminierter Algorithmus. Folgt daraus auch, dass er partiell und total korrekt ist?


----------



## HansPaulKlaus (11. Nov 2009)

1.Wie ich in meinem Beitrag schon erklärt habe terminiert der Algorithmus immer.(auch wenn es sehr lang dauern kann).

2.Der Algorithmus hält nur an wenn die richtige Karte gefunden wurde (das ist lt. Aufgabenstellung so)

Aus 1. und 2. folgt die totale Korrektheit und aus dieser folgt die partielle Korrektheit.


----------



## Wang (11. Nov 2009)

HansPaulKlaus hat gesagt.:


> 1.Wie ich in meinem Beitrag schon erklärt habe terminiert der Algorithmus immer.(auch wenn es sehr lang dauern kann).
> 
> 2.Der Algorithmus hält nur an wenn die richtige Karte gefunden wurde (das ist lt. Aufgabenstellung so)
> 
> Aus 1. und 2. folgt die totale Korrektheit und aus dieser folgt die partielle Korrektheit.



Vielen Dank, HansPaulKlaus.
Schade, dass du kein registriertes Mitglied des Forums bist...


----------



## Wang (11. Nov 2009)

Die Sache mit Determiniertheit:
Ich sehe das so, dass der Algorithmus nicht determiniert, da das Ergebnis immer offen ist.

Bitte kurz um Rückmeldung, ob das stimmt und auch die Argumentation richtig ist?

Danke! :toll:


----------



## Marco13 (11. Nov 2009)

@HansPaulKlaus: _Der Fall den Müder Joe beschrieben hat kann eigentlich nicht eintreten._

Und weil eigentlich eigentlich kein Wort ist, ist die Aussage eigentlich falsch. Die Wahrscheinlichkeit, die richtige Karte zu erwischen ist (bei wirklich zufälliger Wahl) immer 1/n. Das ist beim ersten Versuch so. Und beim zweiten. Und beim dritten. Und bei jedem Versuch kann (unabhängig davon, wie viele Versuche man vorher schon gemacht hat) die falsche Karte erwischt werden. Man kann also nicht sagen, wie lange die Suche dauert, und sie kann unendlich lange dauern - spätestens, wenn die gesuchte Karte gar nicht im Stapel enthalten ist!
(BTW: Das wußte ich auch, bevor ich nochmal auf dem Lösungsblatt nachgesehen habe :bae: )

WENN der Algorithmus terminiert, dann ist das Ergebnis immer das gleiche (nämlich immer die gesuchte Karte) - allerdings ist ja nicht sichergestellt, dass der Algorithmus terminiert, deswegen ist er auch nicht determiniert. Ich würde sagen, dass für das erste Verfahren damit nur eine der aufgezählten Eigenschaften übrig bleibt...


----------



## HansPaulKlaus (11. Nov 2009)

Marco13 hat gesagt.:


> Und weil eigentlich eigentlich kein Wort ist, ist die Aussage eigentlich falsch. Die Wahrscheinlichkeit, die richtige Karte zu erwischen ist (bei wirklich zufälliger Wahl) immer 1/n. Das ist beim ersten Versuch so. Und beim zweiten. Und beim dritten. Und bei jedem Versuch kann (unabhängig davon, wie viele Versuche man vorher schon gemacht hat) die falsche Karte erwischt werden. Man kann also nicht sagen, wie lange die Suche dauert, und sie kann unendlich lange dauern - spätestens, wenn die gesuchte Karte gar nicht im Stapel enthalten ist!



Ob man sich jetzt an dem Wort "eigentlich" aufhalten muss ?! - dann streichen wir es halt.

Nochmal zur Erklärung - Wir gehen von einem Laplace Experiment (oder auch klassische Wahrscheinlichkeit genannt) aus.
D.h. es gibt endlich viele Ergebnisse (Karten) und jedes Ergebnis ist gleich wahrscheinlich.

Du hast natürlich recht - die Ziehungen der Karten sind unabhängig voneinander und man kann nicht vorhersagen wie lange die Suche dauert - Aber einen Fall kann man ausschliessen.Nämlich dass sie unendlich lang dauert.

Warum ist das so ? Nimm z.b. einen einfachen Würfel - würfel 30 mal - wenn du Pech hast kommt beispielsweise die "5" nicht einmal vor dafür kommt die "3" zehn mal vor.Kann passieren.Wiederholst Du das Experiment aber sehr oft z.b. 1.000.000 mal dann werden alle 6 Werte ca. gleich oft eintreten.

Der Fall das eine Karte nicht vorkommt wenn man unendlich oft zieht kann nicht vorkommen - wäre dies möglich dann hätten wir ja keine Gleichverteilung.Die Karte die nicht vorkommt hätte die Wahrscheinlichkeit 0 und alle anderen gezogenen Karten hätten eine von 0 verschiedene Wahrscheinlichkeit was ein Widerspruch zur Gleichverteilung wäre.

Für die Aufgabenstellung heisst das : Auch wenn es sehr viele Karten gibt endet der Algorithmus irgendwann - man muss nur hinreichend oft ziehen (was - und da sind wir uns einig - unter Umständen sehr lang dauern kann)



Wenn auch der Fall eintreten darf dass die Karte nicht im Stapel vorhanden ist würde diese Art der Suche natürlich unendlich lange dauern - das habe ich aber so nicht aus der Aufgabenstellung lesen können.Zumindest wenn man nur bis Punkt 1 liest.


----------



## Marco13 (11. Nov 2009)

Nun, um fundierte Aussagen dazu zu machen, was passiert wenn man "unendlich oft zieht", müßte ich nochmal in einem Buch über Stochastik nachsehen. Werde ich aber nicht machen. Ich fand Stochastik nie so toll. Aber ich werde versuchen, mich hier mal der Notwendigkeit einer fundierten Argumentation zu entziehen, und deine Aussage...
_Die Karte die nicht vorkommt hätte die Wahrscheinlichkeit 0 und alle anderen gezogenen Karten hätten eine von 0 verschiedene Wahrscheinlichkeit was ein Widerspruch zur Gleichverteilung wäre._
...gegen dich verwenden bae:  ) :
Wie oft muss man ziehen, damit die Wahrscheinlichkeit, die gesuchte Karte zu finden, 1 ist?


----------



## tfa (12. Nov 2009)

Wieso Gleichverteilung? In der Aufgabe steht nur etwas von "Zufall". Die Auswahl der Karte muss ja nicht gleichverteilt sein. Außerdem wissen wir nicht, ob es nur endlich viele Karten gibt. Falls nicht, ist es denkbar, dass es _fast ausgeschlossen_ ist, eine bestimmte Karte zu ziehen. Das heißt, die Wahrscheinlichkeit ist 0, trotzdem ist es doch möglich. Die Informationen der Aufgabenstellung reichen nicht aus, um sie sicher beantworten zu können.


----------



## Painii (12. Nov 2009)

tfa hat gesagt.:


> Außerdem wissen wir nicht, ob es nur endlich viele Karten gibt.


Davon sollte man denk ich ausgehen, wenn man sich einen "normalen Karteikasten" vorstellt.

Das Argument was passiert wenn die Karte nicht enthalten ist ist find ich das sinnvollste für Algorithmus 1.


----------



## Wang (12. Nov 2009)

Vielen Dank für die rege Teilnahme an meinem Thread! 
Ich habe jetzt nur das Problem, dass ich als "Informatik-Erstie" nicht weiß, wem ich glauben soll, da irgendwie jeder Recht hat.

Marco13:
Du bist im Besitz der Musterlösung von exakt der gleichen Aufgabe?

Wenn ja, dann wäre es super, wenn du die Argumentation der Musterlösung hier reinstellen könntest...

Danke.


----------



## Marco13 (12. Nov 2009)

Och, sooo super wäre das gar nicht. Schau' dir die Argumente hier im Thread an, und denke darüber nach, und wenn du dann etwas schreibst, was als "falsch" gewertet wird, ist das ja auch nicht weiter schlimm. Es ging ja bisher ohnehin nur um das erste Verfahren, und das ist nur ein Teil der (5.?) Aufgabe... Halte dich mit so einer Detailfrage nicht zuuu lange auf (die Musterlösung, die ich noch von damals habe, ethält auch einige Passagen, die man mit "das kann man nich so genau sagen" zusammenfassen könnte  )


----------



## HansPaulKlaus (12. Nov 2009)

tfa hat gesagt.:


> Wieso Gleichverteilung? In der Aufgabe steht nur etwas von "Zufall". Die Auswahl der Karte muss ja nicht gleichverteilt sein.



Wenn keine weiteren Angaben gemacht werden kann man eigentlich immer von der Gleichverteilung ausgehen.Ansonsten würde in der Aufgabe stehen wie es denn anders verteilt sein soll.

@Wang

Wenn Du auf Nummer sicher gehen willst : Unterstell bei Deiner Lösung einfach dass auch der Fall eintreten kann dass die gesuchte Karte nicht im Stapel ist.Denn dann terminiert der Algorithmus niemals - Da sind sich alle Verfasser die sich bisher gemeldet haben einig.Der Algorithmus wäre nicht mehr total korrekt - aber immer noch partiell korrekt (weil wenn der Algorithmus anhält - dann ist auch die Lösung richtig)


----------



## Wang (12. Nov 2009)

Danke, HansPaulKlaus.

Leider wurde wegen dem "Wortgefecht" meine Frage aus Beitrag Nummer 14 übersehen... Wäre nett, wenn sich dazu noch jemand äußern könnte. 

Thanks.


----------



## HansPaulKlaus. (12. Nov 2009)

Wang hat gesagt.:


> Danke, HansPaulKlaus.
> Leider wurde wegen dem "Wortgefecht" meine Frage aus Beitrag Nummer 14 übersehen... Wäre nett, wenn sich dazu noch jemand äußern könnte.
> Thanks.



Das kommt jetzt drauf an welcher Argumentation man folgen möchte.Für meine gilt :

Determiniertheit : Ja

Determinismus : Nein

Die beiden Begriffe klingen gleich muss man aber trennen.


Determiniertheit -> Du hast einen Algorithmus der für eine bestimmte Eingabe immer das gleiche Ergebnis ausgibt.Dabei kann es Dir ganz egal sein wie der Algorithmus das macht.Beim Determinismus müsste man noch überprüfen ob der Algorithmus auch immer den gleichen "Rechenweg" einschlägt.Da in diesem Beispiel die Karten zufällig gezogen werden ist der "Rechenweg" natürlich nicht immer gleich.

Wenn man unterstellt dass der Algorithmus terminiert dann wäre er in diesem Beispiel auch determiniert.(Denn wenn die Karte im Stapel ist wird sie auch immer gefunden und die Ausgabe "Karte gefunden" ist immer gleich)

Falls man das ganze so sehen möchte wie Marco13 dann wäre die ganze Geschichte nicht determiniert denn es könnte der Fall eintreten dass der Algorithmus die Karte in einem Durchlauf findet und in einem anderen nicht.(Er produziert also für die gleiche Eingabe zwei unterschiedliche Ergebnisse)


----------



## Wang (14. Nov 2009)

Nochmals vielen Dank an alle Helfer! :toll:

Ich bin jetzt den Weg von HansPaulKlaus gegangen und habe für die restlichen Suchvorgänge folgende Eigenschaften ermittelt:

Suchverfahren 2:
- terminierend
- nicht-deterministisch
- determiniert
- rekursiv (abhängig davon, ob die gewünschte Karte gefunden wurde, wird die Suche eingestellt oder fortgesetzt)
- partiell korrekt
- total korrekt


Suchverfahren 3:
- terminierend
- nicht-deterministisch ("Mitte" ist nicht genau definiert)
- determiniert
- rekursiv (einerseits wegen der Möglichkeit des Aufrufs von "Unterstützung", andererseits wegen der Auswahl innerhalb der Unterstützung selbst, dadurch, dass es mehr Unterstützer als Karteikarten gibt)
- partiell korrekt
- total korrekt


Suchverfahren 4:
- terminierend
- deterministisch (Reihenfolge des Ziehens ist festgelegt)
- determiniert
- nicht rekursiv
- partiell korrekt
- total korrekt


Suchverfahren 5:
- terminierend
- nicht-deterministisch ("Mitte" ist nicht klar definiert)
- determiniert
- rekursiv
- partiell korrekt
- total korrekt


Es wäre sehr nett, wenn jemand das korrigieren könnte. 

Vielen Dank.


----------



## HansPaulKlaus (14. Nov 2009)

Habe es nur kurz überflogen bei einem Kaffee - vielleicht habe ich nachher etwas mehr Zeit.Zwei Sachen sind mir aufgefallen bisher.

Verfahren 2 :

Da würde ich sagen dass es nicht rekursiv ist sondern iterativ.Du rufst ja keine Methode auf die dann ein Ergebnis an den Aufrufer zurückschickt.Du guckst einfach nur in deine Karteikartenbox : gefunden nein -> weitermachen oder gefunden ja : aufhören 

Das könnte man mit einer einfachen while-Schleife machen.


Verfahren 3 :

Ist Deterministisch - Weil wenn Du den gleichen Algorithmus auf die gleiche Karteikartenbox anwendest dann macht er immer das gleiche.Du kannst schon bevor der Algorithmus anfängt zu suchen genau vorhersagen wie er suchen wird und wann er aufhört.Der Unterschied zu Verfahren 1 ist - dort wird zufällig eine Karte gezogen.Man kann also nicht vorhersagen wo der Algorithmus die Karten sucht.


----------



## Marco13 (14. Nov 2009)

2.: Man könnte diesen Algorithmus zwar rekursiv implementieren, aber ... ich denke nicht, dass das hier gemeint ist....
3. und 5.: Bei Karten "A,B und C" ist ... welche Karte die mittlere?


----------



## Wang (14. Nov 2009)

Vielen Dank, HansPaulKlaus und Marco13 für Euren sehr starken Einsatz!


----------



## Ezra (14. Nov 2009)

> Der Fall das eine Karte nicht vorkommt wenn man unendlich oft zieht kann nicht vorkommen - wäre dies möglich dann hätten wir ja keine Gleichverteilung.Die Karte die nicht vorkommt hätte die Wahrscheinlichkeit 0 und alle anderen gezogenen Karten hätten eine von 0 verschiedene Wahrscheinlichkeit was ein Widerspruch zur Gleichverteilung wäre.


Deine Argumentation zeigt nur, dass Du den Unterschied zwischen relativer Häufigkeit und Wahrscheinlichkeit nicht begriffen hast. Wenn die Karten im praktischen Versuch kein einziges Mal gezogen werden, ist nur ihre relative Häufigkeit 0, nicht aber ihre Wahrscheinlichkeit.
Der Algorithmus 1 ist definitiv nicht mit Sicherheit terminierend, auch wenn es äußerst wahrscheinlich ist, dass er trotzdem irgendwann terminiert.

Übrigens ist das der einzige Unterschied zum zweiten Algorithmus, der genau diesen offenbar verdeutlichen soll.


----------



## Wang (17. Nov 2009)

Hier die Musterlösung für alle Interessierten.


----------

