MV Abitur Computer Science flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Determinismus

Eigenschaft eines Algorithmus: Bei gleicher Eingabe und gleichem Zustand führt jeder Schritt eindeutig zum selben nächsten Zustand, das Ergebnis ist also vorhersagbar und reproduzierbar.

Basisfall der Rekursion

Abbruchbedingung einer rekursiven Funktion, die ohne weiteren Selbstaufruf einen Wert liefert. Fehlt sie oder wird sie nie erreicht, entsteht ein Stack Overflow durch unendliche Rekursion.

Kopfgesteuerte Schleife

while-Schleife: Die Bedingung wird vor jedem Durchlauf geprüft. Ist sie anfangs falsch, läuft der Rumpf null Mal. Die fußgesteuerte do-while-Schleife prüft erst nach dem Rumpf.

Binäre Suche

Suchverfahren auf sortierten Feldern: Der mittlere Wert wird verglichen und jeweils eine Hälfte ausgeschlossen. Laufzeit O(log n), Voraussetzung ist die Sortierung.

Stabile Sortierung

Ein Sortierverfahren ist stabil, wenn gleiche Schlüssel ihre relative Reihenfolge behalten. Mergesort und Insertionsort sind stabil, Quicksort und Heapsort in der Regel nicht.

Stack (Keller)

Datenstruktur nach dem LIFO-Prinzip: Das zuletzt eingefügte Element wird zuerst entnommen. Operationen sind push, pop und top; Anwendung bei Aufrufstack, Klammerprüfung und Tiefensuche.

Queue (Warteschlange)

Datenstruktur nach dem FIFO-Prinzip: Das zuerst eingefügte Element wird zuerst entnommen. Operationen sind enqueue und dequeue; Anwendung bei Druckerwarteschlangen und Breitensuche.

Binärer Suchbaum

Binärbaum, in dem für jeden Knoten alle Werte im linken Teilbaum kleiner und im rechten größer sind. Suchen und Einfügen kosten O(h); inorder traversiert liefert sortierte Werte.

Inorder-Traversierung

Baumdurchlauf in der Reihenfolge linker Teilbaum, Wurzel, rechter Teilbaum. Bei einem binären Suchbaum ergibt sich dabei die aufsteigend sortierte Folge der Schlüssel.

Primärschlüssel

Minimaler Schlüsselkandidat, der jedes Tupel einer Relation eindeutig identifiziert. Er wird ausgewählt, ist eindeutig und darf niemals NULL sein.

Fremdschlüssel

Attribut einer Relation, das auf den Primärschlüssel einer anderen Relation verweist. Er sichert die referentielle Integrität, da nur existierende Verweise erlaubt sind.

Dritte Normalform

Eine Relation ist in 3NF, wenn sie in 2NF ist und keine transitiven Abhängigkeiten von Nichtschlüsselattributen zum Schlüssel bestehen. Ziel sind Redundanzfreiheit und Vermeidung von Anomalien.

SQL GROUP BY und HAVING

GROUP BY fasst Zeilen mit gleichen Werten zu Gruppen zusammen. HAVING filtert diese Gruppen nach Aggregatfunktionen wie COUNT oder SUM, während WHERE einzelne Zeilen vor der Gruppierung filtert.

Kapselung

Objektorientiertes Prinzip: Interne Attribute werden private deklariert und nur über öffentliche Methoden gelesen oder geändert. Das schützt Invarianten und entkoppelt Schnittstelle von Implementierung.

Dynamische Bindung

Zur Laufzeit wird anhand des tatsächlichen Objekttyps entschieden, welche überschriebene Methode ausgeführt wird. Sie ermöglicht Polymorphie über Referenzen des Obertyps.

Überschreiben (Overriding)

Eine Unterklasse definiert eine Methode mit gleicher Signatur wie die Oberklasse neu. Der Aufruf wird dynamisch gebunden; super ruft die Version der Oberklasse auf.

Überladen (Overloading)

