diff options
Diffstat (limited to 'notes/theo1/exam.md')
| -rw-r--r-- | notes/theo1/exam.md | 335 |
1 files changed, 335 insertions, 0 deletions
diff --git a/notes/theo1/exam.md b/notes/theo1/exam.md new file mode 100644 index 0000000..0b93ea1 --- /dev/null +++ b/notes/theo1/exam.md @@ -0,0 +1,335 @@ +--- +author: Marvin Borner +date: "`\\today`{=tex}" +lang: de-DE +pandoc-latex-environment: + bem-box: + - bem + bsp-box: + - bsp + prob-box: + - prob + proof-box: + - proof + visu-box: + - visu +toc-title: Inhalt +--- + +```{=tex} +\newpage +\renewcommand\O{\mathcal{O}} % IDK WHY +``` +# Tricks + +- $\log_a(x)=\frac{\log_b(x)}{\log_b(a)}$ + +# Big-O-Notation + +- $f\in\O(g)$: $f\le g$ +- $f\in\Omega(g)$: $f\ge g$ +- $f\in o(g)$: $f<g$ +- $f\in\omega(g)$: $f>g$ +- $f\in\Theta(g)$: $f=g$ + +# Master Theorem + +Mit $T(n)=aT(\lceil n/b\rceil)+\O(n^d)$ für $a>0$, $b>1$ und $d\ge0$, +ist +$$T(n)=\begin{cases}\O(n^d)&d>\log_ba\\\O(n^d\log_n)&d=log_ba\\\O(n^{log_ba})&d<\log_ba\end{cases}$$ + +# Bäume + +- Binary Höhe: $\log n$; Binary Anzahl: $\sum_{i=0}^h2^i=2^{h+1}-1$ +- Heap: + - `Heapify`: rekursiv swap bis Bedingung nicht verletzt: + $\O(\log n)$ + - `Decrease`: erniedrigen, dann heapify auf node: $\O(\log n)$ + - `Increase`: erhöhen, dann rekursiv mit parent swappen bis + bedingung nicht verletzt: $\O(\log n)$ + - `ExtractMax`: Wurzel mit letzter leaf ersetzen, `heapify(root)`: + $\O(\log n)$ + - `Insert`: Einfügen an nächster Stelle mit $-\infty$, + `Increase(x)` : $\O(\log n)$ + - `Build`: Array irgendwie als Baum schreiben, `heapify` auf jedem + Knoten von unten nach oben: $\O(n)$ +- Priority queue: Als heap analog + +# Hashing + +- irreversible Reduzierung des Universums + +# Graphen + +- Adjazenzmatrix: $a_{ij}=1$ bzw Gewicht wenn Kante von $i$ nach $j$ + - für dense +- Adjazenzliste: array von Knoten mit Listen von ausgehenden Kanten + - für sparse +- Sources: längste finishing time von DFS +- Sinks: alle Kanten umdrehen, dann sources finden +- SCC: DFS auf umgedrehtem Graph, startend bei ursprünglicher source + (`\textrightarrow`{=tex} SCC). Weiter bei restlichen Knoten (nach + absteigenden finishing times): $\O(V + E)$ +- Cycles: durch DFS wenn visited nochmal visited wird +- Topological sort: no cycles; DFS und Knoten nach absteigenden + finishing times sortieren + +## DFS + +- $\O(V+E)$ bzw. $\O(V^2)$ für Matrix + +TODO: Anleitung schriftlich + +## BFS + +- gleich wie DFS nur queue statt stack +- $\O(V+E)$ bzw. $\O(V^2)$ für Matrix +- gut für shortest path, einfach jedes Mal distance updaten + +## Relaxation + +- anfangs alle $\infty$ außer Start + +```{=tex} +\begin{lstlisting} +function Relax(u,v) + if v.dist > u.dist + w(u, v) + v.dist = u.dist + w(u,v) + v.$\pi$ = u +\end{lstlisting} +``` +## Bellman-Ford + +- $(|V|-1)$-mal alle Kanten relaxen, dann noch einmal alle relaxen + (wenn sich was ändert, dann cycle): $\O(V\cdot E)$ +- in undirected muss in beide Richtungen relaxed werden +- blöd für negative Gewichte +- geht auch dezentral/asynchron, damit einzelne Knoten sich updaten + können + +## Dijkstra + +- gierig: nimmt einfach immer die nächstbeste Kante +- $\O((V+E)\log V)$ mit min-priority Queues +- für PPSP einfach stoppen wenn Knoten erreicht wurde (oder auch + bidirektional, dann besser) + +## Floyd-Warshall + +- besser für APSP (da Bellmand/Dijkstra je für jeden Vertex ausführen + müssten: $\O(V^2\cdot E...)$) +- dreimal `for` für Matrix + +## A\* + +- wie Dijkstra, nur mit nächstem $d(s,u)+w(u,v)+\pi(v)$ statt + $d(s,u)+w(u,v)$ (Heuristik) + +## Kruskal + +- für MST +- Kanten aufsteigend sortieren; je nächste Kante zu leerem Graph + hinzufügen solange kein Zykel entsteht +- oder voll toll mit union-find: $\O(E\log V)$ + - weil dann Zykelerkennung ez geht und so + +## Prim + +- für MST +- bei random starten, dann immer nächstbeste Kante hinzufügen (Kreis + erweitert sich) +- mit priority queue $\O(E\log V)$ + +# Sortierung + +- **stabil**: wenn gleicher Wert am Ende gleichen Index + - selection: stabil + - insertion: stabil + - heap: instabil + - merge: stabil + - quick: stabil (out-of-place) + - counting: stabil (mit Listen als buckets) +- Annahme: konstante Vergleiche + +## Selection + +- je kleinstes Element entfernen und in Ausgabe pushen: $\O(n^2)$ + +## Insertion + +- je Element nach links bewegen bis es kleiner-gleich ist. Dann für + nächstes wiederholen: $\O(n^2)$ oder best-case $\O(n)$ + +## Bubble + +- Paare von hinten durchgehen, je swappen wenn größer: $\O(n^2)$ oder + best-case $\O(n)$ + +## Merge + +- List halbieren, rekursiv beide Listenhälften merge-sorten und + mergen: $\O(n\log n)$ weil Master-Theorem +- merge sollte nicht kopieren (also doof in funktionalen Sprachen) + +## Heap + +- Heap aus Zahlen erstellen, je `ExtractMax` anwenden: $\O(n\log n)$ + worst und best + +## Quick + +- je Pivotelement (e.g. Median) wählen, dann kleiner/größer + Pivot-Hälfte rekursiv zusammenfügen: $\O(n^2)$ oder best-case + $\O(n)$ +- durch random Pivotelement ist worst-case $\O(n\log n)$ zu erwarten + +## Counting + +- array mit buckets, sortieren nach Schlüsselwert; am Ende concat + ausgeben: $\O(K+n)$ - besser als vergleichsbasierte Algorithmen + +## Radix + +- Zahlen werden als Strings vom Ende aus durch Counting-Sort sortiert: + $\O(d(n+K))$ mit $d$ als Anzahl der Ziffern +- block-based: je nochmal $x$ buckets + +## Bucket + +- Werte aus Intervall $[i/n,(i+1)/n[$ werden bucket $i$ zugeordnet; + dann jeden Bucket mit Insertion sortieren: $\O(n)$ oder worst-case + $\O(n\log n)$ + +# Suchen + +## Binary + +- (Array sortiert); `A[n/2]` betrachten, entsprechend in + linker/rechter Hälfte weitersuchen: $\O(\log n)$ + +## Exponential + +- Zweierpotenz-Indizes durchgehen, bei $q<2^i$ binary auf $2^{i-1}$ + und $2^i$ + +## Binary tree + +- links $\le$ parent, rechts $\ge$ parent: $\O(\log n)$ +- rekursiver tree-walk für sort: $\O(n)$ +- insert wird obv sehr unbalanced: $\O(n)$ +- delete einfach nächstbestes passendes Element als Substitution + suchen: $\O(n)$ + +### AVL + +- LeftRotation/RightRotation für balancing von Subbäumen (TODO?) +- insert/delete: $\O(\log n)$ da balancing $\O(1)$ + +# Gier + +- einfach immer das nächstbeste nehmen (Heuristiken) +- häufig nicht optimal, dafür effizient + - bei Knapsack bspw. doof + - für Dijkstra, Kruskal, Prim aber auch global optimal + +## Lokale Suche + +- bei zufälligem Wert starten, lokale Nachbarschaft betrachten. + Aufhören, sobald keine bessere Lösung in lokaler Nachbarschaft ist +- mit unterschiedlichen Startwerten wiederholen +- bei TSP durch swappen eigentlich not too bad (also für TSP obv) + +### Simulated annealing + +- am Anfang zu höherer Wahrscheinlichkeit auch schlechtere Lösungen in + lokaler Nachbarschaft betrachten (in Abhängigkeit der Differenz) +- Wahrscheinlichkeit ist je $e^{-\Delta/T}$ +- eigentlich ganz cool, aber T muss halt passend gewählt werden + +# Dynamik + +- Lösen von Problemen durch Kombination der Teilproblemlösungen + (bottom-up vs. top-down) + +## Knapsack + +- Dieb\*in will möglichst viel stehlen hehe +- Fälle: Objekt $j$ wird nicht eingepackt: $K(V,j)=K(V,j-1)$ +- Fälle: Objekt $j$ wird eingepackt: $K(V,j)=K(V-vol_j,j-1)+val_j$ +- bottom-up Array konstruieren mit beiden Fällen und je Maximum nehmen +- top-down bspw. durch rekursive Memoization +- damit $\O(n\cdot V_\text{total})$ (abhängig von + $V\implies\text{Skalierung siehe Approximationsalgorithmen}$) + +# Backtracking + +- bspw. toll bei Queen's problem +- einfach backtracken im Lösungsbaum wenn Teillösung ungültig + +# Branch and Bound + +- bound: untere Schranke bestimmen und mit aktueller Lösung + vergleichen +- bei TSP ist die untere Schranke bspw. das Gewicht des MST +- verbessert nur durchschittliche Laufzeit + +# Approximationsalgorithmen + +- Algorithmus finden, der der tatsächlichen Lösung möglichst nahe + kommt +- Güte von Approximation $A$ mit Instanz $I$ entsprechend + $\alpha_A=\max_I\frac{\mathrm A(I)}{\mathrm{OPT}(I)}$ +- Beispiele + - Set/Vertex cover + - TSP: Zusätzliche Annahme: Dreiecksungleichung. Dann ist lower + bound MST und upper bound zweifacher Graph Durchlauf unter + Verwendung der Dreiecksungleichung + - damit $\alpha_A\le2$ + - Knapsack: Volumina skalieren und inten - Rundungsfehler ergibt + entsprechend $\alpha_A$ + +# Line + +- $\sigma=\sigma_1,...,\sigma_m$ Sequenz unbekannter $\sigma$ +- `\texttt{opt($\sigma$})`{=tex} sind Kosten des besten offline + Algorithmus +- `\texttt{A($\sigma$})`{=tex} sind Kosten des online Algorithmus für + $\sigma$ +- **c-kompetitiv**, wenn für $\sigma$ gilt + $A(\sigma)\le c\mathrm{opt}(\sigma)$ + +## Buy-or-rent + +- Wie lange Skifahren? Leihen $50$, kaufen $500$ Euro. +- $\sigma_i=1\implies\text{skifahren}$, + $\sigma_i=0\implies\text{nicht skifahren}$ +- $\frac{A(\sigma)}{c\mathrm{opt}(\sigma)}=\frac{50(t-1)+500}{50t}$ + minimal für $t=10$ + - also Ski kaufen nach 10 Tagen + +## List-update + +- move-to-front ist am besten + +## Dating + +- wie viele Dates bevor Entscheidung? +- Kalibrierungsphase mit $t$ Personen; in Phase 2 entscheiden sobald + jemand besser als alle aus Phase 1 +- blabla $t=\frac ne$ also mit ca. 1/3 kalibrieren + +# Closest pair of points + +- brute-force ($\O(n^2)$) und sortieren ($\O(n\log n)$) beides nicht + optimal +- divide and conquer: Raum rekursiv aufteilen, Abstand closest pair je + Seite: $\O(n\log n)$ + - problem in der Mitte lässt sich 2d elegant lösen +- randomisierte Lößung: $\sqrt{n}$ zufällige Punkte und paarweise + Abstände + - kleinster Abstand ist $\delta$ + - Hashing, Würfel, blabla effizient (TODO?) + +# KD-Bäume + +TODO. |