Abitur NRW Informatik – Lernzettel zu Objekten, Datenstrukturen & Algorithmen

Objekte & Klassen

Modellierung im Vergleich

Die Strukturierung von Objekten erfolgt über verschiedene Diagrammtypen.

• Klassendiagramm: Liefert abstrakte, generelle Vorgaben für Attribute und Datentypen.
• Implementationsdiagramm: Zeigt konkrete Details für die Programmierung inklusive Methoden wie Gettern und Settern.
• Objektdiagramm: Bildet reale Zustände und konkrete Attributswerte einzelner Objekte ab.

Beziehungen & Vererbung

Klassen stehen in Beziehung zueinander.

• Vererbung: Eine Unterklasse übernimmt alle Attribute und Methoden der Oberklasse.
• Assoziation: Beschreibt Verbindungen zwischen Klassen unter Angabe von Multiplizitäten wie $0..*$ oder $1$.

💡 Tipp: Achte bei der Vererbung darauf, dass die Unterklasse nur spezialisierte Attribute neu definieren muss.

Dynamische Datenstrukturen

Lineare Datenstrukturen

Zur flexiblen Verwaltung von Datenmengen im Arbeitsspeicher während der Laufzeit.

• Queue: Arbeitet strikt nach dem FIFO-Prinzip (First-In-First-Out), wie eine Warteschlange.
• Stack: Nutzt das LIFO-Prinzip (Last-In-First-Out), vergleichbar mit einem Stapel Teller.
• List: Eine dynamische Kette mit Zeigern, bei der du Elemente flexibel einfügen, löschen und durchschreiten kannst.

Wichtige Methoden

Jede Struktur besitzt spezifische Standardoperationen für den Zugriff.

• Queue-Methoden: enqueue(inhalt) zum Anfügen, dequeue() zum Entfernen des ersten Elements.
• Stack-Methoden: push(inhalt) legt ein Element oben ab, pop() löscht das oberste Element.

💡 Tipp: Mit isEmpty() solltest du immer prüfen, ob die Struktur leer ist, bevor du ein Element entfernst.

Statische Datenstrukturen & Algorithmen

Das Array

Ein Array ist eine statische, lineare Datenstruktur für Daten des gleichen Typs.

• Eigenschaften: Die Größe ist fest definiert und der Zugriff erfolgt direkt über den Index.
• Mehrdimensional: Arrays können verschachtelt werden, um Tabellen oder Matrizen darzustellen.

Primitiver Sortiervergleich

Einfache Algorithmen bringen ungeordnete Arrays in eine feste Reihenfolge.

• Bubblesort: Vergleicht und vertauscht benachbarte Elemente, bis alles sortiert ist.
• Insertionsort: Fügt Elemente nacheinander an der passenden Stelle im bereits sortierten Bereich ein.

Beispiel: Sortieren mit Bubblesort für [12, 2]:

1. Vergleiche $12$ und $2$ $\rightarrow$ $12 > 2$, also tauschen.
2. Ergebnis: [2, 12] (sortiert).

💡 Tipp: Der Index eines Arrays startet in Java immer bei $0$, weshalb das letzte Element bei Index length - 1 liegt.

Fortgeschrittene Sortierung & Bäume

Effiziente Algorithmen

Komplexere Verfahren arbeiten deutlich schneller als primitive Sortieralgorithmen.

• Selectionsort: Sucht gezielt das Maximum oder Minimum und tauscht es auf die Zielposition.
• Quicksort: Teilt die Liste rekursiv anhand eines Pivotelements in "kleiner" und "größer".

Binäre Bäume

Hierarchische, nicht-lineare Datenstrukturen aus Knoten und Kanten ohne Zyklen.

• Binärer Suchbaum: Für jeden Knoten gilt die feste Ordnungsrelation: links kleiner, rechts größer.
• AVL-Baum: Ein selbstbalancierender Suchbaum mit einem Balancefaktor von maximal $\pm 1$.

