MINT lernen

Übung — AFB II (Zusammenhänge herstellen)

Zehn Anwendungsaufgaben zum ganzen Kapitel — von Diagonalen und Suchverläufen bis zum Hochrechnen von Laufzeiten.

Dein Fortschritt:
0 / 0 Aufgaben
2

Aufgabenblock — AFB II

Zehn Aufgaben aus allen Unterkapiteln mit Schwerpunkt Effizienz: Programme analysieren, Suchen und Sortieren verfolgen, Operationen zählen, Laufzeiten hochrechnen und Speicher berechnen — mit gestuften Tipps, wenn du nicht weiterkommst.

A1
Zwei Diagonalen
AFB II

Für eine quadratische Tabelle int[][] m = {{3, 1, 4}, {1, 5, 9}, {2, 6, 5}}; läuft:

int s = 0, t = 0;
for (int i = 0; i < m.length; i++) {
    s = s + m[i][i];
    t = t + m[i][m.length - 1 - i];
}

Analysieren Sie das Programm: Welche Werte haben s und t am Ende?

Ansatz: m[i][i] liegt auf der Hauptdiagonale, m[i][2 − i] auf der Gegendiagonale.
Rechenweg: s: m[0][0] + m[1][1] + m[2][2]; t: m[0][2] + m[1][1] + m[2][0].
Lösung: a) 13 b) 11
Vollständige Lösung
s = 3 + 5 + 5 = 13, t = 4 + 5 + 2 = 11. Das mittlere Element 5 zählt in beiden Summen. Der Durchlauf braucht nur \(n\) Schritte, nicht \(n^2\) — es werden nur zwei Einträge je Zeile gelesen.
A2
Suche ohne Treffer
AFB II

In der sortierten Reihung

wird binär nach 36 gesucht. Untersuchen Sie den Ablauf: Wie viele Vergleiche finden statt, und welche Werte haben links und rechts am Ende?

Ansatz: Erste Mitte (0 + 11) / 2 = 5.
Rechenweg: Mitten 5 (26), 8 (40), 6 (31), 7 (35); danach links = 8, rechts = 7.
Lösung: a) 4 b) 8 c) 7
Vollständige Lösung
26 < 36 → links = 6; 40 > 36 → rechts = 7; 31 < 36 → links = 7; 35 < 36 → links = 8. Nun ist links > rechts: Rückgabe −1 nach 4 Vergleichen. Die Grenzen zeigen auf die Nachbarn 35 (Index 7) und 40 (Index 8), zwischen denen 36 stehen müsste.
A3
Zwei Verfahren, n = 12
AFB II

Vergleichen Sie Selectionsort und Bubblesort mit Abbruch auf einer bereits sortierten Reihung mit 12 Elementen: Wie viele Vergleiche braucht jedes Verfahren?

Ansatz: Selectionsort nutzt keine Vorsortierung.
Rechenweg: Selectionsort \(\frac{12 \cdot 11}{2}\); Bubblesort: ein Durchlauf ohne Tausch mit \(n - 1\) Vergleichen, dann Abbruch.
Lösung: a) 66 b) 11
Vollständige Lösung
Selectionsort sucht in jedem Durchlauf das Minimum im ganzen Rest: \(11 + 10 + \ldots + 1 = 66\). Bubblesort mit Abbruch bemerkt im ersten Durchlauf, dass nichts getauscht wurde, und hört nach 11 Vergleichen auf.
A4
Insertionsort im ungünstigsten Fall
AFB II

Die Reihung {6, 5, 4, 3, 2, 1} wird mit Insertionsort aufsteigend sortiert. Ermitteln Sie die Zahl der Vergleiche und der Verschiebungen.

Ansatz: Jedes neue Element ist kleiner als alle davor.
Rechenweg: Das Element an Index i wird mit allen i Elementen davor verglichen und schiebt alle nach rechts: 1 + 2 + 3 + 4 + 5.
Lösung: a) 15 b) 15
Vollständige Lösung
Umgekehrt sortiert ist der ungünstigste Fall: \(\frac{n(n-1)}{2} = \frac{6 \cdot 5}{2} = 15\) Vergleiche und ebenso viele Verschiebungen — jedes Paar steht falsch herum.
A5
Schleifen zählen
AFB II
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        z++;                         // Fragment 1

for (int k = n; k > 1; k = k / 2)
    y++;                             // Fragment 2

Bestimmen Sie, wie oft z++ für \(n = 20\) und y++ für \(n = 100\) ausgeführt wird.

Ansatz: Fragment 1: Für festes i läuft j von i bis n − 1. Fragment 2: Werte von k aufschreiben.
Rechenweg: Fragment 1: \(20 + 19 + \ldots + 1\). Fragment 2: k = 100, 50, 25, 12, 6, 3 (ganzzahlig halbiert).
Lösung: a) 210 b) 6
Vollständige Lösung
\(\frac{20 \cdot 21}{2} = 210\) (die innere Schleife beginnt bei j = i, deshalb \(n + 1\) statt \(n - 1\) im Zähler). Fragment 2 läuft für k = 100, 50, 25, 12, 6, 3 — sechsmal, also \(\lfloor\log_2 100\rfloor = 6\).
A6
Hochrechnen
AFB II

