BY Abitur Informatik gA key terms

Eine eindeutig beschriebene, endliche Folge von Anweisungen, die aus Eingabedaten in endlich vielen Schritten ein Ergebnis erzeugt. Jeder Schritt muss deterministisch ausführbar sein.

Eine festgelegte Art, Daten im Speicher anzuordnen und zu verwalten, damit bestimmte Operationen wie Suchen, Einfügen oder Löschen effizient möglich sind. Beispiele sind Array, Liste, Stack und Baum.

Eine Datenstruktur mit fester Anzahl gleichartiger Elemente, die über einen Index direkt angesprochen werden. Der Zugriff per Index ist konstant schnell, das Einfügen in der Mitte erfordert Verschieben.

Eine lineare Datenstruktur, bei der Elemente nur am oberen Ende abgelegt und entnommen werden. Es gilt das LIFO-Prinzip: Das zuletzt eingefügte Element wird zuerst entnommen.

Eine lineare Datenstruktur, bei der Elemente an einem Ende eingefügt und am anderen Ende entnommen werden. Es gilt das FIFO-Prinzip: Das zuerst eingefügte Element wird zuerst entnommen.

Eine Datenstruktur aus Knoten, die jeweils ein Datenelement und einen Verweis auf den nächsten Knoten enthalten. Einfügen und Löschen sind ohne Verschieben möglich, der Zugriff erfolgt nur sequenziell.

Eine hierarchische Datenstruktur, bei der jeder Knoten höchstens zwei Kindknoten hat, üblicherweise als linker und rechter Nachfolger unterschieden. Bäume dienen etwa zum schnellen Suchen und Sortieren.

Ein Binärbaum, in dem für jeden Knoten alle Werte im linken Teilbaum kleiner und alle im rechten Teilbaum größer sind. Dadurch lässt sich gezielt suchen; bei entarteten Bäumen sinkt die Effizienz.

Das systematische Besuchen aller Knoten eines Baumes in einer festgelegten Reihenfolge, etwa Inorder, Preorder oder Postorder. Die Reihenfolge bestimmt, in welcher Folge die Knotenwerte ausgegeben werden.

Ein Verfahren, bei dem eine Funktion sich selbst mit veränderten Parametern aufruft, bis eine Abbruchbedingung erreicht ist. Jeder rekursive Aufruf benötigt einen eigenen Speicherbereich auf dem Aufrufstapel.

Die Abbruchbedingung einer rekursiven Funktion, bei der kein weiterer Selbstaufruf erfolgt. Fehlt ein korrekter Basisfall oder wird er nie erreicht, endet die Rekursion nicht.

Die wiederholte Ausführung eines Anweisungsblocks mithilfe einer Schleife, bis eine Bedingung erfüllt ist. Im Gegensatz zur Rekursion entsteht dabei kein zusätzlicher Aufrufstapel.

Ein Suchverfahren, das die Elemente einer Folge nacheinander überprüft, bis der gesuchte Wert gefunden oder das Ende erreicht ist. Sie funktioniert auf unsortierten Daten, benötigt aber lineare Laufzeit.

Ein Suchverfahren auf sortierten Daten, das den Suchbereich durch Vergleich mit dem mittleren Element halbiert. Die Laufzeit wächst logarithmisch, setzt aber sortierte Daten und wahlfreien Zugriff voraus.

Ein Algorithmus, der die Elemente einer Folge in eine festgelegte Ordnung bringt, etwa aufsteigend nach Zahlenwert. Bekannte Vertreter sind Bubblesort, Insertionsort, Mergesort und Quicksort.

Eine Eigenschaft von Sortierverfahren: Elemente mit gleichem Sortierschlüssel behalten ihre ursprüngliche relative Reihenfolge bei. Mergesort ist stabil, Quicksort in der üblichen Form nicht.

Eine Angabe, wie der Aufwand eines Algorithmus mit der Eingabegröße wächst, beschrieben durch eine obere Schranke wie O(n), O(n log n) oder O(n²). Konstanten und kleinere Terme werden dabei vernachlässigt.

Best Case bezeichnet den geringsten, Worst Case den größten Aufwand eines Algorithmus über alle Eingaben einer Größe. Der Worst Case liefert eine sichere Garantie, der Best Case zeigt nur die günstigste Situation.

Die Eigenschaft eines Algorithmus, bei gleicher Eingabe und gleichem Zustand stets denselben nächsten Schritt und dasselbe Ergebnis zu liefern. Nichtdeterministische Verfahren lassen mehrere Folgezustände zu.

Die Eigenschaft eines Algorithmus, nach endlich vielen Schritten zu halten. Der Nachweis erfolgt oft über eine streng monoton fallende Größe, die nicht unter einen festen Wert fallen kann.

Eine Aussage über den Programmzustand, die vor der Schleife gilt und nach jedem Durchlauf erhalten bleibt. Aus ihr lässt sich nach dem Schleifenende die Korrektheit des Ergebnisses begründen.

Eine Variable, die keine Daten selbst, sondern eine Speicheradresse speichert, unter der ein Objekt liegt. Zeiger verknüpfen Knoten zu Listen und Bäumen und ermöglichen das Teilen von Daten.

Eine Einheit aus Daten und den darauf anwendbaren Operationen, beschrieben durch eine Klasse. Objekte kapseln ihren Zustand und bieten nach außen nur eine festgelegte Schnittstelle an.