💡 Tipp: Nutze die binäre Suche auf sortierten Daten, da ihre Laufzeit mit $O(\log n)$ extrem effizient ist.

Traversierung & Struktogramme

Baum-Traversierung

Systematisches Durchlaufen aller Knoten eines Binärbaums über drei Hauptrouten.

• Inorder: Traversierung in der Reihenfolge: linker Teilbaum, Wurzel, rechter Teilbaum (sortierte Ausgabe).
• Preorder: Traversierung in der Reihenfolge: Wurzel, linker Teilbaum, rechter Teilbaum.
• Postorder: Traversierung in der Reihenfolge: linker Teilbaum, rechter Teilbaum, Wurzel.

Struktogramme

Nassi-Shneiderman-Diagramme dienen der logischen Visualisierung von Programmabläufen.

• Struktur: Sequenzen, Verzweigungen (If-Else) und Schleifen werden visuell ineinander geschachtelt.

💡 Tipp: Die Inorder-Traversierung eines binären Suchbaums liefert die Werte immer in aufsteigend sortierter Reihenfolge.

Relationale Datenbanken

Entwurf & Modellierung

Datenbanken sichern die dauerhafte und strukturierte Speicherung großer Datenmengen.

• ER-Modell: Entity-Relationship-Modell zur grafischen Darstellung von Objekten, Attributen und Beziehungen.
• Primärschlüssel: Identifiziert jeden Datensatz in einer Relation eindeutig.
• Fremdschlüssel: Verweist auf den Primärschlüssel einer anderen Tabelle, um Beziehungen abzubilden.

Anomalien vermeiden

Schlechtes Datenbankdesign führt zu Datenfehlern, die es zu verhindern gilt.

• Redundanz: Unnötige Mehrfachspeicherung identischer Daten.
• Inkonsistenz: Widersprüchliche Datenzustände durch unvollständige Updates (Update-Anomalie).

💡 Tipp: Ein zusammengesetzter Primärschlüssel besteht aus mehreren Attributen, die erst gemeinsam Eindeutigkeit garantieren.

SQL & Endliche Automaten

Strukturierte Abfragen

Mit SQL werden Daten gezielt aus relationalen Datenbanken abgefragt.

• Grundstruktur: SELECT bestimmt die Attribute, FROM die Tabellen und WHERE filtert die Zeilen.

Endliche Automaten

Modelle zur Beschreibung von Systemen mit Zuständen und Übergängen.

• Akzeptor: Ein erkennender Automat, der Eingaben prüft und in Endzuständen ($F$) akzeptiert.
• Mealy-Automat: Ein realer Automat, der bei jedem Zustandsübergang eine Ausgabe erzeugt.
• DEA / NEA: Deterministische Automaten haben pro Eingabe genau einen Folgezustand, nicht-deterministische mehrere.

Beispiel: Einfache SQL-Abfrage: SELECT Name FROM Schueler WHERE Stufe = 'Q2'

💡 Tipp: Einen unübersichtlichen NEA kannst du mittels Potenzmengenkonstruktion systematisch in einen DEA umwandeln.

Sprachen, Grammatiken & Netzwerke

Reguläre Grammatiken

Formale Beschreibung von Sprachen über ein mathematisches 4-Tupel $G = (N, T, S, P)$.

• Nichtterminale ($N$): Platzhaltervariablen, die während der Wortgenerierung ersetzt werden.
• Terminale ($T$): Die tatsächlichen, finalen Zeichen der Sprache.
• Produktionen ($P$): Die Ersetzungsregeln für die Generierung von Wörtern.

Rechnernetzwerke & Sicherheit

Konzepte zur physischen Verbindung und fehlerfreien Datenübertragung.

• Topologien: Netzstrukturen wie Stern, Ring oder das hochsichere vermaschte Netz.
• Fehlerdetektion: Verfahren wie das Paritätsbit oder die XOR-Prüfsumme sichern die Datenintegrität.

💡 Tipp: Ein Paritätsbit kann nur eine ungerade Anzahl an Bitfehlern zuverlässig erkennen.