Ein Algorithmus braucht \(T(n) = 5n^2 + 3n\) Schritte. Schätzen Sie ab, um welchen Faktor (gerundet auf eine ganze Zahl) \(T\) steigt, wenn \(n\) von 1000 auf 2000 steigt. Ein anderes \(O(n^2)\)-Programm braucht für 1000 Werte 2 s — wie viele Sekunden für 5000 Werte?

Ansatz: Für große \(n\) zählt nur \(5n^2\).
Rechenweg: \(\frac{T(2000)}{T(1000)} = \frac{20\,006\,000}{5\,003\,000} \approx 4\); Faktor 5 bei \(n\) → Faktor 25 bei der Zeit.
Lösung: a) 4 b) 50
Vollständige Lösung
Der Summand \(3n\) fällt kaum ins Gewicht: Faktor 3,999 ≈ 4. Beim zweiten Programm: \(\left(\frac{5000}{1000}\right)^2 = 25\), also \(25 \cdot 2\,\text{s} = 50\,\text{s}\).
A7
Speicher rechnen
AFB II

Berechnen Sie den Nutzspeicher von new double[1000][1000] in Byte und die Anzahl der int-Werte, die in 2 GB (\(2 \cdot 10^9\) Byte) passen.

Ansatz: double 8 Byte, int 4 Byte.
Rechenweg: \(10^6 \cdot 8\); \(2 \cdot 10^9 : 4\).
Lösung: a) 8 000 000 b) 500 000 000
Vollständige Lösung
Eine Million double-Werte belegen 8 MB. In 2 GB passen \(5 \cdot 10^8\) int-Werte — theoretisch; praktisch begrenzt Java die Länge einer Reihung auf etwas über \(2 \cdot 10^9\) Elemente, und der Speicher wird auch für anderes gebraucht.
A8
Ab wann lohnt sich Sortieren?
AFB II

400 unsortierte Werte sollen \(k\)-mal durchsucht werden: entweder \(k\) lineare Suchen oder einmal Selectionsort und dann \(k\) binäre Suchen (jeweils ungünstigster Fall). Leiten Sie her, ab welchem kleinsten \(k\) die zweite Variante weniger Vergleiche braucht.

Ansatz: Stellen Sie beide Kosten als Term in \(k\) auf.
Rechenweg: Linear: \(400k\). Sortieren: \(\frac{400 \cdot 399}{2} = 79\,800\), binär je \(\lfloor\log_2 400\rfloor + 1 = 9\). Ungleichung \(400k > 79\,800 + 9k\).
Lösung: 205
Vollständige Lösung
\(391k > 79\,800 \Leftrightarrow k > 204{,}1\), also ab \(k = 205\). Die Faustregel \(\frac{n}{2} = 200\) liegt nahe dran.
A9
Mittel und Maximum
AFB II

Bestätigen Sie durch Rechnung: Die lineare Suche braucht bei 99 Elementen im Mittel 50 Vergleiche, wenn der Wert vorkommt und jede Position gleich wahrscheinlich ist. Geben Sie außerdem die Zahl der Vergleiche der binären Suche im ungünstigsten Fall für \(n = 1000\) an.

Ansatz: Mittelwert von 1, 2, …, n.
Rechenweg: \(\frac{n + 1}{2}\); \(2^9 = 512 \le 1000 < 1024\).
Lösung: a) 50 b) 10
Vollständige Lösung
Treffer an Position \(i\) kostet \(i + 1\) Vergleiche; der Mittelwert von 1 bis 99 ist \(\frac{99 + 1}{2} = 50\) — bestätigt. Binär: \(9 + 1 = 10\).
A10
Falsch stehende Paare
AFB II

Für {5, 1, 4, 2, 3} gilt die Behauptung: „Bubblesort braucht genau so viele Vertauschungen wie Insertionsort Verschiebungen.“ Weisen Sie das nach, indem Sie beide Anzahlen bestimmen.

Ansatz: Zählen Sie die Paare \((i, j)\) mit \(i < j\) und \(a[i] > a[j]\).
Rechenweg: Falsch stehende Paare: (5,1), (5,4), (5,2), (5,3), (4,2), (4,3).
Lösung: a) 6 b) 6
Vollständige Lösung
Jede Vertauschung benachbarter Elemente (Bubblesort) und jede Verschiebung (Insertionsort) beseitigt genau ein falsch stehendes Paar. Es gibt 6 solche Paare — also beide Male 6. Ein Tausch braucht aber drei Zuweisungen, eine Verschiebung nur eine.