Algorithmen und Programmierung
Der Bereich Algorithmen und Programmierung prüft, ob du einen Lösungsweg präzise beschreiben, in Kontrollstrukturen übersetzen und seine Korrektheit begründen kannst. Erwartet werden sichere Begriffe und nachvollziehbare Herleitungen, nicht nur lauffähiger Code.
Algorithmusbegriff
Ein Algorithmus ist eine endliche, eindeutige Vorschrift zur Lösung einer ganzen Klasse von Problemen. Prüfe immer die fünf Eigenschaften: Ausführbarkeit, Determiniertheit (gleiche Eingabe liefert gleiches Ergebnis), Determinismus (jeder Schritt ist eindeutig festgelegt), Terminierung (endlich viele Schritte) und Allgemeingültigkeit (für alle zulässigen Eingaben). Zur Darstellung dienen Pseudocode und Struktogramme; im Struktogramm stehen Sequenz, Selektion und Iteration als genormte Symbole.
Datentypen und Kontrollstrukturen
Primitive Typen sind int, double, boolean, char; zusammengesetzte Typen sind Array, String, Liste und Objekt. Unterscheide Wertzuweisung (=) von Vergleich (==) und beachte die ganzzahlige Division: 7/2 ergibt 3, nicht 3.5. Die drei Grundstrukturen sind Sequenz, Selektion (if/else, switch) und Iteration (while kopfgesteuert, do-while fußgesteuert, for zählergesteuert).
Rekursion
Jede rekursive Definition braucht einen Basisfall (Abbruch) und einen Rekursionsschritt, der das Problem echt verkleinert. Die Aufrufe liegen auf dem Call-Stack; fehlt der Basisfall oder verkleinert sich das Problem nicht, entsteht ein StackOverflowError.
Durchgerechnetes Beispiel
Fakultät: int fak(int n){ if (n <= 1) return 1; return n * fak(n-1); }
Abspur für fak(4): 4*fak(3) = 4*3*fak(2) = 4*3*2*fak(1) = 4*3*2*1 = 24. Begründung der Terminierung: Der Parameter sinkt in jedem Schritt um genau 1, der Basisfall n <= 1 wird nach n-1 Aufrufen erreicht. Für n < 0 wäre die Terminierung nicht gesichert, deshalb ist eine Vorbedingung n >= 0 nötig. Jede Rekursion lässt sich iterativ umschreiben (hier mit einer Schleife und einem Akkumulator) – funktional gleichwertig, aber ohne Stack-Wachstum.
Typische Fallen
=mit==verwechseln oder eine Zuweisung in der Bedingung verwenden.- Rekursion ohne (oder mit falsch greifendem) Basisfall; Rekursionsschritt, der den Parameter nicht verkleinert.
- Off-by-one in
for-Schleifen (i < nvs.i <= n) und bei Array-Indizes. - Integer-Division und Modulo bei negativen Zahlen falsch vorhersagen.
- Rekursion als „schneller“ bezeichnen: meist ist sie speicherintensiver.