Aufgabenblock — AFB III
Begründen statt nur ausführen: Behauptungen widerlegen, Verfahren entwerfen und verändern, Formeln beweisen, Laufzeiten beurteilen und Stellung nehmen. Jede Aufgabe hat ein prüfbares Kernergebnis — formuliere die Begründung trotzdem in ganzen Sätzen, bevor du die Musterlösung aufklappst.
Tom behauptet: „Die binäre Suche braucht nie mehr als \(\frac{n}{2}\) Vergleiche.“ Widerlegen Sie die Behauptung mit einem Gegenbeispiel.
Geben Sie für Ihr Gegenbeispiel \(n = 3\) die Zahl der Vergleiche im ungünstigsten Fall an.
Musterlösung anzeigen
Musterlösung: Für \(n = 3\) wird zuerst Index 1 verglichen; liegt \(x\) darunter oder darüber, folgt ein zweiter Vergleich — 2 Vergleiche, aber \(\frac{3}{2} = 1{,}5\). Die Behauptung ist widerlegt. Richtig ist \(\lfloor\log_2 n\rfloor + 1\); erst ab \(n = 6\) liegt das nie über \(\frac{n}{2}\).
Minimum und Maximum einer Reihung einzeln zu suchen kostet \(2(n-1)\) Vergleiche. Entwerfen Sie ein Verfahren, das die Elemente paarweise betrachtet und mit weniger Vergleichen auskommt.
Wie viele Vergleiche braucht Ihr Verfahren für \(n = 100\)?
Musterlösung anzeigen
Musterlösung: Das erste Paar setzt mit einem Vergleich min und max. Für jedes weitere Paar \((a, b)\): a mit b vergleichen, dann das kleinere mit min und das größere mit max. Bei geradem \(n\): \(1 + 3 \cdot \frac{n-2}{2} = \frac{3n}{2} - 2\), für \(n = 100\) also 148 statt 198. Die Klasse bleibt \(O(n)\), der Faktor sinkt von 2 auf 1,5.
Beweisen Sie, dass Bubblesort ohne Abbruchbedingung für jede Eingabe der Länge \(n\) genau \(\frac{n(n-1)}{2}\) Vergleiche ausführt.
Wie viele Vergleiche sind es für \(n = 50\)?
Musterlösung anzeigen
Musterlösung: Im Durchlauf \(i\) (ab 0) vergleicht die innere Schleife die Paare an den Positionen 0 bis \(n - 2 - i\): \(n - 1 - i\) Vergleiche, unabhängig von den Werten. Summe über \(i = 0, \ldots, n - 2\): \((n-1) + \ldots + 1 = \frac{n(n-1)}{2}\). Für \(n = 50\): 1225.
Es soll \(T(n) = 3n^2 + 20n \in O(n^2)\) mit der Konstanten \(c = 4\) gezeigt werden. Zeigen Sie, ab welchem \(n_0\) die Ungleichung \(T(n) \le 4n^2\) gilt, und geben Sie das kleinste \(n_0\) an.
Musterlösung anzeigen
Musterlösung: Für \(n > 0\) ist \(3n^2 + 20n \le 4n^2\) gleichwertig zu \(20 \le n\). Mit \(c = 4\) und \(n_0 = 20\) ist die Definition erfüllt. Probe: \(n = 20\): \(1200 + 400 = 1600 = 4 \cdot 400\); \(n = 19\): \(1083 + 380 = 1463 > 1444\).
Algorithmus A braucht \(100 \cdot n \cdot \log_2 n\), Algorithmus B \(n^2\) Schritte. Beurteilen Sie für \(n = 1024\), welcher Algorithmus schneller ist, und ordnen Sie das Ergebnis in das asymptotische Verhalten ein.
Geben Sie den Unterschied B − A in Schritten an.
Musterlösung anzeigen
Musterlösung: A = 1 024 000, B = 1 048 576: A ist knapp schneller (Unterschied 24 576 Schritte, gut 2 %). Der Gleichstand liegt bei \(n = 100 \log_2 n\), also etwa bei \(n \approx 1000\); für kleinere \(n\) gewinnt B, für größere A — und zwar immer deutlicher, weil \(O(n \log n)\) langsamer wächst als \(O(n^2)\).
Implementieren Sie eine Methode static void umdrehen(int[] a), die die Reihenfolge der Elemente in-place umkehrt.
Wie viele Vertauschungen braucht Ihre Methode für eine Reihung mit 11 Elementen?
for (int i = 0; i < a.length / 2; i++) tauscht a[i] und a[a.length - 1 - i].Musterlösung anzeigen
Musterlösung: for (int i = 0; i < a.length / 2; i++) { int h = a[i]; a[i] = a[a.length - 1 - i]; a[a.length - 1 - i] = h; } — für \(n = 11\) sind das \(\lfloor 11/2 \rfloor = 5\) Vertauschungen; das mittlere Element bleibt stehen. Zeit \(O(n)\), Zusatzspeicher \(O(1)\).
Unter 1000 Kundennummern zwischen 0 und 999 999 sollen doppelte gefunden werden. Bewerten Sie die beiden Verfahren „paarweise vergleichen“ und „Markierungsreihung boolean[1_000_000]“.
Geben Sie die Vergleiche des ersten Verfahrens im ungünstigsten Fall und den Zusatzspeicher des zweiten in Byte an.
Musterlösung anzeigen
Musterlösung: Paarweise: 499 500 Vergleiche, Speicher \(O(1)\). Markierung: 1000 Markierungen, aber 1 MB Speicher (und das Anlegen setzt \(10^6\) Plätze auf false). Bei nur 1000 Werten sind beide Verfahren in Millisekunden fertig; der Speicher der Markierungsreihung ist 250-mal so groß wie die Daten selbst. Hier ist das paarweise Vergleichen völlig ausreichend — bei \(10^6\) Kundennummern wäre die Markierungsreihung klar überlegen.
Beim Insertionsort wird die Einfügestelle linear gesucht. Verändern Sie das Verfahren so, dass die Einfügestelle im bereits sortierten Teil binär gesucht wird, und beurteilen Sie die neue Laufzeit.
Wie viele Vergleiche braucht das Suchen der Einfügestelle höchstens, wenn der sortierte Teil 1000 Elemente hat?
Musterlösung anzeigen
Musterlösung: Die Suche der Stelle kostet nur noch höchstens 10 statt 1000 Vergleiche; insgesamt sinken die Vergleiche auf \(O(n \log n)\). Die Elemente rechts der Einfügestelle müssen aber weiterhin einzeln verschoben werden — im ungünstigsten Fall \(\frac{n(n-1)}{2}\) Verschiebungen. Die Laufzeit bleibt also \(O(n^2)\); die Änderung lohnt sich nur, wenn Vergleiche viel teurer sind als Verschiebungen (z. B. lange Texte).
Eine „ternäre Suche“ teilt den Bereich mit zwei Vergleichen in drei Teile. Für den ungünstigsten Fall gilt \(V(n) = 2 + V(\frac{n}{3})\), \(V(1) = 1\). Entscheiden Sie, ob sie für \(n = 81\) besser ist als die binäre Suche.
Musterlösung anzeigen
Musterlösung: Ternär: \(V(81) = 9\), binär: \(\lfloor\log_2 81\rfloor + 1 = 7\). Die ternäre Suche braucht zwar nur 4 statt 6 Schritte, zahlt aber je Schritt 2 Vergleiche: \(2 \log_3 n \approx 1{,}26 \log_2 n\). Entscheidung: die binäre Suche. Beide liegen in \(O(\log n)\) — die Konstante entscheidet.
Nehmen Sie Stellung zur Aussage: „Eine Kopie kostet \(O(n)\) Speicher, deshalb sind In-place-Verfahren immer vorzuziehen.“
Wie viele Byte belegt eine sortierte Kopie einer int-Reihung mit \(10^6\) Elementen?
Musterlösung anzeigen
Musterlösung: Die Kopie belegt 4 MB — auf einem heutigen Rechner wenig. Dafür bleibt die ursprüngliche Reihenfolge erhalten (etwa die zeitliche Reihenfolge von Messwerten), und andere Programmteile, die dieselbe Reihung nutzen, werden nicht gestört. In-place ist vorzuziehen, wenn Speicher knapp ist (sehr große Daten, kleine Geräte) oder das Original nicht mehr gebraucht wird. Die Aussage ist deshalb zu pauschal: \(O(n)\) Zusatzspeicher ist oft vertretbar.