From b1a909384ea96997c563d43e461cb514212f57e6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Wed, 15 Sep 2021 18:45:28 +0200 Subject: improve images --- .../chapters/10-vektorenmatrizen/skalarprodukt.tex | 4 - buch/chapters/70-graphen/beschreibung.tex | 5 +- buch/chapters/70-graphen/wavelets.tex | 1 - buch/chapters/80-wahrscheinlichkeit/Makefile.inc | 1 + buch/chapters/80-wahrscheinlichkeit/chapter.tex | 8 + buch/chapters/80-wahrscheinlichkeit/markov.tex | 312 +++++++------ buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 2 +- buch/chapters/90-crypto/arith.tex | 1 - buch/chapters/90-crypto/ff.tex | 495 --------------------- buch/chapters/95-homologie/basiswahl.tex | 2 +- buch/chapters/95-homologie/chapter.tex | 3 +- buch/chapters/95-homologie/fixpunkte.tex | 2 +- .../chapters/95-homologie/images/approximation.pdf | Bin 32134 -> 46877 bytes .../chapters/95-homologie/images/approximation.tex | 2 +- buch/chapters/95-homologie/images/complexbasis.pdf | Bin 27033 -> 27139 bytes buch/chapters/95-homologie/images/complexbasis.tex | 14 +- buch/chapters/95-homologie/komplex.tex | 9 +- buch/chapters/95-homologie/simplex.tex | 295 +++++++----- buch/chapters/references.bib | 7 + 19 files changed, 412 insertions(+), 751 deletions(-) (limited to 'buch/chapters') diff --git a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex index f89da33..c1a873d 100644 --- a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex +++ b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex @@ -28,7 +28,6 @@ Man kann dies interpretieren als Linearität der Abbildungen $x\mapsto x\cdot y$ und $y\mapsto x\cdot y$. Dies wird Bilinearität genannt und wie folgt definiert. -% XXX Bilinearität \begin{definition} Seien $U,V,W$ $\Bbbk$-Vektorräume. Eine Abbildung $f\colon U\times V\to W$ heisst {\em bilinear}, @@ -109,7 +108,6 @@ $\|x\|_2^2 = \langle x,x\rangle$. \end{definition} \subsubsection{Dreiecksungleichung} -% XXX Dreiecksungleichung Damit man sinnvoll über Abstände sprechen kann, muss die Norm $\|\mathstrut\cdot\mathstrut\|_2$ der geometrischen Intuition folgen, die durch @@ -227,7 +225,6 @@ genau dann ein, wenn die beiden Vektoren linear abhängig sind. \end{proof} \subsubsection{Polarformel} -% XXX Polarformel Auf den ersten Blick scheint die Norm $\|x\|_2$ weniger Information zu beinhalten, als die symmetrische Bilinearform, aus der sie hervorgegangen ist. @@ -274,7 +271,6 @@ bewiesen. \end{proof} \subsubsection{Komplexe Vektorräume und Sesquilinearformen} -% XXX Sesquilinearform Eine Bilinearform auf einem komplexen Vektorraum führt nicht auf eine Grösse, die sich als Norm eignet. Selbst wenn $\langle x,x\rangle >0$ ist, diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index af934e4..845e640 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -199,8 +199,6 @@ Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung von Knoten $j$ zu Knoten $i$ gibt. -% XXX Abbildung Graph und Verbindungs-Matrix - \subsubsection{Adjazenzmatrix und die Anzahl der Pfade} Die Beschreibung des Graphen mit der Adjazenzmatrix $A=A(G)$ nach \eqref{buch:graphen:eqn:adjazenzmatrix} ermöglicht bereits, eine @@ -356,7 +354,8 @@ von Pfaden durch Ausnützung der Symmetrien des Graphen leichter direkt gefunden werden. -\subsection{Inzidenzmatrix} +\subsection{Inzidenzmatrix +\label{buch:graphen:subsection:inzidenzmatrix}} Die Adjazenzmatrix kann zusätzliche Information, die möglicherweise mit den Kanten verbunden ist, nicht mehr darstellen. Dies tritt zum Beispiel in der Informatik bei der Beschreibung diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index b982bce..073deab 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -51,7 +51,6 @@ kann man die allgemeine Lösung aus Fundamentallösungen zusammensetzen. Die Fundamentallösungen $f(x-\xi,t)$ sind für kleine Zeiten immer noch deutlich in einer Umgebung von $\xi$ konzentriert. -% XXX Ausbreitung der Fundamentallösung illustrieren \begin{figure} \centering \includegraphics{chapters/70-graphen/images/fundamental.pdf} diff --git a/buch/chapters/80-wahrscheinlichkeit/Makefile.inc b/buch/chapters/80-wahrscheinlichkeit/Makefile.inc index 6fd104c..8eed351 100644 --- a/buch/chapters/80-wahrscheinlichkeit/Makefile.inc +++ b/buch/chapters/80-wahrscheinlichkeit/Makefile.inc @@ -9,4 +9,5 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/80-wahrscheinlichkeit/markov.tex \ chapters/80-wahrscheinlichkeit/positiv.tex \ chapters/80-wahrscheinlichkeit/parrondo.tex \ + chapters/80-wahrscheinlichkeit/uebungsaufgaben/8001.tex \ chapters/80-wahrscheinlichkeit/chapter.tex diff --git a/buch/chapters/80-wahrscheinlichkeit/chapter.tex b/buch/chapters/80-wahrscheinlichkeit/chapter.tex index 270c44a..826e022 100644 --- a/buch/chapters/80-wahrscheinlichkeit/chapter.tex +++ b/buch/chapters/80-wahrscheinlichkeit/chapter.tex @@ -39,3 +39,11 @@ dargestellt. \input{chapters/80-wahrscheinlichkeit/markov.tex} \input{chapters/80-wahrscheinlichkeit/positiv.tex} \input{chapters/80-wahrscheinlichkeit/parrondo.tex} + +\section*{Übungsaufgaben} +\rhead{Übungsaufgaben} +\aufgabetoplevel{chapters/80-wahrscheinlichkeit/uebungsaufgaben} +\begin{uebungsaufgaben} +\uebungsaufgabe{8001} +\end{uebungsaufgaben} + diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 1e30010..6dad883 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -17,7 +17,6 @@ werden. % Beschreibung der Markov-Eigenschaft % \subsection{Markov-Eigenschaft} -% XXX Notation, Zustände, Übergangswahrscheinlichkeit Ein stochastischer Prozess ist eine Familie von Zufallsvariablen \index{stochastischer Prozess}% \index{Prozess, stochastisch}% @@ -61,7 +60,6 @@ Zustand $x$ erreicht, wenn er zu den Zeitpunkten $t_0,t_1,\dots,t_n$ die Zustände $x_0,x_1,\dots,x_n$ durchlaufen hat. \subsubsection{Gedächtnislosigkeit} -% XXX Gedächtnislösigkeit, Markov-Eigenschaft \index{Markov-Eigenschaft}% In vielen Fällen ist nur der letzte durchlaufene Zustand wichtig. Die Zustände in den Zeitpunkten $t_0<\dots,shorten >= 0.5cm,shorten <= 0.5cm] (0,{-\s-0.25}) -- (-3.5,{-\s-0.25}); \node[color=darkgreen] at ({0},{(9*2-1)*\s}) {$B_{k-2\mathstrut}$}; \node at (1.75,{9*2*\s}) {$\Delta_{k-1}$}; - \node at (1.75,{-\s}) [above] {$\partial_{k-1\mathstrut}$}; + \node at (1.75,{-\s-0.25}) [above] {$\partial_{k-1\mathstrut}$}; \draw[decorate,decoration={brace,amplitude=4pt}] ({-\s-0.1},{-\s}) -- ({-\s-0.1},{(2*10+1)*\s}); \node at ({-\s-0.17},{10*\s}) [left] {$Z_{k-2\mathstrut}$}; @@ -103,9 +104,10 @@ \rechteck{0}{2}{red} \Rechteck{0}{11} \node at (0,{-\s}) [below] {$C_{k-1\mathstrut}$}; + \draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (0,{-\s-0.25}) -- (-3.5,{-\s-0.25}); \node[color=darkgreen] at ({0},{(5*2-1)*\s}) {$B_{k-1\mathstrut}$}; \node at (1.75,{6.5*2*\s}) {$\Delta_k$}; - \node at (1.75,{-\s}) [above] {$\partial_{k\mathstrut}$}; + \node at (1.75,{-\s-0.25}) [above] {$\partial_{k\mathstrut}$}; \draw[decorate,decoration={brace,amplitude=4pt}] ({-\s-0.1},{-\s}) -- ({-\s-0.1},{(2*7+1)*\s}); \node at ({-\s-0.17},{7*\s}) [left] {$Z_{k-1\mathstrut}$}; @@ -118,6 +120,7 @@ \rechteck{0}{3}{red} \Rechteck{0}{10} \node at (0,{-\s}) [below] {$C_{k\mathstrut}$}; + \draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (0,{-\s-0.25}) -- (-3.5,{-\s-0.25}); \node[color=darkgreen] at ({-0.25},{9*\s}) {$B_{k\mathstrut}$}; \node[color=darkgreen] at (0.24,{2*4*\s}) {$b_1$}; @@ -133,7 +136,7 @@ \node[color=blue] at (0.24,{2*9*\s}) {$\vdots$}; \node[color=blue] at (0.24,{2*10*\s}) {$c_s$}; \node at (1.75,{5.5*2*\s}) {$\Delta_{k+1}$}; - \node at (1.75,{-\s}) [above] {$\partial_{k+1\mathstrut}$}; + \node at (1.75,{-\s-0.25}) [above] {$\partial_{k+1\mathstrut}$}; \draw[decorate,decoration={brace,amplitude=4pt}] ({-\s-0.1},{-\s}) -- ({-\s-0.1},{(2*5+1)*\s}); \node at ({-\s-0.17},{5*\s}) [left] {$Z_{k\mathstrut}$}; @@ -146,6 +149,7 @@ \rechteck{0}{0}{red} \Rechteck{0}{7} \node at (0,{-\s}) [below] {$C_{k+1\mathstrut}$}; + \draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (0,{-\s-0.25}) -- (-3.5,{-\s-0.25}); \node[color=darkgreen] at ({0},{(2.0*2+1)*\s}) {$B_{k+1\mathstrut}$}; \draw[decorate,decoration={brace,amplitude=4pt}] @@ -153,6 +157,10 @@ \node at ({-\s-0.17},{5*\s}) [left] {$Z_{k+1\mathstrut}$}; \end{scope} +\begin{scope}[xshift=10.5cm] + \draw[->,shorten >= 0.5cm,shorten <= 0.5cm] (0,{-\s-0.25}) -- (-3.5,{-\s-0.25}); +\end{scope} + \end{tikzpicture} \end{document} diff --git a/buch/chapters/95-homologie/komplex.tex b/buch/chapters/95-homologie/komplex.tex index 9787bb2..bc4fcf3 100644 --- a/buch/chapters/95-homologie/komplex.tex +++ b/buch/chapters/95-homologie/komplex.tex @@ -30,11 +30,14 @@ heisst ein Kettenkomplex, wenn $\partial_{k-1}\partial_k=0$ gilt für alle $k>0$. \end{definition} -Die aus den Triangulationen konstruieren Vektorräme von +Die aus den Triangulationen konstruierten Vektorräume von Abschnitt~\ref{buch:subsection:triangulation} bilden einen Kettenkomplex. - -XXX nachrechnen: $\partial^2 = 0$ ? +Dazu ist nur nachzurechnen, dass die Zusammensetzung der +Randoperatoren verschwindet. +Wegen der Linearität genügt es, dies für ein einzelnes Simplex zu tun. +Das haben wir aber bereits in Satz~\ref{buch:homologie:satz:randrand} +gemacht. \subsection{Abbildungen \label{buch:subsection:abbildungen}} diff --git a/buch/chapters/95-homologie/simplex.tex b/buch/chapters/95-homologie/simplex.tex index 3bf1004..65ab441 100644 --- a/buch/chapters/95-homologie/simplex.tex +++ b/buch/chapters/95-homologie/simplex.tex @@ -12,10 +12,10 @@ die sogenannten Simplizes entwickeln müssen. \subsection{Simplizes und Rand \label{buch:subsection:simplices}} - -\subsubsection{Rand eines Dreiecks} Die Inzidenz-Matrix eines Graphen hat einer Kante die beiden Endpunkte mit verschiedenen Vorzeichen zugeordnet. + +\subsubsection{Rand eines Dreiecks} Dieses Idee soll jetzt verallgemeinert werden. Der Rand des Dreiecks $\triangle$ in Abbildung~\ref{buch:homologie:figure:zusammenziehbar} @@ -47,7 +47,7 @@ Wir können diese Zuordnung wieder mit einer Matrix ausdrücken. \end{pmatrix*} \] -\subsubsection{Simplizes} +\subsubsection{Standardsimplizes} Punkte, Kanten und Dreiecke sind die einfachsten Fälle sogenannter Simplizes. Wir formulieren die Definition dieser Objekte auf eine Weise, @@ -88,16 +88,29 @@ Anfangspunkt $s_1(0)$ mit einem negativen Vorzeichen versehen wird. Für höhere Dimensionen brauchen wir auf analoge Weise erst wieder einen geeigneten Parameterraum. Die Menge -\[ +\begin{equation} \triangle_n = -\{(t_0,\dots,t_n)\in\mathbb{R}^{n+1}\,|\, t_i\ge 0,t_0+t_1+\dots+t_n=1\} -\] +\{(t_0,\dots,t_n)\in\mathbb{R}^{n+1}\mid t_i\ge 0,t_0+t_1+\dots+t_n=1\} +\subset\mathbb{R}^{n+1} +\label{buch:homologie:eqn:standardsimplex} +\end{equation} beschreibt zum Beispiel für $n=2$ ein Dreieck und für $n=3$ ein Tetraeder. +\index{Tetraeder}% + +\begin{definition} +Die Menge $\triangle_n$ von \eqref{buch:homologie:eqn:standardsimplex} +heisst das $n$-dimensionale Standardsimplex. +\index{Standardsimplex}% +\end{definition} + +Die Standardbasisvektoren von $\mathbb{R}^{n+1}$ werden $e_0,\dots,e_n$ +bezeichnet und sind die Ecken des $n$-dimensionalen Standardsimplex. +\subsubsection{Simplizes in $\mathbb{R}^N$} Gegeben $n+1$-Punkte $P_0,\dots,P_n$ mit Ortsvektoren -$\vec{p}_0,\dots,\vec{p}_n$ können wir eine Abbildung +$\vec{p}_0,\dots,\vec{p}_n\in\mathbb{R}^N$, können wir eine Abbildung \begin{equation} s_n \colon @@ -116,121 +129,203 @@ t_1\vec{p}_1 t_n\vec{p}_n \end{equation} Eine solche Abbildung verallgemeinert also den Begriff einer Strecke +in einem Raum $\mathbb{R}^N$ auf höhere Dimensionen. +Sie ist durch die Eckpunkte vollständig vorgegeben, es reicht also +die Punkte $P_0,\dots,P_n\in\mathbb{R}^N$ zu kennen. + +%\begin{definition} +%\label{buch:def:simplex} +%Ein $n$-dimensionales {\em Simplex} oder {\em $n$-Simplex} in $X$ ist eine +%stetige Abbildung $s_n\colon\triangle_n\to X$. +%\end{definition} +% +%Die Ecken des $n$-Simplex $\triangle_n$ sind die Standardbasisvektoren +%in $\mathbb{R}^{n+1}$. +%Mit $e_k$ bezeichnen wird die Ecke, deren Koordinaten $t_i=0$ sind für +%$k\ne i$, ausser der Koordinaten $t_k$, die den Wert $t_k=1$ hat. + \begin{definition} -\label{buch:def:simplex} -Ein $n$-dimensionales {\em Simplex} oder {\em $n$-Simplex} ist eine -stetige Abbildung $s_n\colon\triangle_n\to X$. +Ein $n$-Simplex in $\mathbb{R}^N$ ist die stückweise lineare Abbildung +$s\colon \triangle_n\to \mathbb{R}^N$ gegeben durch die Bilder der Eckpunkte +$P_i = s(e_i)$. +Wir schreiben auch $[P_0,P_1,\dots,P_n]$ für dieses Simplex. \end{definition} -Die Ecken des $n$-Simplex $\triangle_n$ sind die Standardbasisvektoren -in $\mathbb{R}^{n+1}$. -Mit $e_k$ bezeichnen wird die Ecke, deren Koordinaten $t_i=0$ sind für -$k\ne i$, ausser der Koordinaten $t_k$, die den Wert $t_k=1$ hat. - \subsubsection{Rechnen mit Simplizes} -Damit wir leichter mit Simplizes rechnen können, betrachten wir +Wir möchten später ein geometrisches Objekt aus Simplizes zusammensetzen. +Dazu müssen wir mehrere Simplizes so ein einen Raum abbilden können, dass +sie an den Rändern zusammenpassen. +Dazu müssen wir mit ``Kombinationen'' von Simplizes rechnen können. +Wir betrachten daher jedes Simplex als einen Basisvektor eines abstrakten Vektorraumes. -Zu einem $n$-Simplex gehören Vektorräume $C_l$ für jede Dimension -$l=0$ bis $l=n$. -Der Vektorraum $C_0$ besteht aus Linearkombinationen -\[ -C_0 -= -\{ x_0 P_0 + \dots + x_n P_n \,| x_i\in\mathbb{R} \}, -\] -$C_0$ ist ein $n$-dimensionaler Raum. -Der Vektorraum $C_1$ besteht aus Linearkombinationen der Kanten -\[ -C_1 -= -\biggl\{ -\sum_{ii} (-1)^{j-1} +[P_0,\dots,\widehat{P_i},\dots,\widehat{P_j}\dots,P_l] +\biggr) +\label{buch:homologie:eqn:randrand} +\\ +&= +\sum_{ji} (-1)^{i+j} +[P_0,\dots,\widehat{P_i},\dots,\widehat{P_j}\dots,P_l] +\notag +\end{align} +Der Exponent $j-1$ im zweiten Term von +\eqref{buch:homologie:eqn:randrand} +trägt der Tatsache Rechnung, +dass der Index $i$ übersprungen worden ist. +In der zweiten Summe kann man die Summationsindizes umbenennen, +also $i$ durch $j$ ersetzen und umgekehrt, dann entsteht +\begin{align*} +\partial_{l-1}\partial_l[P_0,\dots,P_l] +&= +\sum_{jj} (-1)^{j+i} +[P_0,\dots,\widehat{P_j},\dots,\widehat{P_i}\dots,P_l] +\\ +&=0. +\qedhere +\end{align*} +\end{proof} + \subsection{Polyeder} \begin{figure} \centering @@ -253,8 +348,8 @@ Die Vereinigung ist aber nicht beliebig, vielmehr ist die Schnittmenge zweier beliebiger 1-Simplizes immer entweder leer, eine Menge mit nur einem Vertex oder ein ganzes 1-Simplex. -Dies reicht aber nicht, wie Abbildung~\ref{buch:homologie:polyeder} -zeigt. +Für höhere Dimensionen muss diese Idee ausgedehnt werden auf +höherdimensionale Simplizes. In einem Graphen dürfen sich Kanten nicht in einem inneren Punkt treffen, sondern nur in Endpunkten. Verallgemeinert auf höherdimensionale Simplizes kann man dies als die @@ -279,7 +374,7 @@ ist kein Polyeder, kann aber leicht zu einem Polyeder gemacht werden, indem man einzelne Kanten mit zusätzlichen Punkten unterteilt. Auch müssen die zweidimensionalen Simplizes aufgeteilt werden. -Die Abbildung~\ref{buch:homologie:figure:polyeder} zeigt auch, dass +Abbildung~\ref{buch:homologie:figure:polyeder} zeigt auch, dass die Darstellung einer Punktmenge als Polyeder nicht eindeutig ist. Man kann die Kanten und Flächen jederzeit weiter unterteilen, ohne dass sich die Gestalt der gesamten Menge dadurch ändert. @@ -287,7 +382,7 @@ dass sich die Gestalt der gesamten Menge dadurch ändert. \subsection{Triangulation \label{buch:subsection:triangulation}} Unser Ziel ist, geometrische Objekte besser verstehen zu können. -Dabei sind uns Deformationen ja sogar Knicke egal, es interessiert uns +Dabei sind uns Deformationen und sogar Knicke egal, es interessiert uns nur die ``Gestalt'' des Objekts. Entfernungen zwischen Punkten sind ebenfalls von untergeordneter Bedeutung, da sie bei Deformation nicht erhalten bleiben. diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index 979f985..ef25059 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -194,3 +194,10 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc number = {2}, pages = {192--210} } + +@online{skript:rudolph, + author = {Günter Rudolph}, + title = {The fundamental matrix of the general random walk with absorbing boundaries}, + year = 2001, + url = {https://eldorado.tu-dortmund.de/bitstream/2003/5380/1/ci75.pdf} +} -- cgit v1.2.1