Algorithmen und Eigenschaften

[Wang]

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:
1. Sie greifen zufällig eine Karte heraus.
2. Hat diese den gewünschten Titel, so sind Sie fertig, ansonsten legen Sie sie zurück und wiederholen das Verfahren ab Schritt 1.


Suchverfahren 2:
1. Sie greifen zufällig eine Karte heraus.
2. Trägt diese den gewünschten Titel, so legen Sie die Karte auf einen Ergebnisstapel, ansonsten legen Sie sie auf die Seite.
3. Ist der Kasten leer, so beenden Sie die Suche.
4. Ansonsten wiederholen Sie das Verfahren ab Schritt 1.


Suchverfahren 3:
1. Sie greifen die Karte heraus, die in der Mitte liegt.
2. Trägt diese den gewünschten Titel, so sind Sie fertig, ansonsten rufen Sie nach Unterstützung (es stehen mehr Helfer als Karteikarten zur Verfügung).
3. In der ersten Hälfte des Kastens suchen Sie weiter beginnend mit Schritt 1, in der zweiten Hälfte sucht ihre Unterstützung nach dem selben Verfahren auch beginnend mit Schritt 1.
4. Das Verfahren ist beendet, wenn jeder entweder eine Karte gefunden hat oder nur mehr leere Kartenabschnitte hat.


Suchverfahren 4:
1. Sie greifen die erste Karte.
2. Trägt diese den gewünschten Titel, so legen Sie diese auf den Ergebnisstapel.
3. Ist der Kasten noch nicht leer, nehmen Sie die nächste Karte und setzen die Suche bei Schritt 2 fort.


Suchverfahren 5: (Vorbedingung: Karteikasten ist lexikographisch sortiert)
1. Sie greifen die Karte, die in der Mitte liegt.
2. Trägt diese den gewünschten Titel, legen Sie die Karte auf den Ergebnisstapel und gehen zu Schritt 6, ansonsten:
3. Ist der gesuchte Titel alphabetisch vor dem Titel auf der ausgewählten Karte, so suchen Sie nur noch in der ersten Hälfte nach dem gleichen Verfahren ab Schritt 1 weiter.
4. Ist der gesuchte Titel alphabetisch hinter dem Titel auf der ausgewählten Karte, so suchen Sie nur noch in der zweiten Hälfte nach dem gleichen Verfahren ab Schritt 1 weiter.
5. Das Verfahren ist erfolglos beendet, wenn der letzte Kartenabschnitt leer ist.
6. Untersuchen Sie die nachfolgende Karte auf den gesuchten Titel. Falls die Karte ebenfalls diesen Titel trägt, legen Sie sie auf den Ergebnisstapel. Und wiederholen Schritt 6.
7. Untersuchen Sie die vorhergehende Karte auf den gesuchten Titel. Falls die Karte ebenfalls diesen Titel trägt, legen Sie sie auf den Ergebnisstapel. Und wiederholen Schritt 7.
8. Das Verfahren ist mit allen Ergebnissen beendet, wenn keine angrenzende Karte mehr auftritt, die den gesuchten Titel trägt.


Vergleichen Sie die oben angeführten Suchverfahren. Welcher Algorithmus erfüllt welche der folgenden Eigenschaften? Begründen Sie Ihre Antworten!

- terminierend
- deterministisch
- determiniert
- rekursiv
- partiell korrekt
- total korrekt

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]

>terminierend

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

 

[diggaa1984]

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

 

[Marco13]

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]

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

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]

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

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

Das erste Verfahren ist nicht rekursiv *wink*

 

[HansPaulKlaus]

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]

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]

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]

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]

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]

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

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]

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]

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]

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]

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]

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]

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]

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

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]

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]

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]

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]

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

 

[Ezra]

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]

Hier die Musterlösung für alle Interessierten.