Algorithmik-Aufgaben
Letzte Lektion des Kurses – die Prüfungsvorbereitung. Wir gehen zwölf typische IHK-Aufgaben zu allen Themen durch: Algorithmus-Grundlagen, Struktogramm, Pseudocode, Kontrollstrukturen, Rekursion, Suche, Sortierung, O-Notation und Datenstrukturen.
Versuche jede Aufgabe erst selbst zu lösen, dann die Musterlösung aufzuklappen. Die Aufgabentypen entsprechen echten IHK-Klausuren: Pseudocode schreiben, Algorithmus auswerten, Komplexität analysieren, Datenstruktur wählen, Sortier-/Suchverfahren anwenden.
1) Überblick
Aufgaben in dieser Lektion
12
Aufgaben
5
Aufgabentypen
9
Themen
~42
Punkte total
Punktzahlen sind Orientierungswerte. In echten IHK-Prüfungen werden algorithmische Aufgaben mit 2-8 Punkten bewertet, je nach Komplexität. Wichtig ist nicht nur das Ergebnis, sondern der saubere Lösungsweg. Pseudocode oder Struktogramme mit erkennbarer Struktur bringen auch bei Fehlern Teilpunkte.
2) Aufgaben Teil A – Grundlagen & Notation
Aufgaben 1–4
Eigenschaften eines Algorithmus
Nennen Sie fünf Eigenschaften, die einen Algorithmus auszeichnen, und erklären Sie jede mit einem Satz.
Musterlösung
- Endlichkeit: Der Algorithmus besteht aus einer endlichen Anzahl von Schritten – die Beschreibung hat ein Ende.
- Terminiertheit: Der Algorithmus hält nach endlich vielen Schritten an. Endlosschleifen sind nicht erlaubt.
- Determiniertheit: Bei gleicher Eingabe liefert der Algorithmus immer dasselbe Ergebnis.
- Determinismus: In jedem Schritt ist klar, welcher Schritt als nächstes ausgeführt wird – keine Mehrdeutigkeit.
- Eindeutigkeit: Jeder einzelne Schritt ist klar und unmissverständlich beschrieben.
Tipp: Achte auf den Unterschied zwischen Determiniertheit (Ergebnis ist eindeutig) und Determinismus (Ablauf ist eindeutig). Ein Algorithmus kann nicht-deterministisch sein (z.B. mit Zufallswahl) und trotzdem determiniert (immer dasselbe korrekte Ergebnis).
Maximum einer Liste finden
Schreiben Sie einen Algorithmus in Pseudocode, der das Maximum einer Liste mit n Zahlen findet und zurückgibt. Geben Sie auch die Zeitkomplexität an.
Musterlösung
FUNKTION findeMax(liste):
// Erstes Element als Kandidat
max = liste[1]
FÜR i VON 2 BIS laenge(liste)
WENN liste[i] > max DANN
max = liste[i]
ENDE WENN
ENDE FÜR
GIB ZURÜCK max
ENDE FUNKTION
Komplexität: O(n) – die Schleife läuft genau (n-1) mal, also linear.Speicher:
O(1) – nur eine Hilfsvariable max.
Klassisches Pattern: Erstes Element als Kandidat nehmen, Rest durchgehen und ersetzen, wenn etwas Besseres kommt. Funktioniert genauso für Minimum (nur
< statt >).Welcher Algorithmus läuft hier?
Gegeben folgender Pseudocode. Was berechnet er? Geben Sie das Ergebnis für die Eingabe n = 10 an. Welche Komplexität hat er?
summe = 0
FÜR i VON 1 BIS n
summe = summe + i
ENDE FÜR
GIB AUS summeMusterlösung
Was er berechnet: Die Summe der ersten n natürlichen Zahlen, also
Für n = 10:
Komplexität:
1 + 2 + 3 + ... + n.Für n = 10:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
Mathematische Formel: n · (n + 1) / 2 = 10 · 11 / 2 = 55 (Gauß'sche Summenformel).Komplexität:
O(n) – die Schleife läuft n-mal.
Interessant: Mit der mathematischen Formel könnte man das Ergebnis sogar in
O(1) berechnen – ohne Schleife. Das ist ein Beispiel dafür, dass ein cleverer Algorithmus dramatisch effizienter sein kann als ein naiver.Primzahltest
Schreiben Sie einen Algorithmus, der prüft, ob eine Zahl n eine Primzahl ist. Geben Sie als Ergebnis „wahr" oder „falsch" zurück.
Musterlösung
FUNKTION istPrimzahl(n):
WENN n < 2 DANN
GIB ZURÜCK falsch
ENDE WENN
// Teiler suchen bis √n
FÜR i VON 2 BIS wurzel(n)
WENN n mod i = 0 DANN
GIB ZURÜCK falsch
ENDE WENN
ENDE FÜR
GIB ZURÜCK wahr
ENDE FUNKTION
Komplexität: O(√n) – wir prüfen nur bis zur Wurzel von n.
Warum nur bis √n? Wenn n einen Teiler > √n hat, muss es zwingend auch einen Teiler < √n geben (das Paar). Wir können also bei √n aufhören, ohne etwas zu übersehen. Diese Optimierung halbiert die nötigen Schleifen-Durchläufe drastisch.
3) Aufgaben Teil B – Such- und Sortier-Algorithmen
Aufgaben 5–8
Sortiervorgang nachvollziehen
Sortieren Sie die folgende Liste mit Bubble Sort und geben Sie den Zustand nach jedem äußeren Durchlauf an:
[5, 1, 4, 2, 8].Musterlösung
Bubble Sort: In jedem Durchgang wandert das größte unsortierte Element ans Ende.
Start: [5, 1, 4, 2, 8]
Durchgang 1:
(5,1)→swap [1, 5, 4, 2, 8]
(5,4)→swap [1, 4, 5, 2, 8]
(5,2)→swap [1, 4, 2, 5, 8]
(5,8)→ok [1, 4, 2, 5, 8]
Nach D1: [1, 4, 2, 5, 8]
Durchgang 2:
(1,4)→ok [1, 4, 2, 5]
(4,2)→swap [1, 2, 4, 5]
(4,5)→ok [1, 2, 4, 5]
Nach D2: [1, 2, 4, 5, 8]
Durchgang 3:
(1,2)→ok, (2,4)→ok
Nach D3: [1, 2, 4, 5, 8]
Durchgang 4:
(1,2)→ok
Nach D4: [1, 2, 4, 5, 8] → SORTIERT
Anzahl Tausche: 4 · Anzahl Vergleiche: 10
Beobachtung: nach Durchgang i ist das i-größte Element an seiner endgültigen Position (ganz rechts oben farbig markiert). Die Liste „kämmt" sich von rechts auf.
Binäre Suche durchspielen
Gegeben das sortierte Array
[3, 7, 11, 14, 19, 23, 31, 42, 47, 56, 68, 85, 99]. Suchen Sie mit binärer Suche den Wert 68. Geben Sie für jeden Schritt L, R, M und den Vergleich an.Musterlösung
Array hat 13 Elemente (Indizes 0–12). Ziel: 68.
Schritt 1:
L=0, R=12, M=(0+12)/2 = 6
liste[6] = 31 < 68 → suche rechts, L=7
Schritt 2:
L=7, R=12, M=(7+12)/2 = 9
liste[9] = 56 < 68 → suche rechts, L=10
Schritt 3:
L=10, R=12, M=(10+12)/2 = 11
liste[11] = 85 > 68 → suche links, R=10
Schritt 4:
L=10, R=10, M=(10+10)/2 = 10
liste[10] = 68 = 68 → GEFUNDEN bei Index 10
Anzahl Vergleiche: 4
Kontrolle: Bei n=13 sind im Worst Case ⌈log₂(13)⌉ = ⌈3,7⌉ = 4 Vergleiche nötig. Wir liegen genau in dieser Grenze. ✓
Vergleichsanzahl Linear vs. Binär
Eine Liste hat 1 Million Elemente. Wie viele Vergleiche sind im schlimmsten Fall nötig für (a) lineare Suche und (b) binäre Suche? Welcher Algorithmus ist um wie viele Größenordnungen schneller?
Musterlösung
(a) Lineare Suche: O(n) im Worst Case → 1 000 000 Vergleiche (Wert am Ende oder gar nicht vorhanden).
(b) Binäre Suche: O(log₂ n) → log₂(1 000 000) ≈ 20 Vergleiche.
Faktor:
(b) Binäre Suche: O(log₂ n) → log₂(1 000 000) ≈ 20 Vergleiche.
Faktor:
1 000 000 / 20 = 50 000
Die binäre Suche ist also ~50 000 mal schneller – das sind ungefähr 5 Größenordnungen.
Praxisbedeutung: Wenn lineare Suche 1 Sekunde braucht, ist binäre Suche in 20 Mikrosekunden fertig. Das ist der Grund, warum Datenbanken sortierte Indizes verwenden – aus „Sekunden" werden „Mikrosekunden".
Sortierverfahren vergleichen
Nennen Sie zwei Vorteile von Merge Sort gegenüber Bubble Sort. Wann würden Sie trotzdem Bubble Sort oder Insertion Sort einsetzen?
Musterlösung
Vorteile von Merge Sort:
- Bessere Zeitkomplexität:
O(n log n)stattO(n²). Bei großen Datenmengen drastisch schneller. - Garantierte Performance: auch im Worst Case
O(n log n). Bubble Sort kann in jedem Szenario zur Worst-Case-Performance werden. - Stabil: erhält die Reihenfolge gleicher Elemente.
- Gut parallelisierbar: die Teile-Schritte können auf mehreren Prozessoren laufen.
- Kleine Listen (z.B. unter 20 Elemente): einfachere Algorithmen haben weniger Overhead, sind in der Praxis oft schneller.
- Fast sortierte Listen: Insertion Sort schafft das in O(n) – schneller als Merge Sort.
- Begrenzter Speicher: Bubble und Insertion sind in-place (O(1) Extra-Speicher). Merge Sort braucht O(n).
- Lehrkontext: einfacher zu verstehen und zu implementieren.
Profi-Tipp: Moderne Implementierungen wie Timsort (Java, Python) kombinieren beides – Insertion Sort für kleine Teile, Merge Sort für die Zusammenführung. „Best of both worlds".
4) Aufgaben Teil C – Komplexität & Datenstrukturen
Aufgaben 9–12
Komplexität analysieren
Geben Sie für jeden Code-Block die Zeitkomplexität in O-Notation an:
(a)
(b)
(c)
(d)
(a)
FÜR i VON 1 BIS n: GIB AUS i(b)
FÜR i VON 1 BIS n: FÜR j VON 1 BIS n: GIB AUS i*j(c)
i = n; SOLANGE i > 1: i = i / 2(d)
FÜR i VON 1 BIS n: j = n; SOLANGE j > 1: j = j / 2Musterlösung
(a) Einfache Schleife n-mal →
(b) Zwei verschachtelte Schleifen, beide n-mal → n · n →
(c) Halbierung in jedem Schritt – wie oft kann man n halbieren bis 1? →
(d) Äußere Schleife n-mal · innere log n-mal →
O(n)(b) Zwei verschachtelte Schleifen, beide n-mal → n · n →
O(n²)(c) Halbierung in jedem Schritt – wie oft kann man n halbieren bis 1? →
O(log n)(d) Äußere Schleife n-mal · innere log n-mal →
O(n log n)
Regeln zur Erinnerung: Verschachtelte Schleifen → multiplizieren. Halbierung → log n. Sequenz → höchster Term gewinnt. Konstante Faktoren weglassen.
Rekursive Funktion auswerten
Was gibt folgende rekursive Funktion für den Aufruf
f(4) zurück? Skizzieren Sie den Aufrufbaum.FUNKTION f(n):
WENN n <= 1 DANN GIB ZURÜCK 1
GIB ZURÜCK n * f(n - 1)
ENDE FUNKTIONMusterlösung
Das ist die Fakultäts-Funktion.
Aufrufkette für f(4):
Komplexität:
Aufrufkette für f(4):
f(4) = 4 * f(3)
= 4 * (3 * f(2))
= 4 * (3 * (2 * f(1)))
= 4 * (3 * (2 * 1)) // Basisfall
= 4 * (3 * 2)
= 4 * 6
= 24
Ergebnis: f(4) = 24, also 4! = 24.Komplexität:
O(n) – n Selbstaufrufe, jeder konstanten Aufwand. Speicher: O(n) für den Call-Stack.
Im Call-Stack stapeln sich vier Frames: f(4), f(3), f(2), f(1). Erst der innerste löst sich auf (Basisfall), dann arbeitet sich das Ergebnis nach oben zurück. Siehe Lektion 5 (Rekursion) für Details.
Stack-Operationen
Gegeben ein leerer Stack. Folgende Operationen werden nacheinander ausgeführt:
push(5), push(3), pop(), push(8), push(1), pop(), pop(), push(7). Was steht zum Schluss im Stack (von unten nach oben)?Musterlösung
Stack-Verlauf: (Top steht rechts)
Start: []
push(5): [5]
push(3): [5, 3]
pop() → 3: [5]
push(8): [5, 8]
push(1): [5, 8, 1]
pop() → 1: [5, 8]
pop() → 8: [5]
push(7): [5, 7]
Endzustand: Stack enthält von unten nach oben: 5, 7. Top ist 7.
LIFO im Kopf: Stack-Operationen sind „Last In, First Out". Jedes pop() entfernt das zuletzt gepushte Element. Diese Aufgabe ist Standard in jeder Algorithmen-Klausur – sauber Zeile für Zeile durcharbeiten, nichts überspringen.
Datenstruktur wählen
Für jedes Szenario, welche Datenstruktur (Array, verkettete Liste, Stack, Queue, Hash-Map, Baum) ist am besten geeignet? Kurz begründen.
(a) Browser-Verlauf (zurück-Knopf)
(b) Telefonbuch mit Namen → Nummer
(c) Druckaufträge in Reihenfolge abarbeiten
(d) Schnelle Suche in stets sortierter Datenmenge
(e) Pixel-Array eines Bildes
(a) Browser-Verlauf (zurück-Knopf)
(b) Telefonbuch mit Namen → Nummer
(c) Druckaufträge in Reihenfolge abarbeiten
(d) Schnelle Suche in stets sortierter Datenmenge
(e) Pixel-Array eines Bildes
Musterlösung
(a) Browser-Verlauf:
Begründung: LIFO – letzte besuchte Seite wird zuerst zurückgeholt. „Zurück" = pop().
(b) Telefonbuch:
Begründung: Lookup per Name (Schlüssel) → Nummer (Wert). Hash-Map bietet O(1) Lookup.
(c) Druckaufträge:
Begründung: FIFO – wer zuerst gedruckt werden soll, kommt zuerst dran. Faire Reihenfolge.
(d) Stets sortierte Datenmenge mit schneller Suche:
Begründung: O(log n) für Suchen, Einfügen, Löschen – und Sortierung wird automatisch erhalten. Sortiertes Array wäre auch denkbar, aber langsam bei häufigem Einfügen.
(e) Pixel-Array eines Bildes:
Begründung: feste Größe, häufiger Zugriff per (x,y)-Koordinaten → O(1). Cache-Lokalität wichtig für Performance.
StackBegründung: LIFO – letzte besuchte Seite wird zuerst zurückgeholt. „Zurück" = pop().
(b) Telefonbuch:
Hash-Map (oder sortiertes Array für sequenzielle Suche)Begründung: Lookup per Name (Schlüssel) → Nummer (Wert). Hash-Map bietet O(1) Lookup.
(c) Druckaufträge:
QueueBegründung: FIFO – wer zuerst gedruckt werden soll, kommt zuerst dran. Faire Reihenfolge.
(d) Stets sortierte Datenmenge mit schneller Suche:
Balancierter Baum (BST)Begründung: O(log n) für Suchen, Einfügen, Löschen – und Sortierung wird automatisch erhalten. Sortiertes Array wäre auch denkbar, aber langsam bei häufigem Einfügen.
(e) Pixel-Array eines Bildes:
Array (2D-Array)Begründung: feste Größe, häufiger Zugriff per (x,y)-Koordinaten → O(1). Cache-Lokalität wichtig für Performance.
Faustregel: Was sind die häufigsten Operationen? Daran orientieren! Index-Zugriff → Array. Lookup per Key → Hash-Map. „Wer war's zuletzt" → Stack. „Wer war's zuerst" → Queue. Sortiert + dynamisch → Baum.
5) Mini-Quiz
Sieben kurze Multiple-Choice-Fragen zur Wiederholung der Kernkonzepte:
Schnell-Quiz
6) Cheatsheet – das musst du auswendig wissen
Am Tag vor der Prüfung überfliegen. Mit diesen Begriffen und Werten parat bist du gut vorbereitet:
Spickzettel
Algorithmus-Eigenschaften
Endlich, terminiert, determiniert, deterministisch, eindeutig (5 Stück).
EVA-Prinzip
Eingabe → Verarbeitung → Ausgabe. Grundschema jedes Algorithmus.
Drei Kontrollstrukturen
Sequenz, Auswahl (if/else), Schleife (while/for). Reichen für alles.
Schleifenarten
while (kopfgesteuert), do-while (fußgesteuert), for (Zählschleife), foreach (über Sammlung).
Rekursion
Basisfall + Rekursionsschritt. Funktion ruft sich selbst auf. Call-Stack.
Lineare Suche
O(n). Liste durchgehen. Keine Sortierung nötig.
Binäre Suche
O(log n). Halbieren. Sortierte Liste Voraussetzung!
Bubble Sort
O(n²). Nachbarn vergleichen, tauschen. Einfach aber langsam.
Selection Sort
O(n²). Minimum suchen, nach vorne tauschen.
Insertion Sort
O(n²) / O(n) bei fast sortiert. Einsortieren wie Karten.
Merge Sort
O(n log n). Teile und herrsche. Stabil, aber O(n) Extra-Speicher.
O-Klassen
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Array
O(1) Zugriff, O(n) Einfügen/Löschen mittendrin. Cache-freundlich.
Verkettete Liste
O(n) Zugriff, O(1) Einfügen am Anfang. Flexibel in der Größe.
Stack (LIFO)
push/pop in O(1). „Last In, First Out". Undo, Call-Stack, Klammern.
Queue (FIFO)
enqueue/dequeue in O(1). „First In, First Out". Druckaufträge, Tasks.
Binärbaum (BST)
Balanciert: O(log n) für alle Operationen. Sortierung integriert.
Hash-Map
O(1) im Durchschnitt. Schlüssel → Wert. Hash-Funktion, Kollisionen.
Wer in der Klausur Fachbegriffe wie „Determiniertheit", „Best/Worst Case", „Divide and Conquer", „Stack Overflow", „Hash-Kollision" und „Balancierter Baum" treffsicher einsetzt, hebt sich von der Masse ab – das macht in der Punktevergabe oft den Unterschied.
Zusammenfassung & Kursabschluss
Damit ist der Kurs Algorithmen & Datenstrukturen abgeschlossen. Eine komplette Tour durch die Grundlagen: was ein Algorithmus überhaupt ist, die wichtigsten Darstellungsformen Struktogramm und Pseudocode, die drei Kontrollstrukturen als Bausteine aller Algorithmen, Rekursion als elegante Alternative zu Schleifen, konkrete Verfahren wie Suche und Sortierung, die O-Notation zur Bewertung und schließlich die wichtigsten Datenstrukturen. Die wichtigsten Take-Aways: Algorithmen sind präzise, terminierte Lösungswege. Mit drei Kontrollstrukturen lässt sich alles ausdrücken. Suche und Sortierung gehören zu den am meisten genutzten Algorithmen. O-Notation beschreibt Wachstum, nicht konkrete Zeit. Die richtige Datenstruktur entscheidet oft mehr als der Algorithmus. Logische Anschlüsse: die Konzepte aus diesem Kurs setzt du in K40a (Java Grundlagen) und K41a (Python) in echten Code um. Datenbank-Indizes (K36) nutzen B-Bäume zur schnellen Suche. Redis (K37) ist im Kern eine massive Hash-Map. Hashing (K11) ist die Grundlage von Hash-Maps und vielen anderen Anwendungen. Wer die Grundlagen aus diesem Kurs verinnerlicht hat, hat das Fundament für nahezu jedes Software-Thema gelegt – Algorithmen und Datenstrukturen sind das eigentliche Herz der Informatik.