Block 02 · Algorithmen & Programmierung

A · Erklärungssatz

In jeder der 9 ausgewerteten Prüfungen steht in Teil 2 (Aufgabe 1 oder 2) eine große Algorithmusaufgabe mit 25–30 Punkten. Fast immer bekommst du ein Klassendiagramm mit Attributen („Getter sind vorhanden“), eine Beispieltabelle mit Daten und eine Methodensignatur. Gesucht ist eine Methode, die eine Liste oder ein Array von Objekten durchläuft und dabei zählt, summiert, filtert, ein Ergebnis-Array füllt oder ein Minimum sucht. Ob du das in Pseudocode, als Struktogramm oder in einer Programmiersprache schreibst, ist meist freigestellt. Der Belegsatz enthält nur die Pseudocode-Konventionen, nicht die Muster. Die musst du können.

ALG-01 · Algorithmus in Pseudocode schreiben Immer

Vorkommen: 9/9 · Prüfungen: alle (W21–S26), Teil 2 Aufgabe 1 oder 2 mit 25–30 Punkten · zusätzlich kleinere Methoden in Teil 1 (S22, S23, S24, W24)

So sieht die Aufgabe aus

• Klassendiagramm (oft nur ein Kasten) mit privaten Attributen, dazu der Satz „Für alle Attribute existieren Get-Methoden“. Du greifst deshalb immer über Getter zu: k.getPreis(), nicht k.preis.
• Beispieldaten als Tabelle, oft mit „vorher → nachher“ (z. B. links die Rohdaten, rechts die erwartete Ergebnisliste). Diese Tabelle ist dein Testfall.
• Methodensignatur, manchmal schon mit erster und letzter Zeile (... return ergebnis). Halte dich an die vorgegebenen Namen und Typen.
• Hilfsmethoden, die du benutzen darfst, z. B. date.between(start, ende) (S26) oder DateTime.compare() (W24). Steht eine solche Methode in der Aufgabe, wird ihre Verwendung erwartet.
• Für Listen ein Kasten List<T> mit add, get, size, contains (eventuell remove). Andere Listenmethoden solltest du nicht voraussetzen.

Pseudocode-Bausteine (IHK-Stil) und ihre Java-Entsprechung

Der Belegsatz (S24) gibt nur die Grundformen vor. Für alles andere gilt: lesbar, eindeutig und konsequent. Diese Schreibweise wird in diesem Block durchgehend verwendet:

Die fünf Grundmuster

Fast jede Prüfungsaufgabe ist eine Kombination dieser Muster. Beispiel-Szenario hier: ein Lager mit Objekten der Klasse Artikel (Attribute artikelNr, bezeichnung, kategorie (1–4), bestand, mindestbestand, preis; Getter vorhanden).

Muster 1 – Zählen mit Bedingung (Rückgabe integer): Zähler vor der Schleife auf 0, in der Schleife bei erfüllter Bedingung um 1 erhöhen.

funktion zaehleNachbestellung(artikel : List<Artikel>) : integer
  anzahl : integer := 0
  zähle i von 0 bis artikel.size() - 1
    a : Artikel := artikel.get(i)
    wenn a.getBestand() < a.getMindestbestand() dann
      anzahl := anzahl + 1
    Ende wenn
  Ende zähle
  rückgabe anzahl
Ende funktion

Muster 2 – Summe und Durchschnitt (Rückgabe double): Summe und Anzahl mitführen, erst nach der Schleife teilen und den Fall „keine passenden Elemente“ abfangen.

funktion durchschnittspreis(artikel : List<Artikel>, kategorie : integer) : double
  summe : double := 0.0
  anzahl : integer := 0
  zähle i von 0 bis artikel.size() - 1
    wenn artikel.get(i).getKategorie() = kategorie dann
      summe := summe + artikel.get(i).getPreis()
      anzahl := anzahl + 1
    Ende wenn
  Ende zähle
  wenn anzahl = 0 dann
    rückgabe 0.0                      // keine Division durch 0
  Ende wenn
  rückgabe summe / anzahl
Ende funktion

Muster 3 – Filtern in eine neue Liste (Rückgabe List<T>): leere Ergebnisliste anlegen, passende Objekte mit add anhängen. Die Originalliste bleibt unverändert.

funktion nachbestellListe(artikel : List<Artikel>) : List<Artikel>
  ergebnis : List<Artikel> := new List<Artikel>()
  zähle i von 0 bis artikel.size() - 1
    a : Artikel := artikel.get(i)
    wenn a.getBestand() < a.getMindestbestand() dann
      ergebnis.add(a)
    Ende wenn
  Ende zähle
  rückgabe ergebnis
Ende funktion

Muster 4 – Ergebnis-Array „je …“ (Rückgabe integer[]): Ein Array, in dem jeder Index für eine Gruppe steht (Kategorie, Stunde, Strecke …). Der Wert des Datensatzes bestimmt den Index. Achte auf die Verschiebung, wenn die Gruppen bei 1 beginnen, der Index aber bei 0.

funktion artikelJeKategorie(artikel : Artikel[]) : integer[]
  ergebnis : integer[] := new integer[4]     // Index 0..3 = Kategorie 1..4, alle 0
  zähle i von 0 bis artikel.length - 1
    k : integer := artikel[i].getKategorie()
    ergebnis[k - 1] := ergebnis[k - 1] + 1
  Ende zähle
  rückgabe ergebnis
