BW Abitur Informatics cheat sheet

Komplexitätsklassen: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n); O-Notation beschreibt die obere Schranke des Wachstums für n → ∞.

Balancierte Binärbäume (AVL, Rot-Schwarz) garantieren Höhe O(log n); ein entarteter Baum hat Höhe O(n) und damit Suchzeit O(n).

Binäre Suche: Voraussetzung sortiertes Feld, Laufzeit O(log n), Halbierung des Intervalls pro Schritt; lineare Suche O(n).

Sortierverfahren: Bubblesort/Insertionsort O(n²), Mergesort/Heapsort O(n log n) garantiert, Quicksort im Mittel O(n log n), im Worst Case O(n²).

Stapel (Stack) arbeitet LIFO mit push/pop, Schlange (Queue) arbeitet FIFO mit enqueue/dequeue; beide O(1) bei geeigneter Implementierung.

Hashverfahren: mittlere Zugriffszeit O(1); Kollisionen werden durch Verkettung oder offene Adressierung (Sondieren) aufgelöst; Lastfaktor beeinflusst die Performance.

Dijkstra findet kürzeste Wege von einer Quelle bei nicht-negativen Kantengewichten; mit Prioritätswarteschlange O((V+E) log V).

Tiefensuche (DFS) nutzt einen Stack bzw. Rekursion und findet Zusammenhangskomponenten; Breitensuche (BFS) nutzt eine Queue und liefert kürzeste Wege in ungewichteten Graphen.

Kontrollstrukturen: Sequenz, Verzweigung (if/else) und Schleife (while, for); while prüft vor dem Durchlauf, do-while nach dem Durchlauf.

Datentypen: primitive Typen (int, double, boolean, char) speichern Werte, Referenztypen speichern Verweise auf Objekte; Vergleich mit == vs. equals() beachten.

Objektorientierung: Klasse als Bauplan, Objekt als Instanz; Kapselung durch private Attribute und öffentliche Methoden; Vererbung mit extends, Polymorphie durch Überschreiben.

Rekursion besteht aus Abbruchbedingung und Rekursionsschritt; jeder Aufruf belegt einen Stack-Rahmen, tiefe Rekursion kann zu StackOverflow führen.

UML-Klassendiagramm: Sichtbarkeit + public, - private, # protected; Assoziation mit Multiplizität, Vererbung als Pfeil mit hohler Dreiecksspitze.

Modellierung: Zustandsdiagramme beschreiben Zustände und Übergänge, Aktivitätsdiagramme den Ablauf; Entity-Relationship-Modelle die Datenstruktur.

Fehlerarten: Syntaxfehler verhindern die Übersetzung, Laufzeitfehler (z. B. Division durch 0) treten bei Ausführung auf, logische Fehler liefern falsche Ergebnisse ohne Absturz.

Testen: Äquivalenzklassen und Grenzwerte bilden Testfälle; ein Testfall besteht aus Eingabe, erwartetem Ergebnis und tatsächlichem Ergebnis.

Von-Neumann-Architektur: Steuerwerk, Rechenwerk (ALU), Speicherwerk, Ein-/Ausgabewerk und Bussystem; Programm und Daten liegen im selben Speicher (Flaschenhals).

Befehlszyklus: Fetch (Befehl holen), Decode (entschlüsseln), Execute (ausführen), Write-back; der Programmzähler zeigt auf den nächsten Befehl.

Speicherhierarchie nach Zugriffszeit: Register < Cache (L1/L2/L3) < Hauptspeicher (RAM) < SSD/Festplatte; Cache nutzt Lokalität von Zugriffen.

Dualzahlen: n Bit stellen 2^n Werte dar; Umrechnung durch fortgesetzte Division durch 2 bzw. Stellenwertverfahren; Zweierkomplement für negative ganze Zahlen.

IP-Adressen (IPv4) sind 32 Bit, in vier Dezimaloktetten notiert; die Subnetzmaske trennt Netz- und Hostanteil; IPv6 nutzt 128 Bit.

OSI-Schichtenmodell (7 Schichten): Physical, Data Link, Network, Transport, Session, Presentation, Application; TCP/IP-Modell fasst dies in vier Schichten zusammen.

TCP ist verbindungsorientiert mit Drei-Wege-Handshake (SYN, SYN-ACK, ACK) und sichert Reihenfolge und Vollständigkeit; UDP ist verbindungslos ohne Garantien.

Ports adressieren Dienste: HTTP 80, HTTPS 443, SMTP 25, DNS 53; DNS löst Domänennamen in IP-Adressen auf.

Relationales Modell: Tabelle (Relation) mit Attributen (Spalten) und Datensätzen (Zeilen); der Primärschlüssel identifiziert eindeutig, der Fremdschlüssel verweist auf einen Primärschlüssel.

SQL-Grundbefehle: SELECT … FROM … WHERE … GROUP BY … HAVING … ORDER BY; DML (INSERT, UPDATE, DELETE) ändert Daten, DDL (CREATE, ALTER, DROP) ändert das Schema.

JOIN verknüpft Tabellen über Schlüssel: INNER JOIN liefert nur übereinstimmende Zeilen, LEFT JOIN alle Zeilen der linken Tabelle plus passende der rechten.

Normalformen: 1NF atomare Werte, 2NF keine partiellen Abhängigkeiten vom Schlüssel, 3NF keine transitiven Abhängigkeiten; Ziel ist die Vermeidung von Redundanz und Anomalien.

Aggregatfunktionen COUNT, SUM, AVG, MIN, MAX fassen Zeilen zusammen; HAVING filtert Gruppen, WHERE filtert Zeilen vor der Gruppierung.

ACID-Eigenschaften von Transaktionen: Atomicity, Consistency, Isolation, Durability; ein Rollback macht eine unvollständige Transaktion rückgängig.

Datenschutz: personenbezogene Daten nach DSGVO; Grundsätze Datensparsamkeit, Zweckbindung, Rechtmäßigkeit und Betroffenenrechte (Auskunft, Löschung).

Informationsgesellschaft: Urheberrecht schützt Werke, Softwarelizenzen regeln Nutzung; digitale Signaturen und Verschlüsselung sichern Authentizität und Vertraulichkeit.