BY Abitur Informatik gA flashcards

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

Definition Algorithmus

Ein Algorithmus ist eine endliche, eindeutige Folge von Anweisungen, die für jede zulässige Eingabe nach endlich vielen Schritten ein Ergebnis liefert. Merkmale: Determiniertheit, Terminierung, Ausführbarkeit, Allgemeingültigkeit.

Eigenschaft Determiniertheit

Determiniertheit bedeutet, dass ein Algorithmus bei gleicher Eingabe und gleichem Zustand stets dasselbe Ergebnis liefert. Sie ist von Determinismus zu unterscheiden, der zusätzlich einen eindeutig festgelegten Ablauf verlangt.

Lineare Suche

Die lineare Suche prüft die Elemente eines Feldes der Reihe nach von vorne, bis der gesuchte Wert gefunden ist oder das Feld endet. Laufzeit O(n), funktioniert auch bei unsortierten Daten.

Binäre Suche

Die binäre Suche vergleicht den gesuchten Wert mit dem mittleren Element eines sortierten Feldes und halbiert danach den Suchbereich. Laufzeit O(log n); Voraussetzung ist eine sortierte Datenstruktur mit direktem Zugriff.

Bubblesort

Bubblesort vergleicht benachbarte Elemente und tauscht sie, wenn sie in falscher Reihenfolge stehen; nach jedem Durchlauf steht das größte Element an seiner Endposition. Laufzeit im Worst Case O(n²), stabil.

Mergesort

Mergesort teilt die Folge rekursiv in zwei Hälften, sortiert diese und mischt sie anschließend linear zusammen. Laufzeit O(n log n) in allen Fällen, benötigt aber zusätzlichen Speicher für das Mischen.

Quicksort

Quicksort wählt ein Pivot-Element, teilt die Folge in kleinere und größere Elemente und sortiert die Teile rekursiv. Durchschnittlich O(n log n), im Worst Case O(n²) bei ungünstiger Pivot-Wahl.

Rekursion Basisfall

Der Basisfall ist die Abbruchbedingung einer rekursiven Methode; er wird ohne weiteren Selbstaufruf berechnet. Fehlt er oder wird er nie erreicht, entsteht ein Stapelüberlauf (Stack Overflow).

Stapel (Stack)

Ein Stapel ist eine Datenstruktur nach dem LIFO-Prinzip: Das zuletzt eingefügte Element wird zuerst entnommen. Grundoperationen sind push (ablegen) und pop (entnehmen); typische Anwendung ist der Aufrufstapel.

Schlange (Queue)

Eine Schlange arbeitet nach dem FIFO-Prinzip: Das zuerst eingefügte Element wird zuerst entnommen. Grundoperationen sind enqueue (hinten anfügen) und dequeue (vorne entnehmen), etwa für Warteschlangen oder Breitensuche.

Verkettete Liste

Eine verkettete Liste speichert Elemente in Knoten, die jeweils einen Verweis auf den nächsten Knoten enthalten. Einfügen und Löschen an bekannter Position ist O(1), der Zugriff auf das n-te Element ist O(n).

Binärbaum

Ein Binärbaum besteht aus Knoten mit höchstens zwei Kindern (links, rechts). Ein binärer Suchbaum ordnet kleinere Werte links und größere rechts ein, sodass Suchen im balancierten Fall O(log n) kostet.

Hashfunktion und Hashtabelle

Eine Hashfunktion bildet Schlüssel auf Indizes einer Hashtabelle ab. Kollisionen (gleicher Index) werden durch Verkettung oder offenes Adressieren behandelt; der mittlere Zugriff ist O(1), im Worst Case O(n).

Klasse und Objekt

Eine Klasse ist der Bauplan, der Attribute und Methoden festlegt; ein Objekt ist eine konkrete Instanz dieser Klasse mit eigenem Zustand. Objekte werden über Konstruktoren erzeugt und über Methoden manipuliert.

Kapselung

Kapselung bedeutet, Attribute als private zu deklarieren und den Zugriff nur über öffentliche Methoden (Getter/Setter) zu erlauben. So bleibt die interne Repräsentation änderbar, ohne die Schnittstelle zu brechen.

Vererbung

Bei Vererbung übernimmt eine Unterklasse Attribute und Methoden ihrer Oberklasse und kann sie erweitern oder überschreiben. Sie modelliert eine ist-ein-Beziehung, etwa Hund ist ein Tier.

Polymorphie

