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.