Ende funktion

Muster 5 – Eindeutige Liste und verschachtelte Schleifen. Aus Rohdaten mit Wiederholungen (viele Bestellungen je Lieferant) soll eine Liste mit genau einem Objekt je Schlüssel entstehen, danach wird für jedes dieser Objekte ein Wert aus allen Rohdaten berechnet. Beispiel: List<Bestellung> (Attribute lieferant, betrag) wird zu List<LieferantSumme> (Attribute lieferant, summe; Konstruktor LieferantSumme(lieferant) setzt summe auf 0).

// Schritt 1: jeden Lieferanten genau einmal aufnehmen
funktion erzeugeUebersicht(bestellungen : List<Bestellung>) : List<LieferantSumme>
  uebersicht : List<LieferantSumme> := new List<LieferantSumme>()
  zähle i von 0 bis bestellungen.size() - 1
    name : string := bestellungen.get(i).getLieferant()
    gefunden : boolean := false
    zähle j von 0 bis uebersicht.size() - 1
      wenn uebersicht.get(j).getLieferant() = name dann
        gefunden := true
      Ende wenn
    Ende zähle
    wenn nicht gefunden dann
      uebersicht.add(new LieferantSumme(name))
    Ende wenn
  Ende zähle
  rückgabe uebersicht
Ende funktion

// Schritt 2: für jedes Übersichtsobjekt (außen) alle Bestellungen (innen) durchlaufen
funktion berechneSummen(bestellungen : List<Bestellung>,
                        uebersicht : List<LieferantSumme>)
  zähle i von 0 bis uebersicht.size() - 1
    ls : LieferantSumme := uebersicht.get(i)
    summe : double := 0.0                      // für JEDES Objekt neu auf 0!
    zähle j von 0 bis bestellungen.size() - 1
      wenn bestellungen.get(j).getLieferant() = ls.getLieferant() dann
        summe := summe + bestellungen.get(j).getBetrag()
      Ende wenn
    Ende zähle
    ls.setSumme(summe)
  Ende zähle
Ende funktion

So gehst du vor

1. Signatur lesen: Was kommt hinein (Parameter), was muss heraus? integer → Zähler oder Summe, double → Durchschnitt, List → Filter, Array → „je Index“, Objekt → Suche/Minimum, void → vorhandene Objekte per Setter ändern.
2. Beispieldaten von Hand durchrechnen. Wenn du das erwartete Ergebnis der Beispieltabelle nicht selbst ausrechnen kannst, hast du die Aufgabe noch nicht verstanden.
3. Muster wählen (eins oder mehrere der fünf oben, dazu Minimum/Maximum aus ALG-03).
4. Variablen vor der Schleife anlegen und initialisieren. Bei verschachtelten Schleifen: Was gilt für alle Durchläufe (außen anlegen), was nur für ein äußeres Element (innen zurücksetzen)?
5. Schleife über alle Elemente: zähle i von 0 bis liste.size() - 1 bzw. bis feld.length - 1.
6. Bedingung mit Gettern formulieren. Jede Bedingung aus dem Aufgabentext einzeln abhaken („nicht defekt“, „im Zeitraum“, „mehr als …“: > oder >=?).
7. Nach der Schleife: Sonderfälle (Division durch 0, nichts gefunden → null), dann rückgabe.
8. Schreibtischtest mit zwei, drei Datensätzen aus der Tabelle der Aufgabe.

ALG-02 · Arrays und Listen durchlaufen Immer

Vorkommen: 9/9 · Arrays in 8/9 (2D-Arrays: W21, S22, S23), Listen List<T> in 5/9 mit steigender Tendenz (S22, W22, S24, W25, S26)

Eindimensionales Array

• Feste Anzahl von Elementen eines Datentyps, festgelegt beim Anlegen: new integer[24]. Die Größe kann sich danach nicht mehr ändern.
• Index von 0 bis length − 1. Ein Array mit 24 Elementen hat die Indizes 0 … 23.
• Neu angelegte Zahlen-Arrays sind in Java mit 0 gefüllt (Objekt-Arrays mit null). In Pseudocode schreibst du die Vorbelegung zur Sicherheit dazu, wenn du dich darauf verlässt.
• Zugriff auf einen ungültigen Index führt in Java zur ArrayIndexOutOfBoundsException, das Programm bricht ab (siehe ALG-07).
• Nachbarelemente (Differenz zwischen Element i und i + 1, wie die Fahrzeit zwischen zwei Haltestellen in W24): Die Schleife darf dann nur bis length - 2 laufen, sonst greift feld[i + 1] im letzten Durchlauf ins Leere.

Zweidimensionales Array (Tabelle)

Ein 2D-Array ist eine Tabelle: daten[zeile][spalte]. daten.length ist die Anzahl der Zeilen, daten[0].length die Anzahl der Spalten. Typische Prüfungsbeispiele: Tag × Stunde, Monat × Verbraucher. Beispiel hier: Kino mit 3 Sälen (Zeilen) und 4 Vorstellungen am Tag (Spalten), gespeichert wird die Besucherzahl.

