Datenstrukturen & Algorithmen
ETH, 2 Semester
ETH, 2 Semester
Set of flashcards Details
| Flashcards | 67 |
|---|---|
| Language | Deutsch |
| Category | Computer Science |
| Level | University |
| Created / Updated | 08.07.2016 / 09.06.2017 |
| Weblink |
https://card2brain.ch/box/datenstrukturen_algorithmen
|
| Embed |
<iframe src="https://card2brain.ch/box/datenstrukturen_algorithmen/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Obere Schranke: Notation & Definition
\(f \in \mathcal{O(g)}\)
Asymptotische obere Schranke
\(\mathcal{O(g)}:=\{f : \mathbb{N} \to \mathbb{R}^+ |\exists c \in \mathbb{R}^+, n_0 \in \mathbb{N} , \forall n \geq n_0: f(n) \leq c*g(n)\}\)
Welche Funktionstypen haben welche "Grössenordnung" in der O-Notation?
\(0 < \frac{1}{n} < 1 \)\(< log(log(log(n))) < log(log(n)) < \sqrt{log(n)} < log(n) < log^2(n) < log^3 (n) < \sqrt{n} < n < n*log(n) < n^2 < n^2 * log(n) < n^3 < 2^n < n * 2^n < 3^n < n! < n^n <^{2n} \)
Untere Schranke: Notation & Definition
\(f \in \Omega (g) \), Asymptotische untere Schranke
\(\Omega (g) :=\{f: \mathbb{N} \to \mathbb{R}^+| \exists c \in \mathbb{R}^+, n_0 \in \mathbb{N} \forall n \geq n_0: f(n) \geq c*g(n) \}\)
Scharfe Schranke: Notation & Definition
\(f \in \Theta (g)\) ist asymptotisch scharf, d.h\(f \in \mathcal{O}(g) \wedge g \in \mathcal{O}(f)\). Beide Funktionen wachsen gleich schnell
\(\Theta(g) := \{f: \mathbb{N} \to \mathbb{R}^+| \exists c \in \mathbb{R}^+, n_0 \in \mathbb{N} \forall n \geq n_0: c^{-1}*g(n) \leq f(n) \leq c*g(n) \}\)
Wie misst man die Qualität von Algorithmen? D.h was muss ein Algorithmus erfüllen, damit er "gut" ist?
*Korrektheit: Das Programm muss machen, was es soll
*Effizienz: Wie viel Platz (Speicher) und Zeit benötigt der Algorithmus
*Qualität der Lösung: Wie nahe kommen wir an das Optimum?
Was ist das Maximum-Subarray-Problem?
Es soll ein Teilstück eines Arrays gefunden werden, in welchem die Summe aller Einträge maximal ist.
Beispielsweise hilfreich beim Aktienkurs: In welchem Zeitraum hat die Aktie am meisten Gewinn erbracht?
Algorithmus zur Berechnung der Präfix-Summen in einem Array? Wie wende ich den Algorithmus beim Max-Subarray-Problem an? Laufzeit?
Laufzeit beträgt\(\mathcal{O(n^2)}\)
Beschreibe das Divide-And-Conquer-Prinzip?
Grundprinzip: Das Problem wird rekursiv in kleinere Teilprobleme zerlegt, bis man es Problemlos lösen kann. Anschliessend wird aus den Teillösungen die Gesamtlösung rekonstruiert.
Eines der wichtigsten Prinzipien für effiziente Algorithmen. Wird u.a in der Sortierung, beim multiplizieren von grossen Zahlen und der diskreten Fourier-Transformation benutzt.
Wie wird Divide and Conquery beim Max-Subarray-Problem angewendet? Wie gross ist die Laufzeit?
Laufzeit: \(\mathcal{O(n*log(n))}\)
Wie ist die beste Lösung für das Max-Subarray-Problem? Laufzeit?
Es existiert eine Lineare Lösung mit der Laufzeit \(\mathcal{O(n)}\)
Sei randmax das Maximale-Subarray, welches bei i-1 endet und
Maximum das Maximum im Bereich 1,..., i-1. Dann ist der Algorithmus der linearen Lösung:
Wieso kann das Max-Subarray-Problem nicht schneller als ... (siehe andere Lernkarte =) ) gelöst werden? Was sind für Überlegungen gemacht worden?
Kann nicht besser als linear werden, da jedes Element mindestens einmal angeschaut werden muss.
Nimmt man an, dass das nicht betrachtete Element in der Lösung ist, so habe es den Wert\(-\infty\) (Egal was man macht, es wird wahrscheinlich grössere Max.-Subarrays geben). Sei das Element nicht in der Lösung enthalten, so habe es den Wert \(\infty\). (D.h es sollte zwingend enthalten sein, um den Wert maximal zu machen.
Was ist die binäre Suche? Was sind die Bedingungen?
Suchalgorithmus für das Suchen in bereits sortierten Listen. Es muss \(A[1] \leq A[2] \leq ... \leq A[n]\)
Basiert auf dem Divide-And-Conquer prinzip. Schlüsselmenge muss begrenzt sein
Wie lautet der Pseudocode für die binäre Suche? Laufzeit?
Laufzeit: \(\mathcal{O(log(n))}\)
Wieso geht die binäre Suche nicht schneller als ... ?
Geht nicht schneller als \(\mathcal{O(log(n))}\)
Denn: Stellt man sich ein Array als binären Suchbaum vor, so hat der Baum immer die Höhe (log(n)). Wenn unsere gesuchte Zahl nun im untersten Knoten liegt, müssen wir mindestens log(n) Knoten betrachten. Ergo kann unser Algorithmus nicht schneller sein
Was ist die Interpolationssuche?
Die Interpolationssuche ist eine Abwandlung der binären Suche. Im Gegensatz zur binären Suche, die das Array in gleichmässige Teilintervalle zerlegt, versucht die Interpolationssuche eine "günstigere" Zerteilung zu finden- Etwa so wie ein Mensch ein Wörterbuch durchsucht. Bei der Suche nach dem Namen Sxxx, schlägt der Mensch das Buch nicht direkt in der Mitte auf, sondern ca. bei 2/3.
Funktioniert nur gut, wenn die Einträge ca. gleichmässig verteilt sind.
Was ist der Unterschied (Algorithmisch) zwischen der Interpolations- und der Binärsuche?
Der einzige Unterschied liegt bei der Unterteilung der Intervalle. Statt \(m := \frac{l+r}{2}\) wird \(m :=[l + \frac{k-A[l]}{A[r]-A[l]}(r-l)]\) verwendet. k ist dabei der Wert des gesuchten Elements
Was ist die exponentielle Suche?
Die exponentielle Suche ist eine Abwandlung der binären Suche. Sie ist besonders für sehr grosse n geeignet. Bevor mit der binären Suche begonnen wird legt man einen Bereich (\([0,n_2]\))fest, in welchem sich die Zahl definitiv befinden muss.
Was ist der Algorithmus der exponentiellen Suche? Laufzeit?
Laufzeit ist: \(\mathcal{O(log(k))}\) (Sofern das Array streng monoton und nicht nur monoton wächst!) (k ist der gesuchte Schlüssel)
Wieso dauert die lineare Suche in einer unsortierten Liste mindestens \(\mathcal{O(n)}\)?
Das "erste Argument", welches einfällt ist: Wenn wir nicht jedes Element mit k vergleichen, könnten wir genau k übersehen.
Dieses Argument ist nicht korrekt, da wir ja (wie bei der sortierten LIste auch) auch Elemente untereinander vergleichen könnten. Das korrekte Argument ist also: Sei b die Anzahl Vergleiche mit k, a die Anzahl Vergleiche ohne. Die a Vergleiche teilen die Elemente in g Gruppen ein (zu Beginn g = n), in welchen jedes Paar von Elementen über eine Kette von Vergleichen verglichen wurde. Das Zusammenlegen von 2 Gruppen benötigt >1 Vergleich, es ist also \(a \geq (n-g)\).
Um nach k zu suchen benötigen wir mind, einen Vergleich pro Gruppe, also ist \(b \geq g \implies a+b\geq n-g+g = n\)
Wie schnell kann das min/max in einer unsortierten Liste gefunden werden?
Mit der linearen Suche in \(\mathcal{O(n)}\)
Was ist das Auswahlproblem?
Auswahlproblem: Abfrage nach Rang in einer gegebenen, nicht sortierten Liste A.
Mit "Rang" ist bspw. das i-kleinste/grösste Element gemeint.
Nach welchem Wert wird beim Auswahlproblem gesucht, wenn \(i = \frac{n}{2}\)?
Nach dem Median
Mit welchen Verfahren kann das Auswahlproblem gelöst werden? Was sind die Laufzeiten?
Sortieren \(\mathcal{O(n*log(n))}\)
Minimum-Fortlaufend entfernen: \(\mathcal{O(n^2)}\)
Median der Mediane nach Blum
Quickselect: \(\mathcal{O(n)}\)
Was ist ein (gutes) Pivotelement?
Ein Element p aus unserem Array A. Je "mittiger" (Wertmässig) das Element p ist, desto besser. Mathematisch ausgedrückt muss ein gutes Pivotelement einen linearen Anteil der Schlüssel auf beiden Seiten haben, also > \(\epsilon *n\)
Was ist der Quickselect?
Beim Quickselect wird ein zufälliger Schlüssel als Pivot gewählt. Es wird gezählt, ob der Pivot jeweils mindestens \(\frac{n}{4}\) Werte hat, die Grösser resp. Kleiner sind. Falls nicht, wird ein neuer zufälliger Pivot gewählt. Solange, bis ein passender gefunden wurde. Im Schnitt werden wir 2 Pivots versuchen müssen.
Problem: Wir können das "Finden" eines Pivots nicht garantieren. Mit pech terminiert der Algorithmus nicht einmal
Möglichkeit zur Lösung des Auswahlproblems.
Algorithmus für Quickselect? Laufzeit?
Laufzeit von \(\mathcal{O(n)}\)
Was ist die IDee des "Median der Mediane nach Blum"?
Die Idee: Garantiert einen guten Pivot finden, ohne, dass die asymptotische Laufzeit des Quickselects darunter leidet.
Um einen optimalen Wert zu finden wird A in 5er Gruppen unterteilt. Innerhalb dieser 5er Gruppe wird der Median "naiv" berechnet. Der Wert sei das Pivotelement der 5er Gruppe. Setze alle Pivot-Elemente zu 5er Gruppen zusammen. Wähle den Median als Pivot. Fahre fort, bis nur noch ein Pivot übrig bleibt. Dies ist unser Pivot für das gesammte Array.
Wieso werden beim Median nach Blum 5er Gruppen verwendet?
Könnte auch > sein. Nur kleinere Werte funktionieren nicht, da wir da keine Asymptotische Laufzeit mehr erhalten.
Blum-Algorithmus? Wie gross ist die Laufzeit?
Laufzeit: \(\mathcal{O(n)}\)
Welche Operationen unterstützt "Hashing"?
-> Insert(k)
->Search(k) - Gibt 1 zurück falls 1 existiert, sonst 0
->Delete(k)
Was ist die "Idee" des Hashings?
Aus dem Element selber soll direkt der Schlüssel des Elements bestimmt werden können. Hierfür soll jeder mögliche Wert K mittels einer Hashfunktion \(h: K \to \{0,1....,m-1\}\)auf eine eindeutige Adresse zuzuordnen.
Problem: Eindeutigkeit!
Was ist die Divisions-Rest-Methode?
Hashing-Funktion, wobei \(h(k) := k \mod m\)
m sollte dabei eine PZ sein
Was ist die Multiplikative Methode?
Hashing-Funktion.
\(h(k) := \lfloor m*(k*z- \lfloor k*z \rfloor)\rfloor\)
m sollte eine PZ sein, z eine irrationale Zahl.
Was nennt man perfektes Hashing?
"Perfektes Hashing" ist das Kollisionsfreie speichern von Schlüsseln. Möglich wenn man vor dem Festlegen der Hashing-Funktion alle Schlüssel kennt. Ansonsten eher unwahrscheinlich
Wann ist eine Klasse von Hashfunktionen universell?
Wenn \(\forall x \neq y: \delta (x,y,H) \leq \frac{|H|}{m}\), wobei \(\delta(x,y,H) := (\begin{matrix} 1 & {h(x)=h(y)}\\ 0&sonst \end{matrix})\)
Was ist die Möglichkeit der "Direkten Verkettung"? (Zusammenhang: Hashing)
Was sind die Laufzeiten für die Grundoperatoren?
An jeden Adressenplatz wird eine Liste gehängt. Wird eine Adresse nun mehrmals getroffen wird einfach die Liste aufgefüllt.
Problem: Speicherplatz (Es müssten extrem grosse Arrays freigehalten werden, da ja theoretisch alle Werte die selbe Adresse haben müssten...) Kann teilweise mit Zeigern behoben werden.
Löschen, Einfügen Problemlos
Suchen: kann bis zu \(\mathcal{O}\)(n)
Was ist eine Sondierungsfolge:
Die Reihenfolge wie wir nach freien Plätzen in einer Hashtabelle suchen wird "Sonderiungsfolge genannt"
Was ist die Sondierungsfunktion?
Die Sondierungsfunktion ist eine Funktion s(j,k) , die so gewählt wurde, dass (h(k)-s(j,k)) mod m für j = 0, ...., m-1 (bei Bedarf) alle möglichen Plätze in der Hashtabelle abklappert
Wie funktioniert lineares sondieren?
Beim linearen Sondieren wird die Hash-Tabelle "nach links" abgeklappert, falls der Platz besetzt ist... D.h die Adressen h(k), dann h(k) -1,....
Es ist s(j,k) = j
Was ist die primäre Häufung?
Ein Phänomen welches beim linearen sondieren auftritt. Ketten mit Werten wachsen praktisch zusammen. Wenn man pecht hat und einen Schlüssel am Rand einer dieser Ketten hasht, kann das Suchen unter Umständen sehr sehr lange dauern.