Ein Bauplan, der festlegt, welche Attribute und Methoden die zugehörigen Objekte besitzen. Aus einer Klasse lassen sich beliebig viele Objekte mit eigenem Zustand erzeugen.

Das Prinzip, interne Daten eines Objekts vor direktem Zugriff zu schützen und nur über definierte Methoden zugänglich zu machen. Dadurch bleibt die Implementierung austauschbar, ohne Nutzer zu brechen.

Die Ableitung einer Klasse von einer Oberklasse, wobei Attribute und Methoden übernommen und ergänzt oder überschrieben werden können. Vererbung modelliert eine Ist-ein-Beziehung zwischen Klassen.

Die Eigenschaft, dass derselbe Methodenaufruf je nach tatsächlicher Objektklasse unterschiedliches Verhalten zeigt. So kann Code mit Oberklassen-Typen arbeiten und Unterklassen flexibel einsetzen.

Eine besondere Methode einer Klasse, die beim Erzeugen eines Objekts automatisch ausgeführt wird. Sie initialisiert die Attribute und hat keinen Rückgabetyp.

Eine Festlegung von Methodensignaturen ohne Implementierung, die eine Klasse erfüllen muss. Schnittstellen erlauben lose Kopplung und ermöglichen Polymorphie über nicht verwandte Klassen hinweg.

Eine tabellarische Auflistung aller Belegungen der Eingangsvariablen eines logischen Ausdrucks mit dem jeweiligen Ausgabewert. Sie dient zum Prüfen von Äquivalenz und zum Ableiten von Schaltfunktionen.

Ein Rechenwerk mit den Werten wahr und falsch sowie den Operatoren UND, ODER und NICHT. Die Rechenregeln wie De Morgan erlauben das Umformen und Vereinfachen logischer Ausdrücke.

Eine elektronische Grundschaltung, die eine boolesche Funktion realisiert, etwa AND, OR, NOT, NAND oder XOR. Mehrere Gatter bilden zusammen eine logische Schaltung.

Ein grafisches Verfahren zum Vereinfachen boolescher Ausdrücke. Benachbarte Felder unterscheiden sich in genau einer Variablen und lassen sich zu größeren Blöcken zusammenfassen.

Eine Schaltung, die zwei Dualziffern addiert. Der Halbaddierer liefert Summe und Übertrag, der Volladdierer verarbeitet zusätzlich einen eingehenden Übertrag und ist kaskadierbar.

Darstellungen von Zahlen zu einer Basis. Das Dualsystem nutzt die Basis 2, das Hexadezimalsystem die Basis 16, wobei vier Dualziffern genau einer Hexadezimalziffer entsprechen.

Eine Darstellung ganzer Zahlen im Dualsystem, bei der das höchstwertige Bit das Vorzeichen trägt. Negative Zahlen entstehen durch Invertieren aller Bits und Addieren von eins.

Eine Zahlendarstellung aus Vorzeichen, Mantisse und Exponent, die sehr große und sehr kleine Werte mit begrenzter Genauigkeit erlaubt. Rundungsfehler sind bei Vergleichen zu berücksichtigen.

Ein Verbund von Rechnern, die über Übertragungsmedien Daten austauschen. LAN bezeichnet ein lokales Netz begrenzter Ausdehnung, WAN ein Weitverkehrsnetz über große Entfernungen.

Eine numerische Kennung, die einen Rechner in einem IP-Netz eindeutig adressiert. Zusammen mit der Subnetzmaske bestimmt sie, welcher Teil der Adresse das Netz und welcher den Host bezeichnet.

Ein Übertragungsprinzip, bei dem Daten in kleine Pakete zerlegt, einzeln durch das Netz geleitet und beim Empfänger wieder zusammengesetzt werden. Ausfälle einzelner Wege lassen sich so umgehen.

Ein Architekturmuster, bei dem ein Client Anfragen stellt und ein Server diese bearbeitet und beantwortet. Rollen und Zuständigkeiten sind klar getrennt, der Server ist häufig zentraler Flaschenhals.

Ein Verfahren, das Daten in unlesbare Form überführt, sodass nur Berechtigte sie zurückgewinnen. Symmetrische Verfahren nutzen einen gemeinsamen Schlüssel, asymmetrische ein Schlüsselpaar aus öffentlichem und privatem Schlüssel.

Eine Funktion, die Daten beliebiger Länge auf einen Wert fester Länge abbildet. Kryptografische Hashes sind kollisionsresistent und dienen der Integritätsprüfung sowie der Speicherung von Passwörtern.

Eine Datenbank speichert Daten strukturiert und dauerhaft. Eine Relation ist eine Tabelle aus Zeilen und Spalten, deren Spalten feste Datentypen besitzen und deren Zeilen je einen Datensatz darstellen.

Ein Attribut oder eine Attributkombination einer Relation, das jeden Datensatz eindeutig identifiziert. Er darf keinen NULL-Wert enthalten und ist die Grundlage für Beziehungen zu anderen Tabellen.

Ein Attribut einer Relation, das auf den Primärschlüssel einer anderen Relation verweist und so Beziehungen zwischen Tabellen herstellt. Die referenzielle Integrität verhindert Verweise auf nicht existierende Datensätze.

Eine deklarative Sprache zum Anlegen, Abfragen und Ändern relationaler Datenbanken. Abfragen beschreiben mit SELECT, FROM und WHERE, welche Daten geliefert werden sollen, nicht den Weg dorthin.