zeilen : integer[]
zeilen := new integer[besucher.length]
zähle z von 0 bis besucher.length - 1
  summe : integer := 0
  zähle s von 0 bis besucher[z].length - 1
    summe := summe + besucher[z][s]
  Ende zähle
  zeilen[z] := summe
Ende zähle

spalten : integer[]
spalten := new integer[besucher[0].length]
zähle s von 0 bis besucher[0].length - 1
  summe : integer := 0
  zähle z von 0 bis besucher.length - 1
    summe := summe + besucher[z][s]
  Ende zähle
  spalten[s] := summe
Ende zähle

Merkhilfe: Die äußere Schleife läuft über das, wofür du je ein Ergebnis willst. Willst du je Saal eine Summe, läuft außen der Saal. Für eine Gesamtsumme oder ein Maximum über alle Zellen ist die Reihenfolge egal, dann reicht eine Variable außerhalb beider Schleifen.

Listen: List<T>

Eine Liste wächst und schrumpft dynamisch. In der Prüfung ist sie meist als Klasse List<T> mit wenigen Methoden vorgegeben (T steht für den Elementtyp, z. B. List<Artikel>). In Java entspricht das List<T> bzw. ArrayList<T>.

Duplikate vermeiden: Vor dem add prüfen, ob das Element schon da ist. Bei einfachen Werten (Zahlen, Strings) geht das direkt mit contains. Bei Objekten vergleicht contains in Java mit equals, und das prüft ohne Überschreiben nur, ob es dasselbe Objekt ist. Wenn die Aufgabe nicht ausdrücklich sagt, dass contains z. B. „namensgleiche“ Objekte erkennt (so in S26), suchst du mit einer eigenen inneren Schleife nach dem Schlüssel (Muster 5 in ALG-01).

namen : List<string> := new List<string>()
zähle i von 0 bis bestellungen.size() - 1
  n : string := bestellungen.get(i).getLieferant()
  wenn nicht namen.contains(n) dann
    namen.add(n)
  Ende wenn
Ende zähle

Elemente beim Durchlaufen entfernen: Nach remove(i) rutscht das nächste Element auf Position i. Zählt die Schleife danach normal weiter (i + 1), wird dieses Element nie geprüft.

Drei saubere Lösungen: (1) rückwärts laufen (von size() - 1 bis 0), dann betrifft die Verschiebung nur schon geprüfte Elemente; (2) mit solange laufen und i nur erhöhen, wenn nichts entfernt wurde; (3) gar nicht entfernen, sondern die gewünschten Elemente in eine neue Liste filtern (Muster 3).

i : integer := liste.size() - 1
solange i >= 0
  wenn liste.get(i).istAbgelaufen() dann
    liste.remove(i)
  Ende wenn
  i := i - 1
Ende solange

Array oder Liste?

ALG-03 · Minimum/Maximum, lineare Suche Oft

Vorkommen: 4/9 · Prüfungen: W21, W23, S24, W25 (dazu Min/Max in S22 innerhalb der 2D-Aufgabe) · Ø 21 Punkte

Minimum und Maximum

Prinzip: Man merkt sich den „bisher besten“ Wert und vergleicht jedes weitere Element damit. Entscheidend ist der Startwert.

funktion kleinsterBestand(artikel : Artikel[]) : integer
  min : integer := artikel[0].getBestand()       // Startwert: erstes Element
  zähle i von 1 bis artikel.length - 1
    wenn artikel[i].getBestand() < min dann
      min := artikel[i].getBestand()
    Ende wenn
  Ende zähle
  rückgabe min
Ende funktion

Wird nicht der Wert, sondern das Objekt oder seine Position gesucht („welcher Artikel hat den kleinsten Bestand?“), merkst du dir den Index (minIndex := i) oder das Objekt selbst und vergleichst mit dessen Getter. Bei Gleichstand entscheidet < (erstes gefundenes bleibt) oder <= (letztes gewinnt).

Lineare Suche

Die Elemente werden der Reihe nach geprüft, bis das gesuchte gefunden ist. Aufwand im schlechtesten Fall: alle n Elemente (O(n)). Wird nichts gefunden, gibt man ein vereinbartes „nicht gefunden“ zurück: null bei Objekten, -1 bei Indizes, false bei Ja/Nein-Fragen.

funktion sucheArtikel(artikel : List<Artikel>, nr : integer) : Artikel
  i : integer := 0
  solange i < artikel.size() und artikel.get(i).getArtikelNr() <> nr
    i := i + 1
  Ende solange
  wenn i < artikel.size() dann
    rückgabe artikel.get(i)
  Ende wenn
  rückgabe null                                   // nicht gefunden
Ende funktion

Wichtig ist die Reihenfolge der Bedingungen: erst den Index prüfen, dann zugreifen. Bei und wird der zweite Teil nicht mehr ausgewertet, wenn der erste falsch ist (Kurzschlussauswertung). Alternativen mit gleicher Wirkung: eine Zählschleife mit rückgabe direkt beim Treffer, oder eine boolesche Variable gefunden als Abbruchbedingung. Eine Zählschleife ohne Abbruch funktioniert auch, prüft aber unnötig alle weiteren Elemente.

Nächster Nachbar (Minimum einer berechneten Größe)

