1 files changed, 137 insertions, 0 deletions
diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex
new file mode 100755
index 0000000..879b210
--- /dev/null
+++ b/buch/papers/multiplikation/problemstellung.tex
@@ -0,0 +1,137 @@
+%
+% teil1.tex -- Beispiel-File für das Paper
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Laufzeiten von Algorithmen}
+\rhead{Laufzeiten von Algorithmen}
+Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente Ausführung dieser Operation von grosser Bedeutung.
+Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen.
+Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der Standardalgorithmus l\"osen.
+
+\label{muliplikation:sec:bigo}
+Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Relation zur Inputgrösse \cite{multiplikation:bigo}.
+$f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$, wenn $x \rightarrow \infty$.
+Dies ist gegeben, falls es für $f \in \mathcal{O}(n^k)$ eine Konstante $C$ gibt, mit $f(n) \leq Cn^k$.
+% Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$.
+Vereinfacht werden f\"ur Algorithmen die folgenden Sprechweisen verwendet:
+\begin{itemize}
+	\item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt
+	\item $f \in \mathcal{O}(n) \rightarrow f$ w\"achst linear
+	\item $f \in \mathcal{O}  (n^2   ) \rightarrow f$ w\"achst quadratisch
+	\item $f \in \mathcal{O}(\log n) \rightarrow f$ w\"achst logarithmisch
+	\item $f \in \mathcal{O}(n \log n) \rightarrow f$ hat super-lineares Wachstum
+	\item $f \in \mathcal{O}  (e^n   ) \rightarrow f$ w\"achst exponentiell
+	\item usw.
+\end{itemize}
+
+Konstanten werden nicht beachtet, eine Laufzeit von  $4n^2$ führt, für $n \rightarrow \infty$ zu $\mathcal{O}(n^2)$.
+In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
+Bei einer doppelt logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven abgebildet.
+
+
+
+\subsubsection{Beispielalgorithmen}
+
+Es folgen einige Beispiele von Algorithmen, welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen.
+
+
+\begin{table}[t]
+	\begin{tabular}{ll}
+		\begin{minipage}{0.48\textwidth}
+			\begin{algorithm}[H]\footnotesize\caption{}
+				\label{multiplikation:alg:b1}
+				\setlength{\lineskip}{7pt}
+				\begin{algorithmic}
+					\Function{B1}{$a, b$}
+					\State \textbf{return} $a+b$
+					\EndFunction
+					\State
+					\State
+				\end{algorithmic}
+			\end{algorithm}
+		\end{minipage}
+		&
+		\begin{minipage}{0.48\textwidth}
+			\begin{algorithm}[H]\footnotesize\caption{}
+				\label{multiplikation:alg:b2}
+				\setlength{\lineskip}{7pt}
+				\begin{algorithmic}
+					\Function{B2}{$a, b$}
+					\State $ x \gets a+b $
+					\State $ y \gets a \cdot b $
+					\State \textbf{return} $x+y$
+					\EndFunction
+				\end{algorithmic}
+			\end{algorithm}
+		\end{minipage} \\
+		\begin{minipage}{0.48\textwidth}
+			\begin{algorithm}[H]\footnotesize\caption{}
+				\setlength{\lineskip}{7pt}
+				\begin{algorithmic}
+					\label{multiplikation:alg:linear}
+					\Function{L}{$\mathbf{a}, \mathbf{b}$,n}
+					\State $ sum \gets 0$
+					\For{$i = 0,1,2 \dots,n$}
+					\State $ sum \gets sum + A[i] \cdot B[i] $
+					\EndFor
+
+					\State \textbf{return} $sum$
+
+					\EndFunction
+					\State
+					\State
+				\end{algorithmic}
+			\end{algorithm}
+		\end{minipage}
+		&
+		\begin{minipage}{0.48\textwidth}
+			\begin{algorithm}[H]\footnotesize\caption{}
+				\label{multiplikation:alg:q1}
+				\setlength{\lineskip}{7pt}
+				\begin{algorithmic}
+					\Function{Q}{$\mathbf{A}, \mathbf{B}$,n}
+					\State $ sum \gets 0$
+					\For{$i = 0,1,2 \dots,n$}
+					\For{$j = 0,1,2 \dots,n$}
+					\State $ sum \gets sum + A[i] \cdot B[j] $
+					\EndFor
+					\EndFor
+					\State \textbf{return} $sum$
+					\EndFunction
+				\end{algorithmic}
+			\end{algorithm}
+		\end{minipage}
+	\end{tabular}
+\end{table}
+
+%\begin{table}
+%	\begin{tabular}[t]{ll}
+
+%	\end{tabular}
+%\end{table}
+
+\paragraph{Beschr\"ankter Algorithmus}
+Algorithmus \ref{multiplikation:alg:b1} ist ein Beispiel mit beschränkter Laufzeit $\mathcal{O}(1)$
+Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen Einfluss auf die Laufzeit.
+
+Wie erwähnt werden Konstanten nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu  $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$.
+
+
+\paragraph{Linearer Algorithmus}
+
+Der Algorithmus \ref{multiplikation:alg:linear} hat ein lineares Verhalten.
+Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}(n)$.
+
+\paragraph{Quadratischer Algorithmus}
+
+Der Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten.
+Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O} (n^2 )$.
+
+
+\begin{figure}
+	\center
+	\includegraphics[]{papers/multiplikation/images/bigo}
+	\caption{Laufzeiten von verschiedensten Zeitkomplexitäten. Bei einer doppelt logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven dargestellt.}
+	\label{multiplikation:fig:bigo}
+\end{figure}