MV Abitur Computer Science cheat sheet

Eigenschaften eines Algorithmus: Determiniertheit, Determinismus, Endlichkeit, Terminierung, Ausführbarkeit, Allgemeinheit.

Drei Grundstrukturen der Kontrollflüsse: Sequenz, Selektion (if/else, switch) und Iteration (while = kopfgesteuert, do-while = fußgesteuert, for = zählergesteuert).

Rekursion braucht eine Abbruchbedingung (Basisfall) und einen Rekursionsschritt, der das Problem verkleinert; jeder rekursive Aufruf belegt einen Stack-Rahmen.

Jede rekursive Funktion ist in eine iterative mit explizitem Stack überführbar; umgekehrt gilt das ebenfalls.

Datentypen: primitive Typen (int, double, boolean, char) speichern Werte, Referenztypen speichern Adressen auf Objekte; int ist 32 Bit, long 64 Bit, double nach IEEE 754.

Ganzzahldivision schneidet ab, Modulo a % b liefert den Rest; bei negativen Operanden gilt in Java das Vorzeichen des Dividenden.

Laufzeitklassen: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ); binäre Suche O(log n) nur auf sortierten Feldern, lineare Suche O(n).

Sortieren: Bubblesort/Insertionsort O(n²), Mergesort/Heapsort O(n log n); Mergesort ist stabil, Heapsort nicht; Quicksort im Mittel O(n log n), im Worst Case O(n²).

Wertparameter werden kopiert, Referenzparameter übergeben die Objektadresse; eine Änderung am Objekt ist im Aufrufer sichtbar, eine Neu-Zuweisung der Referenz nicht.

Stack: LIFO-Prinzip, Operationen push, pop, top/isEmpty; Einsatz bei Klammerprüfung, Undo, Aufrufstack, Tiefensuche.

Queue: FIFO-Prinzip, Operationen enqueue, dequeue, front; Einsatz bei Druckerwarteschlange, Breitensuche, Puffer.

Liste: einfach verkettet (ein next-Zeiger), doppelt verkettet (next und prev); Einfügen an bekannter Position O(1), Suchen O(n).

Binärbaum: jeder Knoten höchstens zwei Kinder; binärer Suchbaum mit links < Wurzel < rechts erlaubt Suchen/Einfügen in O(h), h = Höhe, entartet O(n).

Traversierungen: Inorder (links-Wurzel-rechts, liefert beim Suchbaum sortierte Folge), Preorder, Postorder, Levelorder (Breitensuche mit Queue).

Relation = Tabelle, Tupel = Zeile, Attribut = Spalte; Schlüsselkandidat ist minimal und identifiziert jedes Tupel eindeutig, Primärschlüssel wird gewählt und ist NOT NULL.

Fremdschlüssel verweist auf den Primärschlüssel einer anderen Relation und sichert referentielle Integrität; Integritätsbedingungen sind Eindeutigkeit, NOT NULL und CHECK.

SQL-DQL: SELECT Spalten FROM Tabelle WHERE Bedingung GROUP BY ... HAVING ... ORDER BY; Ausführungsreihenfolge logisch: FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY.

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

Klasse = Bauplan (Attribute, Methoden, Sichtbarkeiten), Objekt = Instanz mit eigenem Zustand; Erzeugen mit new ruft den Konstruktor auf.