Gesucht ist das Objekt mit der kleinsten Entfernung zu einem Punkt. Die Entfernung wird für jedes Element erst berechnet (Satz des Pythagoras), dann wie ein normales Minimum behandelt. Kommt eine Bedingung dazu („nur freie Taxis“), brauchst du den Startwert null, weil das erste Element vielleicht gar nicht in Frage kommt.

d = √((x₂ − x₁)² + (y₂ − y₁)²)

funktion naechstesFreiesTaxi(taxis : List<Taxi>, fx : double, fy : double) : Taxi
  bestes : Taxi := null
  minAbstand : double := 0.0                      // erst gültig, wenn bestes <> null
  zähle i von 0 bis taxis.size() - 1
    t : Taxi := taxis.get(i)
    wenn t.istFrei() dann
      dx : double := t.getX() - fx
      dy : double := t.getY() - fy
      d : double := wurzel(dx * dx + dy * dy)
      wenn bestes = null oder d < minAbstand dann
        bestes := t
        minAbstand := d
      Ende wenn
    Ende wenn
  Ende zähle
  rückgabe bestes                                 // null, wenn kein Taxi frei ist
Ende funktion

Beste Übereinstimmung („kleinste passende Differenz“)

Variante der Minimumsuche, z. B. in W25 („Tisch, dessen Platzzahl am wenigsten über der Personenzahl liegt“). Eigenes Beispiel: Für einen Umzug mit 14,5 m³ Ladung wird der kleinste Transporter gesucht, der noch reicht. Zuerst filtert eine Bedingung die ungeeigneten aus (volumen >= bedarf), dann wird unter den übrigen die kleinste Differenz gesucht.

funktion passendesFahrzeug(fahrzeuge : List<Fahrzeug>, bedarf : double) : Fahrzeug
  bestes : Fahrzeug := null
  zähle i von 0 bis fahrzeuge.size() - 1
    f : Fahrzeug := fahrzeuge.get(i)
    wenn f.getVolumen() >= bedarf dann
      wenn bestes = null oder f.getVolumen() < bestes.getVolumen() dann
        bestes := f
      Ende wenn
    Ende wenn
  Ende zähle
  rückgabe bestes
Ende funktion

Ist die Abweichung in beide Richtungen erlaubt (z. B. „Wert, der am nächsten an 20 liegt“), vergleichst du den Betrag der Differenz: abs(wert - 20).

ALG-04 · Speicherbedarf berechnen / Zahlensysteme Wahrscheinlich

Vorkommen: 3/9 · Prüfungen: W22 (Dezimal → Binär, Datentypen), W23 (Speicherbedarf in GiB, 7 P), S26 (Speicherbedarf in TiB, 5 P) · W23 und S26 waren fast identisch

Bit, Byte und die zwei Arten von Präfixen

• 1 Bit = kleinste Einheit (0 oder 1). 1 Byte = 8 Bit. Mit n Bit lassen sich 2ⁿ verschiedene Werte darstellen (vorzeichenlos 0 … 2ⁿ − 1; mit Vorzeichen −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1). Beispiel 10 Bit: 1 024 Werte.
• SI-Präfixe (dezimal, Faktor 1000): kB, MB, GB, TB. Benutzt von Festplattenherstellern und für Datenraten (Mbit/s).
• IEC-Binärpräfixe (Faktor 1024, erkennbar am „i“): KiB, MiB, GiB, TiB. Benutzt für Arbeitsspeicher und von Betriebssystemen (Windows zeigt GiB-Werte allerdings mit der Beschriftung „GB“ an).

Zahlensysteme umrechnen

156 : 2 =  78  Rest 0
 78 : 2 =  39  Rest 0
 39 : 2 =  19  Rest 1
 19 : 2 =   9  Rest 1
  9 : 2 =   4  Rest 1
  4 : 2 =   2  Rest 0
  2 : 2 =   1  Rest 0
  1 : 2 =   0  Rest 1   ↑ lesen
156 = 1001 1100 (binär)

Stelle: 128 64 32 16  8  4  2  1
Bit:      1  0  1  1  0  0  1  1
= 128 + 32 + 16 + 2 + 1 = 179

Datentypen und ihr Speicherbedarf

Auswahlregel: den kleinsten Typ, dessen Wertebereich sicher reicht (mit Reserve für die Zukunft). Geldbeträge nie als float/double (Rundungsfehler bei 0,1), sondern als DECIMAL(10,2) in der Datenbank bzw. in Cent als ganze Zahl. Nummern mit führenden Nullen oder Sonderzeichen (PLZ, Telefonnummer) sind Text.

Speicherbedarf von Bildern, Video und Audio

Beispiel Dokumentenscanner: A4-Seite mit 300 dpi = 2 480 × 3 508 Pixel, 24 Bit Farbtiefe, 400 Seiten pro Tag, 250 Arbeitstage.

Pixel je Seite   = 2 480 · 3 508                     =      8 699 840 Pixel
Bit je Seite     = 8 699 840 Pixel · 24 Bit/Pixel    =    208 796 160 Bit
Byte je Seite    = 208 796 160 Bit : 8 Bit/Byte      =     26 099 520 Byte
MiB je Seite     = 26 099 520 : 1 024 : 1 024        ≈          24,89 MiB
Byte pro Jahr    = 26 099 520 · 400 · 250            = 2 609 952 000 000 Byte
GiB pro Jahr     = 2 609 952 000 000 : 1 024³        ≈       2 430,71 GiB
TiB pro Jahr     = 2 430,71 : 1 024                  ≈           2,37 TiB

