Probeklausur Flashcards
Komprimierverfahren?
Verfahren zur R… von Datengröße, … dabei wichtige Infos zu …, um sie …
Verfahren zur Reduzierung von Datengröße, ohne dabei wichtige Infos zu verlieren, um sie schneller zu übertragen oder zu speichern.
Huffmancoding
E… K…, die für vK genutzt wird und zur K… von o… p… codes.
B HB ist schlecht für die K…
Entropie Kodierung, die für verlustfreie Kompression genutzt wird und zur Konstruktion von Optimalen präfixen Codes
Balancierte huffmanbau ist schlecht für die Kompression
Entropie?
Mass für… von Daten mit Bits als sein …
Mass für Informationsgehalt von Daten mit Bits als sein Einheit
Warum spricht man in diesem Zusammenhang von “Entropie”?
Geringe Entropie bedeutet, dass die … gut strukturiert sind und daher l zu K…, während höhere Entropie bedeutet, dass die … nicht gut strukturiert sind und daher s zu K. sind.
Geringe Entropie bedeutet, dass die Daten gut strukturiert sind und daher leicht zu komplimieren, während höhere Entropie bedeutet, dass die Daten nicht gut strukturiert sind und daher schwer zu komprimieren sind.
Was ist algorithmische Komplexität?
A… der S… oder R…, die ein Algorithmus benötigt, um … zu lösen, im Verhältnis zur GdE
Anzahl der Schritte oder Ressourcen, die ein Algorithmus benötigt, um ein Problem zu lösen, im Verhältnis zur Größe der Eingabe.
Zeit- oder Speicherkomplexität eines: in Big-O-Notation ausgedrückt wird
Was bedeutet die Bachmann-Landau-Notation?
MD um die atK eines A… zu beschreiben, indem es die oG für die A… von S… beschreibt, die ein A… benötigt, um ein P… zu lösen, im V… zur GdP
Methodedarstellung um die asymptotische Komplexität eines Algorithmus zu beschreiben, indem es die obere Grenze für die Anzahl der Schritte beschreibt, die ein Algorithmus benötigt, um ein Problem zu lösen, im Verhältnis zur Größe des Problems.
Geben Sie bitte für 5 verschiedene Klassen von Komplexitäten Beispielalgorithmen an.
O(1), O(n), O(n^2), O(log (n)), O(n log (n))
O(1)?
Konstante Laufzeit:
Suche in Hashtabelle
O(n)?
Lineare Anstieg:
Lineare Suche in unsortiertem Array
O(n^2)
Quadratisch:
Bubble Sort, Selection Sort, Insertion Sort
O(log (n))?
Binärbaum, Binärsuche
O(n log (n))?
Quicksort, Mergesort
O(n!)
Faktorische LZ:
Travelling Salesman Problem
O(2^n)
Fibonacci
Queue?
LDS mit Z.. an beiden Seiten. Es hat 2 AF
Linearedatensätze mit Zugriff an beiden Seiten. Es hat 2 Anwendungsfälle
Queuetyp 1?
Es f… i… es aus, was zuerst h…
Beispiele:
Schlange -> FIFO:
Es führt immer es aus, was zuerst hineinkommt
Datenverarbeitung, Tastatureingaben
Schlange vor einer Kasse
Queuetyp 2?
Es f… aus, was letztes h…
Beispiele:
Stack -> LIFO:
Es führt immer es aus, was letztes hineinkommt
Stack, Funktionsaufruf
Einkaufswagen in der Supermarkt
Was ist ein Hash in der Informatik?
Funktion, die b… DB hb und es auf kfG Hashwert ab..
Hashwert d… als F…, weil sie für jeden EW einen eAW l…
Es wird zur SS der DI verwendet
Die Hashlänge ist von MV abhängig
Funktion, die beliebige Datenblock hinbekommt und es auf kleine feste Größe Hashwert abbildet.
Hashwert dient als Fingerabdruck, weil sie für jeden Eingabe-Wert einen eindeutigen Ausgabe-Wert liefert.
Es wird zur Sicherstellung der Datenintegrität verwendet
Die Hashlänge ist von der Methodevariante abhängig
Abhängigkeit von Hashfunktion mit Suche?
Hashfunktion e… den HW für das DE. HW ist zur B… vom SO des DEs in der HT erforderlich.
Hashfunktion errechnet den Hashwert für das Datenelement. Hashwert ist zur Bestimmung vom Speicherort des Datenelements in der Hashtabelle erforderlich.
Bubble Sort
BE werden solange v… bis aE in sR sind.
Es hat s… und ip SM
Es ist die e… aber die l… SV mit
LK von …
Benachbarte Elemente werden solange vertauscht bis alle Elemente in sortiertier Reihenfolge sind.
Es hat stabile und in-place Sortiermethode
Es ist die einfachste aber die langsamste Sortierverfahren mit Laufzeitkomplexität von O(n^2)
Quicksort?
Es b… auf dem P… der TuH
Es … ein E… aus der L… als Pivot und t… die L.. in zwei Teile, einen mit Elementen, die … sind, und einen mit Elementen, die … oder g… sind.
Dann s… es jT r… und bT werden schließlich zg, um sie eine sR zu haben.
Es hat ip aber i… SM
Es ist die s.. SV mit LK von
…
Es basiert auf dem Prinzip der Teilen und Herrschen.
Es wählt ein Element aus der Liste als Pivot und teilt die Liste in zwei Teile, einen mit Elementen, die kleiner als das Pivot sind, und einen mit Elementen, die größer oder gleich sind.
Dann sortiert es jeden Teil rekursiv und beide Teilen werden schließlich zusammengeführt,
um sie eine sortierte Reihenfolge zu haben.
Es hat in-place aber instabil Sortiermethode
Es ist die schnellste Sortierverfahren mit Laufkomplexität von O(n log (n))
Mergesort /Zussamenführung?
Es b… auf dem Prinzip …,
w… die L… in 2 T… geteilt wird und jeder TL r… s… wird.
A… werden die beiden TL z…, um eine vsL zu erhalten
Es basiert auf dem Prinzip “Teile und Herrsche”, wobei die Liste in zwei Teile geteilt wird und jeder Teilliste rekursiv sortiert wird.
Anschließend werden die beiden Teillisten zusammengeführt, um eine vollständig sortierte Liste zu erhalten.
Es hat stabile aber nicht in-place Sortiermethode, da es Zwischenspeicher verwendet, um die Daten während des Sortierprozesses zu speichern.
Es hat Laufkomplexität von O(n log (n))
Selection Sort/ Karela Sort?
g… durch die L…
s… kE… -> s… am A… der Liste
g… durch die rL
s.. nkE -> s… an 2. S… der Liste
solange w…
Es hat … aber … SM,
Es hat LZ von …
Es geht durch die Liste und sucht nach kleinstem Element und setzt das am Anfang der Liste. Dann geht es durch die restliche Liste und sucht nach nächstkleinstem Element und platziert es an der 2.Stelle der Liste.
Der Prozess wird solange wiederholt bis die Liste sortiert ist.
Es hat in-place aber unstabile Sortiermethode,
Es hat Laufkomplexität von O(n^2)
Insertion Sort
SV, indem juE an der rS in sTdA e… wird. Es v… ab der 1/2.Elemente mit der Elemente in sTdA.
Wenn das aE kleiner ist, s.. es gE
in der sTL nach rechts.
Es führt solange bis aE in sR sind.
Es hat … aber … Sortiermethod
Es hat Laufzeitkomplexität von…
SV, indem jedes unsortierte Element an der richtigen Stelle in sortiertem Teil des Arrays eingefügt wird.
Es vergleicht ab der 2.Elemente mit der Elemente in
sortiertem Teil des Arrays.
Wenn das aktuelle Elemente kleiner ist, schiebt es die größere Elemente
in der sortierte Teilliste nach rechts.
Es führt solange bis alle elemente in sortierte Reihenfolge sind.
Es hat in-place aber instabil Sortierungsmethod
Es hat Laufzeitkomplexität von O(n^2)