Mehrere Methoden gleichen Namens unterscheiden sich in Anzahl oder Typ der Parameter. Der Compiler wählt statisch anhand der Signatur, also zur Übersetzungszeit.

Abstrakte Klasse

Klasse, die nicht instanziiert werden kann und abstrakte Methoden ohne Rumpf enthalten darf. Unterklassen müssen diese implementieren; anders als beim Interface ist nur Einfachvererbung möglich.

UML-Komposition

Gefüllte Raute am Ganzen: Die Teile existieren nicht ohne das Ganze und werden mit ihm erzeugt und gelöscht. Abzugrenzen von der Aggregation mit leerer Raute.

De Morgan-Gesetze

Boolesche Umformungsregeln: ¬(a ∧ b) = ¬a ∨ ¬b und ¬(a ∨ b) = ¬a ∧ ¬b. Sie erlauben, Negationen in Schaltfunktionen auf die Operanden zu verschieben.

Disjunktive Normalform

Darstellung einer Schaltfunktion als ODER-Verknüpfung von Mintermen, die jeweils alle Variablen als Konjunktion enthalten. Jede Wahrheitstabelle lässt sich direkt in DNF überführen.

Von-Neumann-Flaschenhals

Begrenzung der Rechenleistung, weil Befehle und Daten über denselben Speicher und Bus laufen. CPU und Speicher können daher nicht gleichzeitig Befehle und Daten austauschen.

Drei-Wege-Handshake

Verbindungsaufbau bei TCP mit SYN, SYN-ACK und ACK. Er synchronisiert Sequenznummern beider Seiten und stellt sicher, dass beide Richtungen erreichbar sind.

Subnetzmaske

32-Bit-Maske, die bei IPv4 den Netzanteil vom Hostanteil trennt. Bei n Hostbits ergeben sich 2ⁿ − 2 nutzbare Hostadressen, da Netz- und Broadcastadresse entfallen.

Reguläre Sprache

Sprache, die durch einen regulären Ausdruck, einen endlichen Automaten oder eine rechtslineare Grammatik beschrieben werden kann. Nach dem Satz von Kleene sind diese drei Darstellungen äquivalent.

Deterministischer endlicher Automat

5-Tupel aus Zustandsmenge, Eingabealphabet, Übergangsfunktion, Startzustand und Endzuständen. Die Übergangsfunktion ordnet jedem Zustand-Zeichen-Paar genau einen Folgezustand zu.

Potenzmengenkonstruktion

Verfahren, das einen nichtdeterministischen endlichen Automaten in einen äquivalenten deterministischen umwandelt. Die Zustände des DEA sind dabei Teilmengen der NEA-Zustände.

Kellerautomat

Maschinenmodell mit einem zusätzlichen Kellerspeicher, das genau die kontextfreien Sprachen akzeptiert. Der Keller erlaubt das Zählen, etwa bei aⁿbⁿ.

Kontextfreie Grammatik

Grammatik, deren Produktionen auf der linken Seite genau eine Variable haben. Sie beschreibt Sprachen, die ein Kellerautomat erkennt, und wird für Syntaxdefinitionen von Programmiersprachen genutzt.

Halteproblem

Problem, ob ein gegebenes Programm bei gegebener Eingabe terminiert. Es ist nach Turing unentscheidbar, bewiesen durch Diagonalisierung; für konkrete Fälle kann die Antwort dennoch bekannt sein.

Zweckbindung

DSGVO-Grundsatz nach Art. 5: Personenbezogene Daten dürfen nur für festgelegte, eindeutige und legitime Zwecke erhoben werden. Eine spätere zweckfremde Nutzung ist unzulässig.

Recht auf Löschung

Betroffenenrecht nach Art. 17 DSGVO: Daten sind zu löschen, wenn der Zweck entfällt, die Einwilligung widerrufen wird oder die Verarbeitung unrechtmäßig war, vorbehaltlich gesetzlicher Aufbewahrungspflichten.