Video: Full HD 1 920 × 1 080, 24 Bit, 25 fps, 1 Minute: 1 920 · 1 080 · 3 Byte = 6 220 800 Byte je Bild; · 25 · 60 = 9 331 200 000 Byte ≈ 8,69 GiB pro Minute. Als Datenrate: 155 520 000 Byte/s · 8 = 1 244,16 Mbit/s (Datenraten immer mit SI-Präfix). Audio: CD-Qualität 44 100 Hz · 16 Bit · 2 Kanäle = 1 411 200 Bit/s = 176 400 Byte/s; 3 Minuten = 31 752 000 Byte ≈ 30,28 MiB.

So gehst du vor

1. Alle Angaben mit Einheit herausschreiben (Pixel, Bit/Kanal, Kanäle, Bilder/Tag, Tage/Jahr, Kompression).
2. Größe eines Elements in Bit berechnen, dann ÷ 8 in Byte.
3. Hochrechnen (× Anzahl × Zeitraum). Wochen: 52, Jahr: 365 Tage, sofern nichts anderes angegeben ist.
4. In die verlangte Einheit umrechnen: je Stufe ÷ 1024 (bzw. ÷ 1000 bei SI).
5. Runden wie verlangt; Speicherbedarf und Anzahl Datenträger aufrunden.
6. Antwortsatz mit Einheit. Jede Zeile des Rechenwegs mit Einheiten zeigt dem Prüfer, dass du verstanden hast. Das bringt Teilpunkte, auch wenn sich ein Rechenfehler einschleicht.

ALG-05 · Sortieren Wahrscheinlich

Vorkommen: 2/9 · Prüfungen: W22 (T2 A1, 25 P: Bubblesort → Vergleichsfunktion → generisch), S24 (T2 A2a, 12 P: Sortieren mit übergebener Vergleichsfunktion) · Tendenz eher fallend

Bubblesort

Benachbarte Elemente werden verglichen und vertauscht, wenn sie in der falschen Reihenfolge stehen. Nach jedem Durchlauf ist das größte noch unsortierte Element ganz hinten angekommen („aufgestiegen wie eine Blase“). Deshalb kann die innere Schleife mit jedem Durchlauf ein Element früher aufhören.

funktion bubbleSort(zahlen : integer[])
  zähle i von 0 bis zahlen.length - 2
    zähle j von 0 bis zahlen.length - 2 - i
      wenn zahlen[j] > zahlen[j + 1] dann
        hilf : integer := zahlen[j]              // Dreieckstausch
        zahlen[j] := zahlen[j + 1]
        zahlen[j + 1] := hilf
      Ende wenn
    Ende zähle
  Ende zähle
Ende funktion

Optimierung mit Abbruch: Eine boolesche Variable getauscht wird zu Beginn jedes Durchlaufs auf false gesetzt und beim Tauschen auf true. Wurde in einem Durchlauf nichts getauscht, ist das Feld sortiert und man kann aufhören (äußere Schleife dann als solange getauscht bzw. wiederhole … solange getauscht). Bei bereits sortierten Daten braucht Bubblesort so nur einen Durchlauf.

Selectionsort und Insertionsort (zum Verständnis)

zähle i von 0 bis n - 2
  minPos : integer := i
  zähle j von i + 1 bis n - 1
    wenn feld[j] < feld[minPos] dann
      minPos := j
    Ende wenn
  Ende zähle
  tausche feld[i] und feld[minPos]
Ende zähle

zähle i von 1 bis n - 1
  wert : integer := feld[i]
  j : integer := i - 1
  solange j >= 0 und feld[j] > wert
    feld[j + 1] := feld[j]
    j := j - 1
  Ende solange
  feld[j + 1] := wert
Ende zähle

Größenordnung: Bei 1 000 Elementen sind n² = 1 000 000 Vergleiche, n · log₂ n ≈ 10 000. Für große Datenmengen nimmt man deshalb die Sortierfunktion der Bibliothek (Java: List.sort, Arrays.sort; für Objekte stabil).

Stabilität: Ein Verfahren ist stabil, wenn Elemente mit gleichem Sortierschlüssel ihre bisherige Reihenfolge behalten. Beispiel: Eine Bücherliste ist alphabetisch nach Titel sortiert und wird danach stabil nach Preis sortiert → Bücher mit gleichem Preis stehen weiterhin alphabetisch. Bubblesort ist stabil, solange nur bei > (nicht bei >=) getauscht wird.

Objekte sortieren und die Vergleichsfunktion

Bei Objekten vergleichst du ein Attribut über den Getter, tauschst aber das ganze Objekt: wenn buecher[j].getPreis() > buecher[j + 1].getPreis() dann … Hilfsvariable vom Typ Buch.

Soll derselbe Algorithmus nach verschiedenen Kriterien sortieren können, übergibt man ihm eine Vergleichsfunktion (Java: Comparator). Der Algorithmus fragt nur noch „steht a vor b?“, das Kriterium steckt in der Funktion. Vertrag der Vergleichsfunktion vergleiche(a, b) : integer:

