Algorithmen

Lernfokus

AP2 Anwendungsentwicklung: Abläufe strukturiert darstellen, Standardverfahren zum Sortieren und Suchen einordnen und ihren Aufwand mit der O-Notation bewerten.

• Kontrollstrukturen im Struktogramm und Pseudocode sicher lesen und schreiben.
• Sortier- und Suchverfahren nach Prinzip und Voraussetzung unterscheiden.
• Laufzeitkomplexität in O-Notation einordnen und Rekursion sauber aufbauen.

Struktogramm & Pseudocode

Jeder Algorithmus lässt sich aus drei Grundstrukturen zusammensetzen, die im Struktogramm (Nassi-Shneiderman) als geschachtelte Blöcke ohne Sprünge gezeichnet werden.

• Sequenz: Anweisungen werden streng nacheinander abgearbeitet – ein einfaches Rechteck.
• Verzweigung: ein dreieckiger Bedingungskopf teilt in Ja- und Nein-Zweig (if-else).
• Schleife: kopfgesteuert (while) prüft vor dem Durchlauf – ggf. null Durchläufe; fußgesteuert (do-while) prüft danach – mindestens ein Durchlauf.

Merksatz: Sequenz, Verzweigung, Schleife – mit diesen drei Bausteinen kommt jeder strukturierte Algorithmus ohne GOTO aus.

Sortier- & Suchverfahren

Sortier- und Suchverfahren unterscheiden sich in Vorgehen und Voraussetzung – genau das wird in der AP2 gern abgefragt.

• Einfache Sortierer: Bubblesort (Nachbarn tauschen), Selectionsort (Minimum suchen), Insertionsort (einsortieren) – meist O(n²).
• Effiziente Sortierer: Mergesort und Quicksort nach dem Prinzip „Teile und herrsche" – im Mittel O(n log n), Quicksort im schlechtesten Fall O(n²).
• Suche: lineare Suche geht der Reihe nach durch (O(n)); die binäre Suche halbiert den Bereich (O(log n)).

Merksatz: Die binäre Suche funktioniert nur auf sortierten Daten – ohne Sortierung bleibt nur die lineare Suche.

O-Notation

Die O-Notation beschreibt, wie der Aufwand mit der Eingabegröße n wächst – unabhängig von Hardware und Konstanten.

• O(1): konstant, z. B. Array-Zugriff über den Index.
• O(log n): halbierend, z. B. binäre Suche; O(n): linear, z. B. lineare Suche.
• O(n log n): gute Sortierer (Merge-/Quicksort); O(n²): verschachtelte Schleifen, z. B. Bubblesort.

Merksatz: Nach steigendem Aufwand gilt O(1) < O(log n) < O(n) < O(n log n) < O(n²).

Rekursion

Eine rekursive Funktion löst ein Problem, indem sie sich mit einem verkleinerten Teilproblem selbst aufruft.

• Basisfall: Abbruchbedingung, die ein Ergebnis ohne weiteren Selbstaufruf liefert.
• Rekursionsschritt: Selbstaufruf mit kleinerem Teilproblem, das dem Basisfall näherkommt.
• Stack: jeder Aufruf belegt einen eigenen Stack-Frame – zu tiefe Rekursion führt zum Stack Overflow.

Merksatz: Ohne erreichbaren Basisfall wird jede Rekursion zur Endlosrekursion und läuft in den Stack Overflow.

Prüfungsmodus

Dieser ProtocolCheck führt dich durch die wichtigsten AP2-Aspekte dieses Themas. Du kannst Antworten prüfen, Fragen überspringen und bekommst am Ende eine Auswertung nach Kategorie.