Hallo, JAVA-Freunde! :toll:
Ich bitte um etwas Unterstützung bei der folgenden Aufgabe:
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!
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!