diff options
author | Ayexor <9105454+Ayexor@users.noreply.github.com> | 2021-08-27 18:09:54 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-08-27 18:09:54 +0200 |
commit | 2b2c5daa139aec08d091b658ad6191d6e57024ef (patch) | |
tree | 2c8f3fc7017394746d8e4f92a358e2a11015e072 /buch/papers/multiplikation/problemstellung.tex | |
parent | Anpassungen nach Mail (diff) | |
parent | new image: tetraeder (diff) | |
download | SeminarMatrizen-2b2c5daa139aec08d091b658ad6191d6e57024ef.tar.gz SeminarMatrizen-2b2c5daa139aec08d091b658ad6191d6e57024ef.zip |
Merge branch 'master' into master
Diffstat (limited to '')
-rwxr-xr-x | buch/papers/multiplikation/problemstellung.tex | 137 |
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} |