From 91c10deedee35f5fa673de585c41c06b81248f14 Mon Sep 17 00:00:00 2001 From: michael-OST <75078383+michael-OST@users.noreply.github.com> Date: Mon, 26 Jul 2021 20:59:51 +0200 Subject: Bonus-Chapter updated --- buch/papers/reedsolomon/anwendungen.tex | 35 +++++++++++++-------- .../reedsolomon/images/Compact_Disc_zoomed_in.png | Bin 0 -> 45679 bytes buch/papers/reedsolomon/main.tex | 1 + buch/papers/reedsolomon/references.bib | 11 ++++++- 4 files changed, 33 insertions(+), 14 deletions(-) create mode 100644 buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png (limited to 'buch/papers') 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 new file mode 100644 index 0000000..69556d0 Binary files /dev/null and b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png differ diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index e68b947..ab4e4be 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -49,6 +49,7 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren \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}, -- cgit v1.2.1 From 2b0d4d1b98f7bed5fa05e2ab6c30352390f22eef Mon Sep 17 00:00:00 2001 From: "User-PC\\User" Date: Tue, 27 Jul 2021 11:15:54 +0200 Subject: =?UTF-8?q?Diverse=20=C3=84nderungen=20/=20Korrekturen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/spannung/Einleitung.tex | 27 ++++++++++++------------ buch/papers/spannung/main.tex | 2 +- buch/papers/spannung/teil0.tex | 23 +++++++++++---------- buch/papers/spannung/teil1.tex | 7 +++---- buch/papers/spannung/teil2.tex | 41 +++++++++++++++++++------------------ buch/papers/spannung/teil3.tex | 32 +++++++++++++++-------------- buch/papers/spannung/teil4.tex | 24 +++++++++++----------- 7 files changed, 80 insertions(+), 76 deletions(-) (limited to 'buch/papers') 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 -- cgit v1.2.1 From 4f9cf26c7802a163da6b18cec9db62e75a9730cb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Tue, 27 Jul 2021 12:30:10 +0200 Subject: neue version --- buch/papers/munkres/main.tex | 4 +- buch/papers/munkres/teil0.tex | 19 ++----- buch/papers/munkres/teil1.tex | 65 +++++++++++++++++----- buch/papers/munkres/teil2.tex | 83 ++-------------------------- buch/papers/munkres/teil3.tex | 122 +++++++++++------------------------------- buch/papers/munkres/teil4.tex | 31 +---------- buch/papers/munkres/teil5.tex | 10 +--- 7 files changed, 97 insertions(+), 237 deletions(-) (limited to 'buch/papers') 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{-} -- cgit v1.2.1 From ef1973fdcb29ad84666ccee58633711afb978629 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Tue, 27 Jul 2021 12:45:18 +0200 Subject: fehlendes bild --- buch/papers/munkres/figures/Matrixdarstellung.png | Bin 0 -> 46310 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 buch/papers/munkres/figures/Matrixdarstellung.png (limited to 'buch/papers') diff --git a/buch/papers/munkres/figures/Matrixdarstellung.png b/buch/papers/munkres/figures/Matrixdarstellung.png new file mode 100644 index 0000000..91a376d Binary files /dev/null and b/buch/papers/munkres/figures/Matrixdarstellung.png differ -- cgit v1.2.1