BW Abitur Informatics flashcards

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

O-Notation

Notation für die obere Wachstumsschranke einer Laufzeit oder Speicherfunktion. f(n) = O(g(n)) bedeutet, dass f für große n höchstens proportional zu g wächst.

Binäre Suche

Suchverfahren in einem sortierten Feld, das das Intervall pro Schritt halbiert. Laufzeit O(log n), Voraussetzung ist die Sortierung der Daten.

Stack (Stapel)

Datenstruktur nach dem LIFO-Prinzip: Das zuletzt eingefügte Element wird zuerst entnommen. Operationen push und pop laufen in O(1).

Queue (Schlange)

Datenstruktur nach dem FIFO-Prinzip: Das zuerst eingefügte Element wird zuerst entnommen. Operationen enqueue und dequeue laufen in O(1) bei geeigneter Implementierung.

Hashverfahren

Speichertechnik, bei der eine Hashfunktion einen Schlüssel auf einen Index abbildet. Mittlere Zugriffszeit O(1); Kollisionen werden durch Verkettung oder Sondieren behandelt.

Mergesort

Stabiles Sortierverfahren nach dem Teile-und-Herrsche-Prinzip: Liste halbieren, Teile sortieren, zusammenfügen. Laufzeit O(n log n) im besten, mittleren und schlechtesten Fall.

Quicksort

Sortierverfahren nach Teile-und-Herrsche: Ein Pivotelement teilt die Folge, dann rekursive Sortierung der Teile. Im Mittel O(n log n), im Worst Case O(n²).

Dijkstra-Algorithmus

Verfahren zur Berechnung kürzester Wege von einer Startknoten zu allen anderen bei nicht-negativen Kantengewichten. Mit Prioritätswarteschlange O((V+E) log V).

Tiefensuche (DFS)

Graphdurchlauf, der einen Pfad möglichst weit verfolgt und dann zurückgeht; nutzt Stack oder Rekursion. Findet Zusammenhangskomponenten und erkennt Zyklen.

Breitensuche (BFS)

Graphdurchlauf, der alle Nachbarn eines Knotens zuerst besucht; nutzt eine Queue. Liefert in ungewichteten Graphen kürzeste Wege in Anzahl der Kanten.

Rekursion

Eine Methode ruft sich selbst auf und benötigt eine Abbruchbedingung. Jeder Aufruf belegt einen Stack-Rahmen; fehlende Abbruch führt zu StackOverflow.

Kapselung

Prinzip der objektorientierten Programmierung: Attribute werden private deklariert und nur über öffentliche Methoden gelesen oder verändert. Schützt vor unkontrolliertem Zugriff.

Polymorphie

Gleiche Methodensignatur kann in Unterklassen unterschiedlich implementiert werden. Der Aufruf entscheidet zur Laufzeit, welche Methode ausgeführt wird (dynamisches Binden).

Vererbung

Eine Unterklasse übernimmt Attribute und Methoden der Oberklasse und kann sie erweitern oder überschreiben. In UML als Pfeil mit hohler Dreiecksspitze dargestellt.

UML-Klassendiagramm

Statisches Modell der Klassen mit Attributen, Methoden und Sichtbarkeiten (+ public, - private, # protected). Beziehungen wie Assoziation und Vererbung werden als Linien dargestellt.

Syntax- und Laufzeitfehler

Syntaxfehler verhindern die Übersetzung des Programms. Laufzeitfehler treten erst bei der Ausführung auf, etwa Division durch null oder Zugriff auf ein nicht vorhandenes Objekt.

Äquivalenzklassen beim Testen

Testverfahren, bei dem Eingaben in Klassen mit gleichem erwarteten Verhalten eingeteilt werden. Je ein Testfall pro Klasse, ergänzt durch Grenzwerte, deckt Fehler effizient auf.

Zustandsdiagramm

UML-Diagramm zur Modellierung von Zuständen eines Objekts und den Übergängen dazwischen. Übergänge werden durch Ereignisse und Bedingungen ausgelöst.

Von-Neumann-Architektur

Rechnermodell mit Steuerwerk, Rechenwerk, Speicher und Ein-/Ausgabe. Befehle und Daten liegen im selben Speicher; der gemeinsame Bus bildet den Von-Neumann-Flaschenhals.

Befehlszyklus

Ablauf der Befehlsverarbeitung: Fetch, Decode, Execute, Write-back. Der Programmzähler enthält die Adresse des nächsten auszuführenden Befehls und wird fortgeschrieben.

Speicherhierarchie

Anordnung von Registern, Cache, Hauptspeicher und Massenspeicher nach Zugriffszeit und Kapazität. Schnellere Ebenen sind kleiner und teurer; Caches nutzen räumliche und zeitliche Lokalität.

Zweierkomplement

Darstellung negativer Ganzzahlen im Binärsystem: Alle Bits invertieren und eins addieren. Das höchste Bit gibt das Vorzeichen an; n Bit stellen Werte von -2^(n-1) bis 2^(n-1)-1 dar.

Subnetzmaske

Bitmaske, die bei einer IPv4-Adresse den Netzanteil vom Hostanteil trennt. Einsen markieren das Netz, Nullen die Hosts; die CIDR-Notiz /24 entspricht 255.255.255.0.

OSI-Schichtenmodell

Modell mit sieben Schichten: Physical, Data Link, Network, Transport, Session, Presentation, Application. Jede Schicht erbringt Dienste für die darüberliegende und nutzt die darunterliegende.

TCP-Drei-Wege-Handshake

Verbindungsaufbau mit SYN, SYN-ACK und ACK. TCP garantiert Reihenfolge und Vollständigkeit der Daten; UDP bietet diese Garantien nicht und ist verbindungslos.

DNS

Domain Name System löst Domänennamen in IP-Adressen auf. Standardport ist 53; die Auflösung erfolgt hierarchisch über Root-, Top-Level- und autoritative Server.

Primär- und Fremdschlüssel

Der Primärschlüssel identifiziert jeden Datensatz einer Tabelle eindeutig. Ein Fremdschlüssel verweist auf einen Primärschlüssel einer anderen Tabelle und sichert referenzielle Integrität.

SQL INNER JOIN

Verknüpfung zweier Tabellen über einen Schlüssel, die nur Zeilen mit übereinstimmenden Werten in beiden Tabellen liefert. LEFT JOIN behält zusätzlich alle Zeilen der linken Tabelle.

Dritte Normalform

Eine Tabelle ist in 3NF, wenn sie in 2NF ist und keine transitiven Abhängigkeiten von Nicht-Schlüsselattributen zum Primärschlüssel bestehen. Reduziert Redundanz und Änderungsanomalien.

ACID-Eigenschaften

Eigenschaften von Datenbanktransaktionen: Atomicity (ganz oder gar nicht), Consistency (gültiger Zustand), Isolation (keine Wechselwirkung paralleler Transaktionen) und Durability (dauerhafte Speicherung).

SQL GROUP BY und HAVING

GROUP BY fasst Zeilen mit gleichen Werten zu Gruppen zusammen, oft mit COUNT, SUM oder AVG. HAVING filtert diese Gruppen; WHERE filtert einzelne Zeilen vor der Gruppierung.

DSGVO-Grundsätze

Regeln für personenbezogene Daten: Rechtmäßigkeit, Zweckbindung, Datenminimierung, Richtigkeit, Speicherbegrenzung, Integrität und Rechenschaftspflicht. Betroffene haben Recht auf Auskunft und Löschung.