From 3875ac2b8df9145a66e9f6fcf34e77eb3bc2d072 Mon Sep 17 00:00:00 2001 From: Nunigan Date: Tue, 27 Jul 2021 22:01:05 +0200 Subject: added first part of paper and code --- buch/papers/multiplikation/images/bigo.pdf | Bin 0 -> 24288 bytes buch/papers/multiplikation/images/bigo.tex | 107 ++++++++++++++++ .../multiplikation/images/mm_visualisation.pdf | Bin 0 -> 21665 bytes .../multiplikation/images/mm_visualisation.tex | 45 +++++++ buch/papers/multiplikation/images/strassen.pdf | Bin 0 -> 15850 bytes buch/papers/multiplikation/images/strassen.tex | 140 +++++++++++++++++++++ 6 files changed, 292 insertions(+) create mode 100644 buch/papers/multiplikation/images/bigo.pdf create mode 100644 buch/papers/multiplikation/images/bigo.tex create mode 100644 buch/papers/multiplikation/images/mm_visualisation.pdf create mode 100644 buch/papers/multiplikation/images/mm_visualisation.tex create mode 100644 buch/papers/multiplikation/images/strassen.pdf create mode 100644 buch/papers/multiplikation/images/strassen.tex (limited to 'buch/papers/multiplikation/images') diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf new file mode 100644 index 0000000..dfa2ba4 Binary files /dev/null and b/buch/papers/multiplikation/images/bigo.pdf differ 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 Binary files /dev/null and b/buch/papers/multiplikation/images/mm_visualisation.pdf differ 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 Binary files /dev/null and b/buch/papers/multiplikation/images/strassen.pdf differ 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} -- cgit v1.2.1