diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/10-vektorenmatrizen/linear.tex | 205 | ||||
| -rw-r--r-- | buch/chapters/10-vektorenmatrizen/skalarprodukt.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/50-permutationen/determinante.tex | 102 | ||||
| -rw-r--r-- | buch/chapters/50-permutationen/matrizen.tex | 5 | ||||
| -rw-r--r-- | buch/chapters/60-gruppen/symmetrien.tex | 4 | ||||
| -rw-r--r-- | buch/chapters/70-graphen/wavelets.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/Makefile.inc | 1 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/arith.tex | 1 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/ff.tex | 53 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/rs.tex | 41 | ||||
| -rw-r--r-- | buch/chapters/95-homologie/Makefile.inc | 1 | ||||
| -rw-r--r-- | buch/chapters/95-homologie/chapter.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/95-homologie/homologie.tex | 340 | ||||
| -rw-r--r-- | buch/chapters/95-homologie/komplex.tex | 104 | ||||
| -rw-r--r-- | buch/chapters/95-homologie/simplex.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/references.bib | 13 |
16 files changed, 803 insertions, 75 deletions
diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex index ac2b85d..e368364 100644 --- a/buch/chapters/10-vektorenmatrizen/linear.tex +++ b/buch/chapters/10-vektorenmatrizen/linear.tex @@ -837,7 +837,178 @@ Seite~\pageref{buch:vektorenmatrizen:satz:gruppenregeln} die Eigenschaft $A^{-1}A=I$ ganz allgemein gezeigt. \subsubsection{Determinante} -XXX TODO +Ein Gleichungssystem mit $n$ Gleichungen und $n$ Unbekannten ist genau +dann lösbar, wenn sich der Gauss-Algorithmus bis zum Ende durchführen lässt. +Das ist gleichbedeutend damit, dass keines der Pivot-Elemente verschwindet. +Das Produkt der Pivot-Elemente ist also eine aus der Koeffizientenmatrix +$A$ berechnete Kennzahl, die zu entscheiden erlaubt, ob ein Gleichungssystem +lösbar ist. + +\begin{definition} +\label{buch:linear:determinate:def} +Das Produkt der Pivot-Elemente bei der Durchführung des Gauss-Algorithmus +für eine Gleichungssystem mit quadratischer Koeffizientenmatrix $A$ +heisst die Determinante $\det(A)$ der Matrix $A$. +\end{definition} + +Aus den Regeln für die Durchführung des Gauss-Algorithmus kann man die +folgenden Regeln für die Determinante ableiten. +Wir stellen die Eigenschaften hier nur zusammen, detaillierte Herleitungen +kann man in jedem Kurs zur linearen Algebra finden, zum Beispiel im +Kapitel~2 des Skripts \cite{buch:linalg}. +\begin{enumerate} +\item +\label{buch:linear:determinante:einheitsmatrix} +Die Determinante der Einheitsmatrix ist $\det(I)=1$. +\item +Sind zwei Zeilen einer Matrix gleich, dann tritt beim Gauss-Algorithmus +eine Nullzweile auf, die Matrix kann also nicht regulär sein und die +Determinante ist $0$. +\item +\label{buch:linear:determinante:vorzeichen} +Vertauscht man zwei Zeilen einer Matrix, dann kehrt das Vorzeichen der +Determinante. +\item +Addiert man ein Vielfaches einer Zeile der Matrix zu einer anderen Zeile, +dann ändert der Wert der Determinante nicht. +\item +Wird eine Zeile der Matrix mit einer Zahl $\lambda$ multipliziert, dann +wird auch der Wert der Determinanten mit $\lambda$ multipliziert. +\item +\label{buch:linear:determinante:asymetrisch} +Die Determinante ist eine lineare Funktion der Zeilen von $A$. +Zusammen mit der Eigeschaft~\ref{buch:linear:determinante:vorzeichen} +folgt, dass die Determinante eine antisymmetrische lineare Funktion +der Zeilen ist. +\item +Die Determinante ist durch die Eigenschaften +\ref{buch:linear:determinante:einheitsmatrix} +und +\ref{buch:linear:determinante:asymetrisch} +eindeutig bestimmt. +\item +Der Entwicklungssatz von Laplace. +\index{Entwicklungssatz Laplace}% +Die Determinante der $n\times n$-Matrix $A$ kann mit der Formel +\begin{equation} +\det(A) += +\sum_{i=1}^n (-1)^{i+j} a_{ij} \cdot \det(A_{ij}) +\end{equation} +wobei die $(n-1)\times(n-1)$-Matrix $A_{ij}$ die Matrix $A$ ist, aus der +man Zeile $i$ und Spalte $j$ entfernt hat. +$A_{ij}$ heisst ein {\em Minor} der Matrix $A$. +\index{Minor einer Matrix}% +\end{enumerate} + +Die bekannte Formel $\det\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad-bc$ +ist ein Spezialfall des Entwicklungssatzes von Laplace. +Auch für $3\times 3$-Matrizen ist eine übersichtliche Form möglich, +die als die Sarrus-Formel bekannt ist. +\index{Sarrus-Formel}% + +\begin{satz}[Sarrus] +\label{buch:linear:determinate:sarrus} +Die Determinante einer $3\times 3$-Matrix ist +\[ +\left|\begin{matrix} +a&b&c\\ +d&e&f\\ +g&h&i +\end{matrix}\right| += +aei + bfg + cdh - ceg - bdi - afh. +\] +\end{satz} + +\subsubsection{Die Regel von Cramer} +Die Determinanten ermöglicht auch, eine Formel für die Lösung eines +Gleichungssystems zu geben. +Dies ist bekannt als die {\em Regel von Cramer}. + +\begin{satz} +\label{buch:linear:determinante:cramer} +Die Lösung $x_k$ eines $n\times n$-Gleichungssystem $Ax=b$ mit +Koeffizientenmatrix $A$ und rechter Seite $b$ hat die Lösungen +\begin{equation} +x_k += +\frac{ +\left|\begin{matrix} +a_{11}&a_{12}&\dots &b_1 &\dots &a_{1n}\\ +a_{21}&a_{22}&\dots &b_2 &\dots &a_{2n}\\ +\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ +a_{n1}&a_{n2}&\dots &b_n &\dots &a_{nn} +\end{matrix}\right| +}{ +\det(A), +} +\end{equation} +wobei im Zähler die Spalte $k$ der Matrix $A$ durch den Vektor $b$ +der rechten Seiten ersetzt worden ist. +\end{satz} + +Die Cramersche Formel ist besonders nützlich, wenn die Abhängigkeit +einer Lösungsvariablen von den Einträgen der Koeffizientenmatrix +untersucht werden soll. +Für die Details der Herleitung sei wieder auf \cite{buch:linalg} +verwiesen. + +\subsubsection{Die inverse Matrix mit Hilfe der Determinanten} +Die inverse Matrix löst ein quadratisches Gleichungssystem $Ax=b$ mit +Hilfe der Formel $x=A^{-1}b$. +Man kann daher auch erwarten, dass sich die inverse Matrix dank +der Cramerschen Regel mit Hilfe von Determinanten ausdrücken lässt. +Tatsächlich gilt der folgende Satz. + +\begin{satz} +\label{buch:linalg:inverse:adjunkte} +Die Inverse der $n\times n$-Matrix $A$ ist gegeben durch +\index{Formel für die inverse Matrix}% +\index{inverse Matrix, Formel für}% +\begin{equation} +(A^{-1})_{ij} += +\frac{1}{\det(A)} +\begin{pmatrix} +\det(A_{11}) & -\det(A_{21}) & \dots & (-1)^{i+1}\det(A_{i1}) & \dots + & (-1)^{1+n} \det(A_{n1}) \\ +-\det(A_{12}) & \det(A_{22}) & \dots & (-1)^{i+2}\det(A_{i2}) & \dots + & (-1)^{2+n} \det(A_{n2}) \\ +\vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ +(-1)^{1+j}\det(A_{1j}) & (-1)^{2+j}\det(A_{2j}) & \dots + & (-1)^{i+j} \det(A_{ji}) + & \dots & (-1)^{j+n} \det(A_{nj}) \\ +\vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ +(-1)^{1+n}\det(A_{1n}) & (-1)^{2+n}\det(A_{2n}) & \dots + & (-1)^{i+n}\det(A_{in}) + & \dots & \det(A_{nn}) +\end{pmatrix} +\label{buch:linalg:inverse:formel} +\end{equation} +Die Transponierte der Matrix auf der rechten Seite (ohne den Vorfaktor +$1/\det(A)$ +heisst die {\em Adjunkte} $\operatorname{adj}A$ von $A$. +\index{Adjunkte}% +\end{satz} + +Der Satz~\ref{buch:linalg:inverse:adjoint} liefert eine algebraische +Formel für die Elemente der inversen Matrix. +Für kleine Matrizen wie im nachfolgenden Beispiel ist die +Formel~\eqref{buch:linalg:inverse:formel} oft einfachter anzuwenden. +Besonders einfach wird die Formel für eine $2\times 2$-Matrix, +wo man +\[ +\begin{pmatrix} +a&b\\c&d +\end{pmatrix}^{-1} += +\frac{1}{ad-bc}\begin{pmatrix} +d&-b\\ +-c&a +\end{pmatrix} +\] +erhält. \begin{beispiel} Die Inverse der Matrix @@ -852,21 +1023,22 @@ a&a&1 ist mit Hilfe von Determinanten besonders einfach zu invertieren. Die Determinante von $A$ ist nach der Sarrus-Formel \[ -\det A +\operatorname{adj}A = 1 + 2a^3 - 3a^2. \] -Die adjungiert Matrix ist +Die Adjunkte ist \begin{align*} -A^{-1} +(\operatorname{adj}A)^t &= -\frac{1}{\det{A}} -\begin{pmatrix} -\det A_{11} & \det A_{21} & \det A_{31} \\ -\det A_{12} & \det A_{22} & \det A_{32} \\ -\det A_{13} & \det A_{23} & \det A_{33} -\end{pmatrix} -\\ +%\frac{1}{\det{A}} +\begin{pmatrix*}[r] + \det A_{11} & -\det A_{21} & \det A_{31} \\ +-\det A_{12} & \det A_{22} & -\det A_{32} \\ + \det A_{13} & -\det A_{23} & \det A_{33} +\end{pmatrix*} +\intertext{und damit ist die inverse Matrix} +A^{-1} &= \frac{1}{2a^3-3a^2+1} \renewcommand\arraystretch{1.1} @@ -896,7 +1068,7 @@ A^{-1} 1-a^2 & a^2-a & a^2-a\\ a^2-a & 1-a^2 & a^2-a\\ a^2-a & a^2-a & 1-a^2 -\end{pmatrix} +\end{pmatrix}. \end{align*} Mit $1-a^2=(1+a)(1-a)$ und $a^2-a=a(a-1)$ kann man dies noch etwas vereinfachen, indem man den gemeinsamen Faktor $1-a$ ausklammern. @@ -916,6 +1088,15 @@ für die Inverse einer Matrix der Form \eqref{buch:vektoren-und-matrizen:abeispiel:eqn1}. \end{beispiel} +\subsubsection{Produktregel für die Determinante} +Aus der Charakterisierung der Determinanten kann man auch ableiten, +dass die Produktregel +\[ +\det (AB) = \det(A) \cdot \det(B) +\] +gilt. +Daraus folgt auch, dass $\det(A^{-1})=\det(A)^{-1}$. + % % Lineare Abbildungen % diff --git a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex index d951221..408bfeb 100644 --- a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex +++ b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex @@ -197,7 +197,7 @@ mit Gleichheit genau dann, wenn $x=ty$ ist für ein $t\ge 0$. &= (\|x\|_2 + \|y\|_2)^2 \\ -\|x\|_2 + \|y\|_2 +\|x + y\|_2 &\le \|x\|_2 + \|y\|_2, \end{align*} Gleichheit tritt genau dann ein, wenn diff --git a/buch/chapters/50-permutationen/determinante.tex b/buch/chapters/50-permutationen/determinante.tex index c440caf..805235d 100644 --- a/buch/chapters/50-permutationen/determinante.tex +++ b/buch/chapters/50-permutationen/determinante.tex @@ -7,3 +7,105 @@ \section{Determinante \label{buch:section:determinante}} \rhead{Determinante} +Das Signum einer Permutationsmatrizen lässt sich +gemäss~\eqref{buch:permutationen:determinante} +mit der Determinanten berechnen. +Umgekehrt sollte es auch möglich sein, eine Formel +für die Determinante zu finden. +Die Basis dafür ist der +Entwicklungssatz +\begin{equation} +\det(A) += +\sum_{i=1}^n (-1)^{i+j} a_{ij} \cdot \det(A_{ij}) +\label{buch:permutationen:entwicklungssatz} +\end{equation} +von Laplace für die Determinante. +In den Produkten $a_{ij}\cdot\det(A_{ij})$ enthält +die Untermatrix $A_{ij}$ weder Elemente der Zeile $i$ noch der +Zeile $j$. +Die Summanden auf der rechten Seite von +\eqref{buch:permutationen:entwicklungssatz} +sind daher Produkte der Form +\[ +a_{1i_1} +a_{2i_2} +a_{3i_3} +\dots +a_{ni_n}, +\] +in denen nur Faktoren aus verschiedenen Spalten der Matrix $A$ +vorkommen. +Das ist gleichbedeutend damit, dass unter den Spaltenindizes +$i_1,i_2,i_3,\dots,i_n$ keine zwei gleich sind, dass also +\[ +\sigma += +\begin{pmatrix} +1&2&3&\dots&n\\ +i_1&i_2&i_3&\dots&i_n +\end{pmatrix} +\] +eine Permutation ist. + +Die Determinante muss sich daher als Summe über alle Permutationen +in der Form +\begin{equation} +\det(A) += +\sum_{\sigma\in S_n} +c(\sigma) +a_{1\sigma(1)} +a_{2\sigma(2)} +\dots +a_{n\sigma(n)} +\label{buch:permutationen:cformel} +\end{equation} +schreiben lassen, wobei die Koeffizienten $c(\sigma)$ noch zu bestimmen +sind. +Setzt man in +\eqref{buch:permutationen:cformel} +eine Permutationsmatrix $P_\tau$ ein, dann verschwinden alle +Terme auf der rechten Seite ausser dem zur Permutation $\tau$, +also +\[ +\det(P_\tau) += +\sum_{\sigma \in S_n} +c(\sigma) +(P_\tau)_{1\sigma(1)} +(P_\tau)_{2\sigma(2)} +\dots +(P_\tau)_{n\sigma(n)} += +c(\tau) +1\cdot 1\cdot\dots\cdot 1 += +c(\tau). +\] +Der Koeffizientn $c(\tau)$ ist also genau das Vorzeichen +der Permutation $\tau$. +Damit erhalten wir den folgenden Satz: + +\begin{satz} +Die Determinante einer $n\times n$-Matrix $A$ kann berechnet werden als +\[ +\det(A) += +\sum_{\sigma\in S_n} +\operatorname{sgn}(\sigma) +a_{1\sigma(1)} +a_{2\sigma(2)} +\dots +a_{n\sigma(n)} += +\sum_{\tau\in S_n} +\operatorname{sgn}(\tau) +a_{\tau(1)1} +a_{\tau(2)2} +\dots +a_{\tau(n)n}. +\] +Insbesondere folgt auch $\det(A)=\det(A^t)$. +\end{satz} + diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex index 7e55364..f7e9e31 100644 --- a/buch/chapters/50-permutationen/matrizen.tex +++ b/buch/chapters/50-permutationen/matrizen.tex @@ -181,7 +181,7 @@ Die Determinante einer solchen Permutationsmatrix ist Nach der Produktregel für die Determinante folgt für eine Darstellung der Permutation $\sigma=\tau_1\dots\tau_l$ als Produkt von Transpositionen, dass -\[ +\begin{equation} \det P_{\sigma} = \det P_{\tau_1} \dots \det P_{\tau_l} @@ -189,7 +189,8 @@ dass (-1)^l = \operatorname{sgn}(\sigma). -\] +\label{buch:permutationen:determinante} +\end{equation} Das Vorzeichen einer Permutation ist also identisch mit der Determinante der zugehörigen Permutationsmatrix. diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex index 7364c85..aee3b41 100644 --- a/buch/chapters/60-gruppen/symmetrien.tex +++ b/buch/chapters/60-gruppen/symmetrien.tex @@ -714,8 +714,8 @@ Kurve so zu definieren, dass dabei Längen und Winkel erhalten bleiben. Dieser Ansatz ist die Basis der Theorie der Krümmung sogenannter Riemannscher Mannigfaltigkeiten. -\subsection{Der Satz von Noether -\label{buch:subsection:noether}} +%\subsection{Der Satz von Noether +%\label{buch:subsection:noether}} diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index ef1520e..8baa88c 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -10,7 +10,7 @@ In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen beschreibt, die mit vergleichbarer Amplitude sich über den ganzen -Graphen entsprechen. +Graphen erstrecken. Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen Knoten fast vollständig. diff --git a/buch/chapters/90-crypto/Makefile.inc b/buch/chapters/90-crypto/Makefile.inc index 9543ce1..508add5 100644 --- a/buch/chapters/90-crypto/Makefile.inc +++ b/buch/chapters/90-crypto/Makefile.inc @@ -8,5 +8,4 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/90-crypto/arith.tex \ chapters/90-crypto/ff.tex \ chapters/90-crypto/aes.tex \ - chapters/90-crypto/rs.tex \ chapters/90-crypto/chapter.tex diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex index dcc31b8..b05110f 100644 --- a/buch/chapters/90-crypto/arith.tex +++ b/buch/chapters/90-crypto/arith.tex @@ -91,6 +91,7 @@ Die Berechnung der Quadratwurzel lässt sich in Hardware effizient implementieren. \begin{algorithmus} +\label{buch:crypto:teile-und-hersche} Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$ Multiplikationen \begin{enumerate} diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex index 535b359..a1cb747 100644 --- a/buch/chapters/90-crypto/ff.tex +++ b/buch/chapters/90-crypto/ff.tex @@ -7,6 +7,15 @@ \section{Kryptographie und endliche Körper \label{buch:section:kryptographie-und-endliche-koerper}} \rhead{Kryptographie und endliche Körper} +In diesem Abschnitt soll illustriert werden, wie die Arithmetik in +endlichen Körpern Algorithmen zu konstruieren erlaubt, mit denen sich +zum Beispiel sehr effizient kryptographische Schlüssel aushandeln +lassen. +Der klassische Diffie-Hellmann-Algorithmus in einem Galois-Körper +$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:subsection:elliptische-kurven} +verallgemeinert auf eine sogenannte elliptische Kurve. +Diese Version des Algorithmus ist sehr effizient was die Bitlänge der +Schlüssel betrifft. \subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus \label{buch:subsection:potenzen-diskreter-logarithmus}} @@ -439,6 +448,7 @@ Das Polynom ist \[ p(t) = +XXX \] Nach Division durch $t(t-1)$ erhält man als den Quotienten \begin{align*} @@ -652,13 +662,44 @@ Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen abelschen Gruppe. \end{satz} -\subsubsection{Beispiele} -% XXX -TODO: elliptische Kurven in IPsec: Oakley Gruppen - \subsubsection{Diffie-Hellman in einer elliptischen Kurve} -% XXX -TODO: $g^x$ 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, +aus der sich mit dem +Algorithmus~\ref{buch:crypto:teile-und-hersche} eine effizienter +Potenzieralgorithmus konstruieren lässt. + +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/90-crypto/rs.tex b/buch/chapters/90-crypto/rs.tex deleted file mode 100644 index ec8ec8c..0000000 --- a/buch/chapters/90-crypto/rs.tex +++ /dev/null @@ -1,41 +0,0 @@ -% -% rs.tex -- Reed-Solomon-Code -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Fehlerkorrigierende Codes nach Reed-Solomon -\label{buch:section:reed-solomon}} -\rhead{Fehlerkorrigierende Codes} -Jede Art von Datenübertragung muss sich mit dem Problem der Fehler befassen, -die auf dem Übertragungskanal entstehen können. -Die einfachste Lösung dieses Problem versucht, Fehler zu erkennen und -dann eine erneute Übermittelung zu veranlassen. -Dies ist zum Beispiel bei der Datenübertragung von einer Raumsonde -wie Voyager~1 nicht möglich, die Signallaufzeit von der Sonde und wieder -zurück ist über 40 Stunden. -Es ist auch nicht sinnvoll beim Lesen eines optischen Mediums wie einer -CD oder DVD, wenn ein Fehler durch eine Beschädigung der Oberfläche -des Mediums verursacht wird. -Erneutes Lesen würde das Resultat auch nicht ändern. -Es wird also eine Möglichkeit gesucht, die Daten so zu codieren, dass -ein Fehler nicht nur erkannt sondern auch korrigiert werden kann. - -In diesem Abschnitt werden die algebraisch besonders interessanten -Reed-Solmon-Codes beschrieben. -Ihren ersten Einsatz hatten Sie bei den Voyager-Raumsonden, die 1977 -gestartet wurden. -Sie befinden sich im Moment in einer Entfernung von -Zum ersten mal kommerziell verwendet wurden sie für die optischen -Medien CD und DVD. - -% https://www.youtube.com/watch?v=uOLW43OIZJ0 -% https://www.youtube.com/watch?v=4BfCmZgOKP8 - -\subsection{Was ist ein Code? -\label{buch:subsection:was-ist-ein-code}} - -\subsection{Reed-Solomon-Code -\label{buch:subsection:reed-solomon-code}} - -\subsection{Decodierung -\label{buch:subsection:decodierung}} diff --git a/buch/chapters/95-homologie/Makefile.inc b/buch/chapters/95-homologie/Makefile.inc index 7e6f1e7..41b1569 100644 --- a/buch/chapters/95-homologie/Makefile.inc +++ b/buch/chapters/95-homologie/Makefile.inc @@ -8,7 +8,6 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/95-homologie/simplex.tex \ chapters/95-homologie/komplex.tex \ chapters/95-homologie/homologie.tex \ - chapters/95-homologie/mayervietoris.tex \ chapters/95-homologie/fixpunkte.tex \ chapters/95-homologie/chapter.tex diff --git a/buch/chapters/95-homologie/chapter.tex b/buch/chapters/95-homologie/chapter.tex index eaa56c4..994c400 100644 --- a/buch/chapters/95-homologie/chapter.tex +++ b/buch/chapters/95-homologie/chapter.tex @@ -38,7 +38,7 @@ Damit wird es möglich, das Dreieck vom Rand des Dreiecks zu unterschieden. \input{chapters/95-homologie/simplex.tex} \input{chapters/95-homologie/komplex.tex} \input{chapters/95-homologie/homologie.tex} -\input{chapters/95-homologie/mayervietoris.tex} +%\input{chapters/95-homologie/mayervietoris.tex} \input{chapters/95-homologie/fixpunkte.tex} diff --git a/buch/chapters/95-homologie/homologie.tex b/buch/chapters/95-homologie/homologie.tex index 2b80a17..905ecc3 100644 --- a/buch/chapters/95-homologie/homologie.tex +++ b/buch/chapters/95-homologie/homologie.tex @@ -6,13 +6,349 @@ \section{Homologie \label{buch:section:homologie}} \rhead{Homologie} +Die Idee der Trangulation ermöglicht, komplizierte geometrische +Objekte mit einem einfachen ``Gerüst'' auszustatten und so zu +analysieren. +Projiziert man ein mit einer Kugel konzentrisches Tetraeder auf die +Kugel, entsteht eine Triangulation der Kugeloberfläche. +Statt eine Kugel zu studieren, kann man also auch ein Tetraeder untersuchen. + +Das Gerüst kann natürlich nicht mehr alle Eigenschaften des ursprünglichen +Objektes wiedergeben. +Im Beispiel der Kugel geht die Information darüber, dass es sich um eine +glatte Mannigfaltigkeit handelt, verloren. +Was aber bleibt, sind Eigenschaften des Zusammenhangs. +Wenn sich zwei Punkte mit Wegen verbinden lassen, dann gibt es auch eine +Triangulation mit eindimensionalen Simplices, die diese Punkte als Ecken +enthalten, die sich in der Triangulation mit einer Folge von Kanten +verbinden lassen. +Algebraisch bedeutet dies, dass die beiden Punkte der Rand eines +Weges sind. +Fragen der Verbindbarkeit von Punkten mit Wegen lassen sich also +dadurch studieren, dass man das geometrische Objekt auf einen Graphen +reduziert. + +In diesem Abschnitt soll gezeigt werden, wie diese Idee auf höhere +Dimensionen ausgedehnt werden. +Es soll möglich werden, kompliziertere Fragen des Zusammenhangs, zum +Beispiel das Vorhandensein von Löchern mit algebraischen Mitteln +zu analysieren. \subsection{Homologie eines Kettenkomplexes \label{buch:subsection:homologie-eines-kettenkomplexes}} +Wegzusammenhang lässt sich untersuchen, indem man in der Triangulation +nach Linearkombinationen von Kanten sucht, die als Rand die beiden Punkte +haben. +Zwei Punkte sind also nicht verbindbar und liegen damit in verschiedenen +Komponenten, wenn die beiden Punkte nicht Rand irgend einer +Linearkombination von Kanten sind. +Komponenten können also identifiziert werden, indem man unter allen +Linearkombinationen von Punkten, also $C_0$ all diejenigen ignoriert, +die Rand einer Linearkombinationv on Kanten sind, also $\partial_1C_1$. +Der Quotientenraum $H_0=C_0/\partial_1C_1$ enthält also für jede Komponente +eine Dimension. + +Eine Dimension höher könnten wir danach fragen, ob sich ein geschlossener +Weg zusammenziehen lässt. +In der Triangulation zeichnet sich ein geschlossener Weg dadurch aus, +dass jedes Ende einer Kante auch Anfang einer Folgekante ist, dass also +der Rand der Linearkombination von Kanten 0 ist. +Algebraisch bedeutet dies, dass wir uns für diejenigen Linearkombinationen +$z\in C_1$ interessieren, die keinen Rand haben, für die also $\partial_1z=0$ +gilt. + +\begin{definition} +Die Elemente von +\[ +Z_k += +Z_k^C += +\{z\in C_k\;|\; \partial_k z = 0\} += +\ker \partial_k +\] +heissen die {\em ($k$-dimensionalen) Zyklen} von $C_*$. +\end{definition} + +In einem Dreieck ist der Rand ein geschlossener Weg, der sich zusammenziehen +lässt, indem man ihn durch die Dreiecksfläche deformiert. +Entfernt man aber die Dreiecksfläche, ist diese Deformation nicht mehr +möglich. +Einen zusammenziehbaren Weg kann man sich also als den Rand eines Dreiecks +einer vorstellen. +``Löcher'' sind durch geschlossene Wege erkennbar, die nicht Rand eines +Dreiecks sein können. +Wir müssen also ``Ränder'' ignorieren. + +\begin{definition} +Die Elemente von +\[ +B_k += +B_k^C += +\{\partial_{k+1}z\;|\; C_{k+1}\} += +\operatorname{im} \partial_{k+1} +\] +heissen die {\em ($k$-dimensionalen) Ränder} von $C_*$. +\end{definition} + +Algebraisch ausgedrückt interessieren uns also nur Zyklen, die selbst +keine Ränder sind. +Der Quotientenraum $Z_1/B_1$ ignoriert unter den Zyklen diejenigen, die +Ränder sind, drückt also algebraisch die Idee des eindimensionalen +Zusammenhangs aus. +Wir definieren daher + +\begin{definition} +Die $k$-dimensionale Homologiegruppe des Kettenkomplexes $C_*$ ist +\[ +H_k(C) = Z_k/B_k = \ker \partial_k / \operatorname{im} \partial_{k+1}. +\] +Wenn nur von einem Kettenkomplex die Rede ist, kann auch $H_k(C)=H_k$ +abgekürzt werden. +\end{definition} + +Die folgenden zwei ausführlichen Beispiele sollen zeigen, wie die +Homologiegruppe $H_2$ die Anwesenheit eines Hohlraumes detektieren kann, +der entsteht, wenn man aus einem Tetraeder das innere entfernt. + +\begin{beispiel} +\begin{figure} +\centering +XXX Bild eines Tetraeders mit Bezeichnung der Ecken und Kanten +\caption{Triangulation eines Tetraeders, die Orientierung von Kanten +und Seitenflächen ist immer so gewählt, dass die Nummern der Ecken +aufsteigend sind. +\label{buch:homologie:tetraeder:fig}} +\end{figure} +Ein Tetraeder ist ein zweidmensionales Simplex, wir untersuchen seinen +Kettenkomplex und bestimmen die zugehörigen Homologiegruppen. +Zunächst müssen wir die einzelnen Mengen $C_k$ beschreiben und verwenden +dazu die Bezeichnungen gemäss Abbildung~\ref{buch:homologie:tetraeder:fig}. +$C_0$ ist der vierdimensionale Raum aufgespannt von den vier Ecken +$0$, $1$, $2$ und $3$ des Tetraeders. +$C_1$ ist der sechsdimensionale Vektorraum der Kanten +\[ +k_0 = [0,1],\quad +k_1 = [0,2],\quad +k_2 = [0,3],\quad +k_3 = [1,2],\quad +k_4 = [1,3],\quad +k_5 = [2,3] +\] +Der Randoperator $\partial_1$ hat die Matrix +\[ +\partial_1 += +\begin{pmatrix*}[r] +-1&-1&-1& 0& 0& 0\\ + 1& 0& 0&-1&-1& 0\\ + 0& 1& 0& 1& 0&-1\\ + 0& 0& 1& 0& 1& 1 +\end{pmatrix*}. +\] + +Wir erwarten natürlich, dass sich zwei beliebige Ecken verbinden lassen, +dass es also nur eine Komponente gibt und dass damit $H_1=\Bbbk$ ist. +Dazu beachten wir, dass das Bild von $\partial_1$ genau aus den Vektoren +besteht, deren Komponentensumme $0$ ist. +Das Bild $B_0$ von $\partial_1$ ist daher die Lösungsmenge der einen +Gleichung +\( +x_0+x_1+x_2+x_3=0. +\) +Der Quotientenraum $H_0=Z_0/B_0 = C_0/\operatorname{im}\partial_1$ +ist daher wie erwartet eindimensional. + +Wir bestimmen jetzt die Homologiegruppe $H_1$. +Da sich im Tetraeder jeder geschlossene Weg zusammenziehen lässt, +erwarten wir $H_1=0$. + +Die Menge der Zyklen $Z_1$ wird bestimmt, indem man die Lösungsmenge +des Gleichungssystems $\partial_1z=0$ bestimmt. +Der Gauss-Algorithmus für die Matrix $\partial_1$ liefert das +Schlusstableau +\[ +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline +k_0&k_1&k_2&k_3&k_4&k_5\\ +\hline + 1& 0& 0& -1& -1& 0\\ + 0& 1& 0& 1& 0& -1\\ + 0& 0& 1& 0& 1& 1\\ + 0& 0& 0& 0& 0& 0\\ +\hline +\end{tabular} +\] +Daraus lassen sich drei linear unabhängig eindimensionale Zyklen ablesen, +die zu den Lösungsvektoren +\[ +z_1 += +\begin{pmatrix*}[r] +1\\ +-1\\ +0\\ +1\\ +0\\ +0 +\end{pmatrix*}, +\qquad +z_2 += +\begin{pmatrix*}[r] +1\\ +0\\ +-1\\ +0\\ +1\\ +0 +\end{pmatrix*}, +\qquad +z_3 += +\begin{pmatrix*}[r] +0\\ +1\\ +-1\\ +0\\ +0\\ +1 +\end{pmatrix*} +\] +gehören. + +$C_2$ hat die vier Seitenflächen +\[ +f_0=[0,1,2],\quad +f_1=[0,1,3],\quad +f_2=[0,2,3],\quad +f_3=[1,2,3] +\] +als Basis. +Der zweidimensionale Randoperator ist die $6\times 4$-Matrix +\[ +\partial_2 += +\begin{pmatrix*}[r] + 1& 1& 0& 0\\ +-1& 0& 1& 0\\ + 0&-1&-1& 0\\ + 1& 0& 0& 1\\ + 0& 1& 0&-1\\ + 0& 0& 1& 1 +\end{pmatrix*}. +\] +Man kann leicht nachrechnen, dass $\partial_1\partial_2=0$ ist, wie es +für einen Kettenkomplex sein muss. + +Um nachzurechnen, dass die Homologiegruppe $H_1=0$ ist, müssen wir jetzt +nachprüfen, ob jeder Zyklus in $Z_1$ auch Bild der Randabbildung $\partial_2$ +ist. +Die ersten drei Spalten von $\partial_2$ sind genau die drei Zyklen +$z_1$, $z_2$ und $z_3$. +Insbesondere lassen sich alle Zyklen als Ränder darstellen, die +Homologiegruppe $H_1=0$ verschwindet. + +Die Zyklen in $C_2$ sind die Lösungen von $\partial_2z=0$. +Der Gauss-Algorithmus für $\partial_2$ liefert das -Tableau +\[ +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline +f_0&f_1&f_2&f_3\\ +\hline +1&0&0& 1\\ +0&1&0&-1\\ +0&0&1& 1\\ +0&0&0& 0\\ +0&0&0& 0\\ +0&0&0& 0\\ +\hline +\end{tabular} +\] +Daraus liest man ab, dass es genau einen Zyklus nämlich +\[ +z += +\begin{pmatrix} +-1\\1\\-1\\1 +\end{pmatrix} +\] +$Z_2$ besteht also aus Vielfachen des Vektors $z$. + +Da es nur ein zweidimensionales Simplex gibt, ist $C_3$ eindimensional. +Die Randabbildung $\partial_3$ hat die Matrix +\[ +\partial_3 += +\begin{pmatrix} +1\\ +-1\\ +1\\ +-1 +\end{pmatrix}. +\] +Die Zyklen $Z_2$ und die Ränder $B_2$ bilden also dieselbe Menge, auch +die Homologie-Gruppe $H_2$ ist $0$. + +Da es keine vierdimensionalen Simplizes gibt, ist $B_3=0$. +Die Zyklen $Z_3$ bestehen aus den Lösungen von $\partial_3w=0$, da +aber $\partial_3$ injektiv ist, ist $Z_3=0$. +Daher ist auch $H_3=0$. +\end{beispiel} + +\begin{beispiel} +Für dieses Beispiel entfernen wir das Innere des Tetraeders, es entsteht +ein Hohlraum. +Am Kettenkomplex der Triangulation ändert sich nur, dass $C_3$ jetzt +nur noch den $0$-Vektor enthält. +Das Bild $B_2=\operatorname{im}\partial_3$ wird damit auch $0$-dimensional, +während es im vorigen Beispiel eindimensional war. +Die einzige Änderung ist also in der Homologiegruppe +$H_2 = Z_2/B_2 = Z_2 / \{0\} \simeq \Bbbk$. +Die Homologiegruppe $H_2$ hat jetzt Dimension $1$ und zeigt damit den +Hohlraum an. +\end{beispiel} \subsection{Induzierte Abbildung \label{buch:subsection:induzierte-abbildung}} +Früher haben wurde eine Abbildung $f_*$ zwischen Kettenkomplexen $C_*$ und +$D_*$ so definiert, +dass sie mit den Randoperatoren verträglich sein muss. +Diese Forderung bewirkt, dass sich auch eine lineare Abbildung +\[ +H_k(f) \colon H_k(C) \to H_k(D) +\] +zwischen den Homologiegruppen ergibt, wie wir nun zeigen wollen. + +Um eine Abbildung von $H_k(C)$ nach $H_k(D)$ zu definieren, müssen wir +zu einem Element von $H_k(C)$ ein Bildelement konstruieren. +Ein Element in $H_k(C)$ ist eine Menge von Zyklen in $Z^C_k$, die sich +nur um einen Rand in $B_k$ unterscheiden. +Wir wählen also einen Zyklus $z\in Z_k$ und bilden ihn auf $f_k(z)$ ab. +Wegen $\partial^D_kf(z)=f\partial^C_kz = f(0) =0 $ ist auch $f_k(z)$ +ein Zyklus. +Wir müssen jetzt aber noch zeigen, dass eine andere Wahl des Zyklus +das gleiche Element in $H_k(D)$ ergibt. +Dazu genügt es zu sehen, dass sich $f(z)$ höchstens um einen Rand +ändert, wenn man $z$ um einen Rand ändert. +Sei also $b\in B^C_k$ ein Rand, es gibt also ein $w\in C_{k+1}$ mit +$\partial^C_{k+1}w=b$. +Dann gilt aber auch +\[ +f_k(z+b) += +f_k(z) + f_k(b) += +f_k(z) + f_k(\partial^C_{k+1}w) += +f_k(z) + \partial^D_{k+1}(f_k(w)). +\] +Der letzte Term ist ein Rand in $D_k$, somit ändert sich $f_k(z)$ nur +um diesen Rand, wenn man $z$ um einen Rand ändert. +$f_k(z)$ und $f_k(z+b)$ führen auf die selbe Homologieklasse. -\subsection{Homologie eines simplizialen Komplexes -\label{buch:subsection:simplizialekomplexe}} diff --git a/buch/chapters/95-homologie/komplex.tex b/buch/chapters/95-homologie/komplex.tex index 6dd8efb..fa2d8e1 100644 --- a/buch/chapters/95-homologie/komplex.tex +++ b/buch/chapters/95-homologie/komplex.tex @@ -6,9 +6,105 @@ \section{Kettenkomplexe \label{buch:section:komplex}} \rhead{Kettenkomplexe} +Die algebraische Struktur, die in Abschnitt~\ref{buch:subsection:triangulation} +konstruiert wurde, kann noch etwas abstrakter konstruiert werden. +Es ergibt sich das Konzept eines Kettenkomplexes. +Die Triangulation gibt also Anlass zu einem Kettenkomplex. +So lässt sich zu einem geometrischen Objekt ein algebraisches +Vergleichsobjekt konstruieren. +Im Idealfall lassens ich anschliessend geometrische Eigenschaften mit +algebraischen Rechnungen zum Beispiel in Vektorräumen mit Matrizen +beantworten. -\subsection{Randoperator von Simplexen -\label{buch:subsection:randoperator-von-simplexen}} +\subsection{Definition +\label{buch:subsection:kettenkomplex-definition}} +Die Operation $\partial$, die für Simplizes konstruiert worden ist, +war linear und hat die Eigenschaft $\partial^2$ gehabt. +Diese Eigenschaften reichen bereits für Definition eines Kettenkomplexes. + +\begin{definition} +Eine Folge $C_0,C_1,C_2,\dots$ von Vektorräumen über dem Körper $\Bbbk$ +mit einer Folge von linearen Abbildungen +$\partial_k\colon C_k \to C_{k-1}$, dem {\em Randoperator}, +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 +Abschnitt~\ref{buch:subsection:triangulation} bilden einen +Kettenkomplex. + +XXX nachrechnen: $\partial^2 = 0$ ? + +\subsection{Abbildungen +\label{buch:subsection:abbildungen}} +Wenn man verschiedene geometrische Objekte mit Hilfe von Triangulationen +vergleichen will, dann muss man auch das Konzept der Abbildungen zwischen +den geometrischen Objekten in die Kettenkomplexe transportieren. + +Eine Abbildung zwischen Kettenkomplexen muss einerseits eine lineare +Abbildung der Vektorräume $C_k$ sein, andererseits muss sich eine +solche Abbildung mit dem Randoperator vertragen. +Wir definieren daher + +\begin{definition} +Eine Abbildung $f_*$ zwischen zwei Kettenkomplexe $(C_*,\partial^C_*)$ und +$(D_*,\partial^D_*)$ heisst eine Abbildung von Kettenkomplexen, wenn +für jedes $k$ +\begin{equation} +\partial^D_k +\circ +f_{k} += +f_{k+1} +\circ +\partial^C_k +\label{buch:komplex:abbildung} +\end{equation} +gilt. +\end{definition} + +Die Beziehung~\eqref{buch:komplex:abbildung} kann übersichtlich als +kommutatives Diagramm dargestellt werden. +\begin{equation} +\begin{tikzcd} +0 + & C_0 \arrow[l, "\partial_0^C"] + \arrow[d, "f_0"] + & C_1 \arrow[l,"\partial_1^C"] + \arrow[d, "f_1"] + & C_2 \arrow[l,"\partial_2^C"] + \arrow[d, "f_2"] + & \dots \arrow[l] + \arrow[l, "\partial_{k-1}^C"] + & C_k + \arrow[l, "\partial_k^C"] + \arrow[d, "f_k"] + & C_{k+1}\arrow[l, "\partial_{k+1}^C"] + \arrow[d, "f_{k+1}"] + & \dots +\\ +0 + & D_0 \arrow[l, "\partial_0^D"] + & D_1 \arrow[l,"\partial_1^D"] + & D_2 \arrow[l,"\partial_2^D"] + & \dots \arrow[l] + \arrow[l, "\partial_{k-1}^D"] + & D_k + \arrow[l, "\partial_k^D"] + & D_{k+1}\arrow[l, "\partial_{k+1}^D"] + & \dots +\end{tikzcd} +\label{buch:komplex:abbcd} +\end{equation} +Die Relation~\eqref{buch:komplex:abbildung} drückt aus, dass man jeden +den Pfeilen im Diagram~\eqref{buch:komplex:abbcd} folgen kann und +dabei zwischen zwei Vektorräumen unabhängig vom Weg die gleiche Abbildung +resultiert. + +Die Verfeinerung einer Triangulation erzeugt eine solche Abbildung von +Komplexen. + + +% XXX simpliziale Approximation -\subsection{Kettenkomplexe und Morphismen -\label{buch:subsection:kettenkomplex}} diff --git a/buch/chapters/95-homologie/simplex.tex b/buch/chapters/95-homologie/simplex.tex index 5ca2ca8..397ba07 100644 --- a/buch/chapters/95-homologie/simplex.tex +++ b/buch/chapters/95-homologie/simplex.tex @@ -233,6 +233,6 @@ Vorzeichen zu, die Matrix ist \subsection{Triangulation -\label{buch:subsection:}} +\label{buch:subsection:triangulation}} diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index a5d0201..977bf81 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -20,6 +20,12 @@ keywords = "World Wide Web, Search engines, Information retrieval, PageRank, Goo abstract = "In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24 million pages is available at http://google.stanford.edu/ To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of Web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the Web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and Web proliferation, creating a Web search engine today is very different from three years ago. This paper provides an in-depth description of our large-scale Web search engine — the first such detailed public description we know of to date. Apart from the problems of scaling traditional search techniques to data of this magnitude, there are new technical challenges involved with using the additional information present in hypertext to produce better search results. This paper addresses this question of how to build a practical large-scale system which can exploit the additional information present in hypertext. Also we look at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want." } +@book{buch:linalg, + title = {Lineare Algebra}, + author = {Andreas M"uller}, + url = {https://github.com/AndreasFMueller/LinAlg.git}, + year = {2010} +} @book{buch:mathsem-wavelets, title = {Mathematisches Seminar Wavelets}, @@ -33,6 +39,13 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc year = {2016}, } +@online{buch:rfc2409, + title = {The Internet Key Exchange (IKE)}, + author = { D. Harkins and D. Carrel}, + url = {https://datatracker.ietf.org/doc/html/rfc2409}, + year = {1998} +} + @online{buch:fftw, title = {Fastest Fourier Transform in the West}, url = {http://www.fftw.org/}, |