From 4614294614e6f6b38e0ca86e77871e75b4c26071 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 16 Mar 2021 15:48:10 +0100 Subject: add new slides --- vorlesungen/slides/8/Makefile.inc | 5 - vorlesungen/slides/8/chapter.tex | 7 - vorlesungen/slides/8/fourier.tex | 83 +++++++++++ vorlesungen/slides/8/inzidenz.tex | 4 +- vorlesungen/slides/8/markov/google.tex | 123 ---------------- vorlesungen/slides/8/markov/irreduzibel.tex | 136 ----------------- vorlesungen/slides/8/markov/markov.tex | 111 -------------- vorlesungen/slides/8/markov/pf.tex | 53 ------- vorlesungen/slides/8/markov/stationaer.tex | 57 ------- vorlesungen/slides/8/spanningtree.tex | 164 +++++++++++++++++++++ vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg | Bin 0 -> 231575 bytes vorlesungen/slides/8/tokyo/tokyosubway.pdf | Bin 0 -> 1016965 bytes .../slides/8/tokyo/transportnetworkgraph.png | Bin 0 -> 114239 bytes 13 files changed, 249 insertions(+), 494 deletions(-) create mode 100644 vorlesungen/slides/8/fourier.tex delete mode 100644 vorlesungen/slides/8/markov/google.tex delete mode 100644 vorlesungen/slides/8/markov/irreduzibel.tex delete mode 100644 vorlesungen/slides/8/markov/markov.tex delete mode 100644 vorlesungen/slides/8/markov/pf.tex delete mode 100644 vorlesungen/slides/8/markov/stationaer.tex create mode 100644 vorlesungen/slides/8/spanningtree.tex create mode 100644 vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg create mode 100644 vorlesungen/slides/8/tokyo/tokyosubway.pdf create mode 100644 vorlesungen/slides/8/tokyo/transportnetworkgraph.png (limited to 'vorlesungen/slides/8') diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc index 233835a..d46dc7f 100644 --- a/vorlesungen/slides/8/Makefile.inc +++ b/vorlesungen/slides/8/Makefile.inc @@ -28,10 +28,5 @@ chapter8 = \ ../slides/8/tokyo/bahn0.tex \ ../slides/8/tokyo/bahn1.tex \ ../slides/8/tokyo/bahn2.tex \ - ../slides/8/markov/google.tex \ - ../slides/8/markov/markov.tex \ - ../slides/8/markov/irreduzibel.tex \ - ../slides/8/markov/stationaer.tex \ - ../slides/8/markov/pf.tex \ ../slides/8/chapter.tex diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex index ac06775..6a0b13f 100644 --- a/vorlesungen/slides/8/chapter.tex +++ b/vorlesungen/slides/8/chapter.tex @@ -30,10 +30,3 @@ \folie{8/tokyo/bahn1.tex} \folie{8/tokyo/bahn2.tex} -\folie{8/markov/google.tex} -\folie{8/markov/markov.tex} -\folie{8/markov/stationaer.tex} -\folie{8/markov/irreduzibel.tex} -\folie{8/markov/pf.tex} - - diff --git a/vorlesungen/slides/8/fourier.tex b/vorlesungen/slides/8/fourier.tex new file mode 100644 index 0000000..86d8086 --- /dev/null +++ b/vorlesungen/slides/8/fourier.tex @@ -0,0 +1,83 @@ +% +% fourier.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Fourier-Transformation} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Algebra} +Die Laplace-Matrix eines Graphen ist symmetrisch +\uncover<2->{% + +$\Rightarrow$ +Es gibt eine Basis aus Eigenvektoren $g_i\in\mathbb{R}^n$ von $L(G)$: +\begin{align*} +L(G)g_i&=\lambda_i g_i +\end{align*}} +\end{block} +\uncover<12->{% +\vspace{-20pt} +\begin{block}{Fourier-Transformation} +Jedes $f\in\mathbb{R}^n$ kann durch die $g_i$ ausgedrückt werden +\begin{align*} +\uncover<13->{ +f&= a_1 g_1 + \dots + a_n g_n +} +\\ +\uncover<14->{ +&= \hat{f}_1 g_1 + \dots + \hat{f}_ng_n = \sum_{k=1}^n \hat{f}_kg_k +} +\end{align*} +\uncover<15->{% +Zerlegung nach Zeitkonstante $\lambda_i$ +} +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<3->{% +\begin{block}{Anwendung} +Wärmeleitungsgleichung +\begin{align*} +\uncover<4->{ +\frac{d}{dt}f &= L(G) f +} +\intertext{\uncover<5->{{\usebeamercolor[fg]{title}Ansatz:}}} +\uncover<6->{ +f&=a_1g_1T_1(t)+\dots + a_ng_nT_n(t) +} +\\ +\uncover<7->{ +\frac{d}{dt}f +&= +a_1g_1\dot{T}_1(t) + \dots + a_1g_1 \dot{T}_n(t) +} +\\ +\uncover<8->{ +&= +a_1Lg_1 + \dots + a_nLg_n +} +\\ +\uncover<9->{ +&= +a_1\lambda_1 g_1 + \dots + a_n\lambda_n g_n +} +\\ +\uncover<10->{ +\dot{T}_i(t) &= \lambda_i T_i(t) +} +\uncover<11->{ +\quad +\Rightarrow +\quad +T_i(t) = e^{\lambda_it} \uncover<-9>{T_i(0)} +} +\end{align*} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/inzidenz.tex b/vorlesungen/slides/8/inzidenz.tex index 87578df..952c85b 100644 --- a/vorlesungen/slides/8/inzidenz.tex +++ b/vorlesungen/slides/8/inzidenz.tex @@ -126,8 +126,8 @@ B(G) 1&0&0&1&1&0\\ 1&1&0&0&0&1\\ 0&1&1&0&1&0\\ -0&0&1&0&0&0\\ -0&0&0&1&0&1 +0&0&1&0&0&1\\ +0&0&0&1&0&0 \end{pmatrix} \\[12pt] \uncover<4->{ diff --git a/vorlesungen/slides/8/markov/google.tex b/vorlesungen/slides/8/markov/google.tex deleted file mode 100644 index d1ec31d..0000000 --- a/vorlesungen/slides/8/markov/google.tex +++ /dev/null @@ -1,123 +0,0 @@ -% -% google.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\setlength{\abovedisplayskip}{5pt} -\setlength{\belowdisplayskip}{5pt} -\frametitle{Google-Matrix} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{center} -\begin{tikzpicture}[>=latex,thick] - -\def\r{2.4} -\coordinate (A) at (0,0); -\coordinate (B) at (0:\r); -\coordinate (C) at (60:\r); -\coordinate (D) at (120:\r); -\coordinate (E) at (180:\r); - -\foreach \a in {2,...,5}{ - \fill[color=white] ({60*(\a-2)}:\r) circle[radius=0.2]; - \draw ({60*(\a-2)}:\r) circle[radius=0.2]; - \node at ({60*(\a-2)}:\r) {$\a$}; -} -\fill[color=white] (A) circle[radius=0.2]; -\draw (A) circle[radius=0.2]; -\node at (A) {$1$}; - -{\color<6>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); -} - -{\color<7>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) to[out=-150,in=-30] (E); -} - -{\color<8>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-90,in=30] (A); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-30,in=90] (B); -} - -{\color<9>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (C); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (A); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); -} - -{\color<10>{red} - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); - \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) to[out=90,in=-150] (D); -} - -\end{tikzpicture} -\end{center} -\vspace{-10pt} -\renewcommand{\arraystretch}{1.1} -\uncover<5->{ -\begin{align*} -H&=\begin{pmatrix} -\uncover<6->{0 } - &\uncover<7->{0 } - &\uncover<8->{{\color<8>{red}\frac{1}{2}}} - &\uncover<9->{{\color<9>{red}\frac{1}{3}}} - &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ -\uncover<6->{{\color<6>{red}\frac{1}{2}}} - &\uncover<7->{0 } - &\uncover<8->{{\color<8>{red}\frac{1}{2}}} - &\uncover<9->{0 } - &\uncover<10->{0 }\\ -\uncover<6->{{\color<6>{red}\frac{1}{2}}} - &\uncover<7->{{\color<7>{red}\frac{1}{2}}} - &\uncover<8->{0 } - &\uncover<9->{{\color<9>{red}\frac{1}{3}}} - &\uncover<10->{0 }\\ -\uncover<6->{0 } - &\uncover<7->{0 } - &\uncover<8->{0 } - &\uncover<9->{0 } - &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ -\uncover<6->{0 } - &\uncover<7->{{\color<7>{red}\frac{1}{2}}} - &\uncover<8->{0 } - &\uncover<9->{{\color<9>{red}\frac{1}{3}}} - &\uncover<10->{0 } -\end{pmatrix} -\\ -\uncover<11->{ -h_{ij} -&= -\frac{1}{\text{Anzahl Links ausgehend von $j$}} -} -\end{align*}} -\end{column} -\begin{column}{0.48\textwidth} -\begin{block}{Aufgabe} -Bestimme die Wahrscheinlichkeit $p(i)$, mit der sich ein Surfer -auf der Website $i$ befindet -\end{block} -\uncover<2->{ -\begin{block}{Navigation} -$p(i) = P(i,\text{vor Navigation})$, -\uncover<3->{$p'(i)=P(i,\text{nach Navigation})$} -\uncover<4->{ -\[ -p'(i) = \sum_{j=1}^n h_{ij} p(j) -\]} -\end{block}} -\vspace{-15pt} -\begin{block}{Freier Wille} -\vspace{-12pt} -\[ -G = \alpha H + (1-\alpha)\frac{UU^t}{n} -\] -Google-Matrix -\end{block} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/irreduzibel.tex b/vorlesungen/slides/8/markov/irreduzibel.tex deleted file mode 100644 index 87e90e4..0000000 --- a/vorlesungen/slides/8/markov/irreduzibel.tex +++ /dev/null @@ -1,136 +0,0 @@ -% -% irreduzibel.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\frametitle{Irreduzible Markovkette} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{center} -\begin{tikzpicture}[>=latex,thick] -\def\r{2} -\coordinate (A) at ({\r*cos(0*60)},{\r*sin(0*60)}); -\coordinate (B) at ({\r*cos(1*60)},{\r*sin(1*60)}); -\coordinate (C) at ({\r*cos(2*60)},{\r*sin(2*60)}); -\coordinate (D) at ({\r*cos(3*60)},{\r*sin(3*60)}); -\coordinate (E) at ({\r*cos(4*60)},{\r*sin(4*60)}); -\coordinate (F) at ({\r*cos(5*60)},{\r*sin(5*60)}); - -\uncover<-2>{ -\draw (A) -- (B); -\draw (A) -- (C); -\draw (A) -- (D); -\draw (A) -- (E); -\draw (A) -- (F); - -\draw (B) -- (A); -\draw (B) -- (C); -\draw (B) -- (D); -\draw (B) -- (E); -\draw (B) -- (F); - -\draw (C) -- (A); -\draw (C) -- (B); -\draw (C) -- (D); -\draw (C) -- (E); -\draw (C) -- (F); - -\draw (D) -- (A); -\draw (D) -- (B); -\draw (D) -- (C); -\draw (D) -- (E); -\draw (D) -- (F); - -\draw (E) -- (A); -\draw (E) -- (B); -\draw (E) -- (C); -\draw (E) -- (D); -\draw (E) -- (F); - -\draw (F) -- (A); -\draw (F) -- (B); -\draw (F) -- (C); -\draw (F) -- (D); -\draw (F) -- (E); -} - -\uncover<3->{ - -\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] (A) to[out=90,in=-30] (B); -\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] (A) -- (C); -\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) -- (A); -\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] (B) to[out=150,in=30] (C); -\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) to[out=-90,in=-150,distance=1cm] (B); -\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) to[out=-60,in=180] (A); -\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) -- (B); - -\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] - (D) to[out=-90,in=150] (E); -\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] - (E) -- (D); -\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] - (E) to[out=-30,in=-150] (F); -\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] - (F) -- (E); -\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] - (F) to[out=120,in=0] (D); -\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] - (D) -- (F); -} - -\fill[color=white] (A) circle[radius=0.2]; -\fill[color=white] (B) circle[radius=0.2]; -\fill[color=white] (C) circle[radius=0.2]; -\fill[color=white] (D) circle[radius=0.2]; -\fill[color=white] (E) circle[radius=0.2]; -\fill[color=white] (F) circle[radius=0.2]; - -\draw (A) circle[radius=0.2]; -\draw (B) circle[radius=0.2]; -\draw (C) circle[radius=0.2]; -\draw (D) circle[radius=0.2]; -\draw (E) circle[radius=0.2]; -\draw (F) circle[radius=0.2]; - -\node at (A) {$1$}; -\node at (B) {$2$}; -\node at (C) {$3$}; -\node at (D) {$4$}; -\node at (E) {$5$}; -\node at (F) {$6$}; - -\end{tikzpicture} -\end{center} -\uncover<2->{% -\begin{block}{Irreduzibel} -Graph zusammenhängend $\Rightarrow$ -Keine Zerlegung in Teilgraphen möglich -\end{block}} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<3->{% -\begin{block}{Reduzibel} -Die Zustandsmenge zerfällt in zwei disjunkte Teilmengen $V=V_1\cup V_2$ -und es gibt keine Übergängen zwischen den Mengen: -\uncover<4->{% -\begin{align*} -P -&= -\begin{pmatrix*}[l] -0 &0.2&0.5& & & \\ -0.3&0.2&0.5& & & \\ -0.7&0.6&0 & & & \\ - & & &0 &0.3&0.4\\ - & & &0.4&0 &0.6\\ - & & &0.6&0.7&0 -\end{pmatrix*} -\end{align*}}% -\uncover<5->{% -$P$ zerfällt in zwei Blöcke die unabhängig voneinander analysiert werden können -} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/markov.tex b/vorlesungen/slides/8/markov/markov.tex deleted file mode 100644 index e92ff0f..0000000 --- a/vorlesungen/slides/8/markov/markov.tex +++ /dev/null @@ -1,111 +0,0 @@ -% -% markov.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\bgroup -\setlength{\abovedisplayskip}{5pt} -\setlength{\belowdisplayskip}{5pt} -\begin{frame}[t] -\frametitle{Markovketten} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{center} -\begin{tikzpicture}[>=latex,thick] - -\def\r{2.2} - -\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); -\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); -\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); -\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); -\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); - -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!40] - (A) -- (C); -\draw[color=white,line width=8pt] (B) -- (D); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!80] - (B) -- (D); - -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!60] - (A) -- (B); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!20] - (B) -- (C); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] - (C) -- (D); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] - (D) -- (E); -\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] - (E) -- (A); - -\fill[color=white] (A) circle[radius=0.2]; -\fill[color=white] (B) circle[radius=0.2]; -\fill[color=white] (C) circle[radius=0.2]; -\fill[color=white] (D) circle[radius=0.2]; -\fill[color=white] (E) circle[radius=0.2]; - -\draw (A) circle[radius=0.2]; -\draw (B) circle[radius=0.2]; -\draw (C) circle[radius=0.2]; -\draw (D) circle[radius=0.2]; -\draw (E) circle[radius=0.2]; - -\node at (A) {$1$}; -\node at (B) {$2$}; -\node at (C) {$3$}; -\node at (D) {$4$}; -\node at (E) {$5$}; - -\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 0.6$}; -\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 0.2$}; -\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 1$}; -\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 1$}; -\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 1$}; -\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 0.4$}; -\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 0.8$}; - -\end{tikzpicture} -\end{center} -\vspace{-10pt} -\uncover<7->{% -\begin{block}{Verteilung} -\begin{itemize} -\item<8-> -Welche stationäre Verteilung auf den Knoten stellt sich ein? -\item<9-> -$P(i)=?$ -\end{itemize} -\end{block}} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<2->{% -\begin{block}{\strut\mbox{Übergang\only<3->{s-/Wahrscheinlichkeit}smatrix}} -$P_{ij} = P(i | j)$, Wahrscheinlichkeit, in den Zustand $i$ überzugehen, -\begin{align*} -P -&= -\begin{pmatrix} - & & & &1\phantom{.0}\\ -0.6& & & & \\ -0.4&0.2& & & \\ - &0.8&1\phantom{.0}& & \\ - & & &1\phantom{.0}& -\end{pmatrix} -\end{align*} -\end{block}} -\vspace{-10pt} -\uncover<4->{% -\begin{block}{Eigenschaften} -\begin{itemize} -\item<5-> $P_{ij}\ge 0\;\forall i,j$ -\item<6-> Spaltensumme: -\( -\displaystyle -\sum_{i=1}^n P_{ij} = 1\;\forall j -\) -\end{itemize} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/pf.tex b/vorlesungen/slides/8/markov/pf.tex deleted file mode 100644 index da2ef2b..0000000 --- a/vorlesungen/slides/8/markov/pf.tex +++ /dev/null @@ -1,53 +0,0 @@ -% -% pf.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\frametitle{Perron-Frobenius-Theorie} -\vspace{-20pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{block}{Positive Matrizen und Vektoren} -$P\in M_{m\times n}(\mathbb{R})$ -\begin{itemize} -\item<2-> -$P$ heisst positiv, $P>0$, wenn $p_{ij}>0\;\forall i,j$ -\item<3-> -$P\ge 0$, wenn $p_{ij}\ge 0\;\forall i,j$ -\end{itemize} -\end{block} -\uncover<4->{% -\begin{block}{Beispiele} -\begin{itemize} -\item<5-> -Adjazenzmatrix $A(G)$ -\item<6-> -Gradmatrix $D(G)$ -\item<7-> -Wahrscheinlichkeitsmatrizen -\end{itemize} -\end{block}} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<8->{% -\begin{block}{Satz} -Es gibt einen positiven Eigenvektor $p$ von $P$ zum Eigenwert $1$ -\end{block}} -\uncover<9->{% -\begin{block}{Satz} -$P$ irreduzible Matrix, $P\ge 0$, hat einen Eigenvektor $p$, $p\ge 0$, -zum Eigenwert $1$ -\end{block}} -\uncover<10->{% -\begin{block}{Potenzmethode} -Falls $P\ge 0$ einen eindeutigen Eigenvektor $p$ hat\uncover<11->{, -dann konveriert die rekursiv definierte Folge -\[ -p_{n+1}=\frac{Pp_n}{\|Pp_n\|}, p_0 \ge 0, p_0\ne 0 -\]}% -\uncover<12->{$\displaystyle\lim_{n\to\infty} p_n = p$} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/markov/stationaer.tex b/vorlesungen/slides/8/markov/stationaer.tex deleted file mode 100644 index 92fab16..0000000 --- a/vorlesungen/slides/8/markov/stationaer.tex +++ /dev/null @@ -1,57 +0,0 @@ -% -% stationaer.tex -% -% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -% -\begin{frame}[t] -\frametitle{Stationäre Verteilung} -%\vspace{-15pt} -\begin{columns}[t,onlytextwidth] -\begin{column}{0.48\textwidth} -\begin{block}{Zeitentwicklung} -\begin{itemize} -\item<2-> -$P$ eine Wahrscheinlichkeitsmatrix -\item<3-> -$p_0\in\mathbb{R}^n$ Verteilung zur Zeit $t=0$ bekannt -\item<4-> -$p_k\in\mathbb{R}^n$ Verteilung zur Zeit $t=k$ -\end{itemize} -\uncover<5->{% -Entwicklungsgesetz -\begin{align*} -P(i,t=k) -&= -\sum_{j=1}^n P_{ij} P(j,t=k-1) -\\ -\uncover<6->{ -p_k &= Pp_{k-1} -} -\end{align*}} -\end{block} -\end{column} -\begin{column}{0.48\textwidth} -\uncover<7->{% -\begin{block}{Stationär} -Bedingung: $p_{k\mathstrut} = p_{k-1}$ -\uncover<8->{ -\begin{align*} -\Rightarrow -Pp &= p -\end{align*}}\uncover<9->{% -Eigenvektor zum Eigenwert $1$} -\end{block}} -\uncover<10->{% -\begin{block}{Fragen} -\begin{enumerate} -\item<11-> -Gibt es eine stationäre Verteilung? -\item<12-> -Gibt es einen Eigenvektor mit Einträgen $\ge 0$? -\item<13-> -Gibt es mehr als eine Verteilung? -\end{enumerate} -\end{block}} -\end{column} -\end{columns} -\end{frame} diff --git a/vorlesungen/slides/8/spanningtree.tex b/vorlesungen/slides/8/spanningtree.tex new file mode 100644 index 0000000..425fe1c --- /dev/null +++ b/vorlesungen/slides/8/spanningtree.tex @@ -0,0 +1,164 @@ +% +% spanningtree.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame} +\frametitle{Spannbäume} + +\vspace{-16pt} + +\begin{columns}[t] + +\begin{column}{0.40\hsize} +\begin{block}{Netzwerk} +Alle Knoten erreichen, Schleifen vermeiden $\Rightarrow$ Spannbaum +\vspace{-15pt} +\begin{center} +\begin{tikzpicture}[>=latex,scale=0.18] + +\coordinate (A) at ( 1.2927,-15.0076); +\coordinate (B) at ( 5.0261,- 7.7143); +\coordinate (C) at ( 4.9260,-13.0335); +\coordinate (D) at (12.2094,-22.9960); +\coordinate (F) at (17.8334,-13.4687); +\coordinate (G) at ( 6.4208,-10.2438); +\coordinate (H) at (17.2367,- 3.1047); +\coordinate (K) at (24.3760,- 3.0293); +\coordinate (L) at (23.2834,- 1.3563); +\coordinate (M) at (28.7093,- 4.0627); + +\fill (A) circle[radius=0.5]; +\fill (B) circle[radius=0.5]; +\fill (C) circle[radius=0.5]; +\fill (D) circle[radius=0.5]; +\fill (F) circle[radius=0.5]; +\fill (G) circle[radius=0.5]; +\fill (H) circle[radius=0.5]; +\fill (K) circle[radius=0.5]; +\fill (L) circle[radius=0.5]; +\fill (M) circle[radius=0.5]; + +%\uncover<1-4>{ +%\node at (A) [above] {$A$}; +%\node at (B) [above] {$B$}; +%\node at (C) [below] {$C$}; +%\node at (D) [below] {$D$}; +%\node at (F) [below right] {$F$}; +%\node at (G) [above] {$G$}; +%\node at (H) [above] {$H$}; +%\node at (K) [above right] {$K$}; +%\node at (L) [above] {$L$}; +%\node at (M) [above] {$M$}; +%} + +\uncover<5->{ +\node at (A) [above] {$1$}; +\node at (B) [above] {$2$}; +\node at (C) [below] {$3$}; +\node at (D) [below] {$4$}; +\node at (F) [below right] {$5$}; +\node at (G) [above] {$6$}; +\node at (H) [above] {$7$}; +\node at (K) [above right] {$8$}; +\node at (L) [above] {$9$}; +\node at (M) [above] {$10$}; +} + +\draw (L)--(H); +\draw (L)--(K); +\draw (L)--(M); + +\draw (H)--(B); +\draw (H)--(G); +\draw (H)--(F); +\draw (H)--(K); + +\draw (K)--(F); +\draw (K)--(M); + +\draw (M)--(F); +\draw (M)--(D); + +\draw (B)--(A); +\draw (B)--(C); +\draw (B)--(G); + +\draw (G)--(C); +\draw (G)--(F); + +\draw (F)--(D); + +\draw (C)--(F); +\draw (C)--(A); +\draw (C)--(D); + +\draw (A)--(D); + +\uncover<2>{ +\draw[line width=2pt,join=round] + (A)--(D)--(C)--(F)--(G)--(B)--(H)--(K)--(L)--(M); +} + +\uncover<3>{ +\draw[line width=2pt,join=round] + (M)--(D)--(A)--(C)--(G)--(B)--(H)--(L)--(K)--(F); +} + +\uncover<4->{ +\draw[line width=2pt] (M)--(K)--(L)--(H)--(F)--(D); +\draw[line width=2pt] (F)--(G)--(C)--(A); +\draw[line width=2pt] (G)--(B); +} + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +Wieviele Spannbäume gibt es? +\end{block} +\end{column} + +\begin{column}{0.56\hsize} +\uncover<5->{% +\begin{block}{Laplace-Matrix} +\vspace{-15pt} +\[ +L= +\tiny +\begin{pmatrix} + 3&-1&-1&-1& 0& 0& 0& 0& 0& 0\\ +-1& 4&-1& 0& 0&-1&-1& 0& 0& 0\\ +-1&-1& 5&-1&-1&-1& 0& 0& 0& 0\\ +-1& 0&-1& 4&-1& 0& 0& 0& 0&-1\\ + 0& 0&-1&-1& 6&-1&-1&-1& 0&-1\\ + 0&-1&-1& 0&-1& 4&-1& 0& 0& 0\\ + 0&-1& 0& 0&-1&-1& 5&-1&-1& 0\\ + 0& 0& 0& 0&-1& 0&-1& 4&-1&-1\\ + 0& 0& 0& 0& 0& 0&-1&-1& 3&-1\\ + 0& 0& 0&-1&-1& 0& 0&-1&-1& 4\\ +\end{pmatrix} +\] +\end{block}} +\vspace{-15pt} +\uncover<6->{% +\begin{block}{Satz von Kirchhoff} +Die Anzahl der Spannbäume eines Netzwerkes ist ein Kofaktor +des Laplaceoperators +\vspace{-5pt} +\[ +\det L_{ij} = +\left| +L\text{ ohne }\left\{\begin{array}{c}\text{Zeile $i$}\\\text{Spalte $j$}\end{array}\right. +\right| +\] +\end{block}} +\vspace{-12pt} +\uncover<7->{% +{\usebeamercolor[fg]{title}Beispiel:} 41524 +} + +\end{column} + +\end{columns} + +\end{frame} diff --git a/vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg b/vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg new file mode 100644 index 0000000..1c513da Binary files /dev/null and b/vorlesungen/slides/8/tokyo/shinjuku-subway-map.jpg differ diff --git a/vorlesungen/slides/8/tokyo/tokyosubway.pdf b/vorlesungen/slides/8/tokyo/tokyosubway.pdf new file mode 100644 index 0000000..6b84a8d Binary files /dev/null and b/vorlesungen/slides/8/tokyo/tokyosubway.pdf differ diff --git a/vorlesungen/slides/8/tokyo/transportnetworkgraph.png b/vorlesungen/slides/8/tokyo/transportnetworkgraph.png new file mode 100644 index 0000000..4a11183 Binary files /dev/null and b/vorlesungen/slides/8/tokyo/transportnetworkgraph.png differ -- cgit v1.2.1