aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/multiplikation/problemstellung.tex
diff options
context:
space:
mode:
authorNunigan <michael.schmid2@ost.ch>2021-07-27 22:01:05 +0200
committerNunigan <michael.schmid2@ost.ch>2021-07-27 22:01:05 +0200
commit3875ac2b8df9145a66e9f6fcf34e77eb3bc2d072 (patch)
treeb5113260e190dfc7a94e4298bf6eb5ae21c08344 /buch/papers/multiplikation/problemstellung.tex
parentMerge pull request #50 from paschost/patch-1 (diff)
downloadSeminarMatrizen-3875ac2b8df9145a66e9f6fcf34e77eb3bc2d072.tar.gz
SeminarMatrizen-3875ac2b8df9145a66e9f6fcf34e77eb3bc2d072.zip
added first part of paper and code
Diffstat (limited to '')
-rwxr-xr-xbuch/papers/multiplikation/problemstellung.tex104
1 files changed, 104 insertions, 0 deletions
diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex
new file mode 100755
index 0000000..b20a791
--- /dev/null
+++ b/buch/papers/multiplikation/problemstellung.tex
@@ -0,0 +1,104 @@
+%
+% teil1.tex -- Beispiel-File für das Paper
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Problemstellung}
+\rhead{Problemstellung}
+Dank der breiten Anwendung der Matrizenmultiplikation ist eine effiziente L\"osung dieser Operation von grosser Bedeutung.
+Das Ziel dieses Papers ist verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen.
+Wobei gezielt auf Algorithmen, welche das Problem schneller als der Standard Algorithmus L\"osen eingegangen wird.
+
+\subsection{Big $\mathcal{O}$ Notation}
+Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus \cite{multiplikation:bigo}.
+$f(x) \in \mathcal{O}(g(x))$ besagt das die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$.
+Vereinfacht werden f\"ur Algorithmen die folgende Notation 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}
+
+In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die Verschiedenen Laufzeiten miteinander verglichen werden.
+
+\begin{figure}
+ \center
+ \includegraphics[]{papers/multiplikation/images/bigo}
+ \caption{Verschiedene Laufzeiten}
+ \label{multiplikation:fig:bigo}
+\end{figure}
+
+\subsubsection{Beispiel Algorithmen}
+\paragraph{Beschr\"ankter Algorithmus}
+
+Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden.
+
+\begin{algorithm}\caption{}
+ \label{multiplikation:alg:b1}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \Function{B1}{$a, b$}
+ \State \textbf{return} $a+b$
+ \EndFunction
+ \end{algorithmic}
+\end{algorithm}
+
+Wobei Konstanten nicht beachtet werden, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$.
+
+\begin{algorithm}\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}
+
+\paragraph{Linearer Algorithmus}
+
+Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares $\mathcal{O}(n)$ Verhalten.
+
+\begin{algorithm}\caption{}
+ \setlength{\lineskip}{7pt}
+ \begin{algorithmic}
+ \label{multiplikation:alg:l1}
+ \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
+ \end{algorithmic}
+\end{algorithm}
+
+\paragraph{Quadratischer Algorithmus}
+
+Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches $\mathcal{O}(n^2)$ Verhalten.
+
+\begin{algorithm}[H]\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}
+
+