diff options
author | Andreas Müller <andreas.mueller@ost.ch> | 2021-08-03 07:37:42 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-08-03 07:37:42 +0200 |
commit | f31aca6129f3c84f1ed4f59378fd31cbdc58ec3b (patch) | |
tree | 97c32dbdcbcc888a9030d149f5a765f006fcd631 /buch/papers/multiplikation/problemstellung.tex | |
parent | 1. Version Kapitel Rotation und Spiegelung (diff) | |
parent | Merge pull request #60 from Kuehnee/master (diff) | |
download | SeminarMatrizen-f31aca6129f3c84f1ed4f59378fd31cbdc58ec3b.tar.gz SeminarMatrizen-f31aca6129f3c84f1ed4f59378fd31cbdc58ec3b.zip |
Merge branch 'master' into master
Diffstat (limited to '')
-rwxr-xr-x | buch/papers/multiplikation/problemstellung.tex | 104 |
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} + + |