Kapselung: Attribute private, Zugriff über Getter/Setter; Sichtbarkeiten private (−), package (~), protected (#), public (+).

Vererbung: Unterklasse erbt Attribute und Methoden der Oberklasse (is-a), kann Methoden überschreiben (@Override) und mit super den Elternkonstruktor aufrufen.

Polymorphie: eine Referenzvariable des Obertyps kann Objekte aller Untertypen halten; der Methodenaufruf wird dynamisch zur Laufzeit gebunden.

Überladen (Overloading) = gleicher Name, unterschiedliche Signatur, statische Bindung; Überschreiben (Overriding) = gleiche Signatur in Unterklasse, dynamische Bindung.

Abstrakte Klasse kann abstrakte Methoden ohne Rumpf enthalten und nicht instanziiert werden; Interface deklariert nur Signaturen (und Konstanten) und erlaubt Mehrfachimplementierung.

UML-Klassendiagramm: Rechteck mit drei Kompartimenten (Name, Attribute, Operationen), Attribute als sichtbarkeit name: Typ.

Beziehungen im UML-Klassendiagramm: Assoziation mit Multiplizitäten, Aggregation (Raute, Teil kann ohne Ganzes existieren), Komposition (gefüllte Raute, existenzabhängig), Vererbung (leerer Dreieckspfeil).

UML-Objektdiagramm zeigt konkrete Instanzen mit unterstrichenem Namen der Form objekt: Klasse und konkreten Attributwerten; es beschreibt einen Schnappschuss des Systems.

Boolesche Algebra: AND (∧), OR (∨), NOT (¬), XOR (⊕); Gesetze von De Morgan: ¬(a∧b) = ¬a∨¬b und ¬(a∨b) = ¬a∧¬b.

Jede Schaltfunktion lässt sich als disjunktive Normalform (DNF, Summe von Mintermen) oder konjunktive Normalform darstellen; KV-Diagramme minimieren auf Primimplikanten.

Halbaddition: Summe = a⊕b, Übertrag = a∧b; Volladdierer verknüpft zwei Halbaddierer und ein ODER für den Übertrag; n-Bit-Addierer durch Reihenschaltung.

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

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

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

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

IPv4-Adresse 32 Bit, Subnetzmaske trennt Netz- und Hostanteil; Anzahl Hosts = 2^(Hostbits) − 2; private Bereiche 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16.

Client-Server: Client stellt Anfrage, Server antwortet zustandslos (HTTP) oder zustandsbehaftet; Ports identifizieren Dienste, z. B. 80 HTTP, 443 HTTPS, 25 SMTP, 53 DNS.

Chomsky-Hierarchie: Typ 3 regulär (rechtslineare Grammatik, endlicher Automat), Typ 2 kontextfrei (Kellerautomat), Typ 1 kontextsensitiv (linear beschränkter Automat), Typ 0 rekursiv aufzählbar (Turingmaschine).

Reguläre Ausdrücke: ∅, ε, Einzelzeichen als Basis; Operationen Vereinigung (|), Konkatenation, Kleene-Stern (*); Priorität Stern vor Konkatenation vor Vereinigung.

Deterministischer endlicher Automat (DEA) ist ein 5-Tupel (Z, Σ, δ, z₀, E) mit δ: Z×Σ→Z; ein NEA erlaubt mehrere oder keine Folgezustände und ε-Übergänge.

Satz von Kleene: Sprache ist regulär genau dann, wenn ein DEA/NEA sie akzeptiert, genau dann, wenn ein regulärer Ausdruck sie beschreibt.

Jeder NEA ist per Potenzmengenkonstruktion in einen DEA überführbar (Zustände des DEA sind Teilmengen der NEA-Zustände); Pumping-Lemma widerlegt Regularität.

Kontextfreie Grammatik G = (V, Σ, P, S); Ableitungsbaum und Links-/Rechtsableitung; mehrdeutig, wenn ein Wort zwei verschiedene Ableitungsbäume hat.

Kellerautomat erkennt genau die kontextfreien Sprachen; der Keller erlaubt das Zählen nicht-regulärer Strukturen wie aⁿbⁿ.

Parser-Verfahren: LL(k) arbeitet top-down mit Vorausschau, LR(k) bottom-up mit Shift-Reduce; rekursiver Abstieg ist ein LL-Verfahren.

Entscheidbarkeit: Halteproblem ist unentscheidbar (Diagonalisierung), Leerheit und Äquivalenz von DEA sind entscheidbar; das Schnittproblem kontextfreier Sprachen ist unentscheidbar.

DSGVO-Grundsätze (Art. 5): Rechtmäßigkeit, Verarbeitung nach Treu und Glauben, Transparenz, Zweckbindung, Datenminimierung, Richtigkeit, Speicherbegrenzung, Integrität/Vertraulichkeit, Rechenschaftspflicht.

Personenbezogene Daten sind alle Informationen über eine identifizierte oder identifizierbare natürliche Person; besondere Kategorien (Art. 9) wie Gesundheit oder Religion sind besonders geschützt.

Betroffenenrechte: Auskunft (Art. 15), Berichtigung (16), Löschung (17), Einschränkung (18), Datenübertragbarkeit (20), Widerspruch (21).

Rechtsgrundlagen der Verarbeitung (Art. 6): Einwilligung, Vertrag, rechtliche Verpflichtung, lebenswichtige Interessen, öffentliches Interesse, berechtigtes Interesse; Einwilligung muss freiwillig, informiert und widerrufbar sein.

Datenschutz durch Technikgestaltung und datenschutzfreundliche Voreinstellungen (Art. 25); Auftragsverarbeitung erfordert Vertrag nach Art. 28.

Meldepflicht bei Datenschutzverletzung an die Aufsichtsbehörde binnen 72 Stunden (Art. 33), bei hohem Risiko zusätzlich an Betroffene (Art. 34).

Schutzziele der Informationssicherheit: Vertraulichkeit, Integrität, Verfügbarkeit (CIA); ergänzend Authentizität, Verbindlichkeit/Nichtabstreitbarkeit.

Kryptografie: symmetrisch (AES, ein gemeinsamer Schlüssel, schnell) vs. asymmetrisch (RSA, Public/Private Key); Hashfunktionen (SHA-256) sind Einwegfunktionen für Integrität, nicht zur Verschlüsselung.

Urheberrecht: Werke sind geschützt, Software zählt zu Sprachwerken; Nutzungsrechte müssen eingeräumt werden, Open Source regelt Rechte über Lizenzen wie GPL (Copyleft) oder MIT (permissiv).