Ausleihe in der Schulbibliothek
AFB I–IIDie Schulbibliothek speichert die Nummern der 1 500 ausgegebenen Leseausweise in einer Reihung. Bei jeder Ausleihe wird geprüft, ob die Nummer gültig ist. Zur Wahl stehen die lineare Suche auf der unsortierten Reihung und die binäre Suche auf einer sortierten Reihung.
- Geben Sie für beide Verfahren die Zahl der Vergleiche im besten und im ungünstigsten Fall an.
- Erläutern Sie, warum die lineare Suche bei einer gültigen Nummer im Mittel etwa \(\frac{n+1}{2}\) Vergleiche braucht, und nennen Sie die Voraussetzung dafür.
- Durch eine Kooperation mit zwei Nachbarschulen wächst die Zahl der Ausweise auf 6 000. Schätzen Sie ab, wie sich die Zahlen aus a) für den ungünstigsten Fall ändern.
- Skizzieren Sie in einem gemeinsamen Diagramm die Zahl der Vergleiche im ungünstigsten Fall beider Verfahren in Abhängigkeit von \(n\) für \(1 \le n \le 32\).
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Lineare Suche: bester Fall 1 (Nummer an Index 0), ungünstigster Fall 1 500 (Nummer ganz hinten oder ungültig). Binäre Suche: bester Fall 1 (Nummer in der ersten Mitte), ungünstigster Fall \(\lfloor\log_2 1500\rfloor + 1 = 10 + 1 = 11\), da \(2^{10} = 1024 \le 1500 < 2048\).
Erwartungshorizont zu Aufgabe b)
Steht die Nummer an Index \(i\), braucht die Suche \(i + 1\) Vergleiche, also je nach Position 1, 2, …, \(n\). Der Mittelwert ist \(\frac{1 + 2 + \ldots + n}{n} = \frac{n(n+1)/2}{n} = \frac{n+1}{2}\), hier \(750{,}5\). Voraussetzung: Die Nummer ist vorhanden, und jede Position ist gleich wahrscheinlich. Für ungültige Nummern gilt dagegen immer \(n\).
Erwartungshorizont zu Aufgabe c)
Die Datenmenge vervierfacht sich (zweimal verdoppelt). Lineare Suche: linear, also viermal so viele — 6 000 Vergleiche. Binäre Suche: pro Verdopplung ein Vergleich mehr, also \(11 + 2 = 13\); Kontrolle: \(2^{12} = 4096 \le 6000 < 8192\), \(\lfloor\log_2 6000\rfloor + 1 = 13\). Die besten Fälle bleiben bei 1.
Erwartungshorizont zu Aufgabe d)
Lineare Suche: Ursprungsgerade durch \((1\,|\,1)\) bis \((32\,|\,32)\) (Punkte, da \(n\) ganzzahlig). Binäre Suche: Treppe, die bei \(n = 1, 2, 4, 8, 16, 32\) um je eine Stufe auf 1, 2, 3, 4, 5, 6 springt und dazwischen waagerecht bleibt. Die Kurven stimmen bei \(n = 1\) und \(n = 2\) überein; danach öffnet sich die Schere immer weiter. Achsen beschriften (\(n\), Vergleiche).
Parkhaus mit Dauerparkern
AFB II–IIIEin Parkhaus hat 4 000 Dauerparker. Ihre Kennzeichen sind als Zahlencodes unsortiert in einer Reihung gespeichert. An jedem Tag fahren 900 Autos ein; bei jeder Einfahrt wird geprüft, ob der Code in der Reihung steht. Rechnen Sie jeweils mit dem ungünstigsten Fall und für das Sortieren mit einem einfachen Verfahren mit \(\frac{n(n-1)}{2}\) Vergleichen.
- Berechnen Sie die Zahl der Vergleiche an einem Tag, wenn stets linear gesucht wird, und die Zahl der Vergleiche, wenn die Reihung einmal sortiert und dann binär gesucht wird (Sortieren plus erster Tag).
- Ermitteln Sie, ab dem wievielten Tag sich das einmalige Sortieren insgesamt lohnt, wenn sich die Dauerparker nicht ändern.
- Vergleichen Sie den zusätzlichen Speicherbedarf beider Suchverfahren.
- Tatsächlich kommen jeden Tag etwa 50 neue Dauerparker hinzu, andere kündigen. Erörtern Sie, ob sich das Vorgehen „sortieren und binär suchen“ unter diesen Bedingungen noch lohnt.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Linear: \(900 \cdot 4000 = 3\,600\,000\) Vergleiche pro Tag. Sortieren: \(\frac{4000 \cdot 3999}{2} = 7\,998\,000\); binär \(\lfloor\log_2 4000\rfloor + 1 = 11 + 1 = 12\) Vergleiche pro Einfahrt, also \(900 \cdot 12 = 10\,800\) pro Tag. Sortieren plus erster Tag: \(8\,008\,800\).
Erwartungshorizont zu Aufgabe b)
| Tag d | nur linear | sortieren + binär |
|---|---|---|
| 1 | 3 600 000 | 8 008 800 |
| 2 | 7 200 000 | 8 019 600 |
| 3 | 10 800 000 | 8 030 400 |
Ansatz \(3\,600\,000\,d > 7\,998\,000 + 10\,800\,d \Leftrightarrow d > \frac{7\,998\,000}{3\,589\,200} \approx 2{,}23\). Ab dem 3. Tag ist das Sortieren insgesamt günstiger.
Erwartungshorizont zu Aufgabe c)
Beide Verfahren arbeiten in-place direkt auf der gegebenen Reihung. Die lineare Suche braucht nur die Laufvariable i, die binäre Suche links, rechts und mitte. Der Zusatzspeicher ist in beiden Fällen konstant, also unabhängig von \(n\); der Unterschied von zwei int-Variablen ist bedeutungslos. (Das Sortieren mit einfachen Verfahren braucht ebenfalls nur konstanten Zusatzspeicher.)
Erwartungshorizont zu Aufgabe d)
Dafür: Die Suche selbst bleibt mit 12 statt bis zu 4 000 Vergleichen pro Einfahrt extrem schnell; bei 900 Einfahrten am Tag ist der Suchaufwand der linearen Variante hoch. Dagegen: Jede Änderung muss die Sortierung erhalten. Täglich komplett neu zu sortieren kostet rund 8 Mio. Vergleiche — mehr als 3,6 Mio. für einen Tag lineare Suche. Günstiger ist es, jeden neuen Code an seine Stelle einzufügen: finden per binärer Suche, dann im Mittel etwa \(\frac{n}{2} = 2\,000\) Elemente verschieben; bei 50 Neuen etwa 100 000 Operationen, dazu Löschungen. Eine statische Reihung hat eine feste Länge, sie muss also größer angelegt oder neu erzeugt werden. Fazit: Mit Einfügen an der richtigen Stelle lohnt sich die sortierte Reihung weiterhin deutlich (etwa 0,1 Mio. + 0,01 Mio. gegen 3,6 Mio. Operationen pro Tag); tägliches Neusortieren mit einem einfachen Verfahren lohnt sich nicht. Eine begründete Abwägung mit Zahlen ist entscheidend.