Mögliche Klausurfrage Flashcards
Binärbaum
DS zur Ab.. der hS
Jeder K… besitzt max 1/2 Nachfolger.
K… ohne V… = W…
K… ohne N… = B…
Datenstruktur zur Abbildung der hierarsischen Strukturen.
Jeder Knoten besitzt max 2 Nachfolger.
Knoten ohne Vorgänger = Wurzel
Knoten ohne Nachfolger = Blätter
Balancierter Baum?
Sp.A von bB, der ss, dass die HdB b… ist und die TjK im Baum ag wird.
Ziel:
Eine b… L… und E… bei der V… des Baums:
wie S…, E…, L… von E… im Baum
Spezielle Art von binärem Baum, der sicherstellt, dass die Höhe des Baums begrenzt ist und die Tiefe jedes Knotens im Baum ausgeglichen wird.
Ziel:
Eine bessere Leistung und Effizienz bei der Verwendung des Baums: wie Suchen, Einfügen und Löschen von Elementen im Baum.
Daten vs Dateien
D… sind DB, die aus m… D… bestehen
und in gDV sind.
z.B. P… eines P… als B… gespeichert
Dateien sind Datenbestände bzw. Datenbank, die aus mehreren Daten bestehen und in gemeinsame Datenverzeichnis sind.
z.B. Pixel eines Photos als Binär gespeichert
Array
Einfachste s… DT mit vG
LDS mit fL
+: schneller, einfacher
-: sehr a… beim Algo, die seine A… sich mit der Zeit ändert wie SS
Einfachste strukturierte Datentyp mit vorgegebene Größe.
Lineare Datensätze mit fester Länge
+: schneller, einfacher
-: sehr auswendig beim Algo, die seine Anzahl sich mit der Zeit ändert wie Selection Sort
Datenstruktur
SuOD von Daten, die durch die e…Daten und iO c…
Speicher und Organisationdienst von Daten, die durch die erhaltene Daten und ihre Operationen charakterisiert
Nebenläufigkeit
SF zur gz E… von mA mit sogar vuA, die gegenseitig b… können.
z.B. Z… auf den gD
Systemfähigkeit zur gleichzeitigen Exekution von mehreren Aufgaben mit sogar völlig unabhängigen Anweisungen, die gegenseitig beeinflüßen können.
z.B. Zugriff auf den gleichen Daten
Semaphore
DS zum SvZ bzw. K… auf ggR zwischen mP oder T…
P( ) Method: Proberen = P…, W… auf V.. von V( ) M… bevor hzg
V( ) Method: Vrijgeben = F… für P( ) M…
+:
Es löst eSP ohne DU
Es schütz gZ von Fehler aufgrund iZ auf R…
Datenstruktur zum Steuern von Zugriff bzw. Kommunikation auf gemeinsam genutzte Ressourcen zwischen mehreren Prozessen oder Threads.
P( ) Method: Proberen = Probieren, Warte auf Verfügbarkeit von V( ) Method bevor hineinzugehen
V( ) Method: Vrijgeben = Freigeben für P( ) Method
+:
Es löst einfache Signalisierungsprobleme ohne Datenübertragung.
Es schütz gemeinsame Zugriff von Fehler aufgrund inkonsistenzen Zugriff auf Ressourcen.
Backtracking
Eine rM, bei der durch sÜ von mL eine gL gefunden wird.
GL wird in kTP unterteilt,
ap und danach b…
Gültig -> fs
Ungültig -> zs
z.B: L… von S…
Eine rekursive Methode, bei der durch systematisches Überprüfen von möglichen Lösungen eine gültige Lösung gefunden wird.
Größe Lösung wird in kleinere Teilprobleme unterteilt , ausprobiert und danach bewertet.
Gültig -> Fortsetzen
Ungültig -> Zurückspringen
z.B. Lösen von Sudokus
Divide and Conquer
P… von rZ vom gP in kP um es e… zu l…
z.B. BT, MS, QS
Prinzip von rekursive Zerlegung vom größen Problem in kleinere Probleme um es einfacher zu lösen
z.B. Backtracking, Mergesort, Quicksort
Traveling Salesman Problem
OV für Suche der kW zum B… von LvS bis wieder in AS.
Seine L.. kann durch mA e… werden:
1. B… K…: berechnen amR, was jedoch für gP sehr i… sein kann.
2. H… M…: bieten s… Lösungen, aber sie sind nicht immer o… (Oft verwendet)
3. E… A…, wie die bnb Methode und die d… Programmierung: bieten oL, aber b… mZ.
Optimierungsverfahren für Suche der kürzesten Weg zum Besuch von Liste von Städten bis wieder in Ausgangsstadt.
Seine Lösung kann durch mehrere Algo erreicht werden:
1. Brutale kraft: berechnen alle möglichen Routen, was jedoch für große Probleme sehr ineffizient sein kann.
2. Heuristische Methoden bieten schnellere Lösungen, aber sie sind nicht immer optimal. (Oft verwendet)
3. Exakte Algorithmen, wie die branch-and-bound-Methode und die dynamische Programmierung, bieten optimale Lösungen, aber benötigen mehr Zeit.
Endliche Automaten: Mealy
In Vergleich zu Moore-Automaten:
Das AS h… nicht nur von seinem Z…, sondern auch von seinem E… ab.
Es besteht aus bA von Z,Ü, und E.
AL jÜ durch eine K… aus einem aZ und einem E…
JÜ führt zum nZ und A…
+:
Sehr f… und e… azp.
um ÄvS oder EB zu b…
In Vergleich zu Moore-Automaten, hängt das Ausgangssignal nicht nur von seinem Zustand, sondern auch von seinem Eingang ab.
Es besteht aus begrenzter Anzahl von Zuständen, Übergängen, und Eingängen.
Auslösung jeder Übergang durch eine Kombination aus einem aktuellen Zustand und einem Eingang.
Jeder Übergang führt zum neuen Zustand und Ausgang.
+:
Sehr flexibel, Einfach anzupassen
um Änderung vom System oder Eingabebedingungen zu berücksichtigen.
Design by Contract
kV/K bzw. FL von eED, gE und zu e… B zur V… von uF
Klare Vereinbarung/Vertrag bzw. Festlegung von erwarteten Eingabedaten, geplantem Ergebnis und zu erfüllender Bedingung zur Vermeidung von unerwartetem Fehler
Assertion
ZS ist AW im DM durch Ü… bestimmter B… und zu der AG. von FM bevor A… eines A…/F…
Es ist hilfreich, F… fz zu e…und zu f…, bevor es zu gP führt.
Zusicherung ist Anweisung im Debug Mode durch Überprüfung bestimmter Bedingung und zu der Ausgabe von Fehlermeldung bevor Ausführung eines Algos/Funktions.
Es ist hilfreich, Fehler frühzeitig zu erkennen und zu fixieren, bevor es zu größere Problemen führt.
Run Length Coding
L… aef gZ wird c…
Konzept:
JA einer Folge von gZ wird mit einer Zahl c…, und g… von dem eZ.
Es führt zur RdDG und VdÜZ
z.B. …
Länge aufeinanderfolgender gleichen Zeichen/Bytes wird codiert
Konzept:
Jeder Abschnitt einer Folge von gleichen Zeichen wird mit einer Zahl codiert, und gefolgt von dem eigentlichen Zeichen.
Es führt zur Reduzierung der Datengröße und Verbesserung der Übertragungszeit
z.B. AAABBC = 3A2B1C
Burrows-Wheeler-Transformation
DKV durch T… einer gZF in aZF, die l… zu k… ist.
Konzept:
T… der gZF durch V… der Z… und S… der lZ jeder Z… an die eS von Matrix
LS dieser M… als die rZF
z.B. …
+ Es kann r… gemacht werden
+ L… Komprimierung
+ Zur V… der K… mithilfe andere DKV
- D… werden nicht v…
Datenkompressionsverfahren durch Transformierung einer gegebenen Zeichenfolge in anderer Zeichenfolge, die leichter zu komprimieren ist.
Konzept:
Transponierung der gegebenen Zeichenfolge durch Verschiebung der Zeile und Setzung der letzten Zeichen jeder Zeile an die erste Stelle von Matrix .
Letzte Spalte dieser Matrix als die resultierende Zeichenfolge
z.B. BANANA -> ANNBAA
+ Es kann rückgänging gemacht werden
+ Leichtere Komprimierung
+ Zur Verbesserung der Kompressionsrate mithilfe andere Datenkompressionsverfahren
- Daten werden nicht verkleinert
Move To Front
DKV durch ZO von SdE in der Liste an den AdL abhängig von H… der SV
Es besteht aus:
K…:
jS durch sS in der Liste k…
De…:
die Liste v…, um das S… wzs.
z.B. …
1 0 2 1 0 3 1
-: D.. werden nicht v…
Datenkompressionsverfahren durch Zuordnung von Stelle der Elemente in der Liste an den Anfang der Liste abhängig von Häufigkeit der Symbolverwendung
Es besteht aus:
Kodierung:
Jedes Symbol wird durch seine Stelle in der Liste kodiert
Dekodierung:
Die Liste wird verwendet, um das Symbol wiederherzustellen.
z.B. AABABCA
A= 3, B=2, C=1
1 0 2 1 0 3 1
- Daten werden nicht verkleinert
Dreiecktausch vs XOR Swap
DT ist e… und ü… aber benötigt eSP für HV
Dreiecktausch ist einfacher und übersichtlicher aber benötigt extra Speicherplatz für Hilfsvariable
Verkettete Liste
D… DS, die aus 1 R… von me vK besteht.
JK enthält 1 W… und 1 V… auf den nK in der Liste.
(Für e… SM)
Dynamische Datenstruktur, die aus einer Reihe von miteinander verknüpften Knoten besteht.
Jeder Knoten enthält einen Wert und einen Verweis auf den nächsten Knoten in der Liste. (Für einfachere SuchMethod)
Pointer/Zeiger
V…, der 1 A… im S… b… als ZS
Variable, der eine Adresse im Speicher beinhaltet als Zwischenspeicher
Quantisierung
Es e…, sS in eine eA von W… zu c…, die d… zu va ist.
Die Q… des QS hängt jedoch von der G… der dS
und dem sp.V der Q… ab.
Es ermöglicht, stetige Signale in eine endliche Anzahl von Werten zu codieren, die digital zu verarbeiten ist.
Die Qualität des quantisierten Signals hängt jedoch von der Größe der diskreten Schritte und dem spezifischen Verfahren der Quantisierung ab.
