1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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}
|
