Merge pull request #52 from Nunigan/master

Multiplikation #1

6 files changed, 292 insertions, 0 deletions

diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf
new file mode 100644
index 0000000..dfa2ba4
--- /dev/null
+++ b/buch/papers/multiplikation/images/bigo.pdf
diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex
new file mode 100644
index 0000000..e3293e4
--- /dev/null
+++ b/buch/papers/multiplikation/images/bigo.tex
@@ -0,0 +1,107 @@
+\documentclass[border=10pt,varwidth]{standalone}
+\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{geometry}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathrsfs}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{lipsum}
+\usepackage{amscd}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage{pgfplots}
+\usepackage{txfonts}
+\usepackage[all]{xy}
+\usepackage{paralist}
+\usepackage[colorlinks=true]{hyperref}
+\usepackage{array}
+\usepackage{tikz}
+\usepackage{slashed}
+\usepackage{pdfpages}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\usetikzlibrary{arrows,matrix,positioning}
+\usetikzlibrary{overlay-beamer-styles}
+\usetikzlibrary{matrix.skeleton}
+\usetikzlibrary{automata,positioning}
+\usetikzlibrary{decorations.text}
+\usepackage{listings}
+\usepackage{multirow}
+\usepackage{color}
+
+\begin{document}
+
+\begin{tikzpicture}
+\begin{axis}[
+    axis lines = left,
+    xlabel = $n$ (Data Input),
+    ylabel = {$t$ (time)},
+    legend pos=north east,
+    very thick,
+    ymax = 500,
+    yticklabels=\empty,
+    xticklabels=\empty,
+    scale only axis=true,
+  width=12cm, height=6cm,
+    ]
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=red,
+]
+{1};
+\addlegendentry{$\mathcal{O}(1)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=green,
+]
+{x};
+\addlegendentry{$\mathcal{O}(n)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=blue,
+]
+{x^2};
+\addlegendentry{$\mathcal{O}(n^2)$}
+\addplot [
+    domain= 1:10,
+    samples=100,
+    color=purple,
+]
+{x^3};
+\addlegendentry{$\mathcal{O}(n^3)$}
+\addplot [
+    domain= 1:10,
+    samples=100,
+    color=black,
+]
+{exp(x)};
+\addlegendentry{$\mathcal{O}(e^n)$}
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=orange,
+]
+{log2(x)};
+\addlegendentry{$\mathcal{O}(\log n)$}
+
+\addplot [
+    domain= 1:20,
+    samples=100,
+    color=gray,
+]
+{x*log2(x)};
+\addlegendentry{$\mathcal{O}(n \log n)$}
+\end{axis}
+\end{tikzpicture}
+
+\end{document}
diff --git a/buch/papers/multiplikation/images/mm_visualisation.pdf b/buch/papers/multiplikation/images/mm_visualisation.pdf
new file mode 100644
index 0000000..9309df1
--- /dev/null
+++ b/buch/papers/multiplikation/images/mm_visualisation.pdf
diff --git a/buch/papers/multiplikation/images/mm_visualisation.tex b/buch/papers/multiplikation/images/mm_visualisation.tex
new file mode 100644
index 0000000..6e8f789
--- /dev/null
+++ b/buch/papers/multiplikation/images/mm_visualisation.tex
@@ -0,0 +1,45 @@
+
+  \begin{tikzpicture}[ampersand replacement=\&]
+
+    \matrix (A)[matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}] at (0,0)
+     {
+     A_{1,1} \& \cdots \& A_{1,k} \& \cdots \& A_{1,n} \\
+     \vdots \&  \& \vdots \&  \& \vdots \\
+     A_{i,1} \& \cdots \& A_{i,k} \& \cdots \& A_{i,n} \\
+     \vdots \&  \& \vdots \& \& \vdots \\
+     A_{m,1} \& \cdots \& A_{m,k} \& \cdots \& A_{m,n} \\
+     };
+ 
+  	 \node [right=0.1 of A] (mul) {$\cdot$};
+
+	 
+     \matrix (B)[right=0.1 of mul, matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}]
+      {
+      B_{1,1} \& \cdots \& B_{1,j} \& \cdots \& B_{1,p} \\
+      \vdots \&  \& \vdots \&  \& \vdots \\
+      B_{k,1} \& \cdots \& B_{k,j} \& \cdots \& B_{k,p} \\
+      \vdots \&  \& \vdots \& \& \vdots \\
+      B_{n,1} \& \cdots \& B_{n,j} \& \cdots \& B_{n,p} \\
+      };
+  
+  	 \node [right=0.1 of B] (eq) {$=$};
+
+     \matrix (C)[right=0.1 of eq, matrix of math nodes, label skeleton, left delimiter=[,right delimiter={]}]
+      {
+      C_{1,1} \& \cdots \& C_{1,j} \& \cdots \& C_{1,p} \\
+      \vdots \&  \& \vdots \&  \& \vdots \\
+      C_{i,1} \& \cdots \& C_{i,j} \& \cdots \& C_{i,p} \\
+      \vdots \&  \& \vdots \& \& \vdots \\
+      C_{m,1} \& \cdots \& C_{m,j} \& \cdots \& C_{m,p} \\
+      };
+
+
+       \node[opacity=0.5, rounded corners=2pt, inner sep=-1pt, fill=green, fit=(A-3-1)(A-3-5)] {};
+       \node[opacity=0.5, rounded corners=2pt, inner sep=-1pt, fill=blue, fit=(B-1-3)(B-5-3)] {};
+       \node[opacity=0.5, rounded corners=2pt, inner sep=-1pt, fill=red, fit=(C-3-3)] {};
+
+
+   \end{tikzpicture}
+
+\end{document}
+
diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf
new file mode 100644
index 0000000..9899dcb
--- /dev/null
+++ b/buch/papers/multiplikation/images/strassen.pdf
diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex
new file mode 100644
index 0000000..797772b
--- /dev/null
+++ b/buch/papers/multiplikation/images/strassen.tex
@@ -0,0 +1,140 @@
+\documentclass[border=10pt]{standalone}
+\usepackage[left=25mm,right=25mm,top=25mm,bottom=25mm]{geometry}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{times}
+\usepackage{geometry}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathrsfs}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{lipsum}
+\usepackage{amscd}
+\usepackage{graphicx}
+\usepackage{fancyhdr}
+\usepackage{textcomp}
+\usepackage{pgfplots}
+\usepackage{txfonts}
+\usepackage[all]{xy}
+\usepackage{paralist}
+\usepackage[colorlinks=true]{hyperref}
+\usepackage{array}
+\usepackage{tikz}
+\usepackage{slashed}
+\usepackage{pdfpages}
+\usepackage{cite}
+\usepackage{url}
+\usepackage{amsmath,amsfonts,amssymb}
+\usepackage{tikz}
+\usetikzlibrary{arrows,matrix,positioning}
+\usetikzlibrary{overlay-beamer-styles}
+\usetikzlibrary{matrix.skeleton}
+\usetikzlibrary{automata,positioning}
+\usetikzlibrary{decorations.text}
+\usepackage{listings}
+\usepackage{multirow}
+\usepackage{color}
+
+\begin{document}
+
+\begin{tikzpicture}[ampersand replacement=\&]
+
+\foreach \i in {1,...,4}
+{
+	\small{
+		\matrix (X\i)[matrix of math nodes,nodes in empty cells,
+		nodes = {draw, minimum size=10mm,
+			anchor=center,
+			inner sep=0pt, outer sep=0pt},
+		column sep=-\pgflinewidth,
+		row sep=-\pgflinewidth,
+		] at (0,-\i*5)
+		{
+			A_{11}B_{11} \& A_{12}B_{11} \& A_{21}B_{11} \& A_{22}B_{11} \\
+			A_{11}B_{21} \& A_{12}B_{21} \& A_{21}B_{21} \& A_{22}B_{21} \\
+			A_{11}B_{11} \& A_{12}B_{12} \& A_{21}B_{12} \& A_{22}B_{12} \\
+			A_{11}B_{22} \& A_{12}B_{22} \& A_{21}B_{22} \& A_{22}B_{22} \\
+		};}
+	
+	\foreach \j in {1,...,7}
+	{
+		\matrix(M\i\j)[matrix of math nodes,nodes in empty cells,
+		nodes = {draw, minimum size=10mm,
+			anchor=center,
+			inner sep=0pt, outer sep=0pt},
+		column sep=-\pgflinewidth,
+		row sep=-\pgflinewidth,
+		] at (\j*5,-\i*5)
+		{
+			\& \& \& \\
+			\& \& \& \\
+			\& \& \& \\
+			\& \& \& \\
+		};
+	}
+}
+
+\huge{
+	\node at (-3,-20)  {$C_{22}=$};
+	\node at (-3,-15) {$C_{21}=$} ;
+	\node at (-3,-10) {$C_{12}=$} ;
+	\node at (-3,-5) {$C_{11}=$} ;
+	
+	\node at (5,-2)  {I};
+	\node at (10,-2)  {II};
+	\node at (15,-2)  {III};
+	\node at (20,-2)  {IV};
+	\node at (25,-2)  {V};
+	\node at (30,-2)  {VI};
+	\node at (35,-2)  {VII};
+}
+
+
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X1-1-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X1-2-2)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X2-3-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X2-4-2)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X3-1-3)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X3-2-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X4-3-3)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(X4-4-4)] {};
+
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-4-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-1-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-4-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M11-1-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M14-1-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M14-2-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M15-4-2)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-2-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M17-4-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-2-2)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M17-4-2)] {};
+
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M23-3-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M23-4-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M25-4-2)] {};
+
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M32-1-3)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M34-1-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M34-2-4)] {};
+
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-4-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-1-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-4-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M41-1-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M42-1-4)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M42-1-3)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M43-3-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M43-4-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M46-1-3)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M46-1-1)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=green, fit=(M46-3-3)] {};
+\node[opacity=0.5, rounded corners=0pt, inner sep=-1pt, fill=red, fit=(M46-3-1)] {};
+\end{tikzpicture}
+
+\end{document}