Polymorphie erlaubt, Objekte verschiedener Unterklassen über eine Referenz des Oberklassentyps anzusprechen. Welche überschriebene Methode ausgeführt wird, entscheidet die dynamische Bindung zur Laufzeit anhand des Objekttyps.

Überschreiben (Overriding)

Beim Überschreiben definiert eine Unterklasse eine Methode mit gleicher Signatur wie die Oberklasse neu. Der Aufruf der Oberklassenversion ist über super möglich; die Auswahl erfolgt dynamisch zur Laufzeit.

Überladen (Overloading)

Überladen bezeichnet mehrere Methoden gleichen Namens mit unterschiedlicher Parameterliste in derselben Klasse. Die Auswahl erfolgt statisch zur Übersetzungszeit anhand der Argumenttypen, nicht anhand des Objekttyps.

Abstrakte Klasse

Eine abstrakte Klasse kann nicht direkt instanziiert werden und darf abstrakte Methoden ohne Rumpf enthalten. Unterklassen müssen diese Methoden implementieren; sie dient als gemeinsame Basis mit vorgegebenem Verhalten.

UML Klassendiagramm

Das Klassendiagramm stellt Klassen als Rechtecke mit Attributen und Methoden dar und verbindet sie über Assoziationen mit Multiplizitäten. Sichtbarkeiten werden mit -, +, # und ~ notiert; Vererbung zeigt ein Dreieckspfeil.

Multiplizität in Assoziationen

Die Multiplizität gibt an, wie viele Objekte an einer Assoziation beteiligt sind, z. B. 1, 0..1 oder 1..*. Sie steht am jeweiligen Assoziationsende und beschreibt die Anzahl der Objekte der Gegenseite.

ER-Modell

Das Entity-Relationship-Modell beschreibt Daten mit Entitätstypen (Rechtecke), Attributen (Ellipsen) und Beziehungstypen (Rauten) samt Kardinalitäten wie 1:1, 1:n oder m:n. Es dient als Ausgangspunkt für das Relationenmodell.

Relationenmodell

Im Relationenmodell wird jeder Entitätstyp zu einer Tabelle mit Attributen als Spalten und einem Primärschlüssel. m:n-Beziehungen werden zu eigenen Zwischentabellen mit den Schlüsseln der beteiligten Tabellen.

Primärschlüssel

Der Primärschlüssel ist ein Attribut oder eine Attributkombination, das jede Zeile einer Relation eindeutig identifiziert. Er darf nicht NULL sein; Fremdschlüssel verweisen auf Primärschlüssel anderer Relationen.

SQL SELECT

SELECT wählt Spalten, FROM nennt die Tabellen, WHERE filtert Zeilen, GROUP BY gruppiert und ORDER BY sortiert. Beispiel: SELECT Name FROM Schueler WHERE Klasse = 10 ORDER BY Name.

SQL JOIN

Ein JOIN verknüpft Zeilen zweier Tabellen über eine gemeinsame Spalte, meist Fremdschlüssel gleich Primärschlüssel. INNER JOIN liefert nur passende Paare, LEFT JOIN zusätzlich alle Zeilen der linken Tabelle ohne Partner.

Endlicher Automat

Ein endlicher Automat besteht aus Zustandsmenge, Eingabealphabet, Übergangsfunktion, Startzustand und Menge der Endzustände. Er akzeptiert ein Wort, wenn nach vollständigem Lesen ein Endzustand erreicht ist.

Deterministischer Automat (DEA)

Bei einem deterministischen endlichen Automaten gibt es für jedes Zeichen und jeden Zustand höchstens einen Folgezustand. Ein nichtdeterministischer Automat (NEA) erlaubt mehrere; jeder NEA lässt sich in einen äquivalenten DEA umwandeln.

Regulärer Ausdruck

Ein regulärer Ausdruck beschreibt eine Sprache über einem Alphabet mit Zeichen, Konkatenation, Alternation (|) und Stern (*). Die von regulären Ausdrücken beschriebenen Sprachen sind genau die von endlichen Automaten akzeptierten.

Binärdarstellung und Zweierkomplement

Natürliche Zahlen werden im Dualsystem mit den Stellenwerten 2^k dargestellt. Negative Ganzzahlen kodiert das Zweierkomplement: alle Bits invertieren und 1 addieren; das führende Bit zeigt dann das Vorzeichen.

ASCII und Unicode

ASCII kodiert 128 Zeichen mit 7 Bit, erweitert mit 8 Bit. Unicode ordnet über eine Million Zeichen Codepunkten zu; UTF-8 kodiert diese mit 1 bis 4 Bytes variabler Länge und ist zu ASCII kompatibel.