Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Was gehört ins Urteil?
AFB ISie sollen die Effizienz zweier Verfahren für eine Anwendung beurteilen. Nennen Sie alle Gesichtspunkte, die in das Urteil gehören.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Effizienz meint den Verbrauch von Rechenzeit und Speicher — abhängig von den Daten und ihrer Nutzung. Kurzer Code ist nicht automatisch schneller Code.
Ansatz: Fragen Sie bei jedem Punkt: Ändert er die Zahl der Operationen oder den Speicher?
Weiter: Zwei Punkte haben mit Effizienz nichts zu tun.
A2
Bester und ungünstigster Fall
AFB IGeben Sie die Wachstumsklassen der Vergleichszahlen an. Schreiben Sie z. B. O(n) oder O(n^2).
Füllen Sie alle Felder aus und prüfen Sie dann. Schreiben Sie Quadrate als
n^2 oder n².| Verfahren | bester Fall | ungünstigster Fall |
|---|---|---|
| lineare Suche | ||
| Insertionsort | ||
| Selectionsort |
Insertionsort profitiert von sortierten Daten (\(n - 1\) Vergleiche), Selectionsort nicht: Er vergleicht immer \(\frac{n(n-1)}{2}\)-mal. Die lineare Suche kann schon beim ersten Element fertig sein.
Ansatz: Bester Fall: Wann ist das Verfahren am schnellsten fertig?
Weiter: Selectionsort hat keine Abbruchmöglichkeit.
A3
Grenzen der Reihungslänge
AFB IIZwei Programme sortieren eine Reihung der Länge n mit Selectionsort. Dabei gilt: Selectionsort braucht für jede Eingabe genau \(\frac{n(n-1)}{2}\) Vergleiche. Ermitteln Sie in beiden Runden mit dem Regler die gesuchte Länge n.
Verschiebe den Regler (ziehen oder auf die Skala tippen) bzw. nutze die Knöpfe − und +; die Werte darüber laufen live mit. Tastatur: Tab zum Regler, ←/→ ein Schritt, Bild↑/Bild↓ zehn Schritte, Pos1/Ende Anfang/Ende, Enter prüft.
Runde 1: Bei n = 224 sind es 24 976 Vergleiche und damit 49 952 µs (knapp unter 50 000 µs); bei n = 225 wären es 25 200 Vergleiche und 50 400 µs. Runde 2: n = 100 ergibt genau 4 950 Vergleiche und ist noch zu wenig, erst n = 101 liefert 5 050 Vergleiche.
Die Zahl der Vergleiche steigt mit n schneller als n selbst. Stellen Sie den Regler so ein, dass die Zielzeile gerade noch (Runde 1) bzw. gerade erst (Runde 2) erfüllt ist.
Probieren Sie in der ersten Runde die Werte um 224, in der zweiten die Werte um 100. Achten Sie in Runde 2 auf „mehr als“ — 4 950 genügt nicht.