Informatik – Grundlegendes Anforderungsniveau (gA)
Die Abiturprüfung im Fach Informatik auf grundlegendem Anforderungsniveau prüft zentrale Konzepte der objektorientierten Modellierung, ausgewählte Datenstrukturen und Algorithmen, Grundlagen relationaler Datenbanken sowie endliche Automaten. Die Aufgaben verlangen meist die Analyse vorgegebener Modelle, die Formulierung von Algorithmen und die sichere Anwendung von Fachbegriffen.
Objektorientierte Modellierung
- Klasse = Bauplan, Objekt = Instanz; Attribute (Daten), Methoden (Verhalten).
- Kapselung: Attribute private, Zugriff über getter/setter.
- Vererbung: generalisierende Oberklasse, spezialisierende Unterklasse; „ist-ein“-Beziehung.
- Assoziation: „hat-ein“-Beziehung, mit Multiplizitäten.
- Polymorphie: gleiche Methode, unterschiedliche Implementierung.
Datenstrukturen und Algorithmen
- Array: fester Speicher, direkter Zugriff O(1); verkettete Liste: dynamisch, Einfügen O(1), Suchen O(n).
- Stack (LIFO): push/pop; Queue (FIFO): enqueue/dequeue.
- Binärer Suchbaum: links < Wurzel < rechts; Inorder-Traversierung liefert sortierte Folge.
- Suchen: linear O(n), binär O(log n) nur bei sortiertem Array.
- Sortieren: Bubble/Insertion/Selection O(n²); Merge O(n log n).
Datenbanken
- ER-Modell: Entität, Beziehung, Attribut; Kardinalitäten (1:1, 1:n, m:n).
- Relationenmodell: Tabelle, Primärschlüssel, Fremdschlüssel; m:n wird zu Zwischentabelle.
- Normalformen: 1NF (atomar), 2NF (keine partiellen Abhängigkeiten), 3NF (keine transitiven Abhängigkeiten).
- SQL: SELECT ... FROM ... WHERE ... GROUP BY ... HAVING ... ORDER BY; JOIN über Fremdschlüssel.
Automaten und formale Sprachen
- Deterministischer endlicher Automat (DEA): Zustände, Eingabealphabet, Übergangsfunktion, Startzustand, Endzustände.
- Akzeptiert genau die Wörter, die vom Start- in einen Endzustand führen.
- Reguläre Ausdrücke und Syntaxdiagramme beschreiben reguläre Sprachen.
Fallbeispiel: DEA für „gerade Anzahl von a“
Aufgabe: Konstruiere DEA über {a,b}, der alle Wörter mit gerader Anzahl von a akzeptiert. Lösung: Zustände Z0 (gerade, Start, Endzustand) und Z1 (ungerade). Übergänge: a wechselt Zustand, b bleibt. Z0 --a--> Z1, Z1 --a--> Z0; b-Schleifen. Endzustand Z0. Begründung: Jedes a ändert die Parität; b beeinflusst nicht. Der Automat ist deterministisch, vollständig (für jedes Symbol Übergang definiert).
Typische Fallen
- Verwechslung von „ist-ein“ (Vererbung) und „hat-ein“ (Assoziation).
- Binäre Suche auf unsortiertem Array anwenden.
- Bei SQL: WHERE filtert Zeilen vor GROUP BY, HAVING filtert Gruppen danach; NULL in COUNT(*) vs. COUNT(spalte) beachten.
- DEA: unvollständige Übergänge (fehlender Übergang = nicht deterministisch) oder Endzustand mit Startzustand verwechseln.
- Rekursion ohne Abbruchbedingung.