aboutsummaryrefslogtreecommitdiffstats
path: root/vorlesungen/slides
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--vorlesungen/slides/8/Makefile.inc11
-rw-r--r--vorlesungen/slides/8/chapter.tex12
-rw-r--r--vorlesungen/slides/8/inzidenz.tex27
-rw-r--r--vorlesungen/slides/8/inzidenzd.tex25
-rw-r--r--vorlesungen/slides/8/markov/google.tex123
-rw-r--r--vorlesungen/slides/8/markov/irreduzibel.tex136
-rw-r--r--vorlesungen/slides/8/markov/markov.tex111
-rw-r--r--vorlesungen/slides/8/markov/pf.tex53
-rw-r--r--vorlesungen/slides/8/markov/stationaer.tex57
-rw-r--r--vorlesungen/slides/8/tokyo/bahn0.tex11
-rw-r--r--vorlesungen/slides/8/tokyo/bahn1.tex28
-rw-r--r--vorlesungen/slides/8/tokyo/bahn2.tex12
-rw-r--r--vorlesungen/slides/8/tokyo/google.tex11
-rw-r--r--vorlesungen/slides/test.tex24
14 files changed, 628 insertions, 13 deletions
diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc
index 0a20f88..cc2c497 100644
--- a/vorlesungen/slides/8/Makefile.inc
+++ b/vorlesungen/slides/8/Makefile.inc
@@ -12,6 +12,8 @@ chapter8 = \
../slides/8/inzidenzd.tex \
../slides/8/diffusion.tex \
../slides/8/laplace.tex \
+ ../slides/8/fourier.tex \
+ ../slides/8/spanningtree.tex \
../slides/8/pfade/adjazenz.tex \
../slides/8/pfade/langepfade.tex \
../slides/8/pfade/beispiel.tex \
@@ -21,5 +23,14 @@ chapter8 = \
../slides/8/floyd-warshall/iteration.tex \
../slides/8/floyd-warshall/wegiteration.tex \
../slides/8/floyd-warshall/wege.tex \
+ ../slides/8/tokyo/google.tex \
+ ../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 bd1c18f..b29145f 100644
--- a/vorlesungen/slides/8/chapter.tex
+++ b/vorlesungen/slides/8/chapter.tex
@@ -10,6 +10,8 @@
\folie{8/inzidenzd.tex}
\folie{8/diffusion.tex}
\folie{8/laplace.tex}
+\folie{8/fourier.tex}
+\folie{8/spanningtree.tex}
\folie{8/pfade/adjazenz.tex}
\folie{8/pfade/langepfade.tex}
@@ -22,7 +24,15 @@
\folie{8/floyd-warshall/wegiteration.tex}
\folie{8/floyd-warshall/wege.tex}
+\folie{8/tokyo/google.tex}
+\folie{8/tokyo/bahn0.tex}
+\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/inzidenz.tex b/vorlesungen/slides/8/inzidenz.tex
index 5911593..87578df 100644
--- a/vorlesungen/slides/8/inzidenz.tex
+++ b/vorlesungen/slides/8/inzidenz.tex
@@ -23,7 +23,9 @@
\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C);
\draw[color=white,line width=5pt] (B) -- (D);
-\draw[color=darkgreen,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D);
+{\color<2->{darkgreen}
+\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D);
+}
\draw[shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B);
\draw[shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C);
@@ -31,7 +33,12 @@
%\draw[shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E);
\draw[shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A);
+\only<-2>{
+\fill[color=white] (B) circle[radius=0.2];
+}
+\only<3->{
\fill[color=red!20] (B) circle[radius=0.2];
+}
\draw (A) circle[radius=0.2];
\draw (B) circle[radius=0.2];
@@ -51,18 +58,21 @@
\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 3$};
\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 4$};
\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 5$};
-\node[color=darkgreen] at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 6$};
+{\color<2->{darkgreen}
+\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 6$};
+}
\end{tikzpicture}
\end{center}
\vspace{-10pt}
+\uncover<5->{%
\begin{block}{Definition}
\vspace{-15pt}
\begin{align*}
B(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante $j$ endet in Knoten $i$}\\
A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$}
\end{align*}
-\end{block}
+\end{block}}
\end{column}
\begin{column}{0.48\textwidth}
\begin{center}
@@ -73,8 +83,12 @@ A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$}
\begin{scope}
+\uncover<3->{
\fill[color=red!20] (1.8,1.8) rectangle (4.75,2.15);
+}
+\uncover<2->{
\fill[color=darkgreen!40,opacity=0.5] (4.46,0.36) rectangle (4.79,2.65);
+}
\foreach \y in {1,...,5}{
\node[color=gray] at (5.3,{2.45-(\y-1)*\dy}) {\tiny $\y$};
}
@@ -87,9 +101,12 @@ A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$}
\node[color=gray] at (5.3,{2.45-2*\dy}) [above,rotate=-90] {\tiny Knoten};
\end{scope}
+\uncover<4->{
\begin{scope}
+\uncover<3->{
\fill[color=red!20] (1.8,-1.16) rectangle (4.25,-0.77);
\fill[color=red!20] (2.3,-2.6) rectangle (2.63,-0.29);
+}
\foreach \y in {1,...,5}{
\node[color=gray] at (4.7,{-0.5-(\y-1)*\dy}) {\tiny $\y$};
\node[color=gray] at ({1.92+(\y-1)*\dx},-0.1) {\tiny $\y$};
@@ -99,6 +116,7 @@ A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$}
\node[color=gray] at ({1.92+2*\dx},0.1) {\tiny Knoten};
\node[color=gray] at (4.7,{-0.5-2*\dy}) [above,rotate=-90] {\tiny Knoten};
\end{scope}
+}
\node (0,0) [right] {$\displaystyle
\begin{aligned}
@@ -112,6 +130,7 @@ B(G)
0&0&0&1&0&1
\end{pmatrix}
\\[12pt]
+\uncover<4->{
A(G)
&=
\begin{pmatrix}
@@ -121,7 +140,7 @@ A(G)
0&1&1&0&0\\
1&0&0&0&0
\end{pmatrix}
-\end{aligned}$};
+\end{aligned}}$};
\end{tikzpicture}
\end{center}
diff --git a/vorlesungen/slides/8/inzidenzd.tex b/vorlesungen/slides/8/inzidenzd.tex
index 18feeae..5f2f51a 100644
--- a/vorlesungen/slides/8/inzidenzd.tex
+++ b/vorlesungen/slides/8/inzidenzd.tex
@@ -23,7 +23,9 @@
\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C);
\draw[color=white,line width=5pt] (B) -- (D);
-\draw[->,shorten >= 0.2cm,shorten <= 0.2cm,color=darkgreen] (B) -- (D);
+{\color<2->{darkgreen}
+\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (D);
+}
\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B);
\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C);
@@ -32,7 +34,12 @@
\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A);
\draw (A) circle[radius=0.2];
+\only<-2>{
+\fill[color=white] (B) circle[radius=0.2];
+}
+\only<3->{
\fill[color=red!20] (B) circle[radius=0.2];
+}
\draw (B) circle[radius=0.2];
\draw (C) circle[radius=0.2];
\draw (D) circle[radius=0.2];
@@ -51,11 +58,14 @@
\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 4$};
\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 5$};
\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 6$};
-\node[color=darkgreen] at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$};
+{\color<2->{darkgreen}
+\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 7$};
+}
\end{tikzpicture}
\end{center}
\vspace{-15pt}
+\uncover<5->{%
\begin{block}{Definition}
\vspace{-20pt}
\begin{align*}
@@ -63,7 +73,7 @@ B(G)_{ij}&=-1&&\Leftrightarrow&&\text{Kante $j$ von $i$}\\
B(G)_{kj}&=+1&&\Leftrightarrow&&\text{Kante $j$ nach $k$}\\
A(G)_{ij}&=\phantom{-}1&&\Leftrightarrow&&\text{Kante von $i$ nach $j$}
\end{align*}
-\end{block}
+\end{block}}
\end{column}
\begin{column}{0.58\textwidth}
\begin{center}
@@ -73,14 +83,18 @@ A(G)_{ij}&=\phantom{-}1&&\Leftrightarrow&&\text{Kante von $i$ nach $j$}
\def\dy{0.48}
\begin{scope}[xshift=4cm,yshift=3cm]
+\uncover<3->{
\fill[color=red!20]
({-0.67-(7-1)*\dx-0.4},{-0.38-(2-1)*\dy-0.2})
rectangle
({-0.67-(7-7)*\dx+0.2},{-0.38-(2-1)*\dy+0.16});
+}
+\uncover<2->{
\fill[color=darkgreen!40,opacity=0.5]
({-0.67-(7-7)*\dx-0.4},{-0.38-(5-1)*\dy-0.2})
rectangle
({-0.67-(7-7)*\dx+0.2},{-0.38-(1-1)*\dy+0.16});
+}
%\draw (0,0) circle[radius=0.05];
\foreach \x in {1,...,7}{
\node[color=gray] at ({-0.67-(7-\x)*\dx},0.0) {\tiny $\x$};
@@ -95,6 +109,7 @@ rectangle
[above,rotate=-90] {\tiny Knoten};
\end{scope}
+\uncover<4->{
\begin{scope}[xshift=2.32cm,yshift=-0.24cm]
%\draw (0,0) circle[radius=0.05];
\fill[color=red!20]
@@ -117,6 +132,7 @@ rectangle
\node[color=gray] at ({0.00},{-0.38-(3-1)*\dy})
[above,rotate=-90] {\tiny Knoten};
\end{scope}
+}
\node at (0,0) {$\displaystyle
\begin{aligned}
@@ -130,6 +146,7 @@ B(G)
0& 0& 0&+1&-1& 0& 0
\end{pmatrix*}
\\[20pt]
+\uncover<4->{
A(G)
&=
\begin{pmatrix*}[r]
@@ -138,7 +155,7 @@ A(G)
\phantom{-}1&\phantom{-}1& 0&\phantom{-}1& 0\\
0&\phantom{-}1&\phantom{-}1& 0&\phantom{-}1\\
\phantom{-}1& 0& 0&\phantom{-}1& 0
-\end{pmatrix*}
+\end{pmatrix*}}
\end{aligned}$};
\end{tikzpicture}
\end{center}
diff --git a/vorlesungen/slides/8/markov/google.tex b/vorlesungen/slides/8/markov/google.tex
new file mode 100644
index 0000000..d1ec31d
--- /dev/null
+++ b/vorlesungen/slides/8/markov/google.tex
@@ -0,0 +1,123 @@
+%
+% 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
new file mode 100644
index 0000000..87e90e4
--- /dev/null
+++ b/vorlesungen/slides/8/markov/irreduzibel.tex
@@ -0,0 +1,136 @@
+%
+% 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
new file mode 100644
index 0000000..e92ff0f
--- /dev/null
+++ b/vorlesungen/slides/8/markov/markov.tex
@@ -0,0 +1,111 @@
+%
+% 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
new file mode 100644
index 0000000..da2ef2b
--- /dev/null
+++ b/vorlesungen/slides/8/markov/pf.tex
@@ -0,0 +1,53 @@
+%
+% 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
new file mode 100644
index 0000000..92fab16
--- /dev/null
+++ b/vorlesungen/slides/8/markov/stationaer.tex
@@ -0,0 +1,57 @@
+%
+% 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/tokyo/bahn0.tex b/vorlesungen/slides/8/tokyo/bahn0.tex
new file mode 100644
index 0000000..9c39712
--- /dev/null
+++ b/vorlesungen/slides/8/tokyo/bahn0.tex
@@ -0,0 +1,11 @@
+%
+% bahn.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\begin{frame}
+\begin{center}
+\includegraphics[width=\hsize]{../slides/8/tokyo/tokyosubway.pdf}
+\end{center}
+\end{frame}
+
diff --git a/vorlesungen/slides/8/tokyo/bahn1.tex b/vorlesungen/slides/8/tokyo/bahn1.tex
new file mode 100644
index 0000000..6ac3344
--- /dev/null
+++ b/vorlesungen/slides/8/tokyo/bahn1.tex
@@ -0,0 +1,28 @@
+%
+% bahn.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+
+\begin{frame}
+\frametitle{Tokyo Bahn-Netz}
+\begin{center}
+\begin{tabular}{rl}
+882&Bahnstationen\\
+108&Bahnlinien\\
+29&Bahngesellschaften\\
+20\,000\,000&Passagiere täglich\\
+7\,000\,000&Passagiere alleine in Shinjuku\\
+\end{tabular}
+\end{center}
+\uncover<2->{
+\begin{block}{Dirichlet-Zerlegung und Bahnhöfe}
+\begin{center}
+\uncover<3->{Passagiere wählen den nächsten Bahnhöfe}\\
+\uncover<4->{$\Downarrow$}\\
+\uncover<5->{Bahnhöfe definieren eine Dirichletzerlegung der Stadt}
+\end{center}
+\end{block}
+}
+\end{frame}
+
diff --git a/vorlesungen/slides/8/tokyo/bahn2.tex b/vorlesungen/slides/8/tokyo/bahn2.tex
new file mode 100644
index 0000000..4adc1bf
--- /dev/null
+++ b/vorlesungen/slides/8/tokyo/bahn2.tex
@@ -0,0 +1,12 @@
+%
+% bahn.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+
+\begin{frame}
+\begin{center}
+\includegraphics[width=\hsize]{../slides/8/tokyo/shinjuku-subway-map.jpg}
+\end{center}
+\end{frame}
+
diff --git a/vorlesungen/slides/8/tokyo/google.tex b/vorlesungen/slides/8/tokyo/google.tex
new file mode 100644
index 0000000..d37c98d
--- /dev/null
+++ b/vorlesungen/slides/8/tokyo/google.tex
@@ -0,0 +1,11 @@
+%
+% google.tex
+%
+% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\begin{frame}
+\begin{center}
+\includegraphics[width=\hsize]{../slides/8/tokyo/transportnetworkgraph.png}
+\end{center}
+\end{frame}
+
diff --git a/vorlesungen/slides/test.tex b/vorlesungen/slides/test.tex
index ca85ddd..6c5d5ff 100644
--- a/vorlesungen/slides/test.tex
+++ b/vorlesungen/slides/test.tex
@@ -7,10 +7,15 @@
%\folie{8/graph.tex}
%\folie{8/grad.tex}
\folie{8/inzidenz.tex}
-%\folie{8/inzidenzd.tex}
-% XXX Diffusion
-\folie{8/diffusion.tex}
-\folie{8/laplace.tex}
+\folie{8/inzidenzd.tex}
+%\folie{8/diffusion.tex}
+%\folie{8/laplace.tex}
+%\folie{8/fourier.tex}
+%\folie{8/spanningtree.tex}
+
+% XXX \folie{8/schwingungen.tex}
+% XXX \folie{8/eigenvektorbasis.tex}
+% XXX \folie{8/spektralegraphentheorie.tex}
%\folie{8/pfade/adjazenz.tex}
%\folie{8/pfade/langepfade.tex}
@@ -27,3 +32,14 @@
% - Google-Matrix
% - Stationär
+%\folie{8/tokyo/google.tex}
+%\folie{8/tokyo/bahn0.tex}
+%\folie{8/tokyo/bahn1.tex}
+%\folie{8/tokyo/bahn2.tex}
+
+
+%\folie{8/markov/google.tex}
+%\folie{8/markov/markov.tex}
+%\folie{8/markov/irreduzibel.tex}
+%\folie{8/markov/stationaer.tex}
+%\folie{8/markov/pf.tex}