funktion nachPreisAufsteigend(a : Buch, b : Buch) : integer
  wenn a.getPreis() < b.getPreis() dann
    rückgabe -1
  Ende wenn
  wenn a.getPreis() > b.getPreis() dann
    rückgabe 1
  Ende wenn
  rückgabe 0
Ende funktion

// mehrstufig: erst Autor, bei gleichem Autor nach Titel
funktion nachAutorDannTitel(a : Buch, b : Buch) : integer
  wenn a.getAutor() <> b.getAutor() dann
    rückgabe a.getAutor().compareTo(b.getAutor())
  Ende wenn
  rückgabe a.getTitel().compareTo(b.getTitel())
Ende funktion

Absteigend sortieren: die Rückgabewerte vertauschen (1 statt −1) oder die Funktion mit (b, a) statt (a, b) rechnen. In Java:

Comparator<Buch> nachPreis = (a, b) -> Double.compare(a.getPreis(), b.getPreis());
Comparator<Buch> nachAutorDannTitel =
        Comparator.comparing(Buch::getAutor).thenComparing(Buch::getTitel);
buecher.sort(nachPreis.reversed());          // teuerstes zuerst

// generische Sortiermethode (W22): für jede Liste mit passendem Comparator
static <T> void sortiere(List<T> liste, Comparator<T> vergleiche) {
    ... wenn vergleiche.compare(a, b) > 0 ist, a und b tauschen ...
}

Vorteile der übergebenen Vergleichsfunktion: ein getesteter Sortieralgorithmus für beliebig viele Sortierkriterien (keine Code-Duplikate), neue Kriterien ohne Änderung am Algorithmus (Open-Closed-Prinzip, Strategie-Muster), mit Generics für beliebige Klassen nutzbar.

ALG-06 · Zeichenketten verarbeiten Wahrscheinlich

Vorkommen: 2/9 · Prüfungen: W21 (Passwortprüfung im Struktogramm, Fehler finden), W25 (Namensspalte per SUBSTRING aufteilen)

Ein String ist eine Folge von Zeichen (char). Wie beim Array beginnt der Index bei 0, das letzte Zeichen hat den Index length() - 1. Strings sind in Java unveränderlich: Methoden wie trim() oder substring() liefern einen neuen String.

Muster 1: Zeichen für Zeichen prüfen

Zwei Varianten, die man auseinanderhalten muss:

• „Alle Zeichen müssen …“ (nur erlaubte Zeichen): Beim ersten Verstoß sofort false zurückgeben, nach der Schleife true.
• „Mindestens ein Zeichen muss …“ (mindestens eine Ziffer): Merker (boolean) vor der Schleife auf false, bei Treffer auf true, erst nach der Schleife auswerten.

Beispiel Benutzername: 5 bis 20 Zeichen, beginnt mit einem Buchstaben, danach nur Buchstaben, Ziffern oder Unterstrich, mindestens eine Ziffer.

funktion pruefeBenutzername(name : string) : boolean
  wenn name.length() < 5 oder name.length() > 20 dann
    rückgabe false
  Ende wenn
  wenn nicht istBuchstabe(name.charAt(0)) dann
    rückgabe false
  Ende wenn
  hatZiffer : boolean := false
  zähle i von 1 bis name.length() - 1
    c : char := name.charAt(i)
    wenn istZiffer(c) dann
      hatZiffer := true
    sonst
      wenn nicht istBuchstabe(c) und c <> '_' dann
        rückgabe false                        // unerlaubtes Zeichen: sofort Schluss
      Ende wenn
    Ende wenn
  Ende zähle
  rückgabe hatZiffer                      // "mindestens eine": erst nach der Schleife
Ende funktion

Muster 2: Text zerlegen

Trennzeichen suchen (indexOf), links und rechts davon mit substring herausschneiden, Leerzeichen mit trim entfernen. Immer überlegen, was passiert, wenn das Trennzeichen fehlt (indexOf liefert −1).

// "53111 Bonn" -> PLZ und Ort
pos : integer := adresse.indexOf(' ')
wenn pos = -1 dann
  // Fehlerfall: kein Leerzeichen -> z. B. Ausnahme oder Rückgabe null
sonst
  plz : string := adresse.substring(0, pos)
  ort : string := adresse.substring(pos + 1, adresse.length()).trim()
Ende wenn

Mit split geht es kürzer, wenn das Trennzeichen eindeutig ist: teile := "14.09.2026".split(".") → teile[0] = "14", teile.length = 3.

Strings vergleichen

In Java vergleicht == bei Objekten die Referenzen (dasselbe Objekt im Speicher?), equals den Inhalt. Zwei inhaltsgleiche Strings, die z. B. aus einer Eingabe oder Datei stammen, sind verschiedene Objekte → == liefert false. Deshalb Strings in Java immer mit equals vergleichen. Im Pseudocode der Prüfung wird = meist akzeptiert (S26 erlaubt ausdrücklich ==). Alphabetische Reihenfolge: compareTo. Zahlen, die als Text vorliegen, werden alphabetisch verglichen: "10" < "9"! Vorher umwandeln.

Zusammenhang mit SQL (W25 T2 A4d): Dort zerlegt man Spalten mit SUBSTRING(spalte, start, länge) – Achtung, in SQL beginnt die Zählung bei 1 und der dritte Parameter ist die Länge, nicht das Ende. Position eines Zeichens: LOCATE(' ', name) bzw. INSTR.

