diff options
Diffstat (limited to '')
19 files changed, 412 insertions, 751 deletions
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<t_{n-1}$ haben dann keinen @@ -110,7 +108,6 @@ p_{xy}(t,s) mit den Zuständen $x,y\in\mathcal{S}$ indiziert sind. \subsubsection{Die Chapman-Kolmogorov-Gleichung} -% XXX Chapman-Kolmogorov-Gleichung \index{Chapman-Kolmogorov-Gleichung}% Man beachte, dass in der Definition der Markov-Eigenschaft keine Voraussetzungen darüber gemacht werden, wie nahe @@ -158,7 +155,6 @@ Jeder Summand auf der rechten Seite beschreibt einen Weg des Prozesses derart, dass er zu den Zwischenzeitpunkten bestimmte Zwischenzustände durchläuft. -% XXX Pfadwahrscheinlichkeit \begin{definition} Die Wahrscheinlichkeit, dass der stochastische Prozess zwischen Zeitpunkten $t_0$ und $t_n$ die Zwischenzustände $x_i$ zu Zeiten $t_i$ durchläuft ist @@ -182,7 +178,6 @@ heisst die {\em Pfadwahrscheinlichkeit} für genannten Pfad. % Diskrete Markov-Kette % \subsection{Diskrete Markov-Kette} -% XXX Diskrete Zeit, Endliche Zustandsmenge Die Markov-Eigenschaft besagt, dass man keine Information verliert, wenn man die Vorgeschichte eines Zeitpunktes ignoriert. Insbesondere kann man eine Menge von geeigneten diskreten @@ -272,7 +267,6 @@ Eine Permutationsmatrix beschreibt einen stochastischen Prozess, dessen \end{beispiel} \subsubsection{Zustandswahrscheinlichkeiten} -% XXX Zustandswahrscheinlichkeit Die Wahrscheinlichkeit, mit der sich der Prozess zum Zeitpunkt $n$ im Zustand $i\in\mathcal{S}$ befindet, wird \[ @@ -298,7 +292,6 @@ Die Zeitentwicklung kann also durch Multiplikation mit der Übergangsmatrix berechnet werden. \subsubsection{Zeitunabhängige Übergangswahrscheinlichkeiten} -% XXX Übergangswahrscheinlichkeit \index{zeitunabhängige Übergangswahrscheinlichkeiten} Besonderes einfach wird die Situation, wenn die Übergangsmatrix $T(n+1,n)$ nicht von der Zeit abhängt. @@ -310,7 +303,6 @@ durch die Matrix-Potenzen $T(n+m,n)=T^m$. Im Folgenden gehen wir immer von einer homogenen Markov-Kette aus. \subsubsection{Stationäre Verteilung} -% XXX stationäre Verteilung Im Beispiel der Google-Matrix erwarten wir intuitiv, dass sich mit der Zeit eine Verteilung einstellt, die sich über die Zeit nicht mehr ändert. @@ -412,7 +404,6 @@ möglich. Eine eindeutige stationäre Verteilung können wir also nur erwarten, wenn alle Zustände miteinander kommunizieren. -% XXX irreduzible Markov-Ketten \begin{definition} Eine homogene Markov-Kette heisst {\em irreduzibel}, alle Zustände miteinander kommunizieren. @@ -543,12 +534,9 @@ Für zwei Punkte $x$ und $y$ bilden die konvexen Kombination $tx+(1-t)y$ für $t\in[0,1]$ die Verbindungsstrecke der beiden Vektoren. Eine Menge ist also konvex, wenn sie mit zwei Punkten immer auch -ihre Verbindungsstrecke enthält -% XXX Bild für Konvexe Menge +ihre Verbindungsstrecke enthält. +% XXX Bild für konvexe Mengen - - -% XXX Grenzverteilung \subsubsection{Grenzverteilung} Im Beispiel der Google-Matrix wurde ein iterativer Algorithmus zur Berechnung des Pagerank verwendet. @@ -609,7 +597,6 @@ gleich sind. \end{beispiel} \subsubsection{Erwartungswert und Varianz} -% XXX Erwartungswert und Varianz für eine Grenzverteilung Wenn sich im Laufe der Zeit eine Grenzverteilung einstellen soll, dann muss es auch möglich sein, Erwartungswert und Varianz dieser Verteilung zu berechnen. @@ -658,7 +645,6 @@ A^{\odot k} = A\odot A^{\odot (k-1)} definieren. \subsubsection{Erwartungswert von Werten auf Übergängen} -% XXX Erwartungswert für Zufallsvariablen, die von den Übergängen abhängen In Abschnitt~\ref{buch:section:paradoxon-von-parrondo} wird ein Spiel vorgestellt, in dem der Gewinn davon abhängt, welcher Übergang stattfindet, nicht welcher Zustand erreicht wird. @@ -709,10 +695,16 @@ Indem man $G$ durch $G^{\odot k}$ ersetzt, kann man beliebige höhere Momente berechnen. \subsection{Absorbierende Zustände} -In diesem Abschnitt gehen wir immer von einer irreduziblen Markov-Kette -aus. +In diesem Abschnitt gehen wir immer von einer irreduziblen, homogenen +Markov-Kette aus. +Ihre Übergangsmatrix enthält die Wahrscheinlichkeiten +\[ +T_{i\!j} += +P(X_{k+1}=i\mid X_{k}=j) +\] +für alle Zeiten $k$. -% XXX Definition Eine Grenzverteilung beschreibt die relative Häufigkeit, mit der der Prozess in den verschiedenen Zuständen vorbeikommt. In einem Spiel, in dem der Spieler ruiniert werden kann, gibt es @@ -758,7 +750,7 @@ ausgehend von einem transienten Zustand in einem bestimmten absorbierenden Zustand landet. Die Matrix $Q$ beschreibt die Übergänge, bevor dies passiert. Die Potenzen von $T$ sind -\[ +\begin{equation} T^2 = \left( @@ -790,7 +782,17 @@ I&\displaystyle R\sum_{l=0}^{k-1} Q^l \\ 0&Q^k \end{array} \right). +\label{buch:markov:eqn:Tpowers} +\end{equation} +Die Potenzen enthalten die Wahrscheinlichkeiten +\[ +(T^k)_{i\!j} += +P(X_k=i\mid X_0=j), \] +dass der Prozess ausgehend vom Zustand $j$ im Schritt $k$ im +Zustand $i$ ankommt. + Wegen der angenommenen Irreduzibilität wird man früher oder später in einem absorbierenden Zustand landet, daher muss $\lim_{k\to\infty} Q^k=0$ sein. @@ -801,137 +803,175 @@ Reihe summieren, man erhält die Matrix \] die für $k\to\infty$ gegen \[ -N +F = \lim_{k\to\infty} \sum_{l=0}^{k-1} Q^l = (I-Q)^{-1} \] konvergiert. -Die Matrix $N$ heisst die {\em Fundamentalmatrix} der absorbierenden +Die Matrix $F$ heisst die {\em Fundamentalmatrix} der absorbierenden Markov-Kette. \index{Fundamental-Matrix}% - -\subsubsection{Absorbtionszeit} -% XXX Absorptionszeit -Wie lange dauert es im Mittel, bis der Prozess in einem -Absorptionszustand $i$ stecken bleibt? -\index{Absorbtionszeit}% -Die Fundamentalmatrix $N$ der Markov-Kette beantwortet diese -Frage. -Wenn der Prozess genau im Schritt $k$ zum ersten Mal im Zustand $i$ -ankommt, dann ist $E(k)$ die mittlere Wartezeit. -Der Prozess verbringt also zunächst $k-1$ Schritte in transienten -Zuständen, bevor er in einen absorbierenden Zustand $i$ wechselt. - -Wir brauchen die Wahrscheinlichkeit für einen Entwicklung des Zustandes -ausgehend vom Zustand $j$, die nach $k-1$ Schritten im Zustand $l$ -landet, von wo er in den absorbierenden Zustand wechselt. -Diese Wahrscheinlichkeit ist -\[ -P(X_k = i\wedge X_{k-1} = l \wedge X_0=j) -= -\sum_{i_1,\dots,i_{k-2}} -r_{il} q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j} -\] -Von den Pfaden, die zur Zeit $k-1$ im Zustand $l$ ankommen gibt es -aber auch einige, die nicht absorbiert werden. -Für die Berechnung der Wartezeit möchten wir nur die Wahrscheinlichkeit -innerhalb der Menge der Pfade, die auch tatsächlich absorbiert werden, -das ist die bedingte Wahrscheinlichkeit -\begin{equation} -\begin{aligned} -P(X_k = i\wedge X_{k-1} = l \wedge X_0=j\mid X_k=i) -&= -\frac{ -P(X_k = i\wedge X_{k-1} = l \wedge X_0=j) -}{ -P(X_k=i) -} -\\ -&= -\sum_{i_1,\dots,i_{k-2}} -q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j}. -\end{aligned} -\label{buch:wahrscheinlichkeit:eqn:ankunftswahrscheinlichkeit} -\end{equation} -Auf der rechten Seite steht das Matrixelement $(l,j)$ von $Q^{k-1}$. - -% XXX Differenz - -Für die Berechnung der erwarteten Zeit ist müssen wir die -Wahrscheinlichkeit mit $k$ multiplizieren und summieren: -\begin{align} -E(k) +Sie gestattet, viele interessante Grössen des Markov-Prozesses zu +berechnen. + +\subsubsection{Erwartete Anzahl Besuche eines Zustandes} +Wie häufig wird ein Zustand $i$ ausgehend von einem Zustand $j$ +besucht? +\index{Anzahl Besuche}% +Dazu definieren wir die ``Besuchs''-Zufallsvariable +\[ +B_{k}=\begin{cases} +1&\qquad\text{$X_k=i$}\\ +0&\qquad\text{sonst,} +\end{cases} +\] +die genau dann $1$ ist, wenn der Prozess ausgehend von $j$ im Zustand +beim $k$-ten Schritt den Zustand $i$ besucht. +Die Zufallsvariable der Anzahl $B$ der Besuche des Zustands $i$ ist die +Summe der $B_k$. +Ein weiterer Nutzen dieser Definition ist, dass sich die Wahrscheinlichkeit +jetzt als Erwartungswert ausdrücken lässt, es ist +$P(X_k=i \mid X_0=j) = E(B_k)$. + +Damit lässt sich jetzt die Fundamentalmatrix auf andere Art interpretieren. +Der Eintrag $N_{i\!j}$ ist +\begin{align*} +F_{i\!j} &= -\sum_{k=0}^\infty -k( -q^{(k)}_{l\!j} -- -q^{(k-1)}_{l\!j} -) -\notag +\biggl(\sum_{k=0}^\infty Q^k\biggr)_{i\!j} \\ &= -\dots -+ -k( -q^{(k-1)}_{l\!j} -- -q^{(k)}_{l\!j} -) +P(X_0=i\mid X_0=j) + -(k+1)( -q^{(k)}_{l\!j} -- -q^{(k+1)}_{l\!j} -) +P(X_1=i\mid X_0=j) + -\dots -\label{buch:wahrscheinlichkeit:eqn:telescope} +P(X_2=i\mid X_0=j) ++\dots \\ -&= -\dots -+ -k -q^{(k-1)}_{l\!j} -\underbrace{ -\mathstrut -- -q^{(k)}_{l\!j} -+ -(k+1) -q^{(k)}_{l\!j} }_{\displaystyle q^{(k)}_{l\!j}} -\mathstrut -- -(k+1) -q^{(k+1)}_{l\!j} -+ -\dots +&=E(B_0) + E(B_1) + E(B_2) + \dots \\ -&= -\dots -+ -q^{(k)}_{l\!j} -+ -\dots +&=E(B_0+B_1+B_2+\dots) +=E(B). +\end{align*} +Die Summe der $B_k$ ist aber die erwartete Anzahl der Besuch im Zustand $i$. + +\begin{satz} +\label{buch:markov:satz:anzahlbesuche} +Die erwartete Anzahl Besuche des Zustands $i$ eines homogenen, +absorbierenden Markovprozesses ausgehend vom Zustand $j$ ist das +Element $F_{i\!j}$ der Fundamentalmatrix $F=(I-Q)^{-1}$. +\end{satz} + +\subsubsection{Absorptionszeit} +\index{Absorptionszeit}% +Wie lange dauert es im Mittel, bis der Prozess ausgehend vom Zustand $j$ +in einem Absorbptionszustand $i$ stecken bleibt? +Sie ist gleich gross wie die Zeit, während der der Prozess nicht absorbierende +Zustände besucht. +Die Zeit $t_j$, bis der Prozess in einen absorbierenden Zustand wechselt, ist also +die erwartete Anzahl Besuche nicht absorbierender Zustände. +Es folgt: +\[ +t_j += +\sum_{\text{$i$ nicht absorbierend}} E(\text{Anzahl Besuche von $i$}\mid X_0=j) += +\sum_{\text{$i$ nicht absorbierend}} F_{i\!j}. +\] +$t_j$ ist also die Summe der Elemente der Spalte $j$ der Fundamentalmatrix $F$. +Man kann diese Summe auch vektoriell schreiben mit einem Zeilenvektor $U^t$ +aus lauter Nullen. +Der Zeilenvektor $t$ mit Einträgen $t_j$ ist dann +\( +t = U^tF. +\) +\begin{satz} +\label{buch:markov:satz:absorptionszeit} +Die Absorptionszeit $t_j$ einer absorbierenden, homogenen Markov-Kette +ausgehend vom Zustand $j$ ist +das $j$-te Element des Zeilenvektors $U^tF$ oder die Summe der +Einträge in Spalte $j$ der Fundamentalmatrix $F$. +\end{satz} + +\subsubsection{Absorptionswahrscheinlichkeit} +\index{Absorptionswahrscheinlichkeit}% +Wie gross ist die Wahrscheinlichkeit, dass der Prozess ausgehend von +Zustand $j$ irgendwann im Zustand $i$ absorbiert wird? +Die Potenzen $T^k$ der Übergangsmatrix enthalten in Zeile $j$ +und Spalte $i$ die Wahrscheinlichkeit, dass nach spätestens $k$ Schritten +geschehen ist. +Wir müssen daher den Grenzwert +\( +\lim_{k\to\infty}T^k +\) +berechnen. +Da $\|Q\|<1$ folgt aus~\eqref{buch:markov:eqn:Tpowers} sofort +\[ +T^\infty += +\lim_{k\to\infty}T^k += +\left( +\begin{array}{cc} +I&RF\\ +0&0 +\end{array} +\right). +\] +Die Matrix $RF$ enthält enthält also in Zeile $i$ und Spalte $j$ +die Wahrscheinlichkeit, dass der Prozess ausgehend vom Zustand $j$ +irgendwann im Zustand $i$ absorbiert wird. + +\subsubsection{Absorption über den letzten Zustand $l$} +Wie gross ist die Wahrscheinlichkeit, dass die von $j$ ausgehende +Absorption in den Zustand $i$ als letzten Zustand vor der Absorption +den Zustand $l$ hat? +Wir schreiben $l\overset{\smash{k}}{\twoheadrightarrow} i$ für das Ereignis, dass der Prozess +im $k$-ten Schritt über den letzten +Zustand $l$ in den Absorbtionszustand $i$ übergeht. +Ist uns der Zeitpunkt dies Übergangs egal, lassen wir das $k$ +weg und schreiben nur $l\twoheadrightarrow i$. + +Damit $l\overset{\smash{k}}{\twoheadrightarrow} i$ eintritt, muss der Prozess im $(k-1)$-ten Schritt im +Zustand $l$ ankommen, was er mit Wahrscheinlichkeit +\[ +P(X_{k-1}=l\wedge X_0=j) = (Q^{k-1})_{l\!j} +\] +tut, und dann den Übergang von $l$ nach $i$ nehmen, was er mit +Wahrscheinlichkeit $r_{il}$ tut. +Somit ist die gesuchte Wahrscheinlichkeit +\begin{equation} +P(X_K=i\wedge X_{k-1}=l\wedge X_0=j) += +P(l\overset{k}{\twoheadrightarrow} i\wedge X_0=j) = -\sum_{k} q^{(k)}_{l\!j}. -\notag -\end{align} -In zwei benachbarten Termen in -\eqref{buch:wahrscheinlichkeit:eqn:telescope} -heben sich die Summanden $kq^{(k)}_{l\!j}$ weg, man spricht von -einer teleskopischen Reihe. -\index{teleskopische Reihe}% -Die verbleibenden Terme sind genau die Matrixelemente der Fundamentalmatrix $N$. -Die Fundamentalmatrix enthält also im Eintrag $(l,j)$ die Wartezeit -bis zur Absorption über den Zustand $l$. - -\subsubsection{Wartezeit} -% XXX Mittlere Zeit bis zu einem bestimmten Zustand +r_{il}(Q^{k-1})_{l\!j}. +\label{buch:markov:eqn:Pilj} +\end{equation} + +Die Wahrscheinlichkeit, dass der Prozess zu irgend einer Zeit von $j$ +ausgehend über den letzten Zustand $l$ in den Absorptionszustand $i$ +übergeht, ist die Summe der Wahrscheinlichkeiten~\eqref{buch:markov:eqn:Pilj} +für alle $k$. +Der Faktor $r_{il}$ ist all diesen Termen gemeinsam, die Summe der +$Q$-Terme kann wieder durch die Fundamentalmatrix als +\[ +P(l\twoheadrightarrow i\wedge X_0 = j) += +\sum_{k=0}^\infty r_{il}(Q^k)_{l\!j} += +r_{il}\biggl(\sum_{k=0}^\infty (Q^k)\biggr)_{l\!j} += +r_{il}F_{l\!j} +\] +geschrieben werden. + +\subsubsection{Wartezeit für eine beliebige Markov-Kette} \index{Wartezeit}% -Die mittlere Wartezeit bis zum Erreichen eines Zustands kann mit der +Die mittlere Wartezeit bis zum Erreichen eines Zustands in einer +beliebigen Markov-Kette kann mit der Theorie zur Berechnung der Absorptionszeit berechnet werden. Dazu modifiziert man den Prozess dahingehend, dass der Zielzustand ein absorbierender Zustand wird. @@ -969,9 +1009,9 @@ Die Wartezeit bis zum Erreichen des Zustands $i$ ausgehend von einem Zustand $n$ kann jetzt aus der Absorbtionszeit der Markov-Kette im Zustand $1$ mit Hilfe der Fundamentalmatrix \[ -\tilde{N} +\tilde{F} = -(E-\tilde{Q})^{-1} +(I-\tilde{Q})^{-1} \] berechnet werden. diff --git a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex index 94b39fc..f27da0b 100644 --- a/buch/chapters/80-wahrscheinlichkeit/parrondo.tex +++ b/buch/chapters/80-wahrscheinlichkeit/parrondo.tex @@ -758,7 +758,7 @@ U^t = \frac13\biggl(-\frac{2}{5}+\frac{1}{4}+\frac{1}{4}\biggr) = --\frac{1}{30} +-\frac{1}{30}. \end{align*} Das Einzelspiel ist also ein Verlustspiel. diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex index 2d7de90..d140489 100644 --- a/buch/chapters/90-crypto/arith.tex +++ b/buch/chapters/90-crypto/arith.tex @@ -295,5 +295,4 @@ für die der $X^k$-Koeffizient von $q(X)$ von $0$ verschieden ist. \end{figure} -% XXX Beispiel F einer Oakley-Gruppe diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex index b295db8..066b9d2 100644 --- a/buch/chapters/90-crypto/ff.tex +++ b/buch/chapters/90-crypto/ff.tex @@ -177,8 +177,6 @@ Es muss davon ausgegangen werden, dass die Kommunikation abgehört wird. Trotzdem soll es für einen Lauscher nicht möglich sein, den ausgehandelten Schlüssel zu ermitteln. -% XXX Historisches zu Diffie und Hellman - Die beiden Partner $A$ und $B$ einigen sich zunächst auf eine Zahl $g$, die öffentlich bekannt sein darf. Weiter erzeugen sie eine zufällige Zahl $a$ und $b$, die sie geheim @@ -227,496 +225,3 @@ $a$ oder $b$ ermitteln können. Die Zahl $s=g^{ab}$ kann also als gemeinsamer Schlüssel verwendet werden. -%% -%% elliptisch.tex -%% -%% (c) 2021 Prof Dr Andreas Müller, OST Ostshweizer Fachhochschule -%% -%\subsection{Elliptische Kurven -%\label{buch:subsection:elliptische-kurven}} -%\index{elliptische Kurve}% -%Das Diffie-Hellman-Verfahren basiert auf der Schwierigkeit, in einem -%Körper $\mathbb{F}_p$ die Gleichung $a^x=b$ nach $x$ aufzulösen. -%Die Addition in $\mathbb{F}_p$ wird dazu nicht benötigt. -%Es reicht, eine Menge mit einer Multiplikation zu haben, fir die -%die Gleichung $a^x=b$ schwierig zu lösen ist. -%Ein Halbgruppe wäre also durchaus ausreichend. -% -%Ein Kandidat für eine solche Gruppe könnte der Einheitskreis -%$S^1=\{z\in\mathbb{C}\;|\; |z|=1\}$ in der komplexen Ebene sein. -%Wählt man eine Zahl $g=e^{i\alpha}$, wobei $\alpha$ ein irrationales -%Vielfaches von $\pi$ ist, dann sind alle Potenzen $g^n$ für natürliche -%Exponenten voneinander verschieden. -%Wäre nämlich $g^{n_1}=g^{n_2}$, dann wäre $e^{i\alpha(n_1-n_2)}=1$ und -%somit müsste $\alpha=2k\pi/(n_1-n_2)$ sein. -%Damit wäre aber $\alpha$ ein rationales Vielfaches von $\pi$, im Widerspruch -%zur Voraussetzung. -%Die Abbildung $n\mapsto g^n\in S^1$ ist auf den ersten Blick etwa ähnlich -%undurchschaubar wie die Abbildung $n\mapsto g^n\in\mathbb{F}_p$. -%Es gibt zwar die komplexe Logarithmusfunktion, mit der man $n$ bestimmen -%kann, dazu muss man aber den Wert von $g^n$ mit beliebiger Genauigkeit -%kennen, denn die Werte von $g^n$ können beliebig nahe beieinander liegen. -% -%Der Einheitskreis ist die Lösungsmenge der Gleichung $x^2+y^2=1$ für -%reelle Koordinaten $x$ und $y$, -%doch Rundungsunsicherheiten verunmöglichen den Einsatz in einem -%Verfahren ähnlich dem Diffie-Hellman-Verfahren. -%Dieses Problem kann gelöst werden, indem für die Variablen Werte -%aus einem endlichen Körper verwendet werden. -%Gesucht ist also eine Gleichung in zwei Variablen, deren Lösungsmenge -%in einem endlichen Körper eine Gruppenstruktur trägt. -%Die Lösungsmenge ist eine ``Kurve'' von Punkten mit -%\index{Kurve}% -%Koordinaten in einem endlichen Körper. -% -%In diesem Abschnitt wird gezeigt, dass sogenannte elliptische Kurven -%über endlichen Körpern genau die verlangen Eigenschaften haben. -% -%\subsubsection{Elliptische Kurven} -%Elliptische Kurven sind Lösungen einer Gleichung der Form -%\begin{equation} -%Y^2+XY=X^3+aX+b -%\label{buch:crypto:eqn:ellipticcurve} -%\end{equation} -%mit Werten von $X$ und $Y$ in einem geeigneten Körper. -%Die Koeffizienten $a$ und $b$ müssen so gewählt werden, dass die -%Gleichung~\eqref{buch:crypto:eqn:ellipticcurve} genügend viele -%Lösungen hat. -%Über den komplexen Zahlen hat die Gleichung natürlich für jede Wahl von -%$X$ drei Lösungen. -%Für einen endlichen Körper können wir dies im allgemeinen nicht erwarten, -%aber wenn wir genügend viele Wurzeln zu $\mathbb{F}$ hinzufügen können wir -%mindestens erreichen, dass die Lösungsmenge so viele Elemente hat, -%dass ein Versuch, die Gleichung $g^x=b$ mittels Durchprobierens zu -%lösen, zum Scheitern verurteilt ist. -% -%\begin{definition} -%\label{buch:crypto:def:ellipticcurve} -%Die {\em elliptische Kurve} $E_{a,b}(\Bbbk)$ über dem Körper $\Bbbk$ ist -%\index{elliptische Kurve}% -%die Menge -%\[ -%E_{a,b}(\Bbbk) -%= -%\{(X,Y)\in\Bbbk^2\;|\;Y^2+XY=X^3+aX+b\}, -%\] -%für $a,b\in\Bbbk$. -%\end{definition} -% -%Um die Anschauung zu vereinfachen, werden wir elliptische Kurven über -%dem Körper $\mathbb{R}$ visualisieren. -%Die daraus gewonnenen geometrischen Einsichten werden wir anschliessend -%algebraisch umsetzen. -%In den reellen Zahlen kann man die -%Gleichung~\eqref{buch:crypto:eqn:ellipticcurve} -%noch etwas vereinfachen. -%Indem man in \eqref{buch:crypto:eqn:ellipticcurve} -%quadratisch ergänzt, bekommt man -%\begin{align} -%Y^2 + XY + \frac14X^2 &= X^3+\frac14 X^2 +aX+b -%\notag -%\\ -%\Rightarrow\qquad -%v^2&=X^3+\frac14X^2+aX+b, -%\label{buch:crypto:eqn:ell2} -%\end{align} -%indem man $v=Y+\frac12X$ setzt. -%Man beachte, dass man diese Substition nur machen kann, wenn $\frac12$ -%definiert ist. -%In $\mathbb{R}$ ist dies kein Problem, aber genau über den Körpern -%mit Charakteristik $2$, die wir für die Computer-Implementation -%bevorzugen, ist dies nicht möglich. -%Es geht hier aber nur um die Visualisierung. -% -%Auch die Form \eqref{buch:crypto:eqn:ell2} lässt sich noch etwas -%vereinfachen. -%Setzt man $X=u-\frac1{12}$, dann verschwindet nach einiger Rechnung, -%die wir hier nicht durchführen wollen, der quadratische Term -%auf der rechten Seite. -%Die interessierenden Punkte sind Lösungen der einfacheren Gleichung -%\begin{equation} -%v^2 -%= -%u^3+\biggl(a-\frac{1}{48}\biggr)u + b-\frac{a}{12}+\frac{1}{864} -%= -%u^3+Au+B. -%\label{buch:crypto:ellvereinfacht} -%\end{equation} -%In dieser Form ist mit $(u,v)$ immer auch $(u,-v)$ eine Lösung, -%die Kurve ist symmetrisch bezüglich der $u$-Achse. -%Ebenso kann man ablesen, dass nur diejenigen $u$-Werte möglich sind, -%für die das kubische Polynom $u^3+Au+B$ auf der rechten Seite von -%\eqref{buch:crypto:ellvereinfacht} -%nicht negativ ist. -% -%Sind $u_1$, $u_2$ und $u_3$ die Nullstellen des kubischen Polynoms -%auf der rechten Seite von~\eqref{buch:crypto:ellvereinfacht}, folgt -%\[ -%v^2 -%= -%(u-u_1)(u-u_2)(u-u_3) -%= -%u^3 -%-(u_1+u_2+u_3)u^2 -%+(u_1u_2+u_1u_3+u_2u_3)u -%- -%u_1u_2u_3. -%\] -%Durch Koeffizientenvergleich sieht man, dass $u_1+u_2+u_3=0$ sein muss. -%\begin{figure} -%\centering -%\includegraphics{chapters/90-crypto/images/elliptic.pdf} -%\caption{Elliptische Kurve in $\mathbb{R}$ in der Form -%$v^2=u^3+Au+B$ mit Nullstellen $u_1$, $u_2$ und $u_3$ des -%kubischen Polynoms auf der rechten Seite. -%Die blauen Punkte und Geraden illustrieren die Definition der -%Gruppenoperation in der elliptischen Kurve. -%\label{buch:crypto:fig:elliptischekurve}} -%\end{figure} -%Abbildung~\ref{buch:crypto:fig:elliptischekurve} -%zeigt eine elliptische Kurve in der Ebene $\mathbb{R}^2$. -% -%\subsubsection{Geometrische Definition der Gruppenoperation} -%In der speziellen Form \ref{buch:crypto:ellvereinfacht} ist die -%elliptische Kurve symmetrisch unter Spiegelung an der $u$-Achse. -%Die Spiegelung ist eine Involution, zweimalige Ausführung führt auf -%den ursprünglichen Punkt zurück. -%Die Inverse in einer Gruppe hat diese Eigenschaft auch, es ist -%daher naheliegend, den gespiegelten Punkt als die Inverse eines -%Elementes zu nehmen. -% -%Eine Gerade durch zwei Punkte der -%in Abbildung~\ref{buch:crypto:fig:elliptischekurve} -%dargestellten Kurve schneidet die Kurve ein drittes Mal. -%Die Gruppenoperation wird so definiert, dass drei Punkte der Kurve -%auf einer Geraden das Gruppenprodukt $e$ haben. -%Da aus $g_1g_2g_3=e$ folgt $g_3=(g_1g_2)^{-1}$ oder -%$g_1g_2=g_3^{-1}$, erhält man das Gruppenprodukt zweier Elemente -%auf der elliptischen Kurve indem erst den dritten Schnittpunkt -%ermittelt und diesen dann an der $u$-Achse spiegelt. -% -%Die geometrische Konstruktion schlägt fehl, wenn $g_1=g_2$ ist. -%In diesem Fall kann man die Tangente im Punkt $g_1$ an die Kurve -%verwenden. -%Dieser Fall tritt zum Beispiel auch in den drei Punkten -%$(u_1,0)$, $(u_2,0)$ und $(u_3,0)$ ein. -% -%Um das neutrale Element der Gruppe zu finden, können wir -%zwei Punkte $g$ und $g^{-1}$ miteinander verknüpfen. -%Die Gerade durch $g$ und $g^{-1}$ schneidet aber die Kurve -%kein drittes Mal. -%Ausserdem sind alle Geraden durch $g$ und $g^{-1}$ für verschiedene -%$g$ parallel. -%Das neutrale Element entspricht also einem unendlich weit entfernten Punkt. -%Das neutrale Element entsteht immer dann als Produkt, wenn zwei -%Punkte die gleiche $u$-Koordinaten haben. -% -%\subsubsection{Gruppenoperation, algebraische Konstruktion} -%Nach den geometrischen Vorarbeiten zur Definition der Gruppenoperation -%kann können wir die Konstruktion jetzt algebraisch umsetzen. -% -%Zunächst überlegen wir uns wieder eine Involution, welche als Inverse -%dienen kann. -%Dazu beachten wir, dass die linke Seite der definierenden Gleichung -%\begin{equation} -%Y^2+XY=X^3-aX+b. -%\label{buch:crypto:eqn:grupopgl} -%\end{equation} -%auch als $Y(Y+X)$ geschrieben werden kann. -%Die Abbildung $Y\mapsto -X-Y$ macht daraus -%\[ -%(-X-Y)(-X-Y+X)=(X+Y)Y, -%\] -%dies ist also die gesuchte Involution. -% -%Seien also $g_1=(x_1,y_1)$ und $g_2=(x_2,y_2)$ zwei verschiedene Lösungen -%der Gleichung \eqref{buch:crypto:eqn:grupopgl} -%Als erstes brauchen wir eine Gleichung für die Gerade durch die beiden -%Punkte. -%Sei also $l(X,Y)$ eine Linearform derart, dass $l(g_1)=d$ und $l(g_2)=d$ -%für ein geeignetes $d\in\Bbbk$. -%Dann gilt auch für die Punkte -%\[ -%g(t) = tg_1 + (1-t)g_2 -%\qquad\Rightarrow\qquad -%l(g(t)) -%= -%tl(g_1) + (1-t)l(g_2) -%= -%tc+(1-t)c -%= -%(t+1-t)c -%=c, -%\] -%jeder Punkt der Geraden durch $g_1$ und $g_2$ lässt sich in dieser Form -%schreiben. -% -%Setzt man jetzt $g(t)$ in die Gleichung ein, erhält man eine kubische -%Gleichung in $t$, von der wir bereits zwei Nullstellen kennen, nämlich -%$0$ und $1$. -%Die kubische Gleichung muss also durch $t$ und $(t-1)$ teilbar sein. -%Diese Berechnung kann man einfach in einem Computeralgebrasystem -%durchführen. -%Das Polynom ist -%\[ -%p(t) -%= -%XXX -%\] -%Nach Division durch $t(t-1)$ erhält man als den Quotienten -%\begin{align*} -%q(t) -%&= -%(y_2-y_1)^2 -%+ -%(y_2-y_1) (x_2-x_1) -%+ -%t(x_2-x_1)^3 -%- -%2x_2^3+3x_1x_2^2-x_1^3 -%\end{align*} -%und den Rest -%\[ -%r(t) -%= -%t(y_1^2+x_1y_1-x_1^3-ax_1-b) -%+ -%(1-t)(y_2^2+x_2y_2-x_2^3-ax_2-b). -%\] -%Die Klammerausdrücke verschwinden, da die sie gleichbedeutend damit sind, -%dass die Punkte Lösungen von \eqref{buch:crypto:eqn:grupopgl} sind. -% -%Für den dritten Punkt auf der Geraden muss $t$ so gewählt werden, dass -%$q(t)=0$ ist. -%Dies ist aber eine lineare Gleichung mit der Lösung -%\begin{align*} -%t -%&= -%-\frac{ -%(y_1-y_2)^2 -%+ -%(y_2-y_1)(x_2-x_1) -%-2x_2^3+3x_1x_2^2-x_1^3 -%}{(x_2-x_1)^3} -%. -%\end{align*} -%Setzt man dies $g(t)$ ein, erhält man für die Koordinaten des dritten -%Punktes $g_3$ die Werte -%\begin{align} -%x_3 -%&= -%\frac{ -%(y_2-y_1)^2(x_2-x_1) + (y_2-y_1)(x_2-x_1)^2 -%-(x_2^4+x_1^4) -%}{ -%(x_2-x_1)^3 -%} -%\label{buch:crypto:eqn:x3} -%\\ -%y_3 -%&= -%\frac{ -%(y_2-y_1)^3 -%+(x_2-x_1)(y_2-y_1)^2 -%-(x_{2}-x_{1})^3 ( y_{2} - y_{1}) -%-(x_{2}-x_{1})^2 ( x_{1} y_{2}- x_{2} y_{1}) -%}{ -%(x_2-x_1)^3 -%} -%\label{buch:crypto:eqn:y3} -%\end{align} -%Die Gleichungen -%\eqref{buch:crypto:eqn:x3} -%und -%\eqref{buch:crypto:eqn:y3} -%ermöglichen also, das Element $g_1g_2^{-1}$ zu berechnen. -%Interessant daran ist, dass in den Formeln die Konstanten $a$ und $b$ -%gar nicht vorkommen. -% -%Es bleibt noch der für den Algorithmus~\ref{buch:crypto:teile-und-hersche} -%wichtige Fall des Quadrierens in der Gruppe zu -%behandeln, also der Fall $g_1=g_2$. -%In diese Fall sind die Formeln -%\eqref{buch:crypto:eqn:x3} -%und -%\eqref{buch:crypto:eqn:y3} -%ganz offensichtlich nicht anwendbar. -%Die geometrische Anschauung hat nahegelegt, die Tangent an die Kurve -%im Punkt $g_1$ zu nehmen. -%In $\mathbb{R}$ würde man dafür einen Grenzübergang $g_2\to g_1$ machen, -%aber in einem endlichen Körper ist dies natürlich nicht möglich. -% -%Wir schreiben die Gerade als Parameterdarstellung in der Form -%\( -%t\mapsto g(t)= (x_1+ut, y_1+vt) -%\) -%für beliebige Parameter in $\Bbbk$. -%Die Werte $u_1$ und $u_2$ müssen so gewählt werden, dass $g(t)$ eine -%Tangente wird. -%Setzt man $g(t)$ in die Gleichung~\eqref{buch:crypto:eqn:grupopgl} ein, -%entsteht ein kubische Gleichung, die genau dann eine doppelte Nullstelle -%bei $0$ hat, wenn $u,v$ die Tangentenrichtung beschreiben. -%Einsetzen von $g(t)$ in \eqref{buch:crypto:eqn:grupopgl} -%ergibt die Gleichung -%\begin{align} -%0 -%&= -%-u^3t^3 -%+ -%(-3u^2x_{1}+v^2+uv)t^2 -%+ -%(2vy_1+uy_1-3ux_1^2+vx_1-au)t -%+ -%(y_1^2+x_1y_1-x_1^3-ax_1-b) -%\label{buch:crypto:eqn:tangente1} -%\end{align} -%Damit bei $t=0$ eine doppelte Nullstelle müssen die letzten beiden -%Koeffizienten verschwinden, dies führt auf die Gleichungen -%\begin{align} -%y_1^2+x_1y_1&=x_1^3+ax_1+b -%\label{buch:crypto:eqn:rest1} -%\\ -%(2y_1 -%+x_1)v -%+(y_1 -%-3x_1^2 -%-a)u -%&=0. -%\label{buch:crypto:eqn:rest2} -%\end{align} -%Die erste Gleichung \eqref{buch:crypto:eqn:rest1} drückt aus, -%dass $g_1$ ein Punkt der Kurve ist, sie ist automatisch erfüllt. -% -%Die zweite Gleichung -%\eqref{buch:crypto:eqn:rest2} -%legt das Verhältnis von $u$ und $v$, also die -%\label{buch:crypto:eqn:rest2} -%Tangentenrichtung fest. -%Eine mögliche Lösung ist -%\begin{equation} -%\begin{aligned} -%u &= x_1+2y_1 -%\\ -%v &= -y_1+3x_1^2+a. -%\end{aligned} -%\label{buch:crypto:eqn:uv} -%\end{equation} -% -%Der Quotient ist ein lineares Polynom in $t$, die Nullstelle parametrisiert -%den Punkt, der $(g_1)^{-2}$ entspricht. -%Der zugehörige Wert von $t$ ist -%\begin{equation} -%t=-\frac{3u^2x_1-v^2-uv}{u^3}. -%\label{buch:crypto:eqn:t} -%\end{equation} -% -% -%Setzt man -%\label{buch:crypto:eqn:t} -%und -%\eqref{buch:crypto:eqn:uv} -%in $g(t)$ ein, erhält man sehr komplizierte Ausdrücke für den dritten Punkt. -%Wir verzichten darauf, diese Ausdrücke hier aufzuschreiben. -%In der Praxis wird man in einem Körper der Charakteristik 2 arbeiten. -%In diesem Körper werden alle geraden Koeffizienten zu $0$, alle ungeraden -%Koeffizienten werden unabhängig vom Vorzeichen zu $1$. -%Damit bekommt man die folgenden, sehr viel übersichtlicheren Ausdrücke -%für den dritten Punkt: -%\begin{equation} -%\begin{aligned} -%x -%&= -%-\frac{ -%y_1^2+x_1y_1+x_1^4+x_1^3+ax_1-a^2 -% }{ -%x_1^2 -%} -%\\ -%y -%&= -%\frac{ -%y_1^3+(x_1^2+x_1+a)y_1^2+(x_1^4 +a^2)y_1+x_1^6+ax_1^4+ax_1^3+a^2x_1^2+a^2x_1+a^3 -%}{ -% x_1^3 -%}. -%\end{aligned} -%\label{buch:crypto:eqn:tangentechar2} -%\end{equation} -%Damit haben wir einen vollständigen Formelsatz für die Berechnung der -%Gruppenoperation in der elliptischen Kurve mindestens für den praktisch -%relevanten Fall einer Kurve über einem Körper der Charakteristik $2$. -% -%\begin{satz} -%Die elliptische Kurve -%\[ -%E_{a,b}(\mathbb{F}_{p^l}) -%= -%\{ -%(X,Y)\in\mathbb{F}_{p^l} -%\;|\; -%Y^2+XY = X^3-aX-b -%\} -%\] -%trägt eine Gruppenstruktur, die wie folgt definiert ist: -%\begin{enumerate} -%\item Der Punkt $(0,0)$ entspricht dem neutralen Element. -%XXX (0,0) muss erst definiert werden -%\item Das inverse Element von $(x,y)$ ist $(-x,-y-x)$. -%\item Für zwei verschiedene Punkte $g_1$ und $g_2$ kann $g_3=(g_1g_2)^{-1}$ -%mit Hilfe der Formeln -%\eqref{buch:crypto:eqn:x3} -%und -%\eqref{buch:crypto:eqn:y3} -%gefunden werden. -%\item Für einen Punkt $g_1$ kann $g_3=g_1^{-2}$ in Charakteristik $2$ mit -%Hilfe der Formeln -%\eqref{buch:crypto:eqn:tangentechar2} -%gefunden werden. -%\end{enumerate} -%Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen -%abelschen Gruppe. -%\end{satz} -% -%\subsubsection{Diffie-Hellman in einer elliptischen Kurve} -%Der klassische Diffie-Hellmann-Schlüsselalgorithmus in einem Körper -%$\mathbb{F}_p$ basiert darauf, dass man beliebige Potenzen eines -%Elementes berechnen kann, und dass es schwierig ist, diese Operation -%umzukehren. -%Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt -%nicht benötigt. -% -%In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation, -%für die sich mit Algorithmus~\ref{buch:crypto:teile-und-hersche} -%eine effizienter Potenzieralgorithmus konstruieren lässt. -%Die resultierende Potenzfunktion stellt sich ebenfalls als -%schwierig zu invertieren heraus, kann also ebenfalls für einen -%Diffie-Hellmann-Schlüsseltausch verwendet werden. -% -%Die im Internet Key Exchange Protokol -%in RFC 2409 -%\cite{buch:rfc2409} -%definierte Oakley-Gruppe 4 -%zum Beispiel verwendet einen Galois-Körper $\mathbb{F}_{2^{185}}$ -%mit dem Minimalpolynom $m(x)=x^{185}+x^{69}+1\in \mathbb{F}_2[x]$ -%und den Koeffizienten -%\begin{align*} -%a&=0\\ -%b&=x^{12}+x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 +1, -%\end{align*} -%die die elliptische Kurve definieren. -% -%Als Elemente $g$ für den Diffie-Hellmann-Algorithmus wird ein Punkt -%der elliptischen Kurve verwendet, dessen $X$-Koordinaten durch das -%Polynom $g_x = x^4+x^3$ gegeben ist. -%Der Standard spezifiziert die $Y$-Koordinate nicht, diese kann aus -%den gegebenen Daten abgeleitet werden. -%Die entstehende Gruppe hat etwa $4.9040\cdot10^{55}$ Elemente, die -%für einen brute-force-Angriff durchprobiert werden müssten. -% -% -% -% -% -% -% -% diff --git a/buch/chapters/95-homologie/basiswahl.tex b/buch/chapters/95-homologie/basiswahl.tex index aacfa9f..391ebf2 100644 --- a/buch/chapters/95-homologie/basiswahl.tex +++ b/buch/chapters/95-homologie/basiswahl.tex @@ -521,7 +521,7 @@ z_8 % variable 18 = 1 0\\ %25 1\\ 1 -\end{pmatrix*} +\end{pmatrix*}. \end{align*} \begin{figure} \centering diff --git a/buch/chapters/95-homologie/chapter.tex b/buch/chapters/95-homologie/chapter.tex index e25188c..88968d2 100644 --- a/buch/chapters/95-homologie/chapter.tex +++ b/buch/chapters/95-homologie/chapter.tex @@ -7,7 +7,8 @@ \label{buch:chapter:homologie}} \lhead{Kettenkomplexe und Homologie} \rhead{} -Mit der Inzidenzmatrix war es möglich, einen Graphen zu beschreiben +Mit der Inzidenzmatrix war es in Kapitel~\ref{buch:chapter:graphen} +möglich, einen Graphen zu beschreiben und verschiedene interessante Eigenschaften desselben zu berechnen. Damit können aber nur eindimensionale Strukturen analysiert werden: Es ist zum Beispiel nicht möglich, ein Dreieck vom Rand eines diff --git a/buch/chapters/95-homologie/fixpunkte.tex b/buch/chapters/95-homologie/fixpunkte.tex index b3b184e..1b86797 100644 --- a/buch/chapters/95-homologie/fixpunkte.tex +++ b/buch/chapters/95-homologie/fixpunkte.tex @@ -58,7 +58,7 @@ Lefshetz-Zahl auf das gleiche Resultat führen müssen. \centering \includegraphics[width=\textwidth]{chapters/95-homologie/images/approximation.pdf} \caption{Stückweise lineare Approximation einer Abbildung derart, -dass die Bildpunkt von Knoten auf Gitterpunkte fallen. +dass die Bildpunkte von Knoten auf Gitterpunkte fallen. Die Abbildung wird damit zu einer Abbildung von Polyedern und die induzierte Abbildung der Kettenkomplexe lässt sich direkt berechnen. Wenn die Auflösung des Gitters klein genug ist, hat die Approximation diff --git a/buch/chapters/95-homologie/images/approximation.pdf b/buch/chapters/95-homologie/images/approximation.pdf Binary files differindex 8bdd2e7..517dde6 100644 --- a/buch/chapters/95-homologie/images/approximation.pdf +++ b/buch/chapters/95-homologie/images/approximation.pdf diff --git a/buch/chapters/95-homologie/images/approximation.tex b/buch/chapters/95-homologie/images/approximation.tex index 042f0e2..1039764 100644 --- a/buch/chapters/95-homologie/images/approximation.tex +++ b/buch/chapters/95-homologie/images/approximation.tex @@ -35,7 +35,7 @@ \xdef\blau{\pgfmathresult} \definecolor{mycolor}{rgb}{\rot,0.8,\blau} \fill[color=mycolor] - (\a:{\s*\r}) -- (\a:{\s*(\r+0.2)}) -- ({\a+1}:{\s*(\r+0.2)}) -- ({\a+1}:{\s*\r}) -- cycle; + (\a:{\s*\r}) -- (\a:{\s*(\r+0.21)}) -- ({\a+1.02}:{\s*(\r+0.21)}) -- ({\a+1.02}:{\s*\r}) -- cycle; } } } diff --git a/buch/chapters/95-homologie/images/complexbasis.pdf b/buch/chapters/95-homologie/images/complexbasis.pdf Binary files differindex 9ff6709..663eaa9 100644 --- a/buch/chapters/95-homologie/images/complexbasis.pdf +++ b/buch/chapters/95-homologie/images/complexbasis.pdf diff --git a/buch/chapters/95-homologie/images/complexbasis.tex b/buch/chapters/95-homologie/images/complexbasis.tex index bab89d2..877351d 100644 --- a/buch/chapters/95-homologie/images/complexbasis.tex +++ b/buch/chapters/95-homologie/images/complexbasis.tex @@ -87,9 +87,10 @@ \rechteck{7}{10}{darkgreen} \rechteck{11}{11}{blue} \Rechteck{0}{11} + \draw[->,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_{i<j} -x_{ij} k_{ij} -\, -\bigg| -\, -x_{ij}\in\mathbb{R} -\biggr\}, -\] -wobei $k_{ij}$ die Kante von der Ecke $i$ zur Ecke $j$ ist. -In Dimension $l$ bezeichnen wir mit $C_l$ den Vektorraum bestehend -aus den Linearkombinationen +Simplizes verschiedener Dimension in $\mathbb{R}^N$ können natürlich +immer unterschieden werden, wir können also den Vektorraum in einzelne +Vektorräume aufteilnen, einen für jede Dimension. +In Dimension $l$ bezeichnen wir mit $C_l$ den Vektorraum, dessen +Basisvektoren $l+1$-Tupel +\( +[P_0,\dots,P_l] +\) +von Punkten von $\mathbb{R}^N$ sind. +Der Vektorraum $C_l$ besteht dann aus Linearkombinationen \[ C_l = \biggl\{ -\sum_{i_1<\dots<i_l} x_{i_1\dots i_l} s_{i_1\dots i_l} -\, -\bigg| -\, -s_{i_1\dots i_l}\in\mathbb{R} -\biggr\}, -\] -wobei $s_{i_1\dots i_l}$ das Simplex mit den Ecken $i_1,\dots,i_l$ ist. - -Für $n=1$ gibt ist $C_1$ ein eindimensionaler Vektorraum und $C_0$ -ist zweidimensional. -Die Randabbildung, die einer Kante den Rand zuordnet, ist -\[ -\partial -\colon -C_1\to C_0 -: -s_{01} -\mapsto -1\cdot s_0 + (-1)\cdot s_1 -\] -und hat in den oben beschriebenden Basen die Matrix -\[ -\partial -= -\begin{pmatrix} -1\\ --1 -\end{pmatrix}. +\sum x_{P_0\dots P_l} [P_0,\dots,P_l] +\;\bigg|\; +x_{P_0\dots P_l}\in\mathbb{R} +\biggr\}. \] +Die Seitenflächen dieses Simplex sind die $l-1$-dimensionalen +Simplizes, die man erhält, indem man eine Ecke weglässt. +Wir bezeichnen mit $[P_0,\dots,\widehat{P_i},\dots,P_l] \in C_{l-1}$ +Die Seitenfläche, die man durch Weglassen der Ecke $P_i$ +erhalten hat. \subsubsection{Rand eines Simplex} -Einem Simplex muss auch der Rand zugeordnet werden können. -Setzt man in $\triangle_2$ den Parameter $t_k=0$, dann erhält -man die Kante, -die der Ecke mit Nummer $k$ gegenüberliegt. -Für jedes $k$ gibt es also eine Abbildung -\[ -i_k -\colon -\triangle_{n-1} \to \triangle_n -: -(t_0,\dots,t_n) +Die Oberfläche eines Simplex ist nicht einfach die Summe der +Seitenflächen. +Die Kanten eines Dreiecks $[P_0,P_1,P_2]$ müssen so aneinandergefügt +werden, dass sie einen Weg um das Dreieck ergeben. +Beginnt man das Dreieck in Richtung der Kanten +$[P_0,P_1]$ und $[P_1,P_2]$ zu umlaufen, trifft man in +``verkehrter'' Richtung auf die Kante $[P_0,P_2]$. +Für den Rand des Dreiecks muss man also diese Kante mit negativem +Vorzeichen zählen: +\begin{align*} +\partial_3 \colon +[P_0,P_1,P_2] \mapsto -(t_0,\dots,t_{k-1},0,t_{k},\dots,t_n), -\] -in die Kante gegenüber der Ecke $e_k$. +[P_0,P_1] ++ [P_1,P_2] +- [P_0,P_2] +&= +[\widehat{P_0},P_1,P_2] +-[P_0,\widehat{P_1},P_2] ++[P_0,P_1,\widehat{P_2}] +\\ +&= +\sum_{i=0}^l (-1)^i [P_0,\dots,\widehat{P_i},\dots,P_3] +\end{align*} Dies ist auch die Art, wie Kanten des Dreiecks $\triangle$ in Abbildung~\ref{buch:homologie:figure:zusammenziehbar} orientiert wurden. -Für den Rand des $2$-Simplexes mussten die Kanten mit alternierenden -Vorzeichen zugeordnet werden. -Damit wird erreicht, dass jeder Punkt sowohl Endpunkt einer -Kante und -ausserdem Anfangspunkt der nächsten Kannte ist. -Diese Eigenschaft soll auch in höheren Dimensionen erhalten bleiben. -Die vier Dreiecke, die den Rand eines $3$-Simplex ausmachen, -müssen so orientiert werden, -dass jede Kante in beiden Richtungen durchlaufen wird. - \begin{definition} \label{buch:def:randoperator} -Der Randoperator ordnet die Kanten eines $n$-Simplex mit alternierenden -Vorzeichen zu, die Matrix ist +Der Randoperator ordnet einem $l$-Simplex dessen $l-1$-dimensonale +Seitenflächen mit alternierenden Vorzeichen zu: \[ +\partial_l : [P_0,\dots,P_l] +\mapsto +\sum_{i=0}^l (-1)^i [P_0,\dots,\widehat{P_i},\dots,P_l]. \] \end{definition} +\subsubsection{Inzidenzmatrix eines gerichteten Graphen und Randoperator} +In Abschnitt~\ref{buch:graphen:subsection:inzidenzmatrix} wurde die +Inzidenzmatrix eines gerichteten Graphen $G=(V,E)$ definiert. +Seien $V=\{v_1,\dots,v_n\}$ die Vertizes des Graphen und +$E=\{e_1,\dots,e_m\}$ die Kanten. +Gibt es eine Kante $e_k = (v_i,v_j)\in E$ im Graphen, dann hat die Inzidenzmatrix +in Spalte $k$ die Einträge $-1$ in Zeile $i$ und $+1$ in Zeile $j$. +Die Kante $e_k$ können wir als eindimensionales Simplex $[v_i,v_j]$ +betrachten. +Die Adjazenzmatrix ordnet ihm die Linearkombination +\[ +A(G)\colon e_k=[v_i,v_j] \mapsto -[v_i] +[v_j] += (-1)^0 [\widehat{v_i},v_j] + (-1)^1 [v_i,\widehat{v_j}] += +\partial_2 [v_i,v_j] +\] +zu. +Die Adjazenzmatrix eines Graphen kann man also als den Randoperator +$\partial_1$ betrachten, der auf den als $1$-dimensionale Simplizes +betrachteten Kanten des Graphen wirkt. + +\subsubsection{Der Rand des Randes} +Der Rand eines Tetraeders setzt sich aus vier Dreiecken +zusammen. +Jede Kante gehört zu genau zwei Seitenflächen. +Wenn die Dreiecke alle so orientiert sind, dass sie ``von ausserhalb'' +des Tetraeders betrachtet positiv orientiert sind, dann wird jede +Kante zweimal in jeder Richtung durchlaufen. +Bildet man den Rand all dieser Seitenflächen, kommte jede Kante +einmal mit positivem und einmal mit negativem Vorzeichen vor, +die Summe ist $0$. + +Ganz allgemein gilt, dass der Rand des Randes verschwindet. + +\begin{satz} +\label{buch:homologie:satz:randrand} +Es gilt $\partial_{l-1}\circ\partial_l=0$. +\end{satz} + +\begin{proof}[Beweis] +Der Rand des Simplex $[P_0,\dots,P_l]$ ist +\[ +\partial_l[P_0,\dots,P_l] += +\sum_{i=0}^l (-1)^i [P_0,\dots,\widehat{P_i},\dots,P_l]. +\] +Darauf muss jetzt der Randoperator $\partial_{l-1}$ angewendet +werden. +Dabei wird jeweils der Index $i$ übersprungen, bei der Bildung der +Summe müssen die Teile daher separat betrachtet werden: +\begin{align} +\partial_{l-1}\partial_l[P_0,\dots,P_l] +&= +\sum_{i=0}^l (-1)^i \partial_{l-1}[P_0,\dots,\widehat{P_i},\dots,P_l] +\notag +\\ +&= +\sum_{i=0}^l (-1)^i +\biggl( +\sum_{j<i} (-1)^j +[P_0,\dots,\widehat{P_j},\dots,\widehat{P_i}\dots,P_l] +\notag +\\ +&\hspace*{2cm} ++ +\sum_{j>i} (-1)^{j-1} +[P_0,\dots,\widehat{P_i},\dots,\widehat{P_j}\dots,P_l] +\biggr) +\label{buch:homologie:eqn:randrand} +\\ +&= +\sum_{j<i} (-1)^{i+j} +[P_0,\dots,\widehat{P_j},\dots,\widehat{P_i}\dots,P_l] +- +\sum_{j>i} (-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_{j<i} (-1)^{i+j} +[P_0,\dots,\widehat{P_j},\dots,\widehat{P_i}\dots,P_l] +\\ +&\qquad +- +\sum_{i>j} (-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} +} |