From 23f0826852c85ea439d4629de13da9cf1d4668f9 Mon Sep 17 00:00:00 2001 From: Marvin Borner Date: Fri, 28 Apr 2023 16:34:02 +0200 Subject: sync --- notes/algo/header.tex | 68 --- notes/algo/main.md | 1228 -------------------------------------------- notes/algo/main.pdf | Bin 388448 -> 0 bytes notes/algo/makefile | 23 - notes/algo/title.tex | 23 - notes/mathe2/exam.pdf | Bin 0 -> 257633 bytes notes/mathe2/examtitle.tex | 4 - notes/mathe2/main.pdf | Bin 557171 -> 521022 bytes notes/mathe2/title.tex | 8 +- notes/mathe3/exam.md | 345 +++++++++++++ notes/mathe3/exam.pdf | Bin 0 -> 260895 bytes notes/mathe3/examtitle.tex | 16 + notes/mathe3/main.md | 17 +- notes/mathe3/main.pdf | Bin 1523230 -> 1495264 bytes notes/mathe3/makefile | 8 + notes/mathe3/title.tex | 10 +- notes/theo1/exam.md | 335 ++++++++++++ notes/theo1/exam.pdf | Bin 0 -> 235026 bytes notes/theo1/examtitle.tex | 16 + notes/theo1/header.tex | 68 +++ notes/theo1/main.md | 1228 ++++++++++++++++++++++++++++++++++++++++++++ notes/theo1/main.pdf | Bin 0 -> 357489 bytes notes/theo1/makefile | 31 ++ notes/theo1/title.tex | 17 + notes/theo2/header.tex | 73 +++ notes/theo2/main.md | 477 +++++++++++++++++ notes/theo2/main.pdf | Bin 0 -> 282520 bytes notes/theo2/makefile | 23 + notes/theo2/title.tex | 21 + sync.sh | 9 +- 30 files changed, 2675 insertions(+), 1373 deletions(-) delete mode 100644 notes/algo/header.tex delete mode 100644 notes/algo/main.md delete mode 100644 notes/algo/main.pdf delete mode 100644 notes/algo/makefile delete mode 100644 notes/algo/title.tex create mode 100644 notes/mathe2/exam.pdf create mode 100644 notes/mathe3/exam.md create mode 100644 notes/mathe3/exam.pdf create mode 100644 notes/mathe3/examtitle.tex create mode 100644 notes/theo1/exam.md create mode 100644 notes/theo1/exam.pdf create mode 100644 notes/theo1/examtitle.tex create mode 100644 notes/theo1/header.tex create mode 100644 notes/theo1/main.md create mode 100644 notes/theo1/main.pdf create mode 100644 notes/theo1/makefile create mode 100644 notes/theo1/title.tex create mode 100644 notes/theo2/header.tex create mode 100644 notes/theo2/main.md create mode 100644 notes/theo2/main.pdf create mode 100644 notes/theo2/makefile create mode 100644 notes/theo2/title.tex diff --git a/notes/algo/header.tex b/notes/algo/header.tex deleted file mode 100644 index 3709c26..0000000 --- a/notes/algo/header.tex +++ /dev/null @@ -1,68 +0,0 @@ -\usepackage{braket} -\usepackage{polynom} -\usepackage{amsthm} -\usepackage{csquotes} -\usepackage{svg} -\usepackage{environ} -\usepackage{mathtools} -\usepackage{tikz,pgfplots} -\usepackage{titleps} -\usepackage{tcolorbox} -\usepackage{enumitem} -\usepackage{listings} -\usepackage{soul} -\usepackage{forest} - -\pgfplotsset{width=10cm,compat=1.15} -\usepgfplotslibrary{external} -\usetikzlibrary{calc,trees,positioning,arrows,arrows.meta,fit,shapes,chains,shapes.multipart} -%\tikzexternalize -\setcounter{MaxMatrixCols}{20} -\graphicspath{{assets}} - -\newpagestyle{main}{\sethead{\toptitlemarks\thesection\quad\sectiontitle}{}{\thepage}\setheadrule{.4pt}} -\pagestyle{main} - -\newtcolorbox{proof-box}{title=Proof,colback=green!5!white,arc=0pt,outer arc=0pt,colframe=green!60!black} -\newtcolorbox{bsp-box}{title=Example,colback=orange!5!white,arc=0pt,outer arc=0pt,colframe=orange!60!black} -\newtcolorbox{visu-box}{title=Visualisation,colback=cyan!5!white,arc=0pt,outer arc=0pt,colframe=cyan!60!black} -\newtcolorbox{bem-box}{title=Note,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black} -\newtcolorbox{prob-box}{title=Problem,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black} -\NewEnviron{splitty}{\begin{displaymath}\begin{split}\BODY\end{split}\end{displaymath}} - -\newcommand\toprove{\textbf{Zu zeigen: }} - -\newcommand\N{\mathbb{N}} -\newcommand\R{\mathbb{R}} -\newcommand\Z{\mathbb{Z}} -\newcommand\Q{\mathbb{Q}} -\newcommand\C{\mathbb{C}} -\renewcommand\P{\mathbb{P}} -\renewcommand\O{\mathcal{O}} -\newcommand\pot{\mathcal{P}} -\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} -\newcommand{\bigcupdot}{\dot{\bigcup}} - -\DeclareMathOperator{\ggT}{ggT} -\DeclareMathOperator{\kgV}{kgV} - -\newlist{abc}{enumerate}{10} -\setlist[abc]{label=(\alph*)} - -\newlist{num}{enumerate}{10} -\setlist[num]{label=\arabic*.} - -\newlist{rom}{enumerate}{10} -\setlist[rom]{label=(\roman*)} - -\makeatletter -\renewenvironment{proof}[1][\proofname] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse} -\makeatother -\def\qedsymbol{\sc q.e.d.} % hmm? - -\lstset{ - basicstyle=\ttfamily, - escapeinside={(*@}{@*)}, - numbers=left, - mathescape -} diff --git a/notes/algo/main.md b/notes/algo/main.md deleted file mode 100644 index 88b3e3c..0000000 --- a/notes/algo/main.md +++ /dev/null @@ -1,1228 +0,0 @@ ---- -author: Marvin Borner -date: "`\\today`{=tex}" -lang: en-US -pandoc-latex-environment: - bem-box: - - bem - bsp-box: - - bsp - prob-box: - - prob - proof-box: - - proof - visu-box: - - visu -toc-title: Content ---- - -```{=tex} -\newpage -\renewcommand\O{\mathcal{O}} % IDK WHY -``` -# Tricks - -## Logarithms - -$$\log_a(x)=\frac{\log_b(x)}{\log_b(a)}$$ - -# Big-O-Notation - -- $f\in\O(g)$: $f$ is of order at most $g$: - $$0\ge\limsup_{n\to\infty}\frac{f(n)}{g(n)}<\infty$$ -- $f\in\Omega(g)$: $f$ is of order at least $g$: - $$0<\liminf_{n\to\infty}\frac{f(n)}{g(n)}\le\infty\iff g\in\O(f)$$ -- $f\in o(g)$: $f$ is of order strictly smaller than $g$: - $$0\ge\limsup_{n\to\infty}\frac{f(n)}{g(n)}=0$$ -- $f\in\omega(g)$: $f$ is of order strictly larger than $g$: - $$\liminf_{n\to\infty}\frac{f(n)}{g(n)}=\infty\iff g\in o(f)$$ -- $f\in\Theta(g)$: $f$ has exactly the same order as $g$: - $$0<\liminf_{n\to\infty}\frac{f(n)}{g(n)}\le\limsup_{n\to\infty}\frac{f(n)}{g(n)}<\infty\iff f\in\O(g)\land f\in\Omega(g)$$ - -## Naming - -- linear $\implies\Theta(n)$ -- sublinear $\implies o(n)$ -- superlinear $\implies\omega(n)$ -- polynomial $\implies\Theta(n^a)$ -- exponential $\implies\Theta(2^n)$ - -## Rules - -- $f\in\O(g_1 + g_2)\land g_1\in\O(g_2)\implies f\in\O(g_2)$ -- $f_1\in\O(g_1)\land f_2\in\O(g_2)\implies f_1+f_2\in\O(g_1+g_2)$ -- $f\in g_1\O(g_2)\implies f\in\O(g_1g_2)$ -- $f\in\O(g_1),g_1\in\O(g_2)\implies f\in\O(g_2)$ - -# Divide and conquer - -::: prob -Given two integers $x$ and $y$, compute their product $x\cdot y$. -::: - -We know that $x=2^{n/2}x_l+x_r$ and $y=2^{n/2}y_l+y_r$. - -We use the following equality: -$$(x_ly_r+x_ry_l)=(x_l+x_r)(y_l+y_r)-x_ly_l-x_ry_r$$ leading to -`\begin{align*} x\cdot y&=2^nx_ly_l+2^{n/2}(x_ly_r+x_ry_l)+x_ry_r\\ &=2^nx_ly_l+2^{n/2}((x_l+x_r)(y_l+y_r)-x_ly_l-x_ry_r)+x_ry_r\\ &=2^{n/2}x_ly_l+(1-2^{n/2})x_ry_r+2^{n/2}(x_l+x_r)(y_ly_r). \end{align*}`{=tex} -Therefore we get the same result with 3 instead of 4 multiplications. - -**If we apply this principle once:** Running time of $(3/4)n^2$ instead -of $n^2$. - -**If we apply this principle recursively:** Running time of -$\O(n^{\log_23})\approx\O(n^{1.59})$ instead of $n^2$ (calculated using -the height of a recursion tree). - -## Recursion tree - -::: visu -```{=tex} -\begin{center}\begin{forest} - [,circle,draw - [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] - [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] - [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] - [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] - ] -\end{forest}\end{center} -``` -::: - -- Level $k$ has $a^k$ problems of size $\frac{n}{b^k}$ -- Total height of tree: $\lceil\log_bn\rceil$ -- Number of problems at the bottom of the tree is - $a^{\log_bn}=n^{\log_ba}$ -- Time spent at the bottom is $\Theta(n^{\log_ba})$ - -## Master theorem - -If $T(n)=aT(\lceil n/b\rceil)+\O(n^d)$ for constants $a>0$, $b>1$ and -$d\ge0$, then -$$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}$$ - -::: bsp -Previous example of clever integer multiplication: -$$T(n)=3T(n/2)+\O(n)\implies T(n)=\O(n^{\log_23})$$ -::: - -# Arrays and lists - -## Array - -- needs to be allocated in advance -- read/write happens in constant time (using memory address) - -## Doubly linked list - -::: visu -```{=tex} -\begin{center}\begin{tikzpicture} - [ - double link/.style n args=2{ - on chain, - rectangle split, - rectangle split horizontal, - rectangle split parts=2, - draw, - anchor=center, - text height=1.5ex, - node contents={#1\nodepart{two}#2}, - }, - start chain=going right, - ] - \node [on chain] {NIL}; - \node [join={by <-}, double link={a}{b}]; - \node [join={by <->}, double link={c}{d}]; - \node (a) [join={by <->}, double link={e}{f}]; - \node (b) [on chain, right=2.5pt of a.east] {$\cdots$}; - \node [double link={y}{z}, right=2.5pt of b.east]; - \node [join={by ->}, on chain] {NIL}; -\end{tikzpicture}\end{center} -``` -::: - -NIL can be replaced by a sentinel element, basically linking the list to -form a loop. - -### Basic operations - -- **Insert**: If the current pointer is at $e$, inserting $x$ after - $e$ is possible in $\O(1)$. -- **Delete**: If the current pointer is at $e$, deleting $x$ before - $e$ is possible in $\O(1)$. -- **Find element with key**: We need to walk through the whole list - $\implies\O(n)$ -- **Delete a whole sublist**: If you know the first and last element - of the sublist: $\O(1)$ -- **Insert a list after element**: Obviously also $\O(1)$ - -## Singly linked list - -::: visu -```{=tex} -\begin{center}\begin{tikzpicture} - [ - link/.style n args=2{ - on chain, - rectangle split, - rectangle split horizontal, - rectangle split parts=2, - draw, - anchor=center, - text height=1.5ex, - node contents={#1\nodepart{two}#2}, - }, - start chain=going right, - ] - \node [on chain] {head}; - \node [join={by ->}, link={a}{b}]; - \node [join={by ->}, link={c}{d}]; - \node (a) [join={by ->}, link={e}{f}]; - \node (b) [on chain, right=2.5pt of a.east] {$\cdots$}; - \node [link={y}{z}, right=2.5pt of b.east]; - \node [join={by ->}, on chain] {NIL}; -\end{tikzpicture}\end{center} -``` -::: - -- needs less storage -- no constant time deletion $\implies$ not good - -# Trees - -::: visu -```{=tex} -\begin{center}\begin{forest} - [root,circle,draw - [a,circle,draw [b,circle,draw] [,circle,draw [,circle,draw]]] - [,circle,draw [,phantom] [,phantom]] - [,circle,draw [,circle,draw] [,circle,draw]]] -\end{forest}\end{center} -``` -- (a) is the parent/predecessor of (b) - -- (b) is a child of (a) -::: - -- *Height of a vertex*: length of the shortest path from the vertex to - the root -- *Height of the tree*: maximum vertex height in the tree - -## Binary tree - -- each vertex has at most 2 children -- *complete* if all layers except the last one are filled -- *full* if the last level is filled completely - -::: visu -```{=tex} -\begin{minipage}{0.5\textwidth}\begin{center} -\textbf{Complete}\bigskip\\ -\begin{forest} - [,circle,draw - [,circle,draw - [,circle,draw [,circle,draw] [,circle,draw]] - [,circle,draw [,circle,draw]]] - [,circle,draw [,circle,draw] [,circle,draw]]] -\end{forest}\end{center}\end{minipage}% -\begin{minipage}{0.5\textwidth}\begin{center} -\textbf{Full}\bigskip\\ -\begin{forest} - [,circle,draw - [,circle,draw - [,circle,draw] - [,circle,draw]] - [,circle,draw [,circle,draw] [,circle,draw]]] -\end{forest}\end{center}\end{minipage} -``` -::: - -### Height of binary tree - -- Full binary tree with $n$ vertices: $\log_2(n+1)-1\in\Theta(\log n)$ -- Complete binary tree with $n$ vertices: - $\lceil\log_2(n+1)-1\rceil\in\Theta(\log n)$ - -### Representation - -- Complete binary tree: Array with entries layer by layer -- Arbitrary binary tree: Each vertex contains the key value and - pointers to left, right, and parent vertices - - Elegant: Each vertex has three pointers: A pointer to its - parent, leftmost child, and right sibling - -# Stack and Queue - -## Stack - -- Analogy: Stack of books to read -- `Push(x)` inserts the new element $x$ to the stack -- `Pop()` removes the next element from the stack (LIFO) - -### Implementation - -- Array with a pointer to the current element, `Push` and `Pop` in - $\O(1)$ -- Doubly linked list with pointer to the end of the list -- Singly linked list and insert elements at the beginning of the list - -## Queue - -- Analogy: waiting line of customers -- `Enqueue(x)` insertes the new element $x$ to the end of the queue -- `Dequeue()` removes the next element from the queue (FIFO) - -### Implementation - -- Array with two pointers, one to the head and one to the tail - $\implies$ `Enqueue`/`Dequeue` in $\O(1)$ -- Linked lists - -# Heaps and priority queues - -## Heaps - -- Data structure that stores elements as vertices in a tree -- Each element has a key value assigned to it -- Max-heap property: all vertices in the tree satisfy - $$\mathrm{key}(\mathrm{parent}(v))\ge\mathrm{key}(v)$$ - -::: visu -```{=tex} -\begin{center}\begin{forest} - [7,circle,draw - [5,circle,draw [1,circle,draw] [3,circle,draw [1,circle,draw] [2,circle,draw] [3,circle,draw]]] - [1,circle,draw [,phantom] [,phantom]] - [2,circle,draw [1,circle,draw] [0,circle,draw]]] -\end{forest}\end{center} -``` -::: - -- Binary heap: - - Each vertex has at most two children - - Layers must be finished before starting a new one (left to right - insertion) - - Advantage: - - Control over height/width of tree - - easy storage in array without any pointers - -### Usage - -- Compromise between a completely unsorted and completely sorted array -- Easier to maintain/build than a sorted array -- Useful for many other data structures (e.g. priority queue) - -### `Heapify` - -The `Heapify` operation can repair a heap with a violated heap property -($\mathrm{key}(i)<\mathrm{key}(\mathrm{child}(i))$ for some vertex $i$ -and at least one child). - -::: visu -```{=tex} -\begin{center}\begin{forest} - [2,circle,draw - [7,circle,draw,tikz={\node [draw,black!60!green,fit to=tree] {};} - [4,circle,draw [3,circle,draw] [3,circle,draw]] - [1,circle,draw]] - [,phantom,circle,draw] - [,phantom,circle,draw] - [6,circle,draw,tikz={\node [draw,black!60!green,fit to=tree] {}; \draw[<-,black!60!green] (.east)--++(2em,0pt) node[anchor=west,align=center]{Not violated!};} - [5,circle,draw [2,circle,draw]]]] { - \draw[<-,red] (.east)--++(2em,0pt) node[anchor=west,align=center]{Violated!}; - } -\end{forest}\end{center} -``` -::: - -**Procedure**: "Let key($i$) float down" - -- Swap $i$ with the larger of its children -- Recursively call `heapify` on this child -- Stop when heap condition is no longer violated - -::: visu -```{=tex} -\begin{minipage}{0.33\textwidth}\begin{center}\textbf{1.}\\\begin{forest} - [2,circle,draw - [7,circle,draw - [4,circle,draw [3,circle,draw] [3,circle,draw]] - [1,circle,draw]] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} - [,phantom,circle,draw] - [,phantom,circle,draw] - [6,circle,draw - [5,circle,draw [2,circle,draw]]]] -\end{forest}\end{center}\end{minipage}% -\begin{minipage}{0.33\textwidth}\begin{center}\textbf{2.}\\\begin{forest} - [7,circle,draw - [2,circle,draw - [4,circle,draw [3,circle,draw] [3,circle,draw]] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} - [1,circle,draw]] - [,phantom,circle,draw] - [,phantom,circle,draw] - [6,circle,draw - [5,circle,draw [2,circle,draw]]]] -\end{forest}\end{center}\end{minipage}% -\begin{minipage}{0.33\textwidth}\begin{center}\textbf{3.}\\\begin{forest} - [7,circle,draw - [4,circle,draw - [2,circle,draw - [3,circle,draw] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} - [3,circle,draw]] - [1,circle,draw]] - [,phantom,circle,draw] - [,phantom,circle,draw] - [6,circle,draw - [5,circle,draw [2,circle,draw]]]] -\end{forest}\end{center}\end{minipage}% -``` -::: - -**Worst case running time**: - -- Number of swapping operations is at most the height of the tree -- Height of tree is at most $h=\lceil\log(n)\rceil=\O(\log n)$ -- Swapping is in $\O(1) \implies$ worst case running time is - $\O(\log n)$ - -### `DecreaseKey` - -The `DecreseKey` operation *decreases* the key value of a particular -element in a correct heap. - -**Procedure**: - -- Decrease the value of the key at index $i$ to new value $b$ -- Call `heapify` at $i$ to let it bubble down - -**Running time**: $\O(\log n)$ - -### `IncreaseKey` - -The `IncreseKey` operation *increases* the key value of a particular -element in a correct heap. - -**Procedure**: - -- Increase the value of the key at index $i$ to new value $b$ -- Walk upwards to the root, exchaning the key values of a vertex and - its parent if the heap property is violated - -**Running time**: $\O(\log n)$ - -::: visu -`IncreaseKey` from 4 to 15: - -```{=tex} -\vspace{.5cm} -\begin{minipage}{0.33\textwidth}\begin{center}\textbf{1.}\\\begin{forest} - [16,circle,draw - [14,circle,draw - [8,circle,draw - [2,circle,draw] - [4,circle,draw,red!60!black]] - [7,circle,draw - [1,circle,draw]]] - [10,circle,draw - [9,circle,draw] - [3,circle,draw]]] -\end{forest}\end{center}\end{minipage}% -\begin{minipage}{0.33\textwidth}\begin{center}\textbf{2.}\\\begin{forest} - [16,circle,draw - [14,circle,draw - [8,circle,draw - [2,circle,draw] - [15,circle,draw,red!60!black]] - [7,circle,draw - [1,circle,draw]]] - [10,circle,draw - [9,circle,draw] - [3,circle,draw]]] -\end{forest}\end{center}\end{minipage}% -\begin{minipage}{0.33\textwidth}\begin{center}\textbf{3.}\\\begin{forest} - [16,circle,draw - [14,circle,draw - [8,circle,draw - [2,circle,draw] - [15,circle,draw,red!60!black] {\draw[<->] () .. controls +(north east:0.6cm) and +(east:1cm) .. (!u);}] - [7,circle,draw - [1,circle,draw]]] - [10,circle,draw - [9,circle,draw] - [3,circle,draw]]] -\end{forest}\end{center}\end{minipage}\bigskip\\ -\begin{minipage}{0.5\textwidth}\begin{center}\textbf{4.}\\\begin{forest} - [16,circle,draw - [14,circle,draw - [15,circle,draw,red!60!black - [2,circle,draw] - [8,circle,draw]] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} - [7,circle,draw - [1,circle,draw]]] - [10,circle,draw - [9,circle,draw] - [3,circle,draw]]] -\end{forest}\end{center}\end{minipage}% -\begin{minipage}{0.5\textwidth}\begin{center}\textbf{5.}\\\begin{forest} - [16,circle,draw - [15,circle,draw,red!60!black - [14,circle,draw - [2,circle,draw] - [8,circle,draw]] - [7,circle,draw - [1,circle,draw]]] - [10,circle,draw - [9,circle,draw] - [3,circle,draw]]] -\end{forest}\end{center}\end{minipage}% -``` -::: - -### `ExtractMax` - -The `ExtractMax` operation *removes* the largest element in a correct -heap. - -**Procedure**: - -- Extract the root element (the largest element) -- Replace the root element by the last leaf in the tree and remove - that leaf -- Call `heapify(root)` - -**Running time**: $\O(\log n)$ - -### `InsertElement` - -The `InsertElement` operation *inserts* a new element in a correct heap. - -**Procedure**: - -- Insert it at the next free position as a leaf, asiign it the key - $-\infty$ -- Call `IncreaseKey` to set the key to the given value - -**Running time**: $\O(\log n)$ - -### `BuildMaxHeap` - -The `BuildMaxHeap` operation makes a heap out of an unsorted array A of -$n$ elements. - -**Procedure**: - -- Write all elements in the tree in any order -- Then, starting from the leafs, call `heapify` on each vertex - -**Running time**: $\O(n)$ - -# Priority queue - -Maintains a set of prioritized elements. The `Dequeue` operation returns -the element with the largest priority value. `Enqueue` and `IncreaseKey` -work as normal. - -## Implementation - -Typically using a heap: - -- Building the heap is $\O(n)$ -- Enqueue: heap `InsertElement`, $\O(\log n)$ -- Dequeue: heap `ExtractMax`, $\O(\log n)$ -- `IncreaseKey`, `DecreaseKey`: $\O(\log n)$ - -"Fibonacci heaps" can achieve `DecreaseKey` in $\O(1)$. - -# Hashing - -**Idea**: - -- Store data that is assigned to particular key values -- Give a "nickname" to each of the key values -- Choose the space of nicknames reasonably small -- Have a way to compute "nicknames" from the keys themselves -- Store the information in an array (size = #nicknames) - -**Formally**: - -- **Universe $U$**: All possible keys, actually used key values are - much less ($m < |U|$) -- **Hash function**: $h: U\to\{1,...,m\}$ -- **Hash values**: $h(k)$ (slot) -- **Collision**: $h(k_1)=h(k_2),\ k_1\ne k_2$ - -## Simple hash function - -If we want to hash $m$ elements in universe $\N$: $$h(k)=k\pmod{m}$$ - -For $n$ slots generally choose $m$ using a prime number $m_p>n$ - -## Hashing with chaining - -Method to cope with collisions: - -Each hash table entry points to a linked list containing all elements -with this particular hash key - collisions make the list longer. - -We might need to traverse this list to retrieve a particular element. - -## Hashing with open addressing - -(**Linear probing**) - -All empty slots get marked as empty - -**Inserting a new key into $h(k)$:** - -- If unused, insert at $h(k)$ -- If used, try insert at $h(k)+1$ - -**Retrieving elements**: Walk from $h(k)$ - -- If we find the key: Yay -- If we hit the empty marker: Nay - -**Removing elements:** - -- Another special symbol marker.. -- Or move entries up that would be affected by the "hole" in the array - -# Graph algorithms - -## Graphs - -A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges -$E\subset V\times V$. - -- edges can be **directed** $(u,v)$ or **undirected** $\{u,v\}$ -- $u$ is **adjacent** to $v$ if there exists an edge between $u$ and - $v$: $u\sim v$ or $u\to v$ -- edges can be **weighted**: $w(u,v)$ -- undirected **degree of a vertex**: - $$d_v:=d(v):=\sum_{v\sim u}w_{vu}$$ -- directed **in-/out-degree of a vertex**: - $$d_in=\sum_{\{u: u\to v\}}w(u,v)$$ - $$d_out=\sum_{\{u: v\to u\}}w(v,y)$$ -- number of vertices: $n=|V|$ -- number of edges: $m=|E|$ -- **simple** path if each vertex occurs at most once -- **cycle** path if it end in the vertex where it started from and - uses each edge at most once -- **strongly connected** directed graph if for all $u,v\in V,\ u\ne v$ - exists a directed path from $u$ to $v$ and a directed path from $v$ - to $u$ -- **acyclic** graph if it does not contain any cycles (**DAG** if - directed) -- **bipartite** graph if its vertex set can be decomposed into two - disjoint subsets such that all edges are only between them - -### Representation - -- Unordered edge list: For each edge, encode start and end point -- Adjacency matrix: - - $n\times n$ matrix that contains entries $a_{ij}=1$ if there is - a directed edge from vertex $i$ to vertex $j$ - - if weighted, $a_{ij}=w{ij}$ - - **implementation** using $n$ arrays of length $n$ - - adjacency test in $\O(1)$ - - space usage $n^2$ -- Adjacency list: - - for each vertex, store a list of all outgoing edges - - if the edges are weighted, store the weight additionally in the - list - - sometimes store both incoming and outgoing edges - - **implementation** using an array with list pointers or using a - list for each vertex that encodes outgoing edges - -**Typical choice**: - -- *dense* graphs: adjacency matrices tend to be easier. -- *sparse* graphs: adjacency lists - -## Depth first search - -**Idea**: Starting at a arbitrary vertex, jump to one of its neighbors, -then one of his neighbors etc., never visiting a vertex twice. At the -end of the chain we backtrack and walk along another chain. - -**Running time** - -- graph: $\O(|V|+|E|)$ -- adjacency matrix: $\O(|V|^2)$ - -**Algorithm**: - -```{=tex} -\begin{lstlisting} -function DFS(G) - for all $u\in V$ - u.color = white # not visited yet - for all $u\in V$ - if u.color == white - DFS-Visit(G, u) - -function DFS-Visit(G, u) - u.color = grey # in process - for all $v\in\mathrm{Adj}(u)$ - if v.color == white - v.pre = u # just for analysis - DFS-Visit(G, v) - u.color = black # done! -\end{lstlisting} -``` -## Strongly connected components - -**Component graph $G^{SCC}$** of a directed graph: - -- vertices of $G^{SCC}$ correspond to the components of $G$ -- edge between vertices $A$ and $B$ in $G^{GCC}$ if vertices $u$ and - $v$ in connected components represented by $A$ and $B$ such that - there is an edge from $u$ to $v$ -- $G^{SCC}$ is a DAG for any directed graph $G$ -- **sink** component if the vertex in $G^{SCC}$ does not have an - out-edge -- **source** component if the vertex in $G^{SCC}$ does not have an - in-edge - -## DFS in sink components - -With sink component $B$: - -- `DFS` on $G$ in vertex $u\in B$: `DFS-Visit` tree covers the whole - component $B$ -- `DFS` on $G$ in vertex $u$ non-sink: `DFS-Visit` tree covers more - than this component - -$\implies$ use DFS to discover SCCs - -## Finding sources - -- **discovery time $d(u)$**: time when DFS first visits $u$ -- **finishing time $f(u)$**: time when DFS is done with $u$ - -Also: $d(A)=\min_{u\in A}d(u)$ and $f(A)=\max_{u\in A}f(u)$. - -Let $A$ and $B$ be two SCCs of $G$ and assume that $B$ is a descendent -of $A$ in $G^{SCC}$. Then $f(B) u.dist + w(u, v) - v.dist = u.dist + w(u,v) - v.$\pi$ = u -\end{lstlisting} -``` -**Also useful**: - -```{=tex} -\begin{lstlisting} -function InitializeSingleSource(G,s) - for all $v\in V$ - v.dist = $\infty$ # current distance estimate - v.$\pi$ = NIL - s.dist = 0 -\end{lstlisting} -``` -## Bellman-Ford algorithm - -SSSP algorithm for general weighted graphs (including negative edges). - -```{=tex} -\begin{lstlisting} -function BellmanFord(G,s) - InitializeSingleSource(G,s) - for i = 1, ..., |V| - 1 - for all edges $(u,v)\in E$ - Relax(u,v) - for all edges $(u,v)\in E$ - if v.dist > u.dist + w(u,v) - return false # cycle detected - return true -\end{lstlisting} -``` -**Running time**: $\O(|V|\cdot|E|)$ - -::: bem -Originally designed for directed graphs. Edges need to be relaxed in -both directions in an undirected graph. Negative weights in an -undirected graph result in an undefined shortest path. -::: - -## Decentralized Bellman-Ford - -**Idea**: "push-based" version of the algorithm: Whenever a value -`v.dist` changes, the vertex `v` communicates this to its neighbors. - -**Synchronous algorithm**: - -```{=tex} -\begin{lstlisting} -function SynchronousBellmanFord(G,w,s) - InitializeSingleSource(G,s) - for i = 1, ..., |V| - 1 - for all $u\in V$ - if u.dist has been updated in previous iteration - for all edges $(u,v)\in E$ - v.dist = min{v.dist, u.dist + w(u, v)} - if no v.dist changed - terminate algorithm -\end{lstlisting} -``` -**Asynchronous algorithm** for static graphs with non-negative weights: - -```{=tex} -\begin{lstlisting} -function AsynchronousBellmanFord(G,w,s) - InitializeSingleSource(G,s) - set $s$ as active, other nodes as inactive - while an active node exists: - u = active node - for all edges $(u,v)\in E$ - v.dist = min{v.dist, u.dist + w(u, v)} - if last operation changed v.dist - set v active - set u inactive -\end{lstlisting} -``` -## Dijkstra's algorithm - -Works on any weighted, (un)directed graph in which all edge weights -$w(u,v)$ are non-negative. - -**Greedy** algorithm: At each point in time it does the "locally best" -action resulting in the "globally optimal" solution. - -### Naive algorithm - -**Idea**: - -- maintain a set $S$ of vertices for which we already know the - shortest path distances from $s$ -- look at neighbors $u$ of $S$ and assign a guess for the shortest - path by using a path through $S$ and adding one edge - -```{=tex} -\begin{lstlisting} -function Dijkstra(G,s) - InitializeSingleSource(G,s) - S = {s} - while S $\ne$ V - U = {u $\notin$ S $\mid$ u neighbor of vertex $\in$ S} - for all u $\in$ U - for all pre(u) $\in$ S that are predecessors of u - d'(u, pre(u)) = pre(u).dist + w(pre(u), u) - d* = min{d'(u,pre(u)) $\mid$ u $\in$ U, pre(U) $\in$ S} - u* = argmin{d'(u,pre(u)) $\mid$ u $\in$ U, pre(U) $\in$ S} - u*.dist = d* - S = S $\cup$ {u*} -\end{lstlisting} -``` -**Running time**: $\O(|V|\cdot|E|)$ - -### Using min-priority queues - -**Algorithm**: - -```{=tex} -\begin{lstlisting} -function Dijkstra(G,w,s) - InitializeSingleSource(G,s) - Q = (V, V.dist) - while Q $\ne\emptyset$ - u = Extract(Q) - for all v adjacent to u - Relax(u,v) and update keys in Q -\end{lstlisting} -``` -It follows that $Q=V\setminus S$. - -**Running time**: $\O((|V|+|E|)\log|V|)$ - -## All pairs shortest paths - -**Naive approach**: - -- run Bellman-Ford or Dijkstra with all possible start vertices -- running time of $\approx\O(|V|^2\cdot|E|)$ -- doesn't reuse already calculated results - -**Better**: Floyd-Warshall - -## Floyd-Warshall algorithm - -**Idea**: - -- assume all vertices are numbered from $1$ to $n$. -- fix two vertices $s$ and $t$ -- consider all paths from $s$ to $t$ that only use vertices $1,...,k$ - as intermediate vertices. Let $\pi_k(s,t)$ be a shortest path *from - this set* and denotee its length by $d_k(s,t)$ -- recursive relation between $\pi_k$ and $\pi_{k-1}$ to construct the - solution bottom-up - -**Algorithm**: - -```{=tex} -\begin{lstlisting} -function FloydWarshall(W) - n = number of vertices - $D^{(0)}$ = W - for k = 1,...,n - let $D^{(k)}$ be a new n $\times$ n matrix - for s = 1,...,n - for t = 1,...,n - $d_k$(s,t) = min{$d_{k-1}$(s,t), $d_{k-1}$(s,k) + $d_{k-1}$(k,t)} - return $D^{(n)}$ -\end{lstlisting} -``` -**Running time**: $\O(|V|^3)\implies$ not that much better than naive -approach but easier to implement - -::: bem -Negative-weight cycles can be detected by looking at the values of the -diagonal of the distance matrix. If it contains negative entries, the -graph contains a negative cycle. -::: - -## Point to Point Shortest Paths - -Given a graph $G$ and two vertices $s$ and $t$ we want to compute the -shortest path between $s$ and $t$ only. - -**Idea**: - -- run `Dijkstra(G,s)` and stop the algorithm when we reached $t$ -- has the same worst case running time as Dijkstra - - often faster in practice - -## Bidirectional Dijkstra - -**Idea**: - -- instead of starting Dijkstra at $s$ and waitung until we hit $t$, we - start copies of the Dijkstra algorithm from $s$ as well as $t$ -- alternate between the two algorithms, stop when they meet - -**Algorithm**: - -- $\mu=\infty$ (best path length currently known) -- alternately run steps of `Dijkstra(G,s)` and `Dijkstra(G',t)` - - when an edge $(v,w)$ is scanned by the forward search and $w$ - has already been visited by the backward search: - - found a path between $s$ and $t$: $s...v\ w...t$ - - length of path is $l=d(s,v)+w(v,w)+d(w,t)$ - - if $\mu>l$, set $\mu=l$ - - analogously for the backward search -- terminate when the search in one direction selects a vertex $v$ that - has already been selected in other direction -- return $\mu$ - -::: bem -It is not always true that if the algorithm stops at $v$, that then the -shortest path between $s$ and $t$ has to go through $v$. -::: - -## Generic labeling method - -A convenient generalization of Dijkstra and Bellman-Ford: - -- for each vertex, maintain a status variable - $S(v)\in\{\text{unreached}, \text{labelchanged}, \text{settled}\}$ -- repeatedly relax edges -- repeat until nothing changes - -```{=tex} -\begin{lstlisting} -function GenericLabelingMethod(G,s) - for all v $\in$ V - v.dist = $\infty$ - v.parent = NIL - v.status = unreached - s.dist = 0 - s.status = labelchanged - while a vertex exists with status labelchanged - pick such vertex v - for all neighbors u of v - Relax(v,u) - if relaxation changed value u.dist - u.status = labelchanged - v.status = settled -\end{lstlisting} -``` -## A\* search - -**Idea**: - -- assume that we know a lower bound $\pi(v)$ on the distance $d(v,t)$ - for all vertices $v$: $$\forall v: \pi(v)\le d(v,t)$$ -- run the *Generic Labeling Method* with start in $s$ -- while Dijkstra selects by $d(s,u)+w(u,v)$, A\* selects by - $d(s,u)+w(u,v)+\pi(v)$ - -**Algorithm**: - -```{=tex} -\begin{lstlisting} -function AstarSearch(G,s,t) - for all v $\in$ V - v.dist = $\infty$ - v.status = unreached - s.dist = 0 - s.status = labelchanged - while a vertex exists with status labelchanged - select u = argmin(u.dist + $\pi$(u)) - if u == t - terminate, found correct distance - for all neighbors v of u - Relax(u,v) - if relaxation changed value v.dist - v.status = labelchanged - u.status = settled -\end{lstlisting} -``` -**Running time**: If the lower bounds are feasible, A\*-search has the -same running time as Dijkstra. Can often work fast but in rare cases -very slow. - -## Union-find data structure - -TODO. - -## Operation O1 - -TODO. - -## Minimal spanning trees - -**Idea**: - -Given an undirected graph $G=(V,E)$ with real-valued edge values -$(w_e)_{e\in E}$ find a tree $T=(V',A)$ with $V=V',A\subset E$ that -minimizes $$\mathrm{weight}(T)=\sum_{e\in A}w_e.$$ Minimal spanning -trees are not unique and most graphs have many minimal spanning trees. - -### Safe edges - -Given a subset $A$ of the edges of an MST, a new edge -$e\in E\setminus A$ is called **safe** with respect to $A$ if there -exists a MST with edge set $A\cup\{e\}$. - -- start with MST $T=(V,E')$ -- take some of its edges $A\subset E'$ -- new edge $e$ is *safe* if $A\cup\{e\}$ can be completed to an MST - $T'$ - -### Cut property to find safe edges - -A cut $(S,V\setminus S)$ is a partition of the vertex set of a graph in -two disjoint subsets. - -TODO. - -### Kruskal's algorithm - -**Idea**: - -- start with an empty tree -- repeatedly add the lightest remaining edge that does not produce a - cycle -- stop when the resulting tree connects the whole graph - -**Naive algorithm** using cut property: - -```{=tex} -\begin{lstlisting} -function KruskalNaiveMST(V,E,W) - sort all edges according to their weight - A = {} - for all e $\in$ E, in increasing order of weight - if A $\cup$ {e} does not contain a cycle - A = A $\cup$ {e} - if |A| = n - 1 - return A -\end{lstlisting} -``` -**Running time**: - -- sorting $\O(|E|\log|E|)$ -- check for cycle: $\O(|E|\cdot?)$ -- total: $\O(|E|\log|E|+|E|\cdot?)$ diff --git a/notes/algo/main.pdf b/notes/algo/main.pdf deleted file mode 100644 index 857e3e3..0000000 Binary files a/notes/algo/main.pdf and /dev/null differ diff --git a/notes/algo/makefile b/notes/algo/makefile deleted file mode 100644 index 58570c7..0000000 --- a/notes/algo/makefile +++ /dev/null @@ -1,23 +0,0 @@ -VIEW = zathura - -all: - @mkdir -p build/ - @pandoc main.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex -B title.tex >/dev/null - @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) & - @progress 3 pdflatex - @cp build/main.pdf . &>/dev/null - @echo done. - -part: - @mkdir -p build/ - @pandoc part.md --filter pandoc-latex-environment -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex >/dev/null - @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) & - @progress 1 pdflatex - @echo done. - -clean: - @$(RM) -rf build - -run: all - @clear - @$(VIEW) build/main.pdf diff --git a/notes/algo/title.tex b/notes/algo/title.tex deleted file mode 100644 index 1b73738..0000000 --- a/notes/algo/title.tex +++ /dev/null @@ -1,23 +0,0 @@ -\begin{titlepage} - \begin{center} - \vspace*{1cm} - - {\huge\textbf{Theoretische Informatik 1\bigskip\\Algorithmen und Datenstrukturen}} - - \vspace{0.5cm} - {\Large Inofficial lecture notes}\\ - \textbf{Marvin Borner} - - % \vfill - % \includegraphics[width=0.4\textwidth]{zeller_logo}\\ - \vfill - - Vorlesung gehalten von\\ - \textbf{Ulrike von Luxburg} - - \vspace{0.8cm} - - \includegraphics[width=0.4\textwidth]{uni_logo}\\ - Wintersemester 2022/23 - \end{center} -\end{titlepage} diff --git a/notes/mathe2/exam.pdf b/notes/mathe2/exam.pdf new file mode 100644 index 0000000..222c5d6 Binary files /dev/null and b/notes/mathe2/exam.pdf differ diff --git a/notes/mathe2/examtitle.tex b/notes/mathe2/examtitle.tex index 5419f39..0c648a8 100644 --- a/notes/mathe2/examtitle.tex +++ b/notes/mathe2/examtitle.tex @@ -9,10 +9,6 @@ \textbf{Marvin Borner} \vfill - \includegraphics[width=0.4\textwidth]{ochs_logo}\\ - \vfill - - \includegraphics[width=0.4\textwidth]{uni_logo}\\ Sommersemester 2022 \end{center} \end{titlepage} diff --git a/notes/mathe2/main.pdf b/notes/mathe2/main.pdf index 7f7ad91..f4af5d6 100644 Binary files a/notes/mathe2/main.pdf and b/notes/mathe2/main.pdf differ diff --git a/notes/mathe2/title.tex b/notes/mathe2/title.tex index 2a33392..d06190d 100644 --- a/notes/mathe2/title.tex +++ b/notes/mathe2/title.tex @@ -8,16 +8,10 @@ {\Large Inoffizielles Skript}\\ \textbf{Marvin Borner} - \vfill - \includegraphics[width=0.4\textwidth]{ochs_logo}\\ \vfill Vorlesung gehalten von\\ - \textbf{Peter Ochs} - - \vspace{0.8cm} - - \includegraphics[width=0.4\textwidth]{uni_logo}\\ + \textbf{Peter Ochs}\\ Sommersemester 2022 \end{center} \end{titlepage} diff --git a/notes/mathe3/exam.md b/notes/mathe3/exam.md new file mode 100644 index 0000000..87c1539 --- /dev/null +++ b/notes/mathe3/exam.md @@ -0,0 +1,345 @@ +--- +author: Marvin Borner +date: "`\\today`{=tex}" +lang: de-DE +pandoc-latex-environment: + bem-box: + - bem + bsp-box: + - bsp + proof-box: + - proof + visu-box: + - visu +toc-title: Inhalt +--- + +```{=tex} +\newpage +``` +# Sinnvolle Rechenregeln + +## Potenzregeln + +- $a^n\cdot a^m=a^{n+m}$ +- $a^n\cdot b^n=(a\cdot b)^n$ +- $(a^n)^m=a^{n\cdot m}$ +- $\frac{a^n}{b^n}=\left(\frac{a}{b}\right)^n$ +- $\frac{a^n}{b^m}=a^{n-m}$ + +## Toll + +- $\sin^2(x)+\cos^2(x)=1$ + +# Euklidischer Algorithmus + +Zur Berechnung des ggT. + +::: bsp +Berechnung von $\ggT(48,-30):$ +`\begin{align*}48&=-1\cdot-30+18\\-30&=-2\cdot18+6\\18&=3\cdot6+0\end{align*}`{=tex} + +$\ggT(48,-30)=6$ +::: + +TODO: kgV mit Primfaktorzerlegung + +# Erweiterter Euklidischer Algorithmus + +Zur Berechnung von $s,t$, da: +$$0\ne a,b\in\Z\implies\exists s,t\in\Z:\ggT(a,b)=sa+tb$$ ggT +gleichsetzen, rückwärts einsetzen und je ausmultiplizieren. + +::: bsp +Mit vorigem Beispiel: +`\begin{align*}6&=-30+2\cdot18\\&=-30+2\cdot(48+1\cdot-30)\\&=2\cdot48+3\cdot-30\end{align*}`{=tex} +::: + +TODO: Polynome. + +# Inverse prüfen + +$$a\in\Z_n\text{ invertierbar}\iff\ggT(a,n)=1$$ $a^{-1}$ ist dann $s$ +aus $sa+tn=1$ des EEA. + +# Zykel + +- zyklische Gruppe, von $a$ erzeugt: + $\langle a\rangle\defeq\{a^n\mid n\in\Z\}$ + +# Fundamentalsatz + +Mit $2\le n\in\N$ gibt es endlich viele paarweise verschiedene +$p_1,...,p_k\in\P$ und $e_1,...,e_k\in\N$, sodass +$$n=p_1^{e_1}\cdot...\cdot p_k^{e_k}.$$ + +# Chinesischer Restsatz + +Lösen von simultaner Kongruenz. + +TODO: Beispiel. + +# Reduzibilität + +- TODO: Nullstellen und so +- TODO: Mit Primzahlen ez + +# Lösen von $a^b\pmod{n}$ + +- falls $n$ groß: Primfaktorzerlegung von $n$ und für jeden Faktor + durchführen. +- Modulo in Potenzen aufnehmen (Trick: $2\pmod{3}=-1$) +- Satz von Euler: $a^{\varphi(n)}\equiv1\pmod{n}$ +- sonst schlau Potenzregeln anwenden + +# Eulersche $\varphi$-Funktion + +- $\varphi(p)=p-1$ für $p\in\P$ +- $\varphi(M)=m_1\cdot...\cdot m_n$ mit $m_i\in\N$ paarweise + teilerfremd (bspw. über chinesischen Restsatz) +- $\varphi(M)=(p_1-1)p_1^{a_1-1}\cdot...\cdot(p_k-1)p_k^{a_k-1}$, mit + Primfaktorzerlegung $M=p_1^{a_1}\cdot...\cdot p_k^{a_k}$ + +::: bsp +$\varphi(100)=\varphi(4\cdot5^2)=\varphi(4)\cdot\varphi(5^2)=2\cdot(5-1)\cdot5^{2-1}=40$ +::: + +# RSA-Verfahren + +Bob (Schlüsselerzeugung) + +1. wählt zwei große $p,q\in\P: p\ne q$ und bildet $n=pq$ +2. berechnet $\varphi(n)=(p-1)(q-1)$ +3. wählt $e$ teilerfremd zu $\varphi(n)$ +4. bestimmt $00\ \exists N\in\N\ \forall k\ge N:\|x_k-a\|<\varepsilon.$$ + +# Eigenschaften von Mengen + +- Sei $x_0\in\R^n,\ \varepsilon>0$. + $K_\varepsilon(x_0)=\{x\in\R^n\mid\|x-x_0\|<\varepsilon\}$ heißt + offene $\varepsilon$-Kugel um $x_0$. +- $D\subseteq\R^n$ **beschränkt** + $\defiff\exists K>0:\|x\|0:K_\varepsilon(x)\subseteq U$ +- $A\subseteq\R^n$ **abgeschlossen** $\defiff A^C=\R^n\setminus A$ + offen +- Sei $(x_k)$ Folge in $A\subseteq\R^n$ mit Grenzwert $a\in\R^n$. $A$ + **abgeschlossen** $\iff a\in A$. +- $x\in\R^n$ Randpunkt von + $D\subseteq\R^n\defiff K_\varepsilon(x)\cap D\ne\emptyset$ und + $K_\varepsilon(x)\cap D^C\ne\emptyset\quad\forall\varepsilon>0$. +- $\partial D$ ist die (abgeschlossene) Menge aller Randpunkte von + $D$. +- $D\subseteq\R^n$ **kompakt** $\defiff$ Jede Folge in $D$ besitzt + eine in $D$ konvergente Teilfolge. +- $D\subseteq\R^n$ **kompakt** $\iff D$ beschränkt und abgeschlossen. +- $\bar{D}\defeq D\cup\partial D$ ist abgeschlossen und heißt + **Abschluss** von $D$. +- $\mathring{D}\defeq D\setminus\partial D$ ist offen und heißt + **Innneres** von $D$. + +# Stetigkeit + +Sei $f: D\subset\R^n\to\R^m$. + +- $f$ stetig in $a\in D\defiff\lim_{x\to a}f(x)=f(a)$ +- $f$ stetig auf $D\defiff f\text{ stetig in }a\quad\forall a\in D$ + +Mit $f: D\subseteq\R^n\to\R^n, v\subseteq f(0)$, $V$ offen: +$$f\text{ stetig}\iff f^{-1}(V)\text{ offen.}$$ + +TODO: Stetige Fortsetzbarkeit + +## Polarkoordinaten + +- $x=r\cdot\cos(\alpha)$ +- $y=r\cdot\sin(\alpha)$ +- statt $(x,y)$ $(r,\alpha)$ gegen $a$ laufen lassen (TODO!) + +## Prüfen + +- In Punkt: $\lim_{v\to v_0} f(v)=f(v_0)$ + - bspw. mit Polarkoordinaten + - oder mit + $0\le|f(x,y)|\le ... \implies \lim_{(x,y)\to(0,0)}f(x,y)=0$ + - bspw. x aus Nenner nehmen + +# Weierstraß Minimax-Theorem + +$f:D\subseteq\R^n\to\R$ stetig, $D$ kompakt. + +$\implies\exists x_\star,x^\star\in D: \underbrace{f(x_\star)}_\mathrm{min}\le f(x)\le\underbrace{f(x^\star)}_\mathrm{max}\quad\forall x\in D$ + +::: bsp +$f:\R^2\to\R$, $f(x,y)=xy$ + +$S=\left\{\begin{pmatrix}x\\y\end{pmatrix}\in\R^2\mid x^2+y^2=1\right\}$ + +$\implies f$ hat Maximum und Minimum auf $S$ +::: + +# TODO: Zeug? + +# Differenziation + +Sei $D\subseteq\R^n$ offen, $f:D\to\R^m$, $f(x)=(f_1(x),...,f_m(x))$ und +$a=(a_1,...,a_n)^\top\in D$. + +- Jacobimatrix: + $$f'(a)\defeq\begin{pmatrix}\frac{\partial f_1}{\partial x_1}(a)&...&\frac{\partial f_1}{\partial x_n}(a)\\\frac{\partial f_m}{\partial x_1}(a)&...&\frac{\partial f_m}{\partial x_n}(a)\\\end{pmatrix}\in\M_{m,n}(\R)$$ +- Gradient: + $$f'(a)^\top=\begin{pmatrix}\frac{\partial f}{\partial x_1}(a)\\\vdots\\\frac{\partial f}{\partial x_n}(a)\end{pmatrix}=:\nabla f(a)=\grad(f(a))\in\R^n$$ + +Sei $D\subseteq\R^n$ offen, $a\in D$, $f: D\to\R^m$. + +- $f$ heißt in $a\in D$ (total) differenzierbar, wenn $f$ geschrieben + werden kann als + $$f(x)=\underbrace{f(a)}_{\in\R^m}+\underbrace{A}_{\in\M_{m,n}(\R)}\cdot(\underbrace{x-a}_{\in\R^m})+\underbrace{R(x)}_{\in\R^m},$$ + wobei $A\in\M_{m,n}(\R)$ und $R: D\to\R^m$ mit + $\lim_{x\to a}\frac{R(x)}{\|x-a\|}=0$ +- $f$ heißt (total) differenzierbar, wenn in jedem Punkt von $D$ + differenzierbar. + +Anderes: + +- $f:D\subseteq\R^n\to\R^m$ differenzierbar in $a\in D$ (D offen) + $\implies f$ stetig in $a$. +- **Tangentialebene**: $g(x)=f(a)+f'(a)\cdot(x-a)$ +- $f$ differenzierbar in $a\in D\iff f_i$ differenzierbar in + $a\in D\quad\forall i\in\{1,...,n\}$. + +## Prüfen + +- ob in Punkt $p$ partiell differenzierbar: partielle Ableitungen + bilden + - falls bspw. Fallunterscheidung und $(0,0)$-Punkt: $h$-Definition + für $x$/$y$ anwenden + - Richtungsableitung: $f_v(x,y)=\frac{(x+hv_1,0+hv_2)-f(0,0)}{h}$ +- total differenzierbar + - je partiell ableiten und prüfen ob Ableitungen stetig + - mit Richtungsleitung versuchen Gegenteil zu beweisen (TODO) + +# Ableitungsregeln + +- $(g\circ f)'(a)=g'(f(a))\cdot f'(a)$ +- $(f+g)'(a)=f'(a)+g'(a)$ +- $(\lambda f)'(a)=\lambda f'(a)$ +- $(f^\top g)'(a)=f(a)^\top g'(a)+g(a)^\top f'(a)$ + +TODO: lhopital + +Anderes: + +- $\left(\ln x\right)'=\frac 1 x$ +- $\left(\frac gh\right)'=\frac{h\cdot g'-g\cdot h'}{h^2}$ +- $\left(\frac{a}{x^k}\right)'=-\frac{ka}{x^{k+1}}$ bzw. unten + Kettenregel + +# Richtungsableitung + +Sei $D\subseteq\R^n$ offen, $f:D\to\R$, $v\in\R^n$ mit $\|v\|=1$. + +$f$ heißt in $a\in D$ differenzierbar in Richtung $v$, falls +$\lim_{h\to0}\frac{f(a+hv)-f(a)}{h}$ exisitert. Der Grenzwert heißt +Richtungsableitung von $f$ in Richtung $v$ in $a$, +$\frac{\partial f}{\partial v}(a)$. + +# Satz von Schwarz + +TODO. + +# Definitheit + +1. Partielle Ableitungen +2. Gradienten mit $0$ gleichsetzen +3. Hessematrix und Punkte einsetzen (falls $x$/$y$ vorhanden) +4. Über Eigenwerte oder Determinante bestimmen + +## Matrix + +Eine symmetrische Matrix $A\in\M_n(\R)$ ist + +- positiv definit $\iff$ $\det(A_k)>0\quad\forall k\in\{1,...,n\}$ +- negativ definit $\iff$ + $\det(A_k)\begin{cases}<0&k\text{ ungerade}\\>0&k\text{ gerade}\end{cases}$ + (-+-+..) + +TODO: über Eigenwerte + +# Extrema + +Sei $D\subseteq\R^n$ offen, +$f\in\varphi^2(D,\R),\ a\in D,\ \nabla f(a)=0$. + +- $H_f(a)$ positiv definit $\implies$ $a$ Stelle eines lokalen + Minimums. +- $H_f(a)$ negativ definit $\implies$ $a$ Stelle eines lokalen + Maximums. +- $H_f(a)$ indefinit $\implies$ $a$ ist Sattelpunkt +- Ist $H_f(a)$ positiv/negativ semidefinit, so ist keine Aussage + möglich. + +# Taylor + +- Taylorpolynom: $T_n(x)=\sum_{k=0}^n\frac{f^{(k)}(x_0)}{k!}(x-x_0)^k$ +- Satz: $f(x)=T_n(x)+R_n(x)$ + - $R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)^{n+1}$ + +# Höhenlinien + +- $f(x,y)=c$ setzen +- nach $y=...$ umformen +- entweder verschiedene $c$ einsetzen oder geg. $N_c(f)$ + +# Implizite Funktionen + +TODO. + +# Umkehrfunktionen + +TODO. + +# Lagrange + +1. Nebenbedingung mit $0$ gleichsetzen +2. Lagrange-Funktion, bspw. + $\mathcal{L}(x,y,\lambda)=f(x,y)+\lambda g(x,y)$ mit $g$ + Nebenbedingung +3. Erste partielle Ableitungen der Lagrange Funktion + ($\mathcal{L}_\lambda=g$) +4. Ableitungen mit $0$ gleichsetzen und lösen (Additionsverfahren gut) +5. Mehrere Ergebnisse dann Extrempunkte +6. Definitheit überprüfen (geränderte Matrix TODO?) diff --git a/notes/mathe3/exam.pdf b/notes/mathe3/exam.pdf new file mode 100644 index 0000000..5a7079a Binary files /dev/null and b/notes/mathe3/exam.pdf differ diff --git a/notes/mathe3/examtitle.tex b/notes/mathe3/examtitle.tex new file mode 100644 index 0000000..cfeb5e4 --- /dev/null +++ b/notes/mathe3/examtitle.tex @@ -0,0 +1,16 @@ +\begin{titlepage} + \begin{center} + \vspace*{1cm} + + {\huge\textbf{Mathematik für Informatik 3}} + + \vspace{0.5cm} + {\Large Klausurvorbereitung}\\ + \textbf{Marvin Borner} + + \vfill + Wintersemester 2022/23 + \end{center} +\end{titlepage} + +\pagebreak\hspace{0pt}\vfill\begin{center}{\Large Dies ist meine WIP Zusammenfassung, welche hauptsächlich mir dienen soll. Ich schreibe außerdem ein inoffizielles Skript, welches auf \url{https://marvinborner.de/mathe3.pdf} zu finden ist.}\end{center}\vfill\hspace{0pt}\pagebreak diff --git a/notes/mathe3/main.md b/notes/mathe3/main.md index f695fbd..2845136 100644 --- a/notes/mathe3/main.md +++ b/notes/mathe3/main.md @@ -544,7 +544,7 @@ Seien $(R, +, \cdot)$ und $(R',\oplus,\odot)$ Ringe. ::: bsp 1. Boolesche Algebra: - $$(\{f,w\}, \texttt{XOR}, 1)\cong ({0,1},\oplus,\odot)$$ + $$(\{f,w\}, \texttt{XOR}, 1)\cong (\{0,1\},\oplus,\odot)$$ $\psi(f)=0,\psi(w)=1$. $\psi$ Isomorphismus, falls Verknüpfungstafeln übereinstimmen `\begin{center}\begin{tabular}{c||c c}\texttt{XOR}&f&w\\\hline f&f&w\\w&w&f\end{tabular}\end{center}`{=tex} @@ -1165,7 +1165,7 @@ beschränkt. $f:D\subseteq\R^n\to\R$ stetig, $D$ kompakt. -$\implies\exists x_\star,x^\star\in D: \underbrace{f(x_\star)}_\mathrm{min}\le f(x)\le f(x^\star)_\mathrm{max}\quad\forall x\in D$ +$\implies\exists x_\star,x^\star\in D: \underbrace{f(x_\star)}_\mathrm{min}\le f(x)\le\underbrace{f(x^\star)}_\mathrm{max}\quad\forall x\in D$ ::: proof ```{=tex} @@ -1257,7 +1257,7 @@ $a=(a_1,...,a_n)^\top\in D$. $$f'(a)^\top=\begin{pmatrix}\frac{\partial f}{\partial x_1}(a)\\\vdots\\\frac{\partial f}{\partial x_n}(a)\end{pmatrix}=:\nabla f(a)=\grad(f(a))\in\R^n$$ als Gradienten von $f$ in $a$. -## Geometriche Deutung der partiellen Ableitung +## Geometrische Deutung der partiellen Ableitung Sei $f:\R^2\to\R,\ a\in\R^2,\ a=\begin{pmatrix}a_1\\a_2\end{pmatrix}$. @@ -1683,11 +1683,12 @@ $D\subseteq\R$ offen, $f:D\to\R$. in jedem Punkt von $D$ partiell differenzierbar ist und alle $\frac{\partial f}{\partial x_i}$ ($i\in\{1,...,n\}$) auf $D$ stetig sind -- $f$ heißt 2-mal stetig differezierbar ($f\in\mathcal{C}^2(D)$), wenn - $f\in\mathcal{C}^1(D)$ und alle $\frac{\partial f}{\partial x_j}$ - ($j\in\{1,...,n\}$) $\in\mathcal{C}^1(D)$. Die partielle Ableitung - von $\frac{\partial f}{\partial x_j}$ nach $x_k$ wird mit - $\frac{\partial^2f}{\partial x_2\partial x_j}$ bezeichnet (partielle +- $f$ heißt 2-mal stetig differenzierbar ($f\in\mathcal{C}^2(D)$), + wenn $f\in\mathcal{C}^1(D)$ und alle + $\frac{\partial f}{\partial x_j}$ ($j\in\{1,...,n\}$) + $\in\mathcal{C}^1(D)$. Die partielle Ableitung von + $\frac{\partial f}{\partial x_j}$ nach $x_k$ wird mit + $\frac{\partial^2f}{\partial x_k\partial x_j}$ bezeichnet (partielle Ableitung zweiter Ordnung). Für $k=j$ schreibt man kurz $\frac{\partial^2f}{\partial x_j^2}$. - Analog ist $f$ $s$-mal stetig differenzierbar diff --git a/notes/mathe3/main.pdf b/notes/mathe3/main.pdf index 4b42dd9..abcbb8d 100644 Binary files a/notes/mathe3/main.pdf and b/notes/mathe3/main.pdf differ diff --git a/notes/mathe3/makefile b/notes/mathe3/makefile index 36d0026..bfe8b0d 100644 --- a/notes/mathe3/makefile +++ b/notes/mathe3/makefile @@ -15,6 +15,14 @@ part: @progress 1 pdflatex @echo done. +exam: + @mkdir -p build/ + @pandoc exam.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/exam.tex --pdf-engine-opt=-shell-escape -H header.tex -B examtitle.tex >/dev/null + @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/exam.tex | grep '^!.*' -A200 --color=always ||true) & + @progress 1 pdflatex + @cp build/exam.pdf . &>/dev/null + @echo done. + clean: @$(RM) -rf build diff --git a/notes/mathe3/title.tex b/notes/mathe3/title.tex index a10f295..8b583a0 100644 --- a/notes/mathe3/title.tex +++ b/notes/mathe3/title.tex @@ -8,18 +8,10 @@ {\Large Inoffizielles Skript}\\ \textbf{Marvin Borner} - \vfill - {\Large \textbf{WARNUNG WIP: Fehler zu erwarten!}\\\textbf{Stand: \today, \currenttime}}\\ - {\large Bitte meldet euch bei mir, falls ihr Fehler findet.} - % \includegraphics[width=0.4\textwidth]{zeller_logo}\\ \vfill Vorlesung gehalten von\\ - \textbf{Rüdiger Zeller} - - \vspace{0.8cm} - - \includegraphics[width=0.4\textwidth]{uni_logo}\\ + \textbf{Rüdiger Zeller}\\ Wintersemester 2022/23 \end{center} \end{titlepage} 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)$: $fg$ +- $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. diff --git a/notes/theo1/exam.pdf b/notes/theo1/exam.pdf new file mode 100644 index 0000000..04de475 Binary files /dev/null and b/notes/theo1/exam.pdf differ diff --git a/notes/theo1/examtitle.tex b/notes/theo1/examtitle.tex new file mode 100644 index 0000000..6d77854 --- /dev/null +++ b/notes/theo1/examtitle.tex @@ -0,0 +1,16 @@ +\begin{titlepage} + \begin{center} + \vspace*{1cm} + + {\huge\textbf{Theoretische Informatik 1\bigskip\\Algorithmen und Datenstrukturen}} + + \vspace{0.5cm} + {\Large Klausurvorbereitung}\\ + \textbf{Marvin Borner} + + \vfill + Wintersemester 2022/23 + \end{center} +\end{titlepage} + +\pagebreak\hspace{0pt}\vfill\begin{center}{\Large Dies ist meine WIP Zusammenfassung, welche hauptsächlich mir dienen soll. Ich schreibe außerdem ein inoffizielles Skript, welches auf \url{https://marvinborner.de/algo.pdf} zu finden ist.}\end{center}\vfill\hspace{0pt}\pagebreak diff --git a/notes/theo1/header.tex b/notes/theo1/header.tex new file mode 100644 index 0000000..3709c26 --- /dev/null +++ b/notes/theo1/header.tex @@ -0,0 +1,68 @@ +\usepackage{braket} +\usepackage{polynom} +\usepackage{amsthm} +\usepackage{csquotes} +\usepackage{svg} +\usepackage{environ} +\usepackage{mathtools} +\usepackage{tikz,pgfplots} +\usepackage{titleps} +\usepackage{tcolorbox} +\usepackage{enumitem} +\usepackage{listings} +\usepackage{soul} +\usepackage{forest} + +\pgfplotsset{width=10cm,compat=1.15} +\usepgfplotslibrary{external} +\usetikzlibrary{calc,trees,positioning,arrows,arrows.meta,fit,shapes,chains,shapes.multipart} +%\tikzexternalize +\setcounter{MaxMatrixCols}{20} +\graphicspath{{assets}} + +\newpagestyle{main}{\sethead{\toptitlemarks\thesection\quad\sectiontitle}{}{\thepage}\setheadrule{.4pt}} +\pagestyle{main} + +\newtcolorbox{proof-box}{title=Proof,colback=green!5!white,arc=0pt,outer arc=0pt,colframe=green!60!black} +\newtcolorbox{bsp-box}{title=Example,colback=orange!5!white,arc=0pt,outer arc=0pt,colframe=orange!60!black} +\newtcolorbox{visu-box}{title=Visualisation,colback=cyan!5!white,arc=0pt,outer arc=0pt,colframe=cyan!60!black} +\newtcolorbox{bem-box}{title=Note,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black} +\newtcolorbox{prob-box}{title=Problem,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black} +\NewEnviron{splitty}{\begin{displaymath}\begin{split}\BODY\end{split}\end{displaymath}} + +\newcommand\toprove{\textbf{Zu zeigen: }} + +\newcommand\N{\mathbb{N}} +\newcommand\R{\mathbb{R}} +\newcommand\Z{\mathbb{Z}} +\newcommand\Q{\mathbb{Q}} +\newcommand\C{\mathbb{C}} +\renewcommand\P{\mathbb{P}} +\renewcommand\O{\mathcal{O}} +\newcommand\pot{\mathcal{P}} +\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} +\newcommand{\bigcupdot}{\dot{\bigcup}} + +\DeclareMathOperator{\ggT}{ggT} +\DeclareMathOperator{\kgV}{kgV} + +\newlist{abc}{enumerate}{10} +\setlist[abc]{label=(\alph*)} + +\newlist{num}{enumerate}{10} +\setlist[num]{label=\arabic*.} + +\newlist{rom}{enumerate}{10} +\setlist[rom]{label=(\roman*)} + +\makeatletter +\renewenvironment{proof}[1][\proofname] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse} +\makeatother +\def\qedsymbol{\sc q.e.d.} % hmm? + +\lstset{ + basicstyle=\ttfamily, + escapeinside={(*@}{@*)}, + numbers=left, + mathescape +} diff --git a/notes/theo1/main.md b/notes/theo1/main.md new file mode 100644 index 0000000..54809bf --- /dev/null +++ b/notes/theo1/main.md @@ -0,0 +1,1228 @@ +--- +author: Marvin Borner +date: "`\\today`{=tex}" +lang: en-US +pandoc-latex-environment: + bem-box: + - bem + bsp-box: + - bsp + prob-box: + - prob + proof-box: + - proof + visu-box: + - visu +toc-title: Content +--- + +```{=tex} +\newpage +\renewcommand\O{\mathcal{O}} % IDK WHY +``` +# Tricks + +## Logarithms + +$$\log_a(x)=\frac{\log_b(x)}{\log_b(a)}$$ + +# Big-O-Notation + +- $f\in\O(g)$: $f$ is of order at most $g$: + $$0\ge\limsup_{n\to\infty}\frac{f(n)}{g(n)}<\infty$$ +- $f\in\Omega(g)$: $f$ is of order at least $g$: + $$0<\liminf_{n\to\infty}\frac{f(n)}{g(n)}\le\infty\iff g\in\O(f)$$ +- $f\in o(g)$: $f$ is of order strictly smaller than $g$: + $$0\ge\limsup_{n\to\infty}\frac{f(n)}{g(n)}=0$$ +- $f\in\omega(g)$: $f$ is of order strictly larger than $g$: + $$\liminf_{n\to\infty}\frac{f(n)}{g(n)}=\infty\iff g\in o(f)$$ +- $f\in\Theta(g)$: $f$ has exactly the same order as $g$: + $$0<\liminf_{n\to\infty}\frac{f(n)}{g(n)}\le\limsup_{n\to\infty}\frac{f(n)}{g(n)}<\infty\iff f\in\O(g)\land f\in\Omega(g)$$ + +## Naming + +- linear $\implies\Theta(n)$ +- sublinear $\implies o(n)$ +- superlinear $\implies\omega(n)$ +- polynomial $\implies\Theta(n^a)$ +- exponential $\implies\Theta(2^n)$ + +## Rules + +- $f\in\O(g_1 + g_2)\land g_1\in\O(g_2)\implies f\in\O(g_2)$ +- $f_1\in\O(g_1)\land f_2\in\O(g_2)\implies f_1+f_2\in\O(g_1+g_2)$ +- $f\in g_1\O(g_2)\implies f\in\O(g_1g_2)$ +- $f\in\O(g_1),g_1\in\O(g_2)\implies f\in\O(g_2)$ + +# Divide and conquer + +::: prob +Given two integers $x$ and $y$, compute their product $x\cdot y$. +::: + +We know that $x=2^{n/2}x_l+x_r$ and $y=2^{n/2}y_l+y_r$. + +We use the following equality: +$$(x_ly_r+x_ry_l)=(x_l+x_r)(y_l+y_r)-x_ly_l-x_ry_r$$ leading to +`\begin{align*} x\cdot y&=2^nx_ly_l+2^{n/2}(x_ly_r+x_ry_l)+x_ry_r\\ &=2^nx_ly_l+2^{n/2}((x_l+x_r)(y_l+y_r)-x_ly_l-x_ry_r)+x_ry_r\\ &=2^{n/2}x_ly_l+(1-2^{n/2})x_ry_r+2^{n/2}(x_l+x_r)(y_ly_r). \end{align*}`{=tex} +Therefore we get the same result with 3 instead of 4 multiplications. + +**If we apply this principle once:** Running time of $(3/4)n^2$ instead +of $n^2$. + +**If we apply this principle recursively:** Running time of +$\O(n^{\log_23})\approx\O(n^{1.59})$ instead of $n^2$ (calculated using +the height of a recursion tree). + +## Recursion tree + +::: visu +```{=tex} +\begin{center}\begin{forest} + [,circle,draw + [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] + [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] + [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] + [,circle,draw [\vdots] [\vdots] [\vdots] [\vdots]] + ] +\end{forest}\end{center} +``` +::: + +- Level $k$ has $a^k$ problems of size $\frac{n}{b^k}$ +- Total height of tree: $\lceil\log_bn\rceil$ +- Number of problems at the bottom of the tree is + $a^{\log_bn}=n^{\log_ba}$ +- Time spent at the bottom is $\Theta(n^{\log_ba})$ + +## Master theorem + +If $T(n)=aT(\lceil n/b\rceil)+\O(n^d)$ for constants $a>0$, $b>1$ and +$d\ge0$, then +$$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}$$ + +::: bsp +Previous example of clever integer multiplication: +$$T(n)=3T(n/2)+\O(n)\implies T(n)=\O(n^{\log_23})$$ +::: + +# Arrays and lists + +## Array + +- needs to be allocated in advance +- read/write happens in constant time (using memory address) + +## Doubly linked list + +::: visu +```{=tex} +\begin{center}\begin{tikzpicture} + [ + double link/.style n args=2{ + on chain, + rectangle split, + rectangle split horizontal, + rectangle split parts=2, + draw, + anchor=center, + text height=1.5ex, + node contents={#1\nodepart{two}#2}, + }, + start chain=going right, + ] + \node [on chain] {NIL}; + \node [join={by <-}, double link={a}{b}]; + \node [join={by <->}, double link={c}{d}]; + \node (a) [join={by <->}, double link={e}{f}]; + \node (b) [on chain, right=2.5pt of a.east] {$\cdots$}; + \node [double link={y}{z}, right=2.5pt of b.east]; + \node [join={by ->}, on chain] {NIL}; +\end{tikzpicture}\end{center} +``` +::: + +NIL can be replaced by a sentinel element, basically linking the list to +form a loop. + +### Basic operations + +- **Insert**: If the current pointer is at $e$, inserting $x$ after + $e$ is possible in $\O(1)$. +- **Delete**: If the current pointer is at $e$, deleting $x$ before + $e$ is possible in $\O(1)$. +- **Find element with key**: We need to walk through the whole list + $\implies\O(n)$ +- **Delete a whole sublist**: If you know the first and last element + of the sublist: $\O(1)$ +- **Insert a list after element**: Obviously also $\O(1)$ + +## Singly linked list + +::: visu +```{=tex} +\begin{center}\begin{tikzpicture} + [ + link/.style n args=2{ + on chain, + rectangle split, + rectangle split horizontal, + rectangle split parts=2, + draw, + anchor=center, + text height=1.5ex, + node contents={#1\nodepart{two}#2}, + }, + start chain=going right, + ] + \node [on chain] {head}; + \node [join={by ->}, link={a}{b}]; + \node [join={by ->}, link={c}{d}]; + \node (a) [join={by ->}, link={e}{f}]; + \node (b) [on chain, right=2.5pt of a.east] {$\cdots$}; + \node [link={y}{z}, right=2.5pt of b.east]; + \node [join={by ->}, on chain] {NIL}; +\end{tikzpicture}\end{center} +``` +::: + +- needs less storage +- no constant time deletion $\implies$ not good + +# Trees + +::: visu +```{=tex} +\begin{center}\begin{forest} + [root,circle,draw + [a,circle,draw [b,circle,draw] [,circle,draw [,circle,draw]]] + [,circle,draw [,phantom] [,phantom]] + [,circle,draw [,circle,draw] [,circle,draw]]] +\end{forest}\end{center} +``` +- (a) is the parent/predecessor of (b) + +- (b) is a child of (a) +::: + +- *Height of a vertex*: length of the shortest path from the vertex to + the root +- *Height of the tree*: maximum vertex height in the tree + +## Binary tree + +- each vertex has at most 2 children +- *complete* if all layers except the last one are filled +- *full* if the last level is filled completely + +::: visu +```{=tex} +\begin{minipage}{0.5\textwidth}\begin{center} +\textbf{Complete}\bigskip\\ +\begin{forest} + [,circle,draw + [,circle,draw + [,circle,draw [,circle,draw] [,circle,draw]] + [,circle,draw [,circle,draw]]] + [,circle,draw [,circle,draw] [,circle,draw]]] +\end{forest}\end{center}\end{minipage}% +\begin{minipage}{0.5\textwidth}\begin{center} +\textbf{Full}\bigskip\\ +\begin{forest} + [,circle,draw + [,circle,draw + [,circle,draw] + [,circle,draw]] + [,circle,draw [,circle,draw] [,circle,draw]]] +\end{forest}\end{center}\end{minipage} +``` +::: + +### Height of binary tree + +- Full binary tree with $n$ vertices: $\log_2(n+1)-1\in\Theta(\log n)$ +- Complete binary tree with $n$ vertices: + $\lceil\log_2(n+1)-1\rceil\in\Theta(\log n)$ + +### Representation + +- Complete binary tree: Array with entries layer by layer +- Arbitrary binary tree: Each vertex contains the key value and + pointers to left, right, and parent vertices + - Elegant: Each vertex has three pointers: A pointer to its + parent, leftmost child, and right sibling + +# Stack and Queue + +## Stack + +- Analogy: Stack of books to read +- `Push(x)` inserts the new element $x$ to the stack +- `Pop()` removes the next element from the stack (LIFO) + +### Implementation + +- Array with a pointer to the current element, `Push` and `Pop` in + $\O(1)$ +- Doubly linked list with pointer to the end of the list +- Singly linked list and insert elements at the beginning of the list + +## Queue + +- Analogy: waiting line of customers +- `Enqueue(x)` insertes the new element $x$ to the end of the queue +- `Dequeue()` removes the next element from the queue (FIFO) + +### Implementation + +- Array with two pointers, one to the head and one to the tail + $\implies$ `Enqueue`/`Dequeue` in $\O(1)$ +- Linked lists + +# Heaps and priority queues + +## Heaps + +- Data structure that stores elements as vertices in a tree +- Each element has a key value assigned to it +- Max-heap property: all vertices in the tree satisfy + $$\mathrm{key}(\mathrm{parent}(v))\ge\mathrm{key}(v)$$ + +::: visu +```{=tex} +\begin{center}\begin{forest} + [7,circle,draw + [5,circle,draw [1,circle,draw] [3,circle,draw [1,circle,draw] [2,circle,draw] [3,circle,draw]]] + [1,circle,draw [,phantom] [,phantom]] + [2,circle,draw [1,circle,draw] [0,circle,draw]]] +\end{forest}\end{center} +``` +::: + +- Binary heap: + - Each vertex has at most two children + - Layers must be finished before starting a new one (left to right + insertion) + - Advantage: + - Control over height/width of tree + - easy storage in array without any pointers + +### Usage + +- Compromise between a completely unsorted and completely sorted array +- Easier to maintain/build than a sorted array +- Useful for many other data structures (e.g. priority queue) + +### `Heapify` + +The `Heapify` operation can repair a heap with a violated heap property +($\mathrm{key}(i)<\mathrm{key}(\mathrm{child}(i))$ for some vertex $i$ +and at least one child). + +::: visu +```{=tex} +\begin{center}\begin{forest} + [2,circle,draw + [7,circle,draw,tikz={\node [draw,black!60!green,fit to=tree] {};} + [4,circle,draw [3,circle,draw] [3,circle,draw]] + [1,circle,draw]] + [,phantom,circle,draw] + [,phantom,circle,draw] + [6,circle,draw,tikz={\node [draw,black!60!green,fit to=tree] {}; \draw[<-,black!60!green] (.east)--++(2em,0pt) node[anchor=west,align=center]{Not violated!};} + [5,circle,draw [2,circle,draw]]]] { + \draw[<-,red] (.east)--++(2em,0pt) node[anchor=west,align=center]{Violated!}; + } +\end{forest}\end{center} +``` +::: + +**Procedure**: "Let key($i$) float down" + +- Swap $i$ with the larger of its children +- Recursively call `heapify` on this child +- Stop when heap condition is no longer violated + +::: visu +```{=tex} +\begin{minipage}{0.33\textwidth}\begin{center}\textbf{1.}\\\begin{forest} + [2,circle,draw + [7,circle,draw + [4,circle,draw [3,circle,draw] [3,circle,draw]] + [1,circle,draw]] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} + [,phantom,circle,draw] + [,phantom,circle,draw] + [6,circle,draw + [5,circle,draw [2,circle,draw]]]] +\end{forest}\end{center}\end{minipage}% +\begin{minipage}{0.33\textwidth}\begin{center}\textbf{2.}\\\begin{forest} + [7,circle,draw + [2,circle,draw + [4,circle,draw [3,circle,draw] [3,circle,draw]] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} + [1,circle,draw]] + [,phantom,circle,draw] + [,phantom,circle,draw] + [6,circle,draw + [5,circle,draw [2,circle,draw]]]] +\end{forest}\end{center}\end{minipage}% +\begin{minipage}{0.33\textwidth}\begin{center}\textbf{3.}\\\begin{forest} + [7,circle,draw + [4,circle,draw + [2,circle,draw + [3,circle,draw] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} + [3,circle,draw]] + [1,circle,draw]] + [,phantom,circle,draw] + [,phantom,circle,draw] + [6,circle,draw + [5,circle,draw [2,circle,draw]]]] +\end{forest}\end{center}\end{minipage}% +``` +::: + +**Worst case running time**: + +- Number of swapping operations is at most the height of the tree +- Height of tree is at most $h=\lceil\log(n)\rceil=\O(\log n)$ +- Swapping is in $\O(1) \implies$ worst case running time is + $\O(\log n)$ + +### `DecreaseKey` + +The `DecreseKey` operation *decreases* the key value of a particular +element in a correct heap. + +**Procedure**: + +- Decrease the value of the key at index $i$ to new value $b$ +- Call `heapify` at $i$ to let it bubble down + +**Running time**: $\O(\log n)$ + +### `IncreaseKey` + +The `IncreseKey` operation *increases* the key value of a particular +element in a correct heap. + +**Procedure**: + +- Increase the value of the key at index $i$ to new value $b$ +- Walk upwards to the root, exchaning the key values of a vertex and + its parent if the heap property is violated + +**Running time**: $\O(\log n)$ + +::: visu +`IncreaseKey` from 4 to 15: + +```{=tex} +\vspace{.5cm} +\begin{minipage}{0.33\textwidth}\begin{center}\textbf{1.}\\\begin{forest} + [16,circle,draw + [14,circle,draw + [8,circle,draw + [2,circle,draw] + [4,circle,draw,red!60!black]] + [7,circle,draw + [1,circle,draw]]] + [10,circle,draw + [9,circle,draw] + [3,circle,draw]]] +\end{forest}\end{center}\end{minipage}% +\begin{minipage}{0.33\textwidth}\begin{center}\textbf{2.}\\\begin{forest} + [16,circle,draw + [14,circle,draw + [8,circle,draw + [2,circle,draw] + [15,circle,draw,red!60!black]] + [7,circle,draw + [1,circle,draw]]] + [10,circle,draw + [9,circle,draw] + [3,circle,draw]]] +\end{forest}\end{center}\end{minipage}% +\begin{minipage}{0.33\textwidth}\begin{center}\textbf{3.}\\\begin{forest} + [16,circle,draw + [14,circle,draw + [8,circle,draw + [2,circle,draw] + [15,circle,draw,red!60!black] {\draw[<->] () .. controls +(north east:0.6cm) and +(east:1cm) .. (!u);}] + [7,circle,draw + [1,circle,draw]]] + [10,circle,draw + [9,circle,draw] + [3,circle,draw]]] +\end{forest}\end{center}\end{minipage}\bigskip\\ +\begin{minipage}{0.5\textwidth}\begin{center}\textbf{4.}\\\begin{forest} + [16,circle,draw + [14,circle,draw + [15,circle,draw,red!60!black + [2,circle,draw] + [8,circle,draw]] {\draw[<->] () .. controls +(north west:0.6cm) and +(west:1cm) .. (!u);} + [7,circle,draw + [1,circle,draw]]] + [10,circle,draw + [9,circle,draw] + [3,circle,draw]]] +\end{forest}\end{center}\end{minipage}% +\begin{minipage}{0.5\textwidth}\begin{center}\textbf{5.}\\\begin{forest} + [16,circle,draw + [15,circle,draw,red!60!black + [14,circle,draw + [2,circle,draw] + [8,circle,draw]] + [7,circle,draw + [1,circle,draw]]] + [10,circle,draw + [9,circle,draw] + [3,circle,draw]]] +\end{forest}\end{center}\end{minipage}% +``` +::: + +### `ExtractMax` + +The `ExtractMax` operation *removes* the largest element in a correct +heap. + +**Procedure**: + +- Extract the root element (the largest element) +- Replace the root element by the last leaf in the tree and remove + that leaf +- Call `heapify(root)` + +**Running time**: $\O(\log n)$ + +### `InsertElement` + +The `InsertElement` operation *inserts* a new element in a correct heap. + +**Procedure**: + +- Insert it at the next free position as a leaf, asiign it the key + $-\infty$ +- Call `IncreaseKey` to set the key to the given value + +**Running time**: $\O(\log n)$ + +### `BuildMaxHeap` + +The `BuildMaxHeap` operation makes a heap out of an unsorted array A of +$n$ elements. + +**Procedure**: + +- Write all elements in the tree in any order +- Then, starting from the leafs, call `heapify` on each vertex + +**Running time**: $\O(n)$ + +# Priority queue + +Maintains a set of prioritized elements. The `Dequeue` operation returns +the element with the largest priority value. `Enqueue` and `IncreaseKey` +work as normal. + +## Implementation + +Typically using a heap: + +- Building the heap is $\O(n)$ +- Enqueue: heap `InsertElement`, $\O(\log n)$ +- Dequeue: heap `ExtractMax`, $\O(\log n)$ +- `IncreaseKey`, `DecreaseKey`: $\O(\log n)$ + +"Fibonacci heaps" can achieve `DecreaseKey` in $\O(1)$. + +# Hashing + +**Idea**: + +- Store data that is assigned to particular key values +- Give a "nickname" to each of the key values +- Choose the space of nicknames reasonably small +- Have a way to compute "nicknames" from the keys themselves +- Store the information in an array (size = #nicknames) + +**Formally**: + +- **Universe $U$**: All possible keys, actually used key values are + much less ($m < |U|$) +- **Hash function**: $h: U\to\{1,...,m\}$ +- **Hash values**: $h(k)$ (slot) +- **Collision**: $h(k_1)=h(k_2),\ k_1\ne k_2$ + +## Simple hash function + +If we want to hash $m$ elements in universe $\N$: $$h(k)=k\pmod{m}$$ + +For $n$ slots generally choose $m$ using a prime number $m_p>n$ + +## Hashing with chaining + +Method to cope with collisions: + +Each hash table entry points to a linked list containing all elements +with this particular hash key - collisions make the list longer. + +We might need to traverse this list to retrieve a particular element. + +## Hashing with open addressing + +(**Linear probing**) + +All empty slots get marked as empty + +**Inserting a new key into $h(k)$:** + +- If unused, insert at $h(k)$ +- If used, try insert at $h(k)+1$ + +**Retrieving elements**: Walk from $h(k)$ + +- If we find the key: Yay +- If we hit the empty marker: Nay + +**Removing elements:** + +- Another special symbol marker.. +- Or move entries up that would be affected by the "hole" in the array + +# Graph algorithms + +## Graphs + +A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges +$E\subset V\times V$. + +- edges can be **directed** $(u,v)$ or **undirected** $\{u,v\}$ +- $u$ is **adjacent** to $v$ if there exists an edge between $u$ and + $v$: $u\sim v$ or $u\to v$ +- edges can be **weighted**: $w(u,v)$ +- undirected **degree of a vertex**: + $$d_v:=d(v):=\sum_{v\sim u}w_{vu}$$ +- directed **in-/out-degree of a vertex**: + $$d_in=\sum_{\{u: u\to v\}}w(u,v)$$ + $$d_out=\sum_{\{u: v\to u\}}w(v,y)$$ +- number of vertices: $n=|V|$ +- number of edges: $m=|E|$ +- **simple** path if each vertex occurs at most once +- **cycle** path if it end in the vertex where it started from and + uses each edge at most once +- **strongly connected** directed graph if for all $u,v\in V,\ u\ne v$ + exists a directed path from $u$ to $v$ and a directed path from $v$ + to $u$ +- **acyclic** graph if it does not contain any cycles (**DAG** if + directed) +- **bipartite** graph if its vertex set can be decomposed into two + disjoint subsets such that all edges are only between them + +### Representation + +- Unordered edge list: For each edge, encode start and end point +- Adjacency matrix: + - $n\times n$ matrix that contains entries $a_{ij}=1$ if there is + a directed edge from vertex $i$ to vertex $j$ + - if weighted, $a_{ij}=w{ij}$ + - **implementation** using $n$ arrays of length $n$ + - adjacency test in $\O(1)$ + - space usage $n^2$ +- Adjacency list: + - for each vertex, store a list of all outgoing edges + - if the edges are weighted, store the weight additionally in the + list + - sometimes store both incoming and outgoing edges + - **implementation** using an array with list pointers or using a + list for each vertex that encodes outgoing edges + +**Typical choice**: + +- *dense* graphs: adjacency matrices tend to be easier. +- *sparse* graphs: adjacency lists + +## Depth first search + +**Idea**: Starting at a arbitrary vertex, jump to one of its neighbors, +then one of his neighbors etc., never visiting a vertex twice. At the +end of the chain we backtrack and walk along another chain. + +**Running time** + +- graph: $\O(|V|+|E|)$ +- adjacency matrix: $\O(|V|^2)$ + +**Algorithm**: + +```{=tex} +\begin{lstlisting} +function DFS(G) + for all $u\in V$ + u.color = white # not visited yet + for all $u\in V$ + if u.color == white + DFS-Visit(G, u) + +function DFS-Visit(G, u) + u.color = grey # in process + for all $v\in\mathrm{Adj}(u)$ + if v.color == white + v.pre = u # just for analysis + DFS-Visit(G, v) + u.color = black # done! +\end{lstlisting} +``` +## Strongly connected components + +**Component graph $G^{SCC}$** of a directed graph: + +- vertices of $G^{SCC}$ correspond to the components of $G$ +- edge between vertices $A$ and $B$ in $G^{GCC}$ if vertices $u$ and + $v$ in connected components represented by $A$ and $B$ such that + there is an edge from $u$ to $v$ +- $G^{SCC}$ is a DAG for any directed graph $G$ +- **sink** component if the vertex in $G^{SCC}$ does not have an + out-edge +- **source** component if the vertex in $G^{SCC}$ does not have an + in-edge + +## DFS in sink components + +With sink component $B$: + +- `DFS` on $G$ in vertex $u\in B$: `DFS-Visit` tree covers the whole + component $B$ +- `DFS` on $G$ in vertex $u$ non-sink: `DFS-Visit` tree covers more + than this component + +$\implies$ use DFS to discover SCCs + +## Finding sources + +- **discovery time $d(u)$**: time when DFS first visits $u$ +- **finishing time $f(u)$**: time when DFS is done with $u$ + +Also: $d(A)=\min_{u\in A}d(u)$ and $f(A)=\max_{u\in A}f(u)$. + +Let $A$ and $B$ be two SCCs of $G$ and assume that $B$ is a descendent +of $A$ in $G^{SCC}$. Then $f(B) u.dist + w(u, v) + v.dist = u.dist + w(u,v) + v.$\pi$ = u +\end{lstlisting} +``` +**Also useful**: + +```{=tex} +\begin{lstlisting} +function InitializeSingleSource(G,s) + for all $v\in V$ + v.dist = $\infty$ # current distance estimate + v.$\pi$ = NIL + s.dist = 0 +\end{lstlisting} +``` +## Bellman-Ford algorithm + +SSSP algorithm for general weighted graphs (including negative edges). + +```{=tex} +\begin{lstlisting} +function BellmanFord(G,s) + InitializeSingleSource(G,s) + for i = 1, ..., |V| - 1 + for all edges $(u,v)\in E$ + Relax(u,v) + for all edges $(u,v)\in E$ + if v.dist > u.dist + w(u,v) + return false # cycle detected + return true +\end{lstlisting} +``` +**Running time**: $\O(|V|\cdot|E|)$ + +::: bem +Originally designed for directed graphs. Edges need to be relaxed in +both directions in an undirected graph. Negative weights in an +undirected graph result in an undefined shortest path. +::: + +## Decentralized Bellman-Ford + +**Idea**: "push-based" version of the algorithm: Whenever a value +`v.dist` changes, the vertex `v` communicates this to its neighbors. + +**Synchronous algorithm**: + +```{=tex} +\begin{lstlisting} +function SynchronousBellmanFord(G,w,s) + InitializeSingleSource(G,s) + for i = 1, ..., |V| - 1 + for all $u\in V$ + if u.dist has been updated in previous iteration + for all edges $(u,v)\in E$ + v.dist = min{v.dist, u.dist + w(u, v)} + if no v.dist changed + terminate algorithm +\end{lstlisting} +``` +**Asynchronous algorithm** for static graphs with non-negative weights: + +```{=tex} +\begin{lstlisting} +function AsynchronousBellmanFord(G,w,s) + InitializeSingleSource(G,s) + set $s$ as active, other nodes as inactive + while an active node exists: + u = active node + for all edges $(u,v)\in E$ + v.dist = min{v.dist, u.dist + w(u, v)} + if last operation changed v.dist + set v active + set u inactive +\end{lstlisting} +``` +## Dijkstra's algorithm + +Works on any weighted, (un)directed graph in which all edge weights +$w(u,v)$ are non-negative. + +**Greedy** algorithm: At each point in time it does the "locally best" +action resulting in the "globally optimal" solution. + +### Naive algorithm + +**Idea**: + +- maintain a set $S$ of vertices for which we already know the + shortest path distances from $s$ +- look at neighbors $u$ of $S$ and assign a guess for the shortest + path by using a path through $S$ and adding one edge + +```{=tex} +\begin{lstlisting} +function Dijkstra(G,s) + InitializeSingleSource(G,s) + S = {s} + while S $\ne$ V + U = {u $\notin$ S $\mid$ u neighbor of vertex $\in$ S} + for all u $\in$ U + for all pre(u) $\in$ S that are predecessors of u + d'(u, pre(u)) = pre(u).dist + w(pre(u), u) + d* = min{d'(u,pre(u)) $\mid$ u $\in$ U, pre(U) $\in$ S} + u* = argmin{d'(u,pre(u)) $\mid$ u $\in$ U, pre(U) $\in$ S} + u*.dist = d* + S = S $\cup$ {u*} +\end{lstlisting} +``` +**Running time**: $\O(|V|\cdot|E|)$ + +### Using min-priority queues + +**Algorithm**: + +```{=tex} +\begin{lstlisting} +function Dijkstra(G,w,s) + InitializeSingleSource(G,s) + Q = (V, V.dist) + while Q $\ne\emptyset$ + u = Extract(Q) + for all v adjacent to u + Relax(u,v) and update keys in Q +\end{lstlisting} +``` +It follows that $Q=V\setminus S$. + +**Running time**: $\O((|V|+|E|)\log|V|)$ + +## All pairs shortest paths + +**Naive approach**: + +- run Bellman-Ford or Dijkstra with all possible start vertices +- running time of $\approx\O(|V|^2\cdot|E|)$ +- doesn't reuse already calculated results + +**Better**: Floyd-Warshall + +## Floyd-Warshall algorithm + +**Idea**: + +- assume all vertices are numbered from $1$ to $n$. +- fix two vertices $s$ and $t$ +- consider all paths from $s$ to $t$ that only use vertices $1,...,k$ + as intermediate vertices. Let $\pi_k(s,t)$ be a shortest path *from + this set* and denotee its length by $d_k(s,t)$ +- recursive relation between $\pi_k$ and $\pi_{k-1}$ to construct the + solution bottom-up + +**Algorithm**: + +```{=tex} +\begin{lstlisting} +function FloydWarshall(W) + n = number of vertices + $D^{(0)}$ = W + for k = 1,...,n + let $D^{(k)}$ be a new n $\times$ n matrix + for s = 1,...,n + for t = 1,...,n + $d_k$(s,t) = min{$d_{k-1}$(s,t), $d_{k-1}$(s,k) + $d_{k-1}$(k,t)} + return $D^{(n)}$ +\end{lstlisting} +``` +**Running time**: $\O(|V|^3)\implies$ not that much better than naive +approach but easier to implement + +::: bem +Negative-weight cycles can be detected by looking at the values of the +diagonal of the distance matrix. If it contains negative entries, the +graph contains a negative cycle. +::: + +## Point to Point Shortest Paths + +Given a graph $G$ and two vertices $s$ and $t$ we want to compute the +shortest path between $s$ and $t$ only. + +**Idea**: + +- run `Dijkstra(G,s)` and stop the algorithm when we reached $t$ +- has the same worst case running time as Dijkstra + - often faster in practice + +## Bidirectional Dijkstra + +**Idea**: + +- instead of starting Dijkstra at $s$ and waitung until we hit $t$, we + start copies of the Dijkstra algorithm from $s$ as well as $t$ +- alternate between the two algorithms, stop when they meet + +**Algorithm**: + +- $\mu=\infty$ (best path length currently known) +- alternately run steps of `Dijkstra(G,s)` and `Dijkstra(G',t)` + - when an edge $(v,w)$ is scanned by the forward search and $w$ + has already been visited by the backward search: + - found a path between $s$ and $t$: $s...v\ w...t$ + - length of path is $l=d(s,v)+w(v,w)+d(w,t)$ + - if $\mu>l$, set $\mu=l$ + - analogously for the backward search +- terminate when the search in one direction selects a vertex $v$ that + has already been selected in other direction +- return $\mu$ + +::: bem +It is not always true that if the algorithm stops at $v$, that then the +shortest path between $s$ and $t$ has to go through $v$. +::: + +## Generic labeling method + +A convenient generalization of Dijkstra and Bellman-Ford: + +- for each vertex, maintain a status variable + $S(v)\in\{\text{unreached}, \text{labelchanged}, \text{settled}\}$ +- repeatedly relax edges +- repeat until nothing changes + +```{=tex} +\begin{lstlisting} +function GenericLabelingMethod(G,s) + for all v $\in$ V + v.dist = $\infty$ + v.parent = NIL + v.status = unreached + s.dist = 0 + s.status = labelchanged + while a vertex exists with status labelchanged + pick such vertex v + for all neighbors u of v + Relax(v,u) + if relaxation changed value u.dist + u.status = labelchanged + v.status = settled +\end{lstlisting} +``` +## A\* search + +**Idea**: + +- assume that we know a lower bound $\pi(v)$ on the distance $d(v,t)$ + for all vertices $v$: $$\forall v: \pi(v)\le d(v,t)$$ +- run the *Generic Labeling Method* with start in $s$ +- while Dijkstra selects by $d(s,u)+w(u,v)$, A\* selects by + $d(s,u)+w(u,v)+\pi(v)$ + +**Algorithm**: + +```{=tex} +\begin{lstlisting} +function AstarSearch(G,s,t) + for all v $\in$ V + v.dist = $\infty$ + v.status = unreached + s.dist = 0 + s.status = labelchanged + while a vertex exists with status labelchanged + select u = argmin(u.dist + $\pi$(u)) + if u == t + terminate, found correct distance + for all neighbors v of u + Relax(u,v) + if relaxation changed value v.dist + v.status = labelchanged + u.status = settled +\end{lstlisting} +``` +**Running time**: If the lower bounds are feasible, A\*-search has the +same running time as Dijkstra. Can often work fast but in rare cases +very slow. + +## Union-find data structure + +TODO. + +## Operation O1 + +TODO. + +## Minimal spanning trees + +**Idea**: + +Given an undirected graph $G=(V,E)$ with real-valued edge values +$(w_e)_{e\in E}$ find a tree $T=(V',A)$ with $V=V',A\subset E$ that +minimizes $$\mathrm{weight}(T)=\sum_{e\in A}w_e.$$ Minimal spanning +trees are not unique and most graphs have many minimal spanning trees. + +### Safe edges + +Given a subset $A$ of the edges of an MST, a new edge +$e\in E\setminus A$ is called **safe** with respect to $A$ if there +exists a MST with edge set $A\cup\{e\}$. + +- start with MST $T=(V,E')$ +- take some of its edges $A\subset E'$ +- new edge $e$ is *safe* if $A\cup\{e\}$ can be completed to an MST + $T'$ + +### Cut property to find safe edges + +A cut $(S,V\setminus S)$ is a partition of the vertex set of a graph in +two disjoint subsets. + +TODO. + +### Kruskal's algorithm + +**Idea**: + +- start with an empty tree +- repeatedly add the lightest remaining edge that does not produce a + cycle +- stop when the resulting tree connects the whole graph + +**Naive algorithm** using cut property: + +```{=tex} +\begin{lstlisting} +function KruskalNaiveMST(V,E,W) + sort all edges according to their weight + A = {} + for all e $\in$ E, in increasing order of weight + if A $\cup$ {e} does not contain a cycle + A = A $\cup$ {e} + if |A| = n - 1 + return A +\end{lstlisting} +``` +**Running time**: + +- sorting $\O(|E|\log|E|)$ +- check for cycle: $\O(|E|\cdot?)$ +- total: $\O(|E|\log|E|+|E|\cdot?)$ diff --git a/notes/theo1/main.pdf b/notes/theo1/main.pdf new file mode 100644 index 0000000..a61d262 Binary files /dev/null and b/notes/theo1/main.pdf differ diff --git a/notes/theo1/makefile b/notes/theo1/makefile new file mode 100644 index 0000000..2cacf25 --- /dev/null +++ b/notes/theo1/makefile @@ -0,0 +1,31 @@ +VIEW = zathura + +all: + @mkdir -p build/ + @pandoc main.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex -B title.tex >/dev/null + @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) & + @progress 3 pdflatex + @cp build/main.pdf . &>/dev/null + @echo done. + +part: + @mkdir -p build/ + @pandoc part.md --filter pandoc-latex-environment -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex >/dev/null + @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) & + @progress 1 pdflatex + @echo done. + +exam: + @mkdir -p build/ + @pandoc exam.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/exam.tex --pdf-engine-opt=-shell-escape -H header.tex -B examtitle.tex >/dev/null + @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/exam.tex | grep '^!.*' -A200 --color=always ||true) & + @progress 1 pdflatex + @cp build/exam.pdf . &>/dev/null + @echo done. + +clean: + @$(RM) -rf build + +run: all + @clear + @$(VIEW) build/main.pdf diff --git a/notes/theo1/title.tex b/notes/theo1/title.tex new file mode 100644 index 0000000..4ed6e46 --- /dev/null +++ b/notes/theo1/title.tex @@ -0,0 +1,17 @@ +\begin{titlepage} + \begin{center} + \vspace*{1cm} + + {\huge\textbf{Theoretische Informatik 1\bigskip\\Algorithmen und Datenstrukturen}} + + \vspace{0.5cm} + {\Large Inofficial lecture notes}\\ + \textbf{Marvin Borner} + + \vfill + + Vorlesung gehalten von\\ + \textbf{Ulrike von Luxburg}\\ + Wintersemester 2022/23 + \end{center} +\end{titlepage} diff --git a/notes/theo2/header.tex b/notes/theo2/header.tex new file mode 100644 index 0000000..959df6a --- /dev/null +++ b/notes/theo2/header.tex @@ -0,0 +1,73 @@ +\usepackage{braket} +\usepackage{polynom} +\usepackage{amsthm} +\usepackage{csquotes} +\usepackage{svg} +\usepackage{environ} +\usepackage{mathtools} +\usepackage{tikz,pgfplots} +\usepackage{titleps} +\usepackage{tcolorbox} +\usepackage{enumitem} +\usepackage{listings} +\usepackage{soul} +\usepackage{forest} +\usepackage{datetime} + +\pgfplotsset{width=10cm,compat=1.15} +\usepgfplotslibrary{external} +\usetikzlibrary{arrows,automata,positioning} +%\usetikzlibrary{calc,trees,positioning,arrows,arrows.meta,fit,shapes,chains,shapes.multipart} +%\tikzexternalize +\setcounter{MaxMatrixCols}{20} +\graphicspath{{assets}} + +\newpagestyle{main}{\sethead{\toptitlemarks\thesection\quad\sectiontitle}{}{\thepage}\setheadrule{.4pt}} +\pagestyle{main} + +\newtcolorbox{proof-box}{title=Beweis,colback=green!5!white,arc=0pt,outer arc=0pt,colframe=green!60!black} +\newtcolorbox{bsp-box}{title=Beispiel,colback=orange!5!white,arc=0pt,outer arc=0pt,colframe=orange!60!black} +\newtcolorbox{visu-box}{title=Visualisation,colback=cyan!5!white,arc=0pt,outer arc=0pt,colframe=cyan!60!black} +\newtcolorbox{bem-box}{title=Bemerkung,colback=white,colbacktitle=white,coltitle=black,arc=0pt,outer arc=0pt,colframe=black} +\newtcolorbox{defi-box}{title=Definition,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black} +\newtcolorbox{satz-box}{title=Satz,colback=gray!5!white,arc=0pt,outer arc=0pt,colframe=gray!60!black} + +\newcommand\toprove{\textbf{Zu zeigen: }} + +\newcommand\defeq{\mathrel{\vcentcolon=}} +\newcommand\defiff{\mathrel{\vcentcolon\Longleftrightarrow}} + +\newcommand\N{\mathbb{N}} +\newcommand\R{\mathbb{R}} +\newcommand\Z{\mathbb{Z}} +\newcommand\Q{\mathbb{Q}} +\newcommand\C{\mathbb{C}} +\renewcommand\P{\mathbb{P}} +\renewcommand\O{\mathcal{O}} +\newcommand\pot{\mathcal{P}} +\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} +\newcommand{\bigcupdot}{\dot{\bigcup}} + +\DeclareMathOperator{\ggT}{ggT} +\DeclareMathOperator{\kgV}{kgV} + +\newlist{abc}{enumerate}{10} +\setlist[abc]{label=(\alph*)} + +\newlist{num}{enumerate}{10} +\setlist[num]{label=\arabic*.} + +\newlist{rom}{enumerate}{10} +\setlist[rom]{label=(\roman*)} + +\makeatletter +\renewenvironment{proof}[1][\proofname] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse} +\makeatother +\def\qedsymbol{\sc q.e.d.} % hmm? + +\lstset{ + basicstyle=\ttfamily, + escapeinside={(*@}{@*)}, + numbers=left, + mathescape +} diff --git a/notes/theo2/main.md b/notes/theo2/main.md new file mode 100644 index 0000000..64e7e06 --- /dev/null +++ b/notes/theo2/main.md @@ -0,0 +1,477 @@ +--- +author: Marvin Borner +date: "`\\today`{=tex}" +lang: de-DE +pandoc-latex-environment: + bem-box: + - bem + bsp-box: + - bsp + defi-box: + - defi + proof-box: + - proof + satz-box: + - satz + visu-box: + - visu +toc-title: Inhalt +--- + +```{=tex} +\newpage +\renewcommand\O{\mathcal{O}} % IDK WHY +``` +# Reguläre Sprachen und endliche Automaten + +## Motivation + +- Eingabe +- Verarbeitung (Berechnungen, Zustände) +- Ausgabe + +## Wörter und Sprachen + +::: defi +Ein *Alphabet* $\Sigma$ sei eine nicht-leere, endliche Menge. Ein *Wort* +$w$ ist entsprechend eine Folge von Elementen aus $\Sigma$. +::: + +::: bsp +- $\Sigma=\{a,...,z\}$, $w=\text{luxburg}$, $|w|=7$ +::: + +::: defi +$\Sigma^n$ ist die Menge aller Wörter der Länge $n$. Die *Kleene'sche +Hülle* ist $\Sigma^*\defeq\bigcup_{n=0}^\infty\Sigma^n$. +$\Sigma^+\defeq\bigcup_{n=1}^\infty\Sigma^n$. + +*Sprache $L$ über $\Sigma$* ist eine Teilmenge von $\Sigma^*$. +::: + +::: defi +Eine *Konkatenation* ist eine Aneinanderhängung zweier Wörter $u$ und +$w$. Eine Konkatenation zweier *Sprachen* $L_1,L_2$ ist +$L_1\circ L_2\defeq\{uw\mid u\in L_1,\ w\in L_2\}$. Die Kleene'sche +Hülle einer Sprache $L$ ist dann +$L^*\defeq\{\underbrace{x_1...x_k}_{\mathclap{\text{Konkatenation von $k$ Wörtern}}}\mid x_i\in L,\ k\in\N_0\}$. + +Eine $k$-fache Aneinanderhängung von Wörtern ist +$w_k=\underbrace{w...w}_\text{$k$-mal}$. +::: + +::: bsp +- $w=010$, $u=001$, $wu=\underbrace{010}_w \underbrace{001}_u$, + $uwu=\underbrace{001}_u \underbrace{010}_w \underbrace{001}_u$ +- $w^3=010\ 010\ 010$ +::: + +::: bem +Die Konkatenation auf $\Sigma^*$ hat die Eigenschaften: + +- assoziativ: $a(bc)=(ab)c$ +- nicht kommutativ: $ab\ne ba$ +- neutrales Element $\varepsilon$: $\varepsilon a=a\varepsilon=a$ +- ein inverses Element +::: + +::: defi +Ein Wort $x$ heißt *Teilwort* eines Wortes $y$, falls es Wörter $u$ und +$v$ gibt, sodass $y=uxv$. + +- Falls $u=\varepsilon$, $x$ *Präfix* von $y$ +- Falls $v=\varepsilon$, $x$ *Suffix* von $y$ +::: + +::: bsp +- $01$ ist Teilwort von $0\textbf{01}11$ +- $10$ ist Präfix von $\textbf{10}10011$ +- $011$ ist Suffix von $10101110\textbf{011}$ +::: + +## Endlicher, deterministischer Automat + +::: defi +Für einen *endlichen, deterministischen Automat* +$(Q,\Sigma,\delta,q_0,F)$ ist + +- $Q$ eine endliche Menge der *Zustände* +- $\Sigma$ das *Alphabet* +- $\delta: Q\times\Sigma\to Q$ die Übergangsfunktion +- $q_0\in Q$ der *Startzustand* +- $F\subset Q$ die Menge der *akzeptierenden Zustände* +::: + +::: bsp +```{=tex} +\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] + \tikzstyle{every state}=[] + + \node[state,initial] (q_1) {$q_1$}; + \node[state,accepting] (q_2) [right of=q_1] {$q_2$}; + \node[state] (q_3) [right of=q_2] {$q_3$}; + + \path[->] + (q_1) edge [loop above] node {0} ( ) + edge [bend left] node {1} (q_2) + (q_2) edge [bend left] node {0} (q_3) + edge [loop above] node {1} ( ) + (q_3) edge [bend left] node {0,1} (q_2); +\end{tikzpicture}\end{center} +``` +$Q=\{q_1,q_2,q_3\}$, $\Sigma=\{0,1\}$, $q_1$ Startzustand, $F=\{q_2\}$. + +$\delta$ kann dargestellt werden durch + + / 0 1 + ------- ------- ------- + $q_1$ $q_1$ $q_2$ + $q_2$ $q_3$ $q_2$ + $q_3$ $q_2$ $q_2$ + +Die Zustandsfolge ist mit $w=001$ +$$q_1\xrightarrow{0}q_1\xrightarrow{0}q_1\xrightarrow{1}q_2.$$ +::: + +::: defi +- partielle Übergangsfunktion: nicht alle Übergänge sind definiert +- totale Übergangsfunktion: alle Übergänge sind definiert +::: + +::: defi +Eine Folge $s_0,...,s_n\in Q$ von Zuständen heißt *Berechnung* des +Automaten $M=(Q,\Sigma,\delta,q_0,F)$ auf dem Wort $w=w_1...w_n$, falls + +- $s_0=q_0$,q +- $\forall i=0,...,n-1: s_{i+1}=\delta(s_i,w_{i+1})$ + +Es ist also eine "gültige" Folge von Zuständen, die man durch Abarbeiten +von $w$ erreicht. +::: + +::: bsp +```{=tex} +\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] + \tikzstyle{every state}=[] + + \node[state,initial] (q_1) {$q_1$}; + \node[state,accepting] (q_2) [right of=q_1] {$q_2$}; + \node[state] (q_3) [right of=q_2] {$q_3$}; + + \path[->] + (q_1) edge [loop above] node {0} ( ) + edge [bend left] node {1} (q_2) + (q_2) edge [bend left] node {0} (q_3) + edge [loop above] node {1} ( ) + (q_3) edge [bend left] node {0,1} (q_2); +\end{tikzpicture}\end{center} +``` +- $w=001$ ergibt die Zustandsfolge $q_1q_1q_1q_2$ +::: + +::: defi +Eine Berechnung *akzeptiert* das Wort $w$, falls die Berechnung in einem +akzeptierten Zustand endet. + +Die von einem endlichen Automaten $M$ *akzeptierte* (erkannte) Sprache +$L(M)$ ist die Menge der Wörter, die von $M$ akzeptiert werden: +$$L(M)\defeq\{w\in\Sigma^*\mid M\text{ akzeptiert } w\}$$ +::: + +::: bem +Eine Berechnung kann mehrmals in akzeptierenden Zuständen +eintreten/austreten. Wichtig ist der Endzustand, nachdem der letzte +Buchstabe des Eingabewortes verarbeitet wurde. +::: + +::: bsp +```{=tex} +\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] + \tikzstyle{every state}=[] + + \node[state,initial] (q_1) {$q_1$}; + \node[state,accepting] (q_2) [right of=q_1] {$q_2$}; + + \path[->] + (q_1) edge [loop above] node {0} ( ) + edge [bend left] node {1} (q_2) + (q_2) edge [bend left] node {0} (q_1) + edge [loop above] node {1} ( ); +\end{tikzpicture}\end{center} +``` +- $w=1101\rightarrow q_1q_2q_2q_1q_2\rightarrow w$ wird akzeptiert +- $w=010\rightarrow q_1q_1q_2q_1\rightarrow w$ wird **nicht** + akzeptiert + +Es folgt: +$$L(M)=\{w\in\Sigma^*\mid w=\varepsilon\text{ oder }w\text{ endet mit }0\}$$ +::: + +::: defi +Sei $\delta:Q\times\Sigma\to Q$ eine Übergangsfunktion. Die *erweiterte +Übergangsfunktion* $\delta^*$: $Q\times\Sigma^*\to Q$ sei induktiv +definiert: + +- $\delta^*(q,\varepsilon)=q$ für alle $q\in Q$ +- Für $w\in\Sigma^*$, $a\in\Sigma$ ist: + $$\delta^*(q,wa)=\delta(\underbrace{\delta^*(q,w)}_{\mathclap{\text{Zustand nach Lesen von $w$}}}, \overbrace{a}^{\mathclap{\text{Lesen von Buchstabe $a$}}}).$$ +::: + +## Reguläre Sprachen und Abschlusseigenschaften + +::: defi +Eine Sprache $L\subset\Sigma^*$ heißt *reguläre Sprache*, wenn es einen +endlichen Automaten $M$ gibt, der diese Sprache akzeptiert. + +Die Menge aller regulären Sprachen ist *REG*. +::: + +::: satz +Sei $L$ eine reguläre Sprache über $\Sigma$. Dann ist auch +$\bar{L}\defeq\Sigma^*\setminus L$ eine reguläre Sprache. + +::: proof +- $L$ regulär $\implies$ es gibt Automaten + $M=(Q,\Sigma,\delta,q_0,F)$, der $L$ akzeptiert +- Definiere "Komplementautomat" + $\bar{M}=(Q,\Sigma,\delta,q_0,\bar{F})$ mit + $\bar{F}\defeq Q\setminus F$. +- Dann gilt: + `\begin{align*} w\in\bar{L}&\iff M\text{ akzeptiert }w\text{ nicht}\\ &\iff \bar{M}\text{ akzeptiert }w. \end{align*}\qed`{=tex} +::: +::: + +::: satz +Die Menge der regulären Sprachen ist abgeschlossen bezüglich der +Vereinigung: $$L_1,L_2\in\text{REG}\implies L_1\cup L_2\in\text{REG}.$$ + +::: proof +Sei $M_1=(Q_1,\Sigma_1,\delta_1,s_1,F_1)$ ein Automat, der L_1 erkennt, +$M_2=(Q_2,\Sigma_2,\delta_2,s_2,F_2)$ ein Automat, der L_2 erkennt. + +Wir definieren den Produktautomaten $M\defeq M_1\times M_2$: +$M=(Q,\Sigma,\Delta,s,F)$ mit + +- $Q=Q_1\times Q_2$ +- $\Sigma=\Sigma_1\cup\Sigma_2$, +- $\underbrace{s}_{\mathclap{\text{neuer Startzustand}}}=(s_1,s_2)$, + $F=\{(f_1,f_2)\mid f_1\in F_1\text{ oder } f_2\in F_2\}$, +- $\underbrace{\Delta}_{\mathclap{\text{neue Übergangsfunktion}}}: Q\times\Sigma\to Q$, + $$\Delta((\underbrace{r_1}_{\in Q_1},\underbrace{r_2}_{\in Q_2}),\underbrace{a}_{\in\Sigma})=(\delta_1(r_1,a),\delta(r_2,a)).$$ + +Übertragung der Definition auf erweiterte Übergangsfunktionen: Beweis +durch Induktion (ausgelassen). + +Nach Definition von $F$ akzeptiert $M$ ein Wort $w$, wenn $M_1$ oder +$M_2$ das entsprechende Wort akzeptieren. Der Satz folgt. `\qed`{=tex} +::: +::: + +::: bsp +```{=tex} +$M_1$: \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] + \tikzstyle{every state}=[] + + \node[state,initial] (q_1) {$q_1$}; + \node[state,accepting] (q_2) [right of=q_1] {$q_2$}; + + \path[->] + (q_1) edge [loop above] node {0} ( ) + edge [bend left] node {1} (q_2) + (q_2) edge [bend left] node {0} (q_1) + edge [loop above] node {1} ( ); +\end{tikzpicture}\end{center} +$M_2$: TODO \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] + \tikzstyle{every state}=[] + + \node[state,initial] (q_1) {$q_1$}; + \node[state] (q_2) [right of=q_1] {$q_2$}; + \node[state,accepting] (q_2) [right of=q_2] {$q_2$}; + + \path[->] + (q_1) edge [loop above] node {0} ( ) + edge [bend left] node {1} (q_2) + (q_2) edge [bend left] node {0} (q_1) + edge [loop above] node {1} ( ) + (q_3) edge [bend left] node {0} (q_1) + edge [loop above] node {1} ( ); +\end{tikzpicture}\end{center} +$M_1\times M_2$: TODO \begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] + \tikzstyle{every state}=[] + + \node[state,initial] (q_1) {$q_1$}; + \node[state,accepting] (q_2) [right of=q_1] {$q_2$}; + + \path[->] + (q_1) edge [loop above] node {0} ( ) + edge [bend left] node {1} (q_2) + (q_2) edge [bend left] node {0} (q_1) + edge [loop above] node {1} ( ); +\end{tikzpicture}\end{center} +``` +::: + +::: satz +Seien $L_1,L_2$ zwei reguläre Sprachen. Dann sind auch $L_1\cap L_2$ und +$L_1\setminus L_2$ reguläre Sprachen. + +::: proof +- $L_1\cap L_2$: Beweis funktioniert analog wie für $L_1\cup L_2$, nur + mit + $$F\defeq\{(q_1,q_2)\mid q_1\in F_1\text{\textbf{ und }}q_2\in F_2\}.$$ +- $L_1\setminus L_2=L_q\cap\bar{L_2}$ + +`\qed`{=tex} +::: +::: + +## Nicht-deterministische Automaten + +::: bsp +TODO (ggf. auch Sipser). + +```{=tex} +\begin{center}\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] + \tikzstyle{every state}=[] + + \node[state,initial] (q_1) {$q_1$}; + \node[state,accepting] (q_2) [right of=q_1] {$q_2$}; + \node[state] (q_3) [right of=q_2] {$q_3$}; + + \path[->] + (q_1) edge [loop above] node {0} ( ) + edge [bend left] node {1} (q_2) + (q_2) edge [bend left] node {0} (q_1) + edge [loop above] node {1} ( ); +\end{tikzpicture}\end{center} +``` +::: + +::: defi +Ein *nicht-deterministischer Automat* besteht aus einem $5$-Tupel +$(Q,\Sigma,\delta,q_0,F)$. + +- $Q$, $\Sigma$, $q_0$, $F$ wie beim deterministischen Automat, +- $\delta: Q\times\Sigma\cup\{\varepsilon\}\to\overbrace{\pot(Q)}^{(*)}$ + Übergangsfunktion + +$(*)$: Die Funktion definiert die **Menge** der möglichen Zustände, in +die man von einem Zustand durch Lesen eines Buchstabens gelangen kann. +::: + +::: defi +Sei $M=(Q,\Sigma,\delta,q_0,F)$ ein nicht-deterministischer endlicher +Automat, $w=w_1...w_n\in\Sigma^*$. Eine Folge von Zuständen +$s_0,s_1,...,s_m\in Q$ heißt *Berechnng von $M$ auf $w$*, falls man $w$ +schreiben kann als $w=u_1u_2...u_m$ mit +$u_i\in\Sigma\cup\{\underbrace{\varepsilon}_{\mathclap{\text{Übergänge $\varepsilon$, hier $u_i=\varepsilon$}}}\}$, +sodass + +- $s_0=q_0$, +- für alle $0\le i\le m-1:s_{i+1}\in\delta(s_1,u_{i+1}).$ + +Die Berechnung heißt *akzeptierend*, falls $s_m\in F$. + +Der nicht-deterministische Automat $M$ *akzeptiert Wort $w$*, falls es +eine akzeptierende Berechnung von $M$ auf $w$ gibt. +::: + +::: bem +$\varepsilon$-Transitionen: TODO. +::: + +::: bsp +Betrachte die regulären Sprachen + +- $A\defeq\{x\in\{0,1\}^*\mid\text{Anzahl }0\text{ gerade}\}$ +- $B\defeq\{x\in\{0,1\}^*\mid\text{Anzahl }0\text{ ungerade}\}$ + +Zugehörige Automaten: TODO + +Nun betrachte *Konkatenation $AB$*. Um die Sprache zu erkennen, müsste +der Automat bei einer Eingabe zunächst einen ersten Teil $A$ des Wortes +betrachten und schauen, ob die Anzahl der $0$ gerade ist. **Irgendwann** +müsste er beschließen, dass nun der zweite Teil $B$ des Wortes anfängt +und er müsste schauen, ob dort die Anzahl der $0$ ungerade ist. + +$$\text{"Irgendwann"}\implies\text{nicht-deterministisch.}$$ + +TODO: Graph. +::: + +## Mächtigkeit + +::: bem +Die Mächtigkeit eines Automaten wird hierbei beschrieben durch die +Anzahl an Sprachen, die dieser erkennen kann. +::: + +::: defi +Zwei Automaten $M_1$, $M_2$ heißen *äquivalent*, wenn sie die gleiche +Sprache erkennen: $$L(M_1)=L(M_2)$$ +::: + +::: satz +Zu jedem nicht-deterministischen endlichen Automaten gibt es einen +äquivalenten deterministischen endlichen Automaten. + +::: proof +Lang aber trivial. Basically konstruiert man einfach eine +deterministische Übergangsfunktion auf den nicht-deterministischen +Verzweigungen. +::: +::: + +::: satz +Es folgt: + +Eine Sprache $L$ ist regulär $\iff$ es gibt einen +nicht-deterministischen Automaten, der $L$ akzeptiert. +::: + +::: satz +Die Klasse der regulären Sprachen ist abgeschlossen unter Konkatenation: +$$L_1,L_2\in\mathrm{REG}\implies L_1L_2\in\mathrm{REG}$$ +::: + +::: satz +Die Klasse REG ist abgeschlossen unter Bildung der Kleene'schen Hülle, +d.h.: $$L\in\mathrm{REG}\implies L^*\in\mathrm{REG}$$ +::: + +## Reguläre Ausdrücke + +::: defi +Sei $\Sigma$ ein Alphabet. Dann: + +- $\underbrace{\emptyset}_{\mathclap{\text{leere Sprache}}}$ und + $\overbrace{\varepsilon}^{\mathclap{\text{leeres Wort}}}$ sind + reguläre Ausdrücke. +- Alle Buchstaben aus $\Sigma$ sind reguläre Ausdrücke. +- Falls $R_1$, $R_2$ reguläre Ausdrücke sind, dann sind auch die + folgenden Ausdrücke regulär: + - $R_1\cup R_2$, + - $R_1\circ R_2$, + - $R_1^*$. +::: + +::: defi +Sei $R$ ein regulärer Ausdruck. Dann ist die *von $R$ induzierte Sprache +$L(R)$* wie folgt definiert: + +- $R=\emptyset\implies L(R)=\emptyset$ +- $R=\epsilon\implies L(R)=\{\varepsilon\}$ +- $R=\sigma\text{ für ein }\sigma\in\Sigma\implies L(R)=\{\sigma\}$ +- $R=R_1\cup R_2\implies L(R)=L(R_1)\cup L(R_2)$ +- $R=R_1\circ R_2\implies L(R)=L(R_1)\circ L(R_2)$ +- $R=R_1^*\implies L(R)=(L(R_1))^*$ +::: + +::: satz +Eine Sprache ist genau dann regulär, wenn sie durch einen regulären +Ausdruck beschrieben wird. + +::: proof +Strukturelle Induktion. Tja. +::: +::: diff --git a/notes/theo2/main.pdf b/notes/theo2/main.pdf new file mode 100644 index 0000000..398474f Binary files /dev/null and b/notes/theo2/main.pdf differ diff --git a/notes/theo2/makefile b/notes/theo2/makefile new file mode 100644 index 0000000..58570c7 --- /dev/null +++ b/notes/theo2/makefile @@ -0,0 +1,23 @@ +VIEW = zathura + +all: + @mkdir -p build/ + @pandoc main.md --filter pandoc-latex-environment --toc -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex -B title.tex >/dev/null + @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) & + @progress 3 pdflatex + @cp build/main.pdf . &>/dev/null + @echo done. + +part: + @mkdir -p build/ + @pandoc part.md --filter pandoc-latex-environment -N -V fontsize=11pt -V geometry:a4paper -V geometry:margin=2.5cm -o $(CURDIR)/build/main.tex --pdf-engine-opt=-shell-escape -H header.tex >/dev/null + @(pdflatex -shell-escape -halt-on-error -output-directory $(CURDIR)/build/ $(CURDIR)/build/main.tex | grep '^!.*' -A200 --color=always ||true) & + @progress 1 pdflatex + @echo done. + +clean: + @$(RM) -rf build + +run: all + @clear + @$(VIEW) build/main.pdf diff --git a/notes/theo2/title.tex b/notes/theo2/title.tex new file mode 100644 index 0000000..3adc197 --- /dev/null +++ b/notes/theo2/title.tex @@ -0,0 +1,21 @@ +\begin{titlepage} + \begin{center} + \vspace*{1cm} + + {\huge\textbf{Theoretische Informatik 2\bigskip\\Berechenbarkeit und Komplexität}} + + \vspace{0.5cm} + {\Large Inoffizielles Skript}\\ + \textbf{Marvin Borner} + + \vfill + {\Large \textbf{WARNUNG WIP: Fehler zu erwarten!}\\\textbf{Stand: \today, \currenttime}}\\ + {\large Bitte meldet euch bei mir, falls ihr Fehler findet.} + % \includegraphics[width=0.4\textwidth]{zeller_logo}\\ + \vfill + + Vorlesung gehalten von\\ + \textbf{Ulrike von Luxburg}\\ + Sommersemester 2023 + \end{center} +\end{titlepage} diff --git a/sync.sh b/sync.sh index 389216d..e2ccf67 100755 --- a/sync.sh +++ b/sync.sh @@ -6,11 +6,14 @@ rm -rf notes/ # mathe for i in $(seq 3); do - mkdir -p "notes/mathe$i/" && find "$path/SM$i/mathe$i/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/mathe$i/" \; + mkdir -p "notes/mathe$i/" && find "$path/SM$i/mathe$i/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "exam.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/mathe$i/" \; done -# algo -mkdir -p "notes/algo/" && find "$path/SM3/algo/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/algo/" \; +# theo1 +mkdir -p "notes/theo1/" && find "$path/SM3/algo/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "exam.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/theo1/" \; + +# theo2 +mkdir -p "notes/theo2/" && find "$path/SM4/theo2/vorbereitung/" -maxdepth 1 -type f \( -name "main.md" -o -name "main.pdf" -o -name "exam.md" -o -name "exam.pdf" -o -name "*.tex" -o -name "makefile" \) -exec cp {} "notes/theo2/" \; git add . git status -- cgit v1.2.3