aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/multiplikation/problemstellung.tex
diff options
context:
space:
mode:
authorNunigan <m2schmid@hsr.ch>2021-08-05 18:04:32 +0200
committerNunigan <m2schmid@hsr.ch>2021-08-05 18:04:32 +0200
commite948351c11835cb6a19abe394ffb61219884b96a (patch)
tree8df880e649095844dd69fd9676dc7a63ad57ebd4 /buch/papers/multiplikation/problemstellung.tex
parentMerge branch 'master' of https://github.com/AndreasFMueller/SeminarMatrizen (diff)
downloadSeminarMatrizen-e948351c11835cb6a19abe394ffb61219884b96a.tar.gz
SeminarMatrizen-e948351c11835cb6a19abe394ffb61219884b96a.zip
update paper
Diffstat (limited to '')
-rwxr-xr-xbuch/papers/multiplikation/problemstellung.tex135
1 files changed, 74 insertions, 61 deletions
diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex
index cd5aaaa..c6fd10e 100755
--- a/buch/papers/multiplikation/problemstellung.tex
+++ b/buch/papers/multiplikation/problemstellung.tex
@@ -5,13 +5,15 @@
%
\section{Problemstellung}
\rhead{Problemstellung}
-Dank der breiten Anwendung der Matrizenmultiplikation ist eine effiziente L\"osung dieser Operation von grosser Bedeutung.
+Wegen 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.
-Gezielt werden auf Algorithmen, welche das Problem schneller als der Standard Algorithmus L\"osen eingegangen.
+Gezielt wird auf Algorithmen eingegange, welche das Problem schneller als der Standard Algorithmus l\"osen.
\subsection{Big $\mathcal{O}$ Notation}
-Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus \cite{multiplikation:bigo}.
+\label{muliplikation:sec:bigo}
+Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhänigkeit 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$.
+Als Beispiel: benötigt eine Funktion $g$, $\mathcal{O}\left(n+n^2 \right)$ Multiplikationen so wächst $f$ mit $\mathcal{O}\left(n^2 \right)$ nicht wesentlich schneller als $g$.
Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\begin{itemize}
\item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt
@@ -23,7 +25,7 @@ Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\item usw.
\end{itemize}
-In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
+In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
\begin{figure}
\center
@@ -34,77 +36,88 @@ In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufze
\subsubsection{Beispiel Algorithmen}
-Folgend einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen.
+Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen.
+
+\begin{minipage}{0.4\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
+ \end{algorithmic}
+ \end{algorithm}
+
+ \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
+ \end{algorithmic}
+ \end{algorithm}
+\end{minipage}
+\hspace{2cm}
+\begin{minipage}{0.4\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}
+
+
+ \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}
+
\paragraph{Beschr\"ankter Algorithmus}
Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen einfluss auf die Laufzeit.
-\begin{algorithm}\footnotesize\caption{}
- \label{multiplikation:alg:b1}
- \setlength{\lineskip}{7pt}
- \begin{algorithmic}
- \Function{B1}{$a, b$}
- \State \textbf{return} $a+b$
- \EndFunction
- \end{algorithmic}
-\end{algorithm}
+
Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$.
-\begin{algorithm}\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}
+
\paragraph{Linearer Algorithmus}
-Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares Verhalten.
+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)$.
-\begin{algorithm}\footnotesize\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 Verhalten.
+Der Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten.
Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchglaufen und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$.
-
-
-\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}
-
-