Tweet
Hab hier ne Aufgabe und komm mit Aufgabe d) und e) nicht zurecht. Hab im Netzt schon unzählige Defs gelesen, weiß aber nicht, welcher nun partiell und total korrekt ist. Können auch alle sein. Wäre euch dankbar für Hilfe 
Stellen Sie sich einen Karteikasten vor, in dem Sie nach einer Karteikarte mit einem bestimmten Titel suchen.
Gehen Sie dabei von folgenden Annahmen aus:
Der Karteikasten enth¨alt nicht mehrere Karteikarten mit dem selben Titel.
Der Karteikasten enth¨alt beim Aufruf des Algorithmus mindestens eine Karte.
Eine g¨ultige Eingabe ist auch ein Titel, der nicht im Karteikasten vorkommt.
Suchverfahren 1:
(1) Sie nehmen die erste Karte aus dem Karteikasten heraus.
(2) Sie geben diese Karte zur¨uck.
Suchverfahren 2:
(1) Sie greifen zuf¨allig eine Karte heraus.
(2) Hat diese den gew¨unschten Titel, so sind Sie fertig, ansonsten legen Sie sie zur¨uck und wiederholen das
Verfahren ab Schritt 1.
Suchverfahren 3:
(1) Sie greifen zuf¨allig eine Karte heraus.
(2) Hat diese den gew¨unschten Titel, so sind Sie fertig, ansonsten legen Sie sie zur¨uck. (3) Sind seit Beginn
der Suche zehn Minuten vergangen, geben Sie auf und beenden die Suche. (4) Ansonsten wiederholen Sie das
Verfahren ab Schritt 1.
Suchverfahren 4:
(1) Sie greifen zuf¨allig eine Karte heraus.
(2) Tr¨agt diese den gew¨unschten 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 5: (Vorbedingung: Karteikasten ist lexikographisch sortiert)
(1) Sie greifen die Karte, die in der Mitte liegt.
(2) Tr¨agt diese den gew¨unschten Titel, legen Sie die Karte auf den Ergebnisstapel und beenden die Suche, ansonsten:
(3) Ist der gesuchte Titel alphabetisch vor dem Titel auf der ausgew¨ahlten Karte, so suchen Sie nur noch in der
ersten H¨alfte nach dem gleichen Verfahren ab Schritt 1 weiter.
(4) Ist der gesuchte Titel alphabetisch hinter dem Titel auf der ausgew¨ahlten Karte, so suchen Sie nur noch in
der zweiten H¨alfte nach dem gleichen Verfahren ab Schritt 1 weiter.
(5) Das Verfahren ist erfolglos beendet, wenn der letzte Kartenabschnitt leer ist.
Vergleichen Sie die oben angef¨uhrten Suchverfahren. Welcher Algorithmus erf¨ullt welche der folgenden Eigenschaften?
(a) terminierend
(b) deterministisch
(c) determiniert
(d) partiell korrekt
(e) total korrekt
Danke für euer Bemühen
Stellen Sie sich einen Karteikasten vor, in dem Sie nach einer Karteikarte mit einem bestimmten Titel suchen.
Gehen Sie dabei von folgenden Annahmen aus:
Der Karteikasten enth¨alt nicht mehrere Karteikarten mit dem selben Titel.
Der Karteikasten enth¨alt beim Aufruf des Algorithmus mindestens eine Karte.
Eine g¨ultige Eingabe ist auch ein Titel, der nicht im Karteikasten vorkommt.
Suchverfahren 1:
(1) Sie nehmen die erste Karte aus dem Karteikasten heraus.
(2) Sie geben diese Karte zur¨uck.
Suchverfahren 2:
(1) Sie greifen zuf¨allig eine Karte heraus.
(2) Hat diese den gew¨unschten Titel, so sind Sie fertig, ansonsten legen Sie sie zur¨uck und wiederholen das
Verfahren ab Schritt 1.
Suchverfahren 3:
(1) Sie greifen zuf¨allig eine Karte heraus.
(2) Hat diese den gew¨unschten Titel, so sind Sie fertig, ansonsten legen Sie sie zur¨uck. (3) Sind seit Beginn
der Suche zehn Minuten vergangen, geben Sie auf und beenden die Suche. (4) Ansonsten wiederholen Sie das
Verfahren ab Schritt 1.
Suchverfahren 4:
(1) Sie greifen zuf¨allig eine Karte heraus.
(2) Tr¨agt diese den gew¨unschten 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 5: (Vorbedingung: Karteikasten ist lexikographisch sortiert)
(1) Sie greifen die Karte, die in der Mitte liegt.
(2) Tr¨agt diese den gew¨unschten Titel, legen Sie die Karte auf den Ergebnisstapel und beenden die Suche, ansonsten:
(3) Ist der gesuchte Titel alphabetisch vor dem Titel auf der ausgew¨ahlten Karte, so suchen Sie nur noch in der
ersten H¨alfte nach dem gleichen Verfahren ab Schritt 1 weiter.
(4) Ist der gesuchte Titel alphabetisch hinter dem Titel auf der ausgew¨ahlten Karte, so suchen Sie nur noch in
der zweiten H¨alfte nach dem gleichen Verfahren ab Schritt 1 weiter.
(5) Das Verfahren ist erfolglos beendet, wenn der letzte Kartenabschnitt leer ist.
Vergleichen Sie die oben angef¨uhrten Suchverfahren. Welcher Algorithmus erf¨ullt welche der folgenden Eigenschaften?
(a) terminierend
(b) deterministisch
(c) determiniert
(d) partiell korrekt
(e) total korrekt
Danke für euer Bemühen
Comment