diff options
Diffstat (limited to 'buch')
35 files changed, 1013 insertions, 402 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/}, diff --git a/buch/papers/munkres/figures/Matrixdarstellung.png b/buch/papers/munkres/figures/Matrixdarstellung.png Binary files differnew file mode 100644 index 0000000..91a376d --- /dev/null +++ b/buch/papers/munkres/figures/Matrixdarstellung.png diff --git a/buch/papers/munkres/main.tex b/buch/papers/munkres/main.tex index 8915a3d..e5282dc 100644 --- a/buch/papers/munkres/main.tex +++ b/buch/papers/munkres/main.tex @@ -3,8 +3,8 @@ % % (c) 2020 Hochschule Rapperswil % -\chapter{Munkres-Algorithmus\label{chapter:munkres}} -\lhead{Munkres-Algorithmus} +\chapter{Das Zuordnungsproblem und der Munkres-Algorithmus\label{chapter:munkres}} +\lhead{Das Zuordnungsproblem und der Munkres-Algorithmus} \begin{refsection} \chapterauthor{Marc Kühne} diff --git a/buch/papers/munkres/teil0.tex b/buch/papers/munkres/teil0.tex index 1ef0538..0578429 100644 --- a/buch/papers/munkres/teil0.tex +++ b/buch/papers/munkres/teil0.tex @@ -3,19 +3,8 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Geschichte\label{munkres:section:teil0}} -\rhead{Geschichte} -Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht. -Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus -weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker -basierte: Dénes Kőnig und Jenő Egerváry. -James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest, -dass der Algorithmus (stark) polynomiell ist. -Seitdem ist der Algorithmus auch als Kuhn-Munkres oder -Munkres-Zuordnungsalgorithmus bekannt. -Die Zeitkomplexität des ursprünglichen Algorithmus war $O(n^4)$, -später wurde zudem festgestellt, dass er modifiziert werden kann, -um eine $O(n^3)$-Laufzeit zu erreichen. - - +\section{Einleitung\label{munkres:section:teil0}} +\rhead{Einleitung} +Im Bereich der Unternehmensplanung (Operations Research) gibt es verschiedene Fragestellungen. Eine davon ist das sogenannte Transportproblem. Zum Transport einheitlicher Objekte von mehreren Angebots- zu mehreren Nachfrageorten ist ein optimaler, d. h. kostenminimaler Plan zu finden, wobei die vorhandenen und zu liefernden Mengen an den einzelnen Standorten gegeben sowie die jeweiligen Transportkosten pro Einheit zwischen allen Standorten bekannt sind. +Nun gibt es im Bereich des klassischen Transportproblems Sonderfälle. Ein Sonderfall ist z.B. das Zuordnungsproblem. diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 7cbbbfd..c13732c 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -3,19 +3,56 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Was ist die ungarische Methode? +\section{Beschrieb des Zuordnungsproblems \label{munkres:section:teil1}} \rhead{Problemstellung} -Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem -in polynomieller Zeit löst. -\begin{itemize} -\item -Polynom = vielgliedrig -\end{itemize} -Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms -wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. -Mit der ungarischen Methode können also lineare Optimierungsprobleme gelöst -werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. -Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so -optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der -Gesamtgewinn maximiert werden kann. + +Das spezielle an einem Zuordnungsproblem ist, dass es an jedem Ort nur eine Einheit angeboten bzw. nachgefragt wird. Es werden hier nicht Mengen möglichst kostenminimal von einem zum anderen +Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.B. Personen, oder Bau-Materialien auf bestimmte Orte, Stellen oder Aufgaben. +Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde der Munkres-Algorithmus, auch die Ungarische Methode genannt, entwickelt. Diese Methode ist ein weiteres Hauptthema dieses Kapitels. + +\subsection{Zuordnungsproblem an einem konkreten Beispiel +\label{munkres:subsection:bonorum}} + +\subsection{Zuordnungsproblem abstrakt +\label{munkres:subsection:bonorum}} + +Es sind alle Angebots- und Bedarfsmengen gleich 1 +\begin{equation} +a_{i}=b_{j}=1 +\end{equation} + +\subsection{alternative Darstellungen des Zuordnungsproblems +\label{munkres:subsection:bonorum}} +\begin{equation} +Netzwerk +\end{equation} +\begin{equation} +Matrix +\end{equation} +\begin{equation} +Bitpartiter Graph +\end{equation} +Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen +zwischen den Elementen zweier Mengen. +Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» +\begin{figure} +\centering +\includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung} +\caption{Typische Netzwerkdarstellung eines Zuordnungsproblems.} +\label{munkres:Vr2} +\end{figure} + +\begin{figure} +\centering +\includegraphics[width=5cm]{papers/munkres/figures/Matrixdarstellung} +\caption{Typische 4x4 Matrixdarstellung eines Zuordnungsproblems.} +\label{munkres:Vr2} +\end{figure} + +\begin{figure} +\centering +\includegraphics[width=5cm]{papers/munkres/figures/bipartiter_graph} +\caption{$K_{3,3}$ vollständig bipartiter Graph mit 3 Knoten pro Teilmenge.} +\label{munkres:Vr2} +\end{figure} diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex index 29db8d7..9a44cd4 100644 --- a/buch/papers/munkres/teil2.tex +++ b/buch/papers/munkres/teil2.tex @@ -3,86 +3,11 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Das Zuordnungsproblem +\section{Schwierigkeit der Lösung (Permutationen) \label{munkres:section:teil2}} -\rhead{Das Zuordnungsproblem} -Das (lineare) Zuordnungsproblem ist ein diskretes Optimierungsproblem aus -der Graphentheorie. -Es handelt sich um einen Spezialfall eines maximalen Matchings -minimalen Gewichtes in einem bipartiten, gewichteten Graphen +\rhead{Schwierigkeit der Lösung (Permutationen)} -Vereinfacht gesagt sind Zuordnungsprobleme spezielle Transportprobleme. -Der Unterschied zu klassischen Transportproblemen liegen darin, -dass hier nicht Mengen möglichst kostenminimal von einem zum anderen -Ort transportiert werden sollen, sondern es geht um die kostenminimale -Zuordnung von z.~B.~Personen, oder Bau-Materialien auf bestimmte -Orte, Stellen oder Aufgaben. -Dabei sind alle Angebots- und Bedarfsmenge gleich 1 -\begin{equation} -a_{i}=b_{j}=1 -\end{equation} +Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine maximale Zuordnung (maximales Matching) gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. -\subsection{Zuordnungsproblem in Netzwerkdarstellung -\label{munkres:subsection:bonorum}} - -\begin{figure} -\centering -\includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung} -\caption{Typische Netzwerkdarstellung eines Zuordnungsproblems.} -\label{munkres:Vr2} -\end{figure} - -\subsection{Matrix Formulierung -\label{munkres:subsection:bonorum}} -In der Matrixformulierung ist eine nicht-negative $n\times n$-Matrix -gegeben, wobei das Element in der $i$-ten Zeile und $j$-ten Spalte -die Kosten für die Zuweisung des $j$-ten Jobs an den $i$-ten Arbeiter -darstellt. -Wir müssen eine Zuordnung der Jobs zu den Arbeitern finden, so dass -jeder Job einem Arbeiter zugewiesen wird und jeder Arbeiter einen -Job zugewiesen bekommt, so dass die Gesamtkosten der Zuordnung -minimal sind. -Dies kann als Permutation der Zeilen und Spalten einer Kostenmatrix -$C$ ausgedrückt werden, um die Spur einer Matrix zu minimieren: -\begin{equation} -\min(L,R)Tr (LCR) -\end{equation} -wobei $L$ und $R$ Permutationsmatrizen sind. -Wenn das Ziel ist, die Zuordnung zu finden, die die maximalen Kosten -ergibt, kann das Problem durch Negieren der Kostenmatrix $C$ gelöst -werden. - -\subsection{Suche der optimalen Lösung -\label{munkres:subsection:bonorum}} -Ist eine maximale Zuordnung (maximales Matching) gefunden, so steht -in jeder Zeile und jeder Spalte der Matrix genau ein Element, das -zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird -auch als Transversale der Matrix bezeichnet. -Deshalb kann die Problemstellung auch anders formuliert werden: Man -ordne die Zeilen- oder die Spaltenvektoren so um, dass die Summe -der Elemente in der Hauptdiagonale maximal wird. -Hieraus wird sofort ersichtlich, dass es in einer -$n\times n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- -bzw.~Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen -gibt, also $n!$. -Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale -Lösung durch Berechnung aller Möglichkeiten zu finden. -Schon bei einer $10\times 10$-Matrix gibt es nahezu 3,63 Millionen (3.628.800) -zu berücksichtigender Permutationen. - -\subsection{Formulierung Bipartiter Graph -\label{munkres:subsection:bonorum}} -Der Algorithmus ist einfacher zu beschreiben, wenn wir das Problem -anhand eines bipartiten Graphen formulieren. -Wir haben einen vollständigen zweistufigen Graphen $G=(S,T;E)$ mit -$n$ Arbeiter-Eckpunkten ($S$) und $n$ Job-Scheitelpunkte ($T$), und -jede Kante hat einen nichtnegativen Preis $c(i,j)$. -Wir wollen ein perfektes Matching mit minimalen Gesamtkosten finden. - -\begin{figure} -\centering -\includegraphics[width=5cm]{papers/munkres/figures/bipartiter_graph} -\caption{$K_{3,3}$ vollständig bipartiter Graph mit 3 Knoten pro Teilmenge.} -\label{munkres:Vr2} -\end{figure} +Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer n×n-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von n Elementen gibt, also n!. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigender Permutationen. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 806cd83..cd47c92 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -3,102 +3,44 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Der Algorithmus in Form von bipartiten Graphen +\section{Der Munkres-Algorithmus (Ungarische Methode) \label{munkres:section:teil3}} -\rhead{Der Algorithmus in Form von bipartiten Graphen} -Mit der ungarischen Methode können also lineare Optimierungsprobleme -gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen -entstehen. +\rhead{Der Munkres-Algorithmus (Ungarische Methode)} -Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen -so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der -Gesamtgewinn maximiert werden kann. +Mit der ungarischen Methode können also lineare Optimierungsprobleme gelöst +werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. +Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so +optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der +Gesamtgewinn maximiert werden kann. -Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen -zwischen den Elementen zweier Mengen. -Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» - -\subsection{Beweis, dass der Algorithmus Fortschritte macht +\subsection{Geschichte \label{munkres:subsection:malorum}} -Wir müssen zeigen, dass der Algorithmus, solange das Matching nicht -die maximal mögliche Größe hat, immer in der Lage ist, Fortschritte -zu machen --- das heißt, entweder die Anzahl der übereinstimmenden -Kanten zu erhöhen oder mindestens eine Kante zu straffen. -Es genügt zu zeigen, dass bei jedem Schritt mindestens eine der -folgenden Bedingungen erfüllt ist: - -\begin{itemize} -\item -$M$ die maximal mögliche Größe. -\item -$Gy$ enthält einen Erweiterungspfad. -\item -$G$ enthält einen losen Pfad: einen Pfad von einem Knoten in $Rs$ -zu einem Knoten in $T$ / $Z$ die aus einer beliebigen Anzahl von -festen Kanten, gefolgt von einer einzelnen losen Kante, besteht. -Die freie Kante einer freien Bahn ist also $Z$ (beinhaltet $T$), -so garantiert es, dass Delta gut definiert ist. -\end{itemize} -Wenn $M$ die maximal mögliche Größe hat, sind wir natürlich fertig. -Andernfalls muss es nach Berges Lemma im zugrundeliegenden Graphen -$G$ einen Augmentierungspfad $P$ in Bezug auf $M$ geben. -Dieser Pfad darf jedoch nicht in $G_y$ existieren: Obwohl jede -geradzahlige Kante in $P$ durch die Definition von $M$ fest ist, -können ungeradzahlige Kanten lose sein und in $G_y$ fehlen. -Ein Endpunkt von $P$ liegt in $R_{S}$, der andere in $R_T$; w.l.o.g., -nehmen Sie an, es beginnt in $R_{S}$. -Wenn jede Kante von $P$ dicht ist, dann bleibt sie ein augmentierender -Pfad in $G_y$ und wir sind fertig. -Andernfalls sei $uv$ die erste lose Kante auf $P$. -Wenn $v$ kein Element von $Z$ ist, dann haben wir einen losen Pfad -gefunden und sind fertig. -Andernfalls ist $v$ von irgendeinem anderen Pfad $Q$ aus festen -Kanten von einem Knoten in $R_{S}$ erreichbar. -Sei $P_{v}$ der Teilpfad von $P$, der bei $v$ beginnt und bis zum -Ende reicht, und sei $P'$ der Pfad, der gebildet wird, indem man -entlang $Q$ gebildet wird, bis ein Scheitelpunkt auf $P_{v}$ erreicht -wird, und dann weiter bis zum Ende von $P_{v}$. -Beachten Sie, dass $P'$ ein erweiternder Pfad in $G$ mit mindestens -einer losen Kante weniger als $P$ ist. -$P$ kann durch $P'$ ersetzt und dieser Argumentationsprozess iteriert -werden (formal, unter Verwendung von Induktion auf die Anzahl der -losen Kanten), bis entweder ein erweiternder Pfad in $G_y$ oder ein -losender Pfad in $G$ gefunden wird. +Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht. +Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus +weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker +basierte: Dénes Kőnig und Jenő Egerváry. +James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest, +dass der Algorithmus (stark) polynomiell ist. +Seitdem ist der Algorithmus auch als Kuhn-Munkres oder +Munkres-Zuordnungsalgorithmus bekannt. +Die Zeitkomplexität des ursprünglichen Algorithmus war $O(n^4)$, +später wurde zudem festgestellt, dass er modifiziert werden kann, +um eine $O(n^3)$-Laufzeit zu erreichen. -\subsection{Beweis, dass die Anpassung des Potentials $y$ $M$ unverändert lässt +\subsection{Besondere Leistung der Ungarischen Methode \label{munkres:subsection:malorum}} -Um zu zeigen, dass jede Kante in $M$ nach der Anpassung von $y$ -erhalten bleibt, genügt es zu zeigen, dass für eine beliebige Kante -in $M$ entweder beide Endpunkte oder keiner von ihnen in $Z$ liegen. -Zu diesem Zweck sei $vu$ eine Kante in $M$ von $T$ nach $S$. -Es ist leicht zu sehen, dass wenn $v$ in $Z$ ist, dann muss auch -$u$ in $Z$ sein, da jede Kante in $M$ dicht ist. -Nehmen wir nun an, dass $u$ kein Element von $Z$ und auch $v$ kein -Element von $Z$ ist. -$u$ selbst kann nicht in $R_{S}$ sein, da es der Endpunkt einer -angepassten Kante ist, also muss es einen gerichteten Pfad von engen -Kanten von einem Knoten in $R_{S}$ zu $u$ geben. -Dieser Pfad muss $v$ vermeiden, da es per Annahme nicht in $Z$ ist, -also ist der Knoten, der $u$ in diesem Pfad unmittelbar vorausgeht, -ein anderer Knoten $v$ (ein Element von $T$) und $v$ ein Element -von $u$ ist eine enge Kante von $T$ nach $S$ und ist somit in $M$. -Aber dann enthält $M$ zwei Kanten, die den Knoten $u$ teilen, was -der Tatsache widerspricht, dass $M$ ein Matching ist. -Jede Kante in $M$ hat also entweder beide Endpunkte oder keinen -Endpunkt in $Z$. +Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem +in polynomieller Zeit löst. +Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms +wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. + -\subsection{Beweis, dass $y$ ein Potential bleibt +\subsection{Beispiel eines händischen Verfahrens \label{munkres:subsection:malorum}} -Um zu zeigen, dass y nach der Anpassung ein Potenzial bleibt, genügt -es zu zeigen, dass keine Kante ihr Gesamtpotenzial über ihre Kosten -hinaus erhöht. -Dies ist für Kanten in $M$ bereits durch den vorangegangenen Absatz -bewiesen. -Man betrachtet also eine beliebige Kante $uv$ von $S$ nach $T$. -Wenn $y(u)$ erhöht wird um $\Delta$, dann wird entweder $v\in -\mathbb{Z}_n$ in diesem Fall wird $y(v)$ verringert um $\Delta$, -wobei das Gesamtpotenzial der Kante unverändert bleibt, oder $v\in -T\setminus Z$, wobei die Definition von $\Delta$ garantiert, dass -$y(u)+y(v)+\Delta \le c(u,v)$ -Also $y$ bleibt ein Potential. +\begin{figure} +\centering +\includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres} +\caption{Händisches Beispiel des Munkres Algorithmus.} +\label{munkres:Vr2} +\end{figure} diff --git a/buch/papers/munkres/teil4.tex b/buch/papers/munkres/teil4.tex index 3d76743..9a27227 100644 --- a/buch/papers/munkres/teil4.tex +++ b/buch/papers/munkres/teil4.tex @@ -3,34 +3,7 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Matrix-Interpretation +\section{- \label{munkres:section:teil4}} -\rhead{Matrix-Interpretation} -Gegeben ist die quadratische Matrix $C=(c_{ij})$ der Grösse $n\times n$. -Ohne Beschränkung der Allgemeinheit werden eine Zuordnung $j -\rightarrow s_j$, $j = 1, \dots, n$ mit minimaler Gesamtsumme -$\sum_{j=1}^{n}c_{s_j,j}$ gesucht, wobei die $s_j$ eine Permutation -von $\{1,\ldots ,n\}$ sind. -Soll die Summe maximiert werden, dann kann $C$ durch $-C$ ersetzt werden. -Die Grundlage dieses Verfahrens ist, dass sich die optimale Zuordnung -unter bestimmten Änderungen der Matrix nicht ändert, sondern nur -der Optimalwert. -Diese Änderungen sind durch Knotenpotentiale bzw.~duale Variablen -\begin{equation} -u_1 u_2,{\dots}, u_n -\end{equation} +\rhead{-} -für die Zeilen und - -\begin{equation}v_1,v_2,\dots,v_n \end{equation} fuer die Spalten angegeben. -Die modifizierte Matrix hat dann die Komponenten $\tilde{c}_{i,j} -= c_{ij} - u_j - v_j$. - -In der Summe über jede kantenmaximale Zuordnung kommt jedes -Knotenpotential genau einmal vor, so dass die Änderung der Zielfunktion -eine Konstante ist. -Sind die Einträge von $C$ nichtnegativ, und sind alle Knotenpotentiale -ebenfalls nichtnegativ, so nennt man die modifizierte Matrix \~{C} -auch eine Reduktion. -Ziel ist, in der reduzierten Matrix möglichst viele Komponenten auf -den Wert Null zu bringen und unter diesen die Zuordnung zu konstruieren. diff --git a/buch/papers/munkres/teil5.tex b/buch/papers/munkres/teil5.tex index f8138f4..b938c50 100644 --- a/buch/papers/munkres/teil5.tex +++ b/buch/papers/munkres/teil5.tex @@ -3,12 +3,6 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Ungarische Methode anhand eines Beispiels +\section{- \label{munkres:section:teil5}} -\rhead{Ungarische Methode anhand eines Beispiels} -\begin{figure} -\centering -\includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres} -\caption{Händisches Beispiel des Munkres Algorithmus.} -\label{munkres:Vr2} -\end{figure} +\rhead{-} diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex index c03b1a4..b9b1d69 100644 --- a/buch/papers/reedsolomon/anwendungen.tex +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -7,21 +7,20 @@ \label{reedsolomon:section:anwendung}} \rhead{Anwendungen} -In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie Funktionieren. +In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie funktionieren. In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt. -Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode an diese Daten zu kommen als über diesen Kanal. +Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode, an diese Daten zu kommen, als über diesen Kanal. - -In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpakete diese einfach noch einmal inert wenigen Millisekunden angefordert werden können. +In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpaketen diese einfach noch einmal innert wenigen Millisekunden angefordert werden können. In der Raumfahrt ist dies nicht möglich, da aufgrund der beschränkten Speichermöglichkeit die gesammelten Daten so rasch wie möglich zur Erde gesendet werden. Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen. Fehlerhafte Daten kann also auf Grund der Zeitverzögerung nicht mehr angefordert werden. -Bei CDs oder DVDs gibt es zwar kein Zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. +Bei CDs oder DVDs gibt es zwar kein zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden muss, so wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. -Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. +Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. %Wie man sieht, eignen sich Reed-Solomon-Codes vor allem für Anwendungen, bei der die Informationen nicht auf einen Anderen Weg beschafft werden kann. % @@ -33,7 +32,6 @@ Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch g % da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. % - Obwohl alle diese Codes nach dem gleichen Prinzip arbeiten gibt es starke Unterschiede in deren Funktionsweise. Dies kommt vor allem daher, da die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitstellt wird, auf denen die Codes implementiert wurden. Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um möglichst effizient zu arbeiten. @@ -75,8 +73,14 @@ Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie ers Codiert. Der Nachrichtenblock hat somit eine Länge von $255$ Zahlen, wovon $233$ als Nutzlast zur Verfügung stehen. Damit ist es möglich bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. -Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, Funktioniert aber nach einem ganz anderen Prinzip. -Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert. +Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. +Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, +Codiert seine Information aber auf eine andere weise. Aus jedem unterteilten Block wird vor dem Versenden ein Paritätsbit erzeugt und dem Block angehängt. Anhand diesem Paritätsbit überprüft der Empfänger, ob bei der Übertragung der Block beschädigt wurde. Ist dies der Fall, wird der Block bei der Decodierung nicht beachtet. Diese so entstandenen ``Lücken'' im Datenstrom werden wiederum vom Reed-Solomon-Code korrigiert. Dieses Zusammenspiel beider Codes garantiert so eine hohe Robustheit gegenüber Übertragungsfeher. + +% +% Funktioniert aber nach einem ganz anderen Prinzip. +% +%Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert. % %Dabei steht die Zahl 255 für grösse des Nachrichtenblocks, der die Anzahl 233 % @@ -107,13 +111,18 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb \begin{figure} \centering - \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Compact_Disc} - \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das ``einbrennen'' von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} + \subfigure[]{ + \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc} + } + \subfigure[]{ + \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc_zoomed_in} + } + \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das Einpressen oder Einbrennen von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} \label{fig:cd} \end{figure} \subsection{QR-Codes} -Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die Physische Grösse eines Codes ist stark abhängig von der Grösse der Codierung sowie dem Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. +Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die physische Grösse eines Codes ist stark abhängig von der Menge an codierten Daten sowie dem verwendeten Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. % @@ -154,6 +163,6 @@ Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen \subfigure[]{ \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} } - \caption{Während (a) noch ein unveränderter QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich dadurch die Fehlerkorrekturfähigkeit je nach grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} + \caption{Während (a) noch einen unveränderten QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich die Fehlerkorrekturfähigkeit je nach Grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} \label{fig:designqr} \end{figure}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png Binary files differnew file mode 100644 index 0000000..69556d0 --- /dev/null +++ b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index 327d01a..017fe94 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -29,6 +29,7 @@ \nocite{reedsolomon:voyager} \nocite{reedsolomon:cd_wiki} \nocite{reedsolomon:cd} +\nocite{reedsolomon:strichepunkte} \nocite{reedsolomon:qr_wiki} \nocite{reedsolomon:qr} %\nocite{reedsolomon:mendezmueller} diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib index e0a75a8..b84b5a4 100644 --- a/buch/papers/reedsolomon/references.bib +++ b/buch/papers/reedsolomon/references.bib @@ -51,7 +51,7 @@ } @online{reedsolomon:cd, - title = {Funktionsweise des QR-Codes}, + title = {Abbildung einer CD}, url = {https://www.stickpng.com/img/electronics/compact-discs/stack-compact-disc}, date = {2021-07-19}, year = {2021}, @@ -59,6 +59,15 @@ day = {19} } +@online{reedsolomon:strichepunkte, + title = {Abbildung der Striche und Punkte einer CD}, + url = {https://www.researchgate.net/figure/The-readable-area-of-a-CD-is-magnified-in-order- to-see-the-pit-and-land-sizing-The_fig7_303401629}, + date = {2021-07-26}, + year = {2021}, + month = {7}, + day = {26} +} + @online{reedsolomon:qr_wiki, title = {Funktionsweise des QR-Codes}, url = {https://de.wikipedia.org/wiki/QR-Code}, diff --git a/buch/papers/spannung/Einleitung.tex b/buch/papers/spannung/Einleitung.tex index b1588ff..8e0d36d 100644 --- a/buch/papers/spannung/Einleitung.tex +++ b/buch/papers/spannung/Einleitung.tex @@ -1,17 +1,18 @@ \section{Einleitung\label{spannung:section:Einleitung}} \rhead{Einleitung} Das Hook'sche Gesetz beschreibt die Beziehung von Spannung und Dehnung von linear-elastischen Materialien im Eindimensionalen. -In diesem Kapitel geht es darum das Hook'sche Gesetz im Dreidimensionalen zu beschreiben. +In diesem Kapitel geht es darum, das Hook'sche Gesetz im Dreidimensionalen zu beschreiben. Durch variable Krafteinwirkungen entstehen in jedem Punkt des Materials eine Vielzahl an unterschiedlichen Spannungen. In jedem erdenklichen Punkt im Dreidimensionalen herrscht daher ein entsprechender individueller Spannungszustand. Um das Hook'sche Gesetz für den 3D Spannungszustand formulieren zu können, reichen Skalare nicht aus. -Darum werden Vektoren, Matrizen und Tensoren zur Hilfe gezogen. +Darum werden Vektoren, Matrizen und Tensoren zu Hilfe gezogen. Mit diesen lässt sich eine Spannungsformel für den 3D Spannungszustand bilden. Diese Spannungsformel ist Grundlage für Computerprogramme und geotechnische Versuche, wie der Oedometer-Versuch. -Um die mathematische Untersuchung vorzunehmen, beschäftigt man sich zuerst mit den spezifischen Gegebenheiten und Voraussetzungen. -Ebenfalls gilt es ein paar wichtige Begriffe und deren mathematischen Zeichen einzuführen. -In diesem Kapitel gehen wir auch auf die Zusammenhänge von Spannung, Dehnungen und Verformungen an elastischen Materialien ein, +Um die mathematischen und physikalischen Berechnungen anwenden zu können, +müssen vorerst ein paar spezifische Bedingungen vorausgesetzt und Annahmen getroffen werden. +Ebenfalls gilt es, ein paar wichtige Begriffe und deren mathematischen Zeichen einzuführen. +In diesem Kapitel gehen wir auch auf die Zusammenhänge von Spannungen, Dehnungen und Verformungen an elastischen Materialien ein, wie sie in gängigen Lehrbüchern der Mechanik oder der Geotechnik behandelt werden, z.~B.~\cite{spannung:Grundlagen-der-Geotechnik}. \section{Spannungsausbreitung\label{spannung:section:Spannungsausbreitung}} @@ -29,7 +30,7 @@ Belastet man den Boden mit einer Spannung so wird diese in den Boden geleitet und von diesem kompensiert. Im Boden entstehen unterschiedlich hohe Zusatzspannungen. Diese Zusatzspannung breitet sich räumlich im Boden aus. -Im Falle einer konstanten Flächenlast $\sigma$ siehe Abbildung~\ref{spannung:Bild4} breitet sich die Zusatzspannung zwiebelartig aus. +Im Falle einer konstanten Flächenlast $\sigma$ siehe Abbildung~\ref{fig:Bild4} breitet sich die Zusatzspannung zwiebelartig aus. \begin{figure} \centering @@ -38,11 +39,11 @@ Im Falle einer konstanten Flächenlast $\sigma$ siehe Abbildung~\ref{spannung:Bi \label{fig:Bild4} \end{figure} -Mit der Tiefe $t$ nimmt diese permanent ab (siehe Abbildung~\ref{spannung:Bild5}). -Wie diese Geometrie der Ausbreitung ist, kann durch viele Modelle und Ansätze näherungsweise beschrieben werden. +Mit der Tiefe $t$ nimmt diese permanent ab (siehe Abbildung~\ref{fig:Bild5}). +Wie diese Geometrie der Ausbreitung aussieht, kann durch viele Modelle und Ansätze näherungsweise beschrieben werden. Diese Zusatzspannung $\sigma$ ist im Wesentlichen abhängig von $(x,y,t)$. Je nach Modell werden noch andere Parameter berücksichtigt. -Das können beispielsweise jenste Bodenkennwerte oder auch der Wassergehalt sein. +Das können beispielsweise verschiedene Bodenkennwerte oder auch der Wassergehalt sein. \begin{figure} \centering @@ -72,18 +73,18 @@ berechnet werden mit: t &= \text{Tiefe [\si{\meter}]} \\ s &= \text{Setzung, Absenkung [m].} \end{align*} -Diese Zusammenhänge sind wie erwähnt unter anderem im Lehrbuch [\cite{spannung:Grundlagen-der-Geotechnik}] beschrieben. +Diese Zusammenhänge sind wie erwähnt unter anderem im Lehrbuch \cite{spannung:Grundlagen-der-Geotechnik} beschrieben. In der praktischen Geotechnik wird man allerdings weitaus schwierigere Situationen antreffen. -Ein Beispiel wäre eine Baugrube mit einem Baugrubenabschluss, wo ein Teil des Bodens abgetragen ist (siehe Abbildung~\ref{spannung:Bild3}). +Ein Beispiel wäre eine Baugrube mit einem Baugrubenabschluss, wo ein Teil des Bodens abgetragen ist (siehe Abbildung~\ref{fig:Bild3}). Die Ausbreitung der Zusatzspannung $\sigma(x,y,t)$ würde hier deutlich komplizierter ausfallen. Dies bedeutet auch eine komplexere Setzung der Bodenoberfläche infolge einer Flächenlast $\sigma$. Aus allen zusätzlichen Spannungen müssen die adäquaten Dehnungen mit Hilfe einer Spannungsgleichung berechnet werden. Diese beruht auf Annahmen nach Hooke auf einem linear-elastischen Boden. -Generell wird im Ingenieurwesen versucht Phänomene möglichst nach dem Hook'schen Gesetz abbilden zu können. +Generell wird im Bauingenieurwesen oder auch im Maschinenbau versucht, manche Phänomene möglichst nach dem Hook'schen Gesetz abbilden zu können. \begin{figure} \centering \includegraphics[width=0.45\linewidth,keepaspectratio]{papers/spannung/Grafiken/Bild3.png} - \caption{Beispiel eines Lastauftrags auf den Boden bei einer komplexeren Situation, welches kompliziertere Spannungsausbreitung zur Folge hat} + \caption{Beispiel eines Lastauftrags auf den Boden bei einer komplexeren Situation, welche kompliziertere Spannungsausbreitung zur Folge hat} \label{fig:Bild3} \end{figure} diff --git a/buch/papers/spannung/main.tex b/buch/papers/spannung/main.tex index bbdf730..d2aeda9 100644 --- a/buch/papers/spannung/main.tex +++ b/buch/papers/spannung/main.tex @@ -3,7 +3,7 @@ % % (c) 2020 Hochschule Rapperswil % -\chapter{Thema\label{chapter:spannung}} +\chapter{Dreidimensionaler Spannungszustand\label{chapter:spannung}} \lhead{Dreiachsiger Spannungszustand} \begin{refsection} \chapterauthor{Adrian Schuler und Thomas Reichlin} diff --git a/buch/papers/spannung/teil0.tex b/buch/papers/spannung/teil0.tex index 7647252..089c28e 100644 --- a/buch/papers/spannung/teil0.tex +++ b/buch/papers/spannung/teil0.tex @@ -1,9 +1,10 @@ \section{Der Spannungszustand\label{spannung:section:Der Spannungsustand}} \rhead{Der Spannungszustand} -Ein Spannungszustand ist durch alle Spannungen, welche in einem beliebigen Punkt im Körper wirken, definiert (siehe Abbildung~\ref{spannung:Bild2}). +Ein Spannungszustand ist durch alle Spannungen, welche in einem beliebigen Punkt im Körper wirken, definiert (siehe Abbildung~\ref{fig:Bild2}). Änderungen der äusseren Kräfte verändern die inneren Spannungszustände im Material. -Um alle Spannungen eines Punktes darstellen zu können, wird ein infinitesimales Bodenelement in Form eines Würfels modellhaft vorgestellt. -Man spricht auch von einem Elementarwürfel, da dieser elementar klein ist. +Um alle Spannungen eines Punktes darstellen zu können, +stellt man sich modellhaft ein infinitesimales Bodenelement in Form eines Würfels vor. +Man spricht auch von einem Elementarwürfel. \begin{figure} \centering @@ -15,19 +16,19 @@ Man spricht auch von einem Elementarwürfel, da dieser elementar klein ist. Es werden jeweils drei Seiten dieses Würfels betrachtet, wobei die drei gegenüberliegenden Seiten im Betrag die selben Spannungen aufweisen, sodass der Elementarwürfel im Gleichgewicht ist. Wäre dieses Gleichgewicht nicht vorhanden, käme es zu Verschiebungen und Drehungen. -Das infinitesimale Bodenteilchen hat die Koordinaten $1$, $2$, $3$. +Das infinitesimale Bodenteilchen hat die Koordinatenachsen $1$, $2$, $3$. Veränderungen der Normalspannungen können durch Schubspannungen kompensiert werden und umgekehrt. -So sind insgesamt neun verschiedene Spannungen möglich, wobei drei Normal- und sechs Schubspannungen sind. +So sind insgesamt neun verschiedene Spannungen möglich, konkret sind dies drei Normal- und sechs Schubspannungen. Normalspannungen wirken normal (mit rechtem Winkel) zur angreifenden Fläche und Schubspannungen parallel zur angreifenden Fläche. Alle Beträge dieser neun Spannungen am Elementarwürfel bilden den Spannungszustand. -Daraus können die äquivalenten Dehnungen $\varepsilon$ mit Hilfe des Hook'schen Gesetz berechnet werden. +Daraus können die äquivalenten Dehnungen $\varepsilon$ mit Hilfe des Hook'schen Gesetzes berechnet werden. Daher gibt es auch den entsprechenden Dehnungszustand. \section{Spannungszustand\label{spannung:section:Spannungsustand}} \rhead{Spannungszustand} -Im einachsigen Spannungszustand herrscht nur die Normalspannung $\sigma_{11}$ (siehe Abbildung~\ref{spannung:Bild1}). +Im einachsigen Spannungszustand herrscht nur die Normalspannung $\sigma_{11}$ (siehe Abbildung~\ref{fig:Bild1}). Das Hook'sche Gesetz beschreibt genau diesen 1D Spannungszustand. Nach Hooke gilt: \[ @@ -59,7 +60,7 @@ mit A &= \text{Fläche [\si{\meter\squared}].} \end{align*} Diese Beziehung gilt bei linear-elastischen Materialien, welche reversible Verformungen zulassen. -Es ist praktisch die relative Dehnung $\varepsilon$ anzugeben und nicht eine absolute Längenänderung $\Delta l$. +Es ist praktisch, die relative Dehnung $\varepsilon$ anzugeben und nicht eine absolute Längenänderung $\Delta l$. \begin{figure} \centering \includegraphics[width=0.35\linewidth,keepaspectratio]{papers/spannung/Grafiken/Bild1.png} @@ -73,10 +74,10 @@ Mithilfe vom Elastizitätsmodul $E$ als Proportionalitätskonstante lässt sich E\cdot\varepsilon \] beschreiben. -Im Falle, dass $E$ nicht konstant ist, kann dieser näherungsweise durch +Im Falle, dass $E$ nicht konstant ist, wird dieser durch \[ E = -\frac{\Delta\sigma}{\Delta\varepsilon} +\frac{\text{d}\sigma}{\text{d}\varepsilon} \] -ausgedrückt werden.
\ No newline at end of file +ausgedrückt.
\ No newline at end of file diff --git a/buch/papers/spannung/teil1.tex b/buch/papers/spannung/teil1.tex index 74516c1..647b452 100644 --- a/buch/papers/spannung/teil1.tex +++ b/buch/papers/spannung/teil1.tex @@ -1,8 +1,8 @@ \section{Skalare, Vektoren, Matrizen und Tensoren\label{spannung:section:Skalare,_Vektoren,_Matrizen_und_Tensoren}} \rhead{Skalare, Vektoren, Matrizen und Tensoren} -Der Begriff Tensor kann als Überbegriff, der mathematischen Objekte Skalar, Vektor und Matrix, betrachtet werden. +Der Begriff Tensor kann als Überbegriff der mathematischen Objekte Skalar, Vektor und Matrix, betrachtet werden. Allerdings sind noch höhere Stufen dieser Objekte beinhaltet. -Ein Skalar, ein Vektor oder eine Matrix ist daher auch ein Tensor. +Skalare, Vektoren oder Matrizen sind daher auch Tensoren. Ein Skalar ist ein Tensor 0. Stufe. Mit einem Vektor können mehrere Skalare auf einmal beschrieben werden. Ein Vektor hat daher die Stufe 1 und ist höherstufig als ein Skalar. @@ -14,11 +14,10 @@ Jede Stufe von Tensoren verlangt andere Rechenregeln. So zeigt sich auch der Nachteil von Tensoren mit Stufen höher als 2. Man ist also bestrebt höherstufige Tensoren mit Skalaren, Vektoren oder Matrizen zu beschreiben. -Der Begriff Tensor wurde 1840 von Rowan Hamilton in die Mathematik eingeführt. +In den 40er Jahren vom 19. Jahrhundert wurde der Begriff Tensor von Rowan Hamilton in die Mathematik eingeführt. James Clerk Maxwell hat bereits mit Tensoren operiert, ohne den Begriff Tensor gekannt zu haben. Erst Woldemar Voigt hat den Begriff in die moderne Bedeutung von Skalar, Matrix und Vektor verallgemeinert. Er hat in der Elastizitätstheorie als erstes Tensoren eingesetzt und beschrieben. Auch Albert Einstein hat solche Tensoren eingesetzt, um in der Relativitätstheorie die Änderung der 4D Raumzeit beschreiben zu können. \cite{spannung:Tensor} -\cite{spannung:Voigtsche-Notation} diff --git a/buch/papers/spannung/teil2.tex b/buch/papers/spannung/teil2.tex index 6326eab..8620afe 100644 --- a/buch/papers/spannung/teil2.tex +++ b/buch/papers/spannung/teil2.tex @@ -3,7 +3,7 @@ Durch komplexe Spannungsausbreitungen im Boden entstehen im 3D Spannungszustand unterschiedliche Normal- und Schubspannungen. \begin{figure} \centering - \includegraphics[width=0.4\linewidth,keepaspectratio]{papers/spannung/Grafiken/infinitesimalerWuerfel.png} + \includegraphics[width=0.30\linewidth,keepaspectratio]{papers/spannung/Grafiken/infinitesimalerWuerfel.png} \caption{Beispiel eines Spannungszustandes; Vergrösserung eines infinitesimalen Bodenteilchen} \label{fig:infinitesimalerWuerfel} \end{figure} @@ -49,7 +49,7 @@ Der Dehnungstensor ist ebenfalls ein Tensor 2. Stufe und kann somit auch als $3\ dargestellt werden und beschreibt den gesamten Dehnungszustand. Der Spannungs- und Dehnungstensor 2. Stufe kann je in einen Tensor 1. Stufe überführt werden, welches ein Spaltenvektor ist. -Gemäss der Hadamard-Algebra dürfen Zeile um Zeile in eine Spalte notiert werden, sodass es einen Spaltenvektor ergibt. +Man darf Zeile um Zeile in eine Spalte notieren, sodass es einen Spaltenvektor ergibt. So ergibt sich der Spannungsvektor \[ @@ -79,7 +79,7 @@ So ergibt sich der Spannungsvektor \sigma_{33} \end{pmatrix} \] -und Dehnungsvektor +und der Dehnungsvektor \[ \overline{\varepsilon} = @@ -140,14 +140,6 @@ C_{3311} & C_{3312} & C_{3313} & C_{3321} & C_{3322} & C_{3323} & C_{3331} & C_{ \end{pmatrix} \] geschrieben werden kann. -Dieser Elastizitätstensor muss für isotrope Materialien zwingend symmetrisch sein. -Folglich gilt: -\[ -\overline{\overline{C}} -= -\overline{\overline{C}}~^{T} -. -\] Die allgemeine Spannungsgleichung lautet nun: \[ \vec\sigma @@ -155,8 +147,7 @@ Die allgemeine Spannungsgleichung lautet nun: \overline{\overline{C}}\cdot\vec{\varepsilon} . \] - -Als Indexnotation +Sie kann ebenfalls als Indexnotation \[ \sigma_{ij} = @@ -164,7 +155,15 @@ Als Indexnotation \sum_{l=1}^3 C_{ijkl}\cdot\varepsilon_{kl} \] -kann dies ebenfalls geschrieben werden. +geschrieben werden. +Der Elastizitätstensor muss für isotrope Materialien zwingend symmetrisch sein. +Folglich gilt: +\[ +\overline{\overline{C}} += +\overline{\overline{C}}~^{T} +. +\] Die Konstanten $C$ werden nun nach dem Hook'schen Gesetz mit Hilfe des Elastizitätsmoduls $E$ definiert. Da dieser Modul durch die eindimensionale Betrachtung definiert ist, @@ -221,7 +220,7 @@ definiert ist. Trägt man die Konstanten in die Matrix ein, ergibt sich \end{pmatrix} . \] -Die Normalspannung $\sigma_{22}$ lässt sich exemplarisch als +Die Normalspannung $\sigma_{22}$ lässt sich zum Beispiel als \[ \sigma_{22} = @@ -229,11 +228,13 @@ Die Normalspannung $\sigma_{22}$ lässt sich exemplarisch als \] berechnen. +Reduzierte Spannungs- und Dehnungsgleichungen + Man betrachte nun die Eigenschaften des Elastizitätstensors. Dieser ist quadratisch und symmetrisch, die verschiedenen Einträge wechseln sich aber miteinander ab. Es ergeben sich keine Blöcke mit einheitlichen Einträgen. -Allerdings weiss man, dass im isotropen Boden der Spannungs-, Dehnungs- und daher auch Elastizitätstensor symmetrisch sind. +Allerdings weiss man, dass im isotropen Boden der Spannungs-, Dehnungs- und daher auch der Elastizitätstensor symmetrisch sind. Wäre dem nicht so, würde sich das Material je nach Richtung unterschiedlich elastisch verhalten. Diese Symmetrie setzt daher voraus, dass \[ @@ -399,7 +400,7 @@ Somit lässt sich die reduzierte allgemeine Spannungsgleichung mit \] beschreiben. Die Konstanten $C$ werden wieder nach dem Hook'schen Gesetz definiert. -Dies ergibt die Spannungsformel, welche weit möglichst vereinfacht ist: +Dies ergibt die Spannungsgleichung, welche weit möglichst vereinfacht ist: \begin{equation} \begin{pmatrix} \sigma_{11}\\ @@ -433,7 +434,7 @@ Dies ergibt die Spannungsformel, welche weit möglichst vereinfacht ist: Im Elastizitätstensor fallen zwei $3\times3$ Blöcke auf, welche nur Einträge mit $0$ haben. Der Tensor besagt also, dass diese jeweiligen Dehnungen keinen Einfluss auf unsere Spannung haben. -Man sieht nun auch ganz gut, dass sich im Vergleich zu der allgemeinen Spannungsgleichung, die Einträge verschoben haben. +Man sieht nun auch ganz gut, dass sich im Vergleich zu der allgemeinen Spannungsgleichung die Einträge verschoben haben. Da nach Voigt zuerst die Normalspannungen und anschliessend die Schubspannungen notiert worden sind, ergeben sich die $3\times3$ Blöcke. Man betrachte als Beispiel die Berechnung von $\sigma_{33}$. @@ -441,8 +442,8 @@ Es ist ersichtlich, dass die Schubdehnungen keinen Einfluss auf $\sigma_{33}$ ha Der Einfluss der zu $\sigma_{33}$ äquivalenten Dehnung $\varepsilon_{33}$ hat den grössten Einfluss. Die anderen Normalspannungen $\sigma_{11}$ und $\sigma_{22}$ haben einen unter anderem mit $\nu$ korrigierten Einfluss. -Von $\overline{\overline{C}}$ bildet man noch die inverse Matrix $\overline{\overline{C}}\mathstrut^{-1}$ um die Gleichung umstellen zu können. -Dadurch erhält man die Dehnungsgleichung: +Von $\overline{\overline{C}}$ bildet man die inverse Matrix $\overline{\overline{C}}\mathstrut^{-1}$, mithilfe des Gauss - Jordan Algorithmus, um die Gleichung umstellen zu können. +Durch einige Berechnungsschritte erhält man die Dehnungsgleichung: \[ \vec{\varepsilon} diff --git a/buch/papers/spannung/teil3.tex b/buch/papers/spannung/teil3.tex index 3e456c3..a9080ea 100644 --- a/buch/papers/spannung/teil3.tex +++ b/buch/papers/spannung/teil3.tex @@ -30,7 +30,7 @@ q \label{spannung:Invariante_q} . \end{equation} -Diese Zusammenhänge werden im Skript [\cite{spannung:Stoffgesetze-und-numerische-Modellierung-in-der-Geotechnik}] aufgezeigt. +Diese Zusammenhänge werden im Skript \cite{spannung:Stoffgesetze-und-numerische-Modellierung-in-der-Geotechnik} aufgezeigt. Die hydrostatische Spannung $p$ kann gemäss Gleichung \eqref{spannung:Invariante_p} als \[ p @@ -38,28 +38,28 @@ p \frac{\sigma_{11}+2\sigma_{33}}{3} \] vereinfacht werden. -Die deviatorische Spannung $q$ wird gemäss Gleichung \eqref{spannung:Invariante_q}als +Die deviatorische Spannung $q$ wird gemäss Gleichung \eqref{spannung:Invariante_q} als \[ q = \sigma_{11}-\sigma_{33} \] -vereinfacht. Man kann $p$ als Isotrop und $q$ als Schub betrachten. +vereinfacht. Man kann $p$ als Druck und $q$ als Schub betrachten. -Die Invarianten können mit der Spannungsformel \eqref{spannung:Spannungsgleichung} berechnet werden. +Die Invarianten $p$ und $q$ können mit der Spannungsgleichung \eqref{spannung:Spannungsgleichung} berechnet werden. Durch geschickte Umformung dieser Gleichung, lassen sich die Module als Faktor separieren. Dabei entstehen spezielle Faktoren mit den Dehnungskomponenten. So ergibt sich \[ -\overbrace{\frac{\sigma_{11}+2\sigma_{33}}{3}}^{p} +\overbrace{\frac{\sigma_{11}+2\sigma_{33}}{3}}^{\displaystyle{p}} = -\frac{E}{3(1-2\nu)} \overbrace{(\varepsilon_{11} - 2\varepsilon_{33})}^{\varepsilon_{v}} +\frac{E}{3(1-2\nu)} \overbrace{(\varepsilon_{11} - 2\varepsilon_{33})}^{\displaystyle{{\varepsilon_{v}}}} \] und \[ -\overbrace{\sigma_{11}-\sigma_{33}}^{q} +\overbrace{\sigma_{11}-\sigma_{33}}^{\displaystyle{q}} = -\frac{3E}{2(1+\nu)} \overbrace{\frac{2}{3}(\varepsilon_{11} - \varepsilon_{33})}^{\varepsilon_{s}} +\frac{3E}{2(1+\nu)} \overbrace{\frac{2}{3}(\varepsilon_{11} - \varepsilon_{33})}^{\displaystyle{\varepsilon_{s}}} . \] Die Faktoren mit den Dehnungskomponenten können so mit @@ -79,8 +79,8 @@ eingeführt werden, mit \varepsilon_{v} &= \text{Hydrostatische Dehnung [-]} \\ \varepsilon_{s} &= \text{Deviatorische Dehnung [-].} \end{align*} -Die hydrostatische Dehnung $\varepsilon_{v}$ kann mit einer Kompression verglichen werden. -Die deviatorische Dehnung $\varepsilon_{s}$ kann mit einer Verzerrung verglichen werden. +Die hydrostatische Dehnung $\varepsilon_{v}$ kann mit einer Kompression und +die deviatorische Dehnung $\varepsilon_{s}$ mit einer Verzerrung verglichen werden. Diese zwei Gleichungen kann man durch die Matrixschreibweise \begin{equation} @@ -90,8 +90,8 @@ Diese zwei Gleichungen kann man durch die Matrixschreibweise \end{pmatrix} = \begin{pmatrix} - \frac{3E}{2(1+\nu)} & 0 \\ - 0 & \frac{E}{3(1-2\nu)} + \displaystyle{\frac{3E}{2(1+\nu)}} & 0 \\ + 0 & \displaystyle{\frac{E}{3(1-2\nu)}} \end{pmatrix} \begin{pmatrix} \varepsilon_{s}\\ @@ -100,9 +100,11 @@ Diese zwei Gleichungen kann man durch die Matrixschreibweise \label{spannung:Matrixschreibweise} \end{equation} vereinfachen. -Man hat so eine Matrix multipliziert mit einem Vektor und erhält einen Vektor. -Änderungen des Spannungszustandes können mit dieser Gleichung vollumfänglich erfasst werden. +Änderungen des Spannungszustandes können mit diesen Gleichungen vollumfänglich erfasst werden. +Diese Spannungsgleichung mit den zwei Einträgen ($p$ und $q$) ist gleichwertig +wie die ursprüngliche Spannungsgleichung mit den neun Einträgen +($\sigma_{11}$, $\sigma_{12}$, $\sigma_{13}$, $\sigma_{21}$, $\sigma_{22}$, $\sigma_{23}$, $\sigma_{31}$, $\sigma_{32}$, $\sigma_{33}$). Mit dieser Formel \eqref{spannung:Matrixschreibweise} lassen sich verschieden Ergebnisse von Versuchen analysieren und berechnen. -Ein solcher Versuch, den oft in der Geotechnik durchgeführt wird, ist der Oedometer-Versuch. +Ein solcher Versuch, der oft in der Geotechnik durchgeführt wird, ist der Oedometer-Versuch. Im nächsten Kapitel wird die Anwendung der Matrix an diesem Versuch beschrieben. diff --git a/buch/papers/spannung/teil4.tex b/buch/papers/spannung/teil4.tex index 2f2e4ce..00b2d4f 100644 --- a/buch/papers/spannung/teil4.tex +++ b/buch/papers/spannung/teil4.tex @@ -1,6 +1,6 @@ -\section{Oedometer-Versuch\label{spannung:section:Oedometer-Versuch}} -\rhead{Oedometer-Versuch} -Mit dem Oedometer-Versuch kann der oedometrische Elastizitätsmodul $E_{OED}$ bestimmt werden. +\section{Oedometrischer Elastizitätsmodul\label{spannung:section:Oedometrischer Elastizitätsmodul}} +\rhead{Oedometrischer Elastizitätsmodul} +Mit dem Oedometer-Versuch kann der oedometrische Elastizitätsmodul $E_{\text{OED}}$ bestimmt werden. Dieser beschreibt ebenfalls das Verhältnis zwischen Spannung und Dehnung, allerdings unter anderen Bedingungen. Diese Bedingung ist das Verhindern der seitlichen Verformung, sprich der Dehnung in Richtung $1$ und $2$. Es wird ein Probeelement mit immer grösseren Gewichten belastet, welche gleichmässig auf das Material drücken. @@ -43,8 +43,8 @@ Diese lautet nun: \end{pmatrix} = \begin{pmatrix} - \frac{E_{OED}}{(1+\nu)} & 0 \\ - 0 & \frac{E_{OED}}{3(1-2\nu)} + \displaystyle{\frac{E_{\text{OED}}}{(1+\nu)}} & 0 \\ + 0 & \displaystyle{\frac{E_{\text{OED}}}{3(1-2\nu)}} \end{pmatrix} \begin{pmatrix} \varepsilon_{11}\\ @@ -52,28 +52,28 @@ Diese lautet nun: \end{pmatrix} . \] -Daraus lässt sich bei jedem Setzungsgrad der oedometrische Elastitzitätsmodul $E_{OED}$ und die seitlichen Spannungen $\sigma_{33}$ mit den 2 Gleichungen +Daraus lässt sich bei jedem Setzungsgrad der oedometrische Elastitzitätsmodul $E_{\text{OED}}$ und die seitlichen Spannungen $\sigma_{33}$ mit den zwei Gleichungen \[ \sigma_{11}-\sigma_{33} = -\frac{E_{OED}}{(1+\nu)}\cdot\varepsilon_{11} +\frac{E_{\text{OED}}}{(1+\nu)}\cdot\varepsilon_{11} \] und \[ \sigma_{11}+2\sigma_{33} = -\frac{E_{OED}}{3(1-2\nu)}\cdot\varepsilon_{11} +\frac{E_{\text{OED}}}{3(1-2\nu)}\cdot\varepsilon_{11} \] berechnen. -Mit diesen Gleichungen hat man das Gleichungssystem um $E_{OED}$ und $\sigma_{33}$ zu berechnen. +Mit diesen Gleichungen hat man das Gleichungssystem um $E_{\text{OED}}$ und $\sigma_{33}$ zu berechnen. Die Poisson-Zahl muss als Kennwert gemäss der Bodenklasse gewählt werden. -Den Versuch kann man auf einem $\sigma$-$\varepsilon$-Diagramm abtragen (siehe Abbildung~\ref{spannung:DiagrammOedometer-Versuch}). +Den Versuch kann man auf einem $\sigma$-$\varepsilon$-Diagramm abtragen (siehe Abbildung~\ref{fig:DiagrammOedometer-Versuch}). Durch die Komprimierung nimmt der Boden mehr Spannung auf, und verformt sich zugleich weniger stark. -Mit diesem ermittelten $E_{OED}$ kann man nun weitere Berechnungen für die Geotechnik durchführen. +Mit diesem ermittelten $E_{\text{OED}}$ kann man nun weitere Berechnungen für die Geotechnik durchführen. \begin{figure} \centering - \includegraphics[width=0.5\linewidth,keepaspectratio]{papers/spannung/Grafiken/DiagrammOedometer-Versuch.png} + \includegraphics[width=0.45\linewidth,keepaspectratio]{papers/spannung/Grafiken/DiagrammOedometer-Versuch.png} \caption{Diagramm Charakteristik verschiedener Elastizitätsmodule bei gleichem Material} \label{fig:DiagrammOedometer-Versuch} \end{figure}
\ No newline at end of file |