ALG-07 · Exceptions / Fehlerbehandlung Wahrscheinlich

Vorkommen: 2/9 · Prüfungen: W21, W25 (Fehlerfall bzw. null behandeln) · verwandt: W24 T2 A2a (Fehlerantwort mit HTTP-Statuscode erzeugen)

Eine Exception (Ausnahme) ist ein Objekt, das einen Fehlerzustand beschreibt. Sie wird an der Fehlerstelle geworfen (throw) und wandert die Aufrufkette hinauf, bis ein passender catch-Block sie fängt. Fängt sie niemand, bricht das Programm mit einer Fehlermeldung (Stacktrace) ab. Vorteil gegenüber Fehlercodes: Normaler Ablauf und Fehlerbehandlung sind getrennt, und ein Fehler kann nicht „aus Versehen“ ignoriert werden.

try {
    int menge = Integer.parseInt(eingabe);
    lager.entnehmen(artikelNr, menge);
    System.out.println("Gebucht.");
} catch (NumberFormatException e) {
    System.out.println("Bitte eine ganze Zahl eingeben.");
} catch (BestandZuNiedrigException e) {
    System.out.println(e.getMessage());
} finally {
    protokoll.schliessen();   // läuft IMMER
}

try
  menge : integer := zuZahl(eingabe)
  lager.entnehmen(artikelNr, menge)
  ausgabe("Gebucht.")
catch (NumberFormatException e)
  ausgabe("Bitte eine ganze Zahl eingeben.")
catch (BestandZuNiedrigException e)
  ausgabe(e.getMessage())
finally
  protokoll.schliessen()
Ende try

Checked und unchecked Exceptions (Java)

throw wirft eine Ausnahme (throw new IllegalArgumentException("Menge muss positiv sein")), throws kündigt in der Signatur an, dass eine Methode eine checked Exception weiterreichen kann. Eigene Ausnahmen erben von Exception (checked) oder RuntimeException (unchecked):

public class BestandZuNiedrigException extends Exception {
    public BestandZuNiedrigException(String meldung) { super(meldung); }
}

public void entnehmen(int menge) throws BestandZuNiedrigException {
    if (menge <= 0) {
        throw new IllegalArgumentException("Menge muss positiv sein");   // unchecked
    }
    if (menge > bestand) {
        throw new BestandZuNiedrigException("Nur " + bestand + " Stück"); // checked
    }
    bestand = bestand - menge;
}

Typische Fehlerfälle in Prüfungsalgorithmen

Exception oder Sonderwert? Ein Sonderwert (null, −1) ist einfach und in der Prüfung oft verlangt („liefert null, wenn kein Tisch frei ist“), muss aber vom Aufrufer geprüft werden – vergisst er es, knallt es später an anderer Stelle. Eine Exception erzwingt die Behandlung (checked) und trägt eine Fehlermeldung, ist aber für „normale“ Ergebnisse wie „nichts gefunden“ oft zu schwer. Faustregel: erwartbares Ergebnis → Sonderwert, echter Fehler/Vertragsbruch → Exception. Prüfungen am Methodenanfang („Wächter“, fail fast) halten den eigentlichen Algorithmus übersichtlich.

ALG-08 · Rekursion Sonstige

Vorkommen: 1/9 · Prüfung: W22 T2 A2 (25 P, davon 12 P Rekursion: Schreibtischtest einer rekursiven Umwandlung Dezimal → Binär, Fehler korrigieren, Rekursion vs. Iteration; dazu iterative Lösung)

Eine Funktion ist rekursiv, wenn sie sich selbst aufruft. Das funktioniert nur mit zwei Bestandteilen: dem Basisfall (Abbruchbedingung, liefert direkt ein Ergebnis) und dem Rekursionsfall (ruft sich mit einem kleineren Problem auf und baut aus dessen Ergebnis das eigene). Jeder Aufruf bekommt eigene Parameter und lokale Variablen auf dem Aufrufstapel (Stack).

funktion fakultaet(n : integer) : integer
  wenn n <= 1 dann        // Basisfall
    rückgabe 1
  Ende wenn
  // Rekursionsfall:
  rückgabe n * fakultaet(n - 1)
Ende funktion

funktion quersumme(n : integer) : integer
  wenn n < 10 dann        // Basisfall:
    rückgabe n            // nur eine Ziffer
  Ende wenn
  // Rekursionsfall:
  rückgabe (n mod 10) + quersumme(n div 10)
Ende funktion

Schreibtischtest einer Rekursion: Eine Zeile je Aufruf; erst alle Aufrufe nach unten notieren, dann die Rückgabewerte von unten nach oben eintragen. Beispiel quersumme(4721):

Jede Rekursion lässt sich iterativ umschreiben (ggf. mit eigenem Stack bzw. einer Liste). Iterative Fakultät: ergebnis := 1; zähle i von 2 bis n: ergebnis := ergebnis * i.

ALG-09 · Nebenläufigkeit Sonstige

Vorkommen: 1/9 · Prüfung: W21 T2 A1b (4 P: Variante zum Blockieren von Terminen bei gleichzeitigen Buchungen wählen und begründen)

