MINT lernen

Übungen: Effizienz beurteilen

Zehn Übungen zum Urteilen — von Fachbegriffen über Vergleichszahlen bis zur begründeten Stellungnahme.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Ü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 I

Sie 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 I

Geben 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².
Verfahrenbester Fallungü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
Fachbegriffe
AFB I

Ordnen Sie jeder Beschreibung den passenden Fachbegriff zu.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Diese Begriffe gehören in jede Begründung: Klasse, Speicher, Stabilität, betrachteter Fall und die Frage, ob sich ein Vorbereitungsschritt auszahlt.
Ansatz: Beginnen Sie mit den Begriffen, die Sie sicher kennen.
Weiter: „Vorverarbeitung“: z. B. einmal sortieren, dann oft binär suchen.
A4
Zufällige Daten
AFB II

500 zufällig angeordnete Werte werden sortiert. Insertionsort braucht auf zufälligen Daten im Mittel etwa \(\frac{n^2}{4}\) Vergleiche. Berechnen Sie die Vergleichszahlen.

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Selectionsort, n = 500: Vergleiche
  2. Insertionsort im Mittel, n = 500: Vergleiche
  3. Insertionsort, wenn die 500 Werte schon sortiert sind: Vergleiche
\(\frac{500 \cdot 499}{2} = 124\,750\) gegen \(\frac{500^2}{4} = 62\,500\): Insertionsort ist im Mittel etwa doppelt so schnell — beide bleiben aber quadratisch. Nur bei vorsortierten Daten wird Insertionsort linear.
Ansatz: Selectionsort: \(\frac{n(n-1)}{2}\).
Weiter: Vorsortiert: jedes Element ab Index 1 braucht genau einen Vergleich.
A5
Stimmt's? — Faustregeln
AFB II

Begründen Sie für sich jede Aussage und entscheiden Sie, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Gute Urteile nennen immer die Bedingung, unter der sie gelten.
Ansatz: Suchen Sie für jede Aussage einen Fall, in dem sie nicht gilt.
Weiter: Zeit und Speicher sind verschiedene Kriterien.
A6
Eigenschaften im Vergleich
AFB II Mix

Vergleichen Sie die Sortierverfahren: Markieren Sie jede Eigenschaft, die das Verfahren hat.

Klicken Sie die Felder an, die zutreffen. Ein zweiter Klick nimmt die Markierung zurück.
Verfahrenstabilin-placeschneller bei vorsortierten Daten
Selectionsort
Insertionsort
Bubblesort mit Abbruch
sortierte Kopie mit Insertionsort
Selectionsort tauscht über große Entfernungen und ist deshalb nicht stabil; er profitiert auch nicht von Vorsortierung. Eine Kopie ist nicht mehr in-place: Sie braucht \(O(n)\) Zusatzspeicher.
Ansatz: Stabil: Überholen sich gleiche Werte? In-place: Wird eine zweite Reihung angelegt?
Weiter: Denken Sie an das Beispiel 5a 5b 2 beim Selectionsort.
A7
Schon sortiert
AFB II Trick

Eine Reihung mit 10 000 Werten ist bereits aufsteigend sortiert. Bestimmen Sie, wie viele Vergleiche Selectionsort trotzdem ausführt.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
\(\frac{10\,000 \cdot 9\,999}{2} = 49\,995\,000\). Selectionsort merkt nicht, dass die Daten sortiert sind: Das Minimum wird in jedem Durchlauf im ganzen Rest gesucht. Insertionsort bräuchte nur 9 999 Vergleiche.
Ansatz: Hat Selectionsort eine Abbruchbedingung?
Weiter: \(\frac{n(n-1)}{2}\) mit \(n = 10\,000\).
A8
Urteil oder Behauptung?
AFB III

Schülerinnen und Schüler haben auf die Frage „Welches Verfahren ist effizienter?“ geantwortet. Beurteilen Sie jede Antwort.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1begründetes Urteil
2unvollständig
Ein Urteil nennt ein Kriterium, bezieht es auf die konkreten Daten und vergleicht mit der Alternative. Eine einzelne Zahl oder eine Messung auf einem Rechner reicht dafür nicht.
Ansatz: Prüfen Sie jede Antwort: Kriterium genannt? Auf die Situation bezogen? Mit Alternative verglichen?
Weiter: Drei Antworten erfüllen alle drei Punkte.
A9
Die Faustregel n/2 prüfen
AFB III

2000 unsortierte Werte; es werden \(k\) Suchen ausgeführt. Variante L sucht linear, Variante S sortiert einmal mit Selectionsort und sucht dann binär (jeweils ungünstigster Fall). Überprüfen Sie die Faustregel „Sortieren lohnt sich ab etwa \(\frac{n}{2}\) Suchen“ exakt.

Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
    Die Faustregel \(\frac{n}{2} = 1000\) liegt nur knapp neben dem exakten Wert 1006 — die binären Suchen fallen kaum ins Gewicht.
    Ansatz: Stellen Sie für beide Varianten die Kosten in Abhängigkeit von \(k\) auf.
    Weiter: Bringen Sie alle \(k\)-Terme auf eine Seite.
    A10
    Stellungnahme für die Bibliothek
    AFB III

    Die Schulbibliothek fragt, ob sich eine nach Autor sortierte Kopie ihres Bestands lohnt. Nehmen Sie Stellung, indem Sie die Begründung vervollständigen.

    Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
    Die Bibliothek hat 8000 Titel, sortiert nach Signatur. Gesucht wird nach dem Autor,
etwa 300-mal am Tag; der Bestand ändert sich einmal pro Woche.

Da die Titel nicht nach dem Autor sortiert sind, ist zunächst nur  möglich.
Eine nach Autor sortierte Kopie braucht  Zusatzspeicher und
muss nach jeder Änderung neu sortiert werden. Mit einfachem Sortieren lohnt das ab etwa  Suchen.
Pro Woche fallen 7 · 300 = 2100 Suchen an. Fazit:
    Zwischen zwei Änderungen gibt es 2100 Suchen — weniger als \(\frac{n}{2} = 4000\). Die lineare Suche kostet \(2100 \cdot 8000 = 16{,}8\) Mio. Vergleiche, das einfache Sortieren allein schon knapp 32 Mio. Mit einem schnellen Sortierverfahren (\(O(n \log n)\)) sähe es anders aus.
    Ansatz: Nach welchem Merkmal ist die Reihung sortiert, nach welchem wird gesucht?
    Weiter: Vergleichen Sie die Zahl der Suchen zwischen zwei Änderungen mit \(\frac{n}{2}\).