Rückblick - Informatik

Das kann ich jetzt

Ich kann Testfälle systematisch auswählen: Normalfall, Grenzfälle, Sonderfälle. (7.1)

Ich kann einen Test mit assertEquals schreiben und eine brauchbare Meldung dazu formulieren. (7.1)

Ich kann begründen, warum „sieht plausibel aus" kein Test ist. (7.1)

Ich kann die Komplexitätsklassen benennen und einem Algorithmus zuordnen. (7.2)

Ich kann aus dem Aufbau eines Programms auf seine Klasse schließen. (7.2)

Ich kann Zeitbedarf und Speicherbedarf getrennt beurteilen. (7.2)

Gemischte Aufgaben

Aufgabe 1: Testfälle finden

Diese Methode soll das Maximum eines Feldes liefern:

public int maximum(int[] pWerte) {
    int groesster = 0;
    for (int i = 0; i < pWerte.length; i++) {
        if (pWerte[i] > groesster) {
            groesster = pWerte[i];
        }
    }
    return groesster;
}

a) Nenne fünf Testfälle: einen Normalfall, zwei Grenzfälle und zwei Sonderfälle.

b) Bei welchem deiner Testfälle liefert die Methode ein falsches Ergebnis? Warum?

c) Berichtige die Methode.

d) Schreib die Testklasse mit @Test und lass sie im Testrunner laufen. Alle Tests müssen grün sein.

e) Ein Sonderfall lässt sich nicht durch Berichtigen retten. Welcher, und wie geht man damit um?

Tipp zu a): Wo suche ich Testfälle?

Immer an denselben Stellen:

Normalfall: ein typisches Feld mit verschiedenen Werten.
Grenzfälle: das Maximum steht ganz vorn; es steht ganz hinten; das Feld hat genau ein Element.
Sonderfälle: alle Werte negativ; alle Werte gleich; ein leeres Feld.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Aufgabe 2: Klassen zuordnen

Bestimme für jeden Ausschnitt die Komplexitätsklasse in Abhängigkeit von n. Begründe mit einer der drei Faustregeln.

// a)
for (int i = 0; i < n; i++) {
    summe = summe + i;
}
 
// b)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        IO.println(i + " " + j);
    }
}
 
// c)
for (int i = 0; i < n; i++) {
    summe = summe + i;
}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        produkt = produkt * 2;
    }
}
 
// d)
int i = n;
while (i > 1) {
    i = i / 2;
}
 
// e)
for (int i = 0; i < n; i++) {
    int j = n;
    while (j > 1) {
        j = j / 2;
    }
}

Ordne danach zu: lineare Suche, binäre Suche, Bubblesort, Mergesort, Zugriff auf ein Feldelement.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Aufgabe 3: Beurteilen und entscheiden

a) Ein Programm braucht für 1000 Datensätze 2 Sekunden. Wie lange braucht es für 10 000, wenn es in O(n), in O(n · log n) und in O(n²) läuft? Rechne für jede Klasse.

b) Warum ist O(n²) für 1000 Elemente meist völlig unproblematisch, für 100 000 aber nicht mehr? Nenne konkrete Zahlen.

c) Ein Verfahren ist in O(n), braucht aber zusätzlichen Speicher in O(n). Ein anderes ist in O(n · log n) und braucht O(1) zusätzlichen Speicher. Wann würdest du welches wählen? Nenne je eine Situation.

d) Eine Kollegin sagt: „Mein Algorithmus ist O(n), der andere O(n²) – meiner ist also immer schneller." Nimm Stellung.

e) Warum ist eine gemessene Laufzeit allein kein guter Beleg für die Güte eines Verfahrens? Nenne zwei Gründe.

Tipp zu a)

Rechne mit Verhältnissen. Wird n verzehnfacht, dann wächst

O(n) um den Faktor 10,
O(n²) um den Faktor 100,
O(n · log n) um etwa 10 · (log 10 000 / log 1000) ≈ 13.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Selbsttest

1. Welche Testfälle gehören zu einer systematischen Auswahl? Wähle alle zutreffenden aus.

{c1{!ein typischer Normalfall}}

{c1{!die Grenzen des Wertebereichs}}

{c1{!Sonderfälle wie leere Eingaben}}

{c1{möglichst viele zufällige Eingaben}}

{h{Drei Sorten sind gemeint – die vierte ersetzt Nachdenken durch Menge.}} {H{Richtig.}}

2. Warum ist der Startwert 0 beim Suchen des Maximums gefährlich?

{r1{Weil 0 nicht im Feld vorkommt.}}

{r1{!Weil bei lauter negativen Werten ein Wert herauskommt, den es im Feld gar nicht gibt.}}

{r1{Weil die Schleife dann nicht läuft.}}

{r1{Er ist nicht gefährlich.}}

{h{Probier das Feld mit minus 5, minus 2 und minus 9 durch.}} {H{Richtig – der Startwert behauptet stillschweigend, kein Wert sei kleiner als 0.}}

3. Wozu dient die Meldung in assertEquals?

{r2{Sie wird immer ausgegeben.}}

{r2{!Sie erscheint beim Fehlschlag und soll erklären, was erwartet wurde.}}

{r2{Sie benennt den Test.}}

{r2{Sie ist nur Kommentar.}}

{h{Wer sie liest, hat gerade einen roten Test vor sich.}} {H{Richtig – Fehler hilft niemandem, eine erklärende Meldung schon.}}

4. Welche Klasse hat eine Schleife über n Elemente, in der eine Halbierung stattfindet?

{r3{O(n)}}

{r3{O(n²)}}

{r3{!O(n log n)}}

{r3{O(log n)}}

{h{Äußere Schleife mal innerer Vorgang.}} {H{Richtig.}}

5. Nacheinander laufen ein O(n)-Abschnitt und ein O(n²)-Abschnitt. Welche Klasse hat das Ganze?

{r4{O(n)}}

{r4{!O(n²)}}

{r4{O(n³)}}

{r4{O(n log n)}}

{h{Bei Anweisungen nacheinander gewinnt die größte Klasse.}} {H{Richtig – der kleinere Anteil fällt für große n nicht ins Gewicht.}}

6. Ein O(n²)-Programm braucht bei 1000 Elementen 2 Sekunden. Wie lange etwa bei 10 000?

{r5{20 Sekunden}}

{r5{!200 Sekunden}}

{r5{2 Sekunden}}

{r5{2000 Sekunden}}

{h{Zehnfaches n bedeutet hundertfacher Aufwand.}} {H{Richtig.}}

7. Ein Verfahren ist O(n), ein anderes O(n²). Welche Aussage stimmt?

{r6{Das erste ist immer schneller.}}

{r6{!Ab einer bestimmten Größe ist das erste schneller, und der Abstand wächst danach immer weiter.}}

{r6{Beide sind gleich schnell.}}

{r6{Das lässt sich ohne Messung gar nicht sagen.}}

{h{Konstante Faktoren fallen aus der Notation heraus – was heißt das für kleine Eingaben?}} {H{Richtig. Deshalb schalten Bibliotheken bei kleinen Feldern auf einfache Verfahren um.}}