Webanwendungen bearbeiten viele Anfragen gleichzeitig (in eigenen Threads oder auf mehreren Servern), alle greifen auf dieselbe Datenbank zu. Solange nur gelesen wird, ist das unproblematisch. Kritisch wird es, wenn zwei Abläufe denselben Datensatz lesen, prüfen und dann ändern.

Lösungen: Sperren und atomare Operationen

• Atomare Operation: Prüfen und Ändern in einem Datenbankbefehl: UPDATE platz SET status = 'verkauft' WHERE id = 712 AND status = 'frei' und danach die Anzahl geänderter Zeilen auswerten. Zusätzlich kann ein UNIQUE-Constraint (z. B. auf Veranstaltung + Platz in der Buchungstabelle) Doppelbuchungen in der Datenbank selbst verhindern.
• Transaktion (ACID): mehrere zusammengehörige Änderungen (Platz sperren, Buchung anlegen, Zahlung vermerken) werden ganz oder gar nicht ausgeführt; Isolation sorgt dafür, dass parallele Transaktionen sich nicht in die Quere kommen.
• Sinnvolle Sperrdauer: so kurz wie möglich. Eine Sperre darf nicht auf eine Benutzereingabe warten (der Nutzer geht Kaffee holen, alle anderen sind blockiert). Muss etwas für den Benutzer „festgehalten“ werden, nimmt man eine zeitlich begrenzte Reservierung mit Ablaufzeit (z. B. 10 Minuten im Warenkorb), die ein Hintergrundprozess oder die nächste Abfrage wieder freigibt.

B · Belegsatz

Enthält nur, was dir auch die IHK beilegen würde: die Pseudocode-Konventionen (wie im Belegsatz S24) und die Anlagen zur Ausgangssituation (Klassen, Testdaten, Hilfsfunktionen). Keine Erklärungen.

Pseudocode, prozedurale Programmierung

wenn [ Bedingung ] dann
   [ Anweisung ]
sonst
   [ Anweisung ]
Ende wenn

zähle [ Variable ] von [ Startwert ] bis [ Endwert ]
   [ Schleifeninhalt ]
Ende zähle

solange [ Bedingung ]
   [ Schleifeninhalt ]
Ende solange

wiederhole
   [ Schleifeninhalt ]
solange [ Bedingung ]

:=

=; <; >; <=; >=; <>

integer
double
string
boolean
array

C · Aufgaben

Alle Aufgaben beziehen sich auf die Ausgangssituation in Anlage 1. Algorithmen sind – sofern nicht anders angegeben – in Pseudocode nach den Konventionen des Belegsatzes zu entwickeln; eine Programmiersprache (z. B. Java) ist ebenfalls zulässig. Für alle Attribute stehen Get-Methoden zur Verfügung (Anlage 2).

ALG-01 · Algorithmus in Pseudocode schreiben

funktion zaehleLadebedarf(raeder : List<Fahrrad>) : integer
  anzahl : integer := ____(1)____
  zähle i von 0 bis ____(2)____
    r : Fahrrad := raeder.get(i)
    wenn ____(3)____ dann
      ____(4)____
    Ende wenn
  Ende zähle
  rückgabe ____(5)____
Ende funktion

ALG-02 · Arrays und Listen durchlaufen

int entfernt = 0;
for (int i = 0; i < raeder.size(); i++) {
    if (raeder.get(i).isDefekt()) {
        raeder.remove(i);
        entfernt++;
    }
}
return entfernt;

ALG-03 · Minimum/Maximum, lineare Suche

funktion minAkku(raeder : Fahrrad[]) : integer
  min : integer := 0
  zähle i von 1 bis raeder.length - 1
    wenn raeder[i].getAkkuStand() < min dann
      min := raeder[i].getAkkuStand()
    Ende wenn
  Ende zähle
  rückgabe min
Ende funktion

ALG-04 · Speicherbedarf berechnen / Zahlensysteme

ALG-05 · Sortieren

ALG-06 · Zeichenketten verarbeiten

ALG-07 · Exceptions / Fehlerbehandlung

static int centProMinute(String betragText, int minuten) {
    int ergebnis = -1;
    try {
        System.out.print("A ");
        if (minuten < 0) {
            throw new IllegalArgumentException("Minuten negativ");
        }
        int betrag = Integer.parseInt(betragText);   // NumberFormatException bei Nicht-Zahl
        ergebnis = betrag / minuten;                 // Ganzzahldivision
        System.out.print("B ");
    } catch (NumberFormatException e) {
        System.out.print("C ");
    } catch (ArithmeticException e) {
        System.out.print("D ");
        ergebnis = 0;
    } finally {
        System.out.print("E ");
    }
    System.out.print("F ");
    return ergebnis;
}

ALG-08 · Rekursion

funktion binaer(n : integer) : string
  wenn n = 0 dann
    rückgabe ""
  Ende wenn
  rückgabe binaer(n div 2) + (n mod 2)
Ende funktion

ALG-09 · Nebenläufigkeit

Originalaufgaben zum Üben

Diese echten Prüfungsaufgaben passen zu diesem Block (Dateien im Ordner Prüfungsvorbereitung). Lösungen gibt es nur für 2023 Sommer, 2023 Winter, 2024 Sommer und 2025 Winter (dort vom u-form-Verlag).