initial versionHEADmaster

1 files changed, 656 insertions, 0 deletions

diff --git a/dt-complexity.tex b/dt-complexity.tex
new file mode 100644
index 0000000..62c0c4b
--- /dev/null
+++ b/dt-complexity.tex
@@ -0,0 +1,656 @@
+% !TEX root = dt-slides-cpu.tex
+
+\section{Komplexität}
+
+\begin{frame}
+\frametitle{Komplexität}
+\begin{center}
+{\Huge Komplexität}
+
+\vspace{1cm}
+
+Komplexität von Problemen und Algorithmen
+\end{center}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - Primzahltest}
+\begin{block}{Primzahl}
+Eine Primzahl ist eine Zahl, die 
+\begin{itemize}
+\item genau zwei Teiler hat 
+\item nur durch sich selbst und 1 teilbar ist
+\end{itemize}
+Deshalb ist 1 keine Primzahl. 0 ist auch keine Primzahl.
+\end{block}
+
+\begin{block}{Primzahltest - PRIMES}
+Schreiben Sie eine Funktion, die
+\begin{itemize}
+\item eine ganze Zahl x als Parameter erhält
+\item berechnet ob die Zahl eine Primzahl ist
+\item davon abhängig True oder False zurückgibt
+\end{itemize}
+\end{block}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Komplexität - Primzahltest}
+
+\begin{block}{Idee: Probedivision}
+Teste für alle Zahlen i von 3 bis x-1, ob man x durch i ohne Rest teilen kann. 
+\end{block}
+
+\begin{block}{Modulooperation}
+Die Modulorestoperation "rem" (in Rust und C ist "\%" das Operatorzeichen) berechnet den Rest einer Division bei Ganzzahlen. Beispiel:
+
+\begin{equation}
+17 \% 3 = 2
+\end{equation}
+
+weil 17 geteilt durch 3 ist 5 Rest 2. Die Zahl b ist ein Teiler von a, wenn
+
+\begin{equation}
+a \% b = 0
+\end{equation}
+
+\end{block}
+
+\begin{lstlisting}
+fn is_prime (x : u128) -> bool {
+    if x < 2 {
+      return false
+    };
+    i = 2;
+    while i < x {
+      if x % i == 0 {
+        return false;
+      }
+      i += 1;
+    }
+    return true;
+}
+\end{lstlisting}
+
+%\vspace{4cm}
+
+\tiny{source: Dennis Komm, Programmieren und Problemlösen, ETH Zürich, 2020, \url{https://lec.inf.ethz.ch/ppl/2020/slides/pplHandout_05_de.pdf}}
+
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - Primzahltest - Laufzeit}
+\begin{block}{Wie lange braucht das Programm, um die Berechnung durchzuführen}
+\begin{itemize}
+\item Was ist die Laufzeit?
+\item Hängt von der Anzahl der Rechenoperationen ab
+\item Hängt von der Hardware ab
+\item Hier: Hängt von der Anzahl der Schleifendurchläufe ab
+\item Große Primzahl $\Rightarrow$ Viele Schleifendurchläufe $\Rightarrow$ Lange Laufzeit
+\end{itemize}
+\end{block}
+
+\begin{block}{Laufzeit als Funktion der Eingabelänge}
+\begin{itemize}
+\item Die Funktion hat als Eingabeparameter x
+\item Die Zahl x wird n Bit dargestellt.
+\item Die Eingabelänge soll die Anzahl der Bits sein, die für die Darstellung der Zahl x benötigt werden
+\item Mit n Bit kann man die Zahlen von 0 bis $2^n-1$ darstellen.
+\item Eine Zahl, die n Bit für die Darstellung benötigt hat ungefähr die Größe $2^n$.
+\item Wie hängt die Laufzeit von der Eingabelänge ab?
+\end{itemize}
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - Laufzeit - Technologiemodell}
+\begin{block}{Laufzeit - Technologiemodell}
+\begin{itemize}
+\item Ganz am Ende zählt die wirkliche Laufzeit in Sekunden, Tagen, Jahren
+\item Für die Betrachtung von Algorithmen und Problemen will man eine Betrachtung, die unabhängig von der speziellen Hardware ist. 
+\item Ausführungsmodell: Instruktionen werden nacheinander auf einem Prozessor ausgeführt
+\item Speichermodell: Der Zugriff auf Speicher dauert immer gleich lang
+\item Elementare Operationen: Rechenoperationen wie (Addition, Subtraktion, Multiplikation, Division, Modulo, ...), Vergleichsoperationen, Zuweisungen, Sprünge
+\item Einheitsmodell: Jede elementare Operation hat die Kosten (Laufzeit): 1
+\end{itemize}
+\end{block}
+
+\begin{block}{Laufzeit - Technologiemodell - Realität}
+\begin{itemize}
+\item Die Addition und Subtraktion hängt von der Anzahl der Bit ab
+\item Eine Multiplikation oder Division ist komplizierter als eine Addition
+\item Wir haben bei Cache gesehen, dass der Zugriff auf Speicher sehr unterschiedlich lang dauern kann
+\end{itemize}
+\end{block}
+
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - Laufzeit des Primzahltest}
+\begin{block}{Laufzeit des Primzahltest}
+\begin{itemize}
+\item Angenommen x ist eine Primzahl mit n Bit
+\item Die Anzahl der Schleifendurchläufe wächst mit der Größe von $x  \approx 2^n$
+\item Die Schleife wird also in etwa $2^n$ mal ausgeführt
+\item Der Algorithmus benötigt 5 Operationen pro Schleifendurchlauf
+\item Vor der Schleife noch zwei Operation
+\item Also etwa $5 \cdot 2^n + 2$ Operationen 
+\item Die Frage: \glqq Wie verändert sich die Laufzeit in Abhängigkeit von n?\grqq
+\item Entspricht: \glqq Wie verändert sich die Anzahl der benötigten Operationen mit n?\grqq
+\end{itemize}
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - Laufzeit / Anzahl der Operationen des Primzahltests }
+\begin{tikzpicture}
+\begin{axis}[
+  domain=0:5,
+  samples=5,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits},
+  legend entries = {$y = 5 \cdot 2^n + 2$, $y = 20 \cdot n - 8$}]
+  \addplot[blue, ultra thick,mark=*] (x,5 * 2^x + 2);
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität}
+\begin{center}
+{\Huge Asymptotische obere Schranken}
+
+\vspace{1cm}
+
+Wie verändert sich die Laufzeit für große Werte von n
+\end{center}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - Asymptotische obere Schranken}
+\begin{block}{Asymptotische obere Schranken}
+\begin{itemize}
+\item Idee: Nur das Verhalten für  $n \rightarrow \infty$  betrachten
+\item Idee: Klassen von Algorithmen und Problemen schaffen
+\end{itemize}
+\end{block}
+
+\begin{block}{$\mathcal{O}$ Notation}
+\begin{itemize}
+\item Die Menge $\mathcal{O}(2^n)$ enthält alle Funktionen, die nicht schneller wachsen als $c \cdot 2^n$ für eine Konstante $c$.
+\item Die Menge $\mathcal{O}(g(n))$ enthält alle Funktionen $f(n)$, die nicht schneller wachsen als $c \cdot g(n)$ für eine Konstante $c$.
+\item Die $\mathcal{O}$ Notation wird verwendet um die Entwicklung der Laufzeit eines Algorithmus für große n zu beschreiben.
+\item Beispiel: Ein Algorithmus der Klasse $\mathcal{O}(n^2)$ verhält sich für große n so, dass sich bei einer Verdopplung der Eingabelänge, die Laufzeit maximal vervierfacht.
+\end{itemize}
+\end{block}
+
+\begin{block}{$\mathcal{O}$ Notation formal}
+
+\begin{equation*}
+f(n) \in \mathcal{O}(g(n))
+ \Leftrightarrow 
+ \exists c > 0, n_0 \in \mathbb{N} \; \rm{so, dass} \; \forall n \ge n_0: f(n) \le c \cdot g(n)
+\end{equation*}
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Entwicklung}
+\begin{tikzpicture}
+\begin{axis}[
+  domain=0:6,
+  samples=7,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits},
+  legend entries = {$y = 5 \cdot 2^n + 2$, $y = 6 \cdot 2^n$}]
+  \addplot[blue, ultra thick,mark=*] (x,5 * 2^x + 2);
+  \addplot[red, ultra thick,mark=*] (x,6 * 2^x);
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Entwicklung}
+\begin{tikzpicture}
+\begin{axis}[
+  domain=0:20,
+  samples=21,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits},
+  legend entries = {$y = 5 \cdot 2^n + n^8 + 2$, $y = 6 \cdot 2^n$}]
+  \addplot[blue, ultra thick,mark=*] (x,5 * 2^x + x^8 + 2);
+  \addplot[red, ultra thick,mark=*] (x,6 * 2^x);
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Entwicklung}
+\begin{tikzpicture}
+\begin{axis}[
+  domain=0:40,
+  samples=21,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits},
+  legend entries = {$y = 5 \cdot 2^n + n^8 + 2$, $y = 6 \cdot 2^n$}]
+  \addplot[blue, ultra thick,mark=*] (x,5 * 2^x + x^8 + 2);
+  \addplot[red, ultra thick,mark=*] (x,6 * 2^x);
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Entwicklung}
+\begin{tikzpicture}
+\begin{axis}[
+  domain=0:60,
+  samples=21,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits},
+  legend entries = {$y = 5 \cdot 2^n + n^8 + 2$, $y = 6 \cdot 2^n$}]
+  \addplot[blue, ultra thick,mark=*] (x,5 * 2^x + x^8 + 2);
+  \addplot[red, ultra thick,mark=*] (x,6 * 2^x);
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Entwicklung}
+\begin{tikzpicture}
+\begin{axis}[
+  ymode = log,
+  domain=0:60,
+  samples=21,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits},
+  legend entries = {$y = 5 \cdot 2^n + n^8 + 2$, $y = 6 \cdot 2^n$}]
+  \addplot[blue, ultra thick,mark=*] (x,5 * 2^x + x^8 + 2);
+  \addplot[red, ultra thick,mark=*] (x,6 * 2^x);
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Entwicklung}
+\begin{tikzpicture}
+\begin{axis}[
+  ymode = log,
+  domain=0:60,
+  samples=21,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits},
+  legend entries = {$y = 5 \cdot 2^n + n^8 + 2$, $y = 500 \cdot 2^n$}]
+  \addplot[blue, ultra thick,mark=*] (x,5 * 2^x + x^8 + 2);
+  \addplot[red, ultra thick,mark=*] (x,500 * 2^x);
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Beispiele}
+\begin{block}{$\mathcal{O}$ Notation formal}
+\begin{equation*}
+f(n) \in \mathcal{O}(g(n))
+ \Leftrightarrow 
+ \exists c > 0, n_0 \in \mathbb{N} \; \rm{so, dass} \; \forall n \ge n_0: f(n) \le c \cdot g(n)
+\end{equation*}
+\end{block}
+\begin{center}
+\begin{tabular}{l l l}
+$f(n)$ & $\mathcal{O}(?)$ & $c, n_0$ \\\hline
+$3n + 4$ & $\mathcal{O}(n)$ & $c = 4, n_0 = 4$ \\
+$2n$ & $\mathcal{O}(n)$ & $c = 2, n_0 = 0$ \\
+$n^2 + 100n$ & $\mathcal{O}(n^2)$ & $c=2, n_0 = 100$ \\
+$n + \sqrt{n}$ & $\mathcal{O}(n)$  & $c=2, n_0 = 1$
+\end{tabular}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Beispiele}
+\begin{center}
+\begin{tabular}{l p{6cm} l}
+Klasse & Anschaulich & Beispiel \\\hline
+$\mathcal{O}(1)$ & Die Laufzeit ist konstant und nicht abhängig von n & Ist eine Binärzahl gerade \\
+$\mathcal{O}(log\; n)$ & Die Laufzeit wächst um einen konstanten Wert, wenn n sich verdoppelt & Suche in einem sortierten Feld \\
+$\mathcal{O}(n)$ & Wenn n sich verdoppelt, dann verdoppelt sich die Laufzeit & Suche in einem unsortierten Feld \\
+$\mathcal{O}(n^m)$ & Die Laufzeit wächst auf das $2^m$ fache, wenn n sich verdoppelt. Polynomielle Klasse P & Kürzester Weg auf einer Landkarte (Dijkstra) \\
+$\mathcal{O}(2^n)$  & Exponentielle Klasse. Ein zusätzliches Eingabewort verdoppelt die Laufzeit & Erfüllbarkeitsproblem (SAT).
+\end{tabular}
+\end{center}
+SAT Problem: Gibt es bei einem booleschen Ausdruck $y = f(x_{n-1}, ..., x_0)$ aus UND, ODER und NICHT mit n Eingangsvariablen, einen Wert für x, dass der Ausgang 1 wird?
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Beispiele für kleine n}
+\begin{tikzpicture}
+\begin{axis}[
+  ymax=60,
+  domain=0:6,
+  samples=21,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits}]
+  \addplot[blue, ultra thick,mark=*,domain=0:5.7] (x,2^x) node[anchor=west] {$2^n$};
+  \addplot[red, ultra thick,mark=*,domain=0:2.7] (x,x^4) node[anchor=west] {$n^4$};
+  \addplot[green, ultra thick,mark=*] (x,x^2) node[anchor=west] {$n^2$};
+  \addplot[pink, ultra thick,mark=*] (x,x) node[anchor=west] {$n$};
+  \addplot[black, ultra thick,mark=*] (x, {ln(x)}) node[anchor=west] {$log n$} ;
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Beispiele für größere n}
+\begin{tikzpicture}
+\begin{axis}[
+  ymax=1200000,
+  domain=0:24,
+  samples=41,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits}]
+  \addplot[blue, ultra thick,mark=*,domain=0:20] (x,2^x) node[anchor=west] {$2^n$};
+  \addplot[red, ultra thick,mark=*] (x,x^4) node[anchor=west] {$n^4$};
+  \addplot[green, ultra thick,mark=*] (x,x^2) node[anchor=west] {$n^2$};
+  \addplot[pink, ultra thick,mark=*] (x,x) node[anchor=west] {$n$};
+  \addplot[black, ultra thick,mark=*] (x, {ln(x)}) node[anchor=west] {$log n$} ;
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - $\mathcal{O}$ Notation - Beispiele für große n}
+\begin{tikzpicture}
+\begin{axis}[
+  ymax=1E19,
+  domain=0:100,
+  samples=41,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits}]
+  \addplot[blue, ultra thick,mark=*,domain=0:63] (x,2^x) node[anchor=west] {$2^n$};
+  \addplot[red, ultra thick,mark=*,domain=0:100] (x,x^4) node[anchor=west] {$n^4$};
+  \addplot[green, ultra thick,mark=*] (x,x^2) node[anchor=west] {$n^2$};
+  \addplot[pink, ultra thick,mark=*] (x,x) node[anchor=west] {$n$};
+  \addplot[black, ultra thick,mark=*] (x, {ln(x)}) node[anchor=west] {$log n$} ;
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität}
+\begin{center}
+{\Huge Primzahltest schneller machen}
+
+\vspace{1cm}
+
+Erster Versuch
+\end{center}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Primzahltest schneller - Erster Versuch}
+\begin{block}{Idee: Gerade Zahlen auslassen}
+\begin{itemize}
+\item Gerade Zahlen sind keine Primzahlen
+\item Abgesehen von der 2
+\end{itemize} 
+\end{block}
+\begin{lstlisting}
+fn is_prime (x : u128) -> bool {
+    if x < 2 | (x > 2 & x % 2 == 0) {
+      return false
+    };
+    i = 3;
+    while i < x {
+      if x % i == 0 {
+        return false;
+      }
+      i += 2;
+    }
+    return true;
+}
+\end{lstlisting}
+
+\vspace{1cm}
+
+\tiny{source: Dennis Komm, Programmieren und Problemlösen, ETH Zürich, 2020, \url{https://lec.inf.ethz.ch/ppl/2020/slides/pplHandout_05_de.pdf}}
+
+\end{frame}
+
+\begin{frame}
+\frametitle{Primzahltest schneller - Erster Versuch}
+\begin{block}{Wie groß ist die Verbesserung?}
+\begin{itemize}
+\item Schleife wird ca. x/2 Mal durchlaufen statt x Mal
+\item Laufzeit wird doppelt so schnell
+\item Dann: $5 \cdot 2^n/2  + 2 = 2.5 \cdot 2^n + 2$
+\item Laufzeit ist immer noch in $\mathcal{O}(2^n)$
+\item Besser, aber immer noch in der exponentiellen Klasse.
+\end{itemize}
+\end{block}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{Komplexität}
+\begin{center}
+{\Huge Primzahltest schneller machen}
+
+\vspace{1cm}
+
+Zweiter Versuch
+\end{center}
+\end{frame}
+
+\begin{frame}[fragile]
+\frametitle{Primzahltest schneller - Zweiter Versuch}
+\begin{block}{Idee: Nur bis $\sqrt{x}$ suchen}
+\begin{itemize}
+\item Wenn x eine Primzahl ist, dann ist sie teilbar durch eine Zahl $1 < a < x$
+\item Dann ist sie auch durch eine Zahl b teilbar mit $a\cdot b = x$ und $1 < b < x$
+\item Es kann nicht sein, dass $a > \sqrt x$ und $b > \sqrt x$, denn dann wäre $a \cdot b > x$
+\item Deshalb muss einer der Teiler a oder b kleiner als $\sqrt x$ sein
+\end{itemize} 
+\end{block}
+\begin{lstlisting}
+fn is_prime (x : u128) -> bool {
+    if x < 2 | (x > 2 & x % 2 == 0) {
+      return false
+    };
+    i = 3;
+    while i < i.isqrt() {
+      if x % i == 0 {
+        return false;
+      }
+      i += 2;
+    }
+    return true;
+}
+\end{lstlisting}
+
+\vspace{1cm}
+
+\tiny{source: Dennis Komm, Programmieren und Problemlösen, ETH Zürich, 2020, \url{https://lec.inf.ethz.ch/ppl/2020/slides/pplHandout_05_de.pdf}}
+
+\end{frame}
+
+\begin{frame}
+\frametitle{Primzahltest schneller - Zweiter Versuch}
+\begin{block}{Wie groß ist die Verbesserung?}
+\begin{itemize}
+\item Schleife wird ca. $\sqrt x / 2$ Mal durchlaufen 
+\item Laufzeit in $\mathcal{O}(\sqrt{2^n}) = \mathcal{O}(2^{n/2)} = \mathcal{O}(1.415^{n)} )$
+\item Immer noch exponentiell, aber eine andere Basis
+\end{itemize}
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Primzahltest - Zweiter Versuch - Vergleich}
+\begin{tikzpicture}
+\begin{axis}[
+  ymax=9E6,
+  domain=0:45,
+  samples=46,
+  ylabel = {Anzahl der Operationen},
+  xlabel = {Anzahl Bits}]
+  \addplot[blue, ultra thick,mark=*,domain=0:23] (x,2^x) node[anchor=west] {$2^n$};
+  \addplot[red, ultra thick,mark=*,domain=0:45] (x,1.415^x) node[anchor=east] {$1.415^n$};
+\end{axis}
+\end{tikzpicture}
+\end{frame}
+
+\begin{frame}
+\frametitle{Primzahltest schneller - Zweiter Versuch - Vergleich}
+\begin{block}{Wie groß ist die Verbesserung?}
+\begin{itemize}
+\item Angenommen man will die Zahl x = 100 000 000 000 031 testen
+\item Angenommen ein Rechner schafft 1000 Schleifendurchläufe pro Sekunde
+\item $ i < x $ : 3100 Jahre
+\item $ i < \sqrt x $: 3 Stunden
+\item Selbst ein Rechner, der 100 mal schneller ist, braucht für den langsameren Primzahlentest noch 31 Jahre.
+\end{itemize}
+\end{block}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{Komplexität}
+\begin{center}
+{\Huge Komplexität Algorithmus vs. Problem}
+
+\vspace{1cm}
+
+Ist das Problem so schwierig, oder habe ich nur einen schlechten Algorithmus?
+\end{center}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität - Problem vs. Algorithmus}
+\begin{block}{Ist das Problem so schwierig, oder finde ich nur schlechte Algorithmen}
+\begin{itemize}
+\item Bei dem Primzahltest haben wir drei Algorithmen gefunden, die sich in der Laufzeit in Abhängigkeit von n unterscheiden
+\item Für die Laufzeit macht $\mathcal{O}(1.415^{n} )$ einen großen Unterschied zu $\mathcal{O}(2^n)$ für größere n
+\item Gibt es Algorithmen, die noch schneller als $\mathcal{O}(1.415^{n} )$ sind?
+\item Man unterscheidet  zwischen der Komplexitätsklasse eines Problems und der Komplexitätsklasse eines konkreten Algorithmus
+\item Wenn man für ein Problem beweisen kann, dass es mindestens in einer Klasse $\mathcal{O}(2^n)$ ist, dann kann man keinen Algorithmus finden, der in einer schnelleren Klasse ist.
+\item Beispielsweise ist man sich für das "Problem des Handlungsreisenden" (engl. "Travelling Salesman Problem") sehr sicher, dass es nicht in Polynomialer Zeit $\mathcal{O}(n^m)$ im worst-case zu lösen ist. \url{https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden}
+\item 2002 haben M. Agrawal, N. Kayal, N. Saxena einen Algorithmus (AKS-Primzahltest) gefunden, der in polynomieller Laufzeit feststellt, ob eine Zahl eine Primzahl ist. Das Primzahlproblem (PRIMES) ist also in der Klasse der Probleme, die in polynomieller Zeit gelöst werden können. Siehe: \url{https://de.wikipedia.org/wiki/AKS-Primzahltest}. Allerdings ist die Konstante so groß, dass in der Praxis z.B. der Miller-Rabin Algorithmus mit $\mathcal{O}(n^2 log n)$ eingesetzt wird.
+\end{itemize}
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität von Schaltungen}
+\begin{center}
+{\Huge Komplexität von booleschen Funktionen}
+
+\vspace{1cm}
+
+Wieviele Gatter brauche ich? Wie ist die Schaltungstiefe?
+\end{center}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität von booleschen Funktionen und Schaltungen}
+\begin{block}{Bei Schaltungen kann man eine analoge Betrachung der Komplexität machen}
+\begin{itemize}
+\item Bei Schaltungen betrachtet man die Anzahl der benötigten Gatter
+\item Dabei nimmt man als Elementargatter häufig alle Gatter mit maximal zwei Eingängen.
+\item Bei Schaltungen schaut man sich auch die Schaltungstiefe an, da damit die zu erwartende Verzögerungszeit verbunden ist
+\item Bei Schaltungen gibt man an in welcher $\mathcal{O}( )$ Klasse man in Bezug auf die Anzahl der Gatter und in welcher $\mathcal{O}( )$ Klasse man in Bezug auf die Schaltungstiefe ist
+\item Auch bei Schaltungen will man das asymptotische Verhalten in Bezug auf die Eingangswortlänge wissen.
+\end{itemize}
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität der UND Funktion}
+\begin{columns}
+\begin{column}{0.4\textwidth}
+\center
+\begin{tikzpicture}[circuit logic IEC, circuit ee IEC,scale=0.6]
+\draw (0,0) node[and gate] (g0) {};
+\draw (0,2) node[and gate] (g1) {};
+\draw (0,4) node[and gate] (g2) {};
+\draw (0,6) node[and gate] (g3) {};
+\draw (2,1) node[and gate] (g4) {};
+\draw (2,5) node[and gate] (g5) {};
+\draw (4,3) node[and gate] (g6) {};
+\foreach \i in {0,1,2,3}
+{
+\draw (g\i.input 1) -- ++(left:0.5);
+\draw (g\i.input 2) -- ++(left:0.5);
+}
+\draw (g0.output) -- ++(right:0.5) |- (g4.input 2);
+\draw (g1.output) -- ++(right:0.5) |- (g4.input 1);
+\draw (g2.output) -- ++(right:0.5) |- (g5.input 2);
+\draw (g3.output) -- ++(right:0.5) |- (g5.input 1);
+\draw (g4.output) -- ++(right:0.5) |- (g6.input 2);
+\draw (g5.output) -- ++(right:0.5) |- (g6.input 1);
+\draw (g6.output) -- ++(right:0.5);
+\end{tikzpicture}
+Baumstruktur 
+\end{column}
+\begin{column}{0.6\textwidth}
+\center
+\begin{tikzpicture}[circuit logic IEC, circuit ee IEC, scale=0.6]
+\coordinate (start) at (0,0) ;
+\draw (0,0) -- ++(right:0.5) node [and gate, anchor=input 2] (g0) {};
+\draw (g0.input 1) -- ++(left:0.5);
+\foreach \i / \in in {0/1,1/2,2/3,3/4,4/5,5/6}
+{
+\draw (g\i.output) -- ++(right:0.25) -- ++(up:0.5) -- ++(right:0.25) node[and gate, anchor=input 2] (g\in) {};
+\draw (g\in.input 1) -- (start |- g\in.input 1);
+}
+\draw (g6.output) -- ++(right:0.25);
+\end{tikzpicture} 
+Kettenstruktur
+\end{column}
+\end{columns}
+\begin{block}{UND mit Baumstruktur}
+Die UND Schaltung mit n Eingängen mit einer Realisierung als Baumstruktur ist in $\mathcal{O}(n)$ bezüglich der Anzahl der benötigten Gatter, da man genau $n-1$ Gatter benötigt. Die Schaltung ist bezüglich der Schaltungstiefe in der Klasse $\mathcal{O}(\log n)$, da sich die Schaltungstiefe bei doppelt so vielen Eingängen um 1 erhöht. 
+\end{block}
+\begin{block}{UND in Kettenstruktur}
+Die UND Schaltung in Kettenstruktur ist auch in der Klasse $\mathcal{O}(n)$  bezüglich der Anzahl der benötigten Gatter. Bezügliche der Schaltungstiefe ist die Schaltung in der Klasse $\mathcal{O}(n)$.
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität Addition}
+\begin{tikzpicture}[circuit logic IEC, circuit ee IEC]
+\draw (8,0) node[rectangle, draw, minimum width = 2cm, minimum height = 2cm] (ha) {HA};
+\draw (5,0) node[rectangle, draw, minimum width = 2cm, minimum height = 2cm] (va1) {VA};
+\draw (2,0) node[rectangle, draw, minimum width = 2cm, minimum height = 2cm] (va2) {VA};
+\draw (-1,0) node[rectangle, draw, minimum width = 2cm, minimum height = 2cm] (va3) {VA};
+\draw (ha.north east) ++(left:0.5) -- ++(up:0.5) node [anchor=south] {$b_0$}  ++(down:1) node[anchor=south] {$b$};
+\draw (ha.north west) ++(right:0.5) -- ++(up:0.5) node [anchor=south] {$a_0$}  ++(down:1) node[anchor=south] {$a$};
+\draw (ha.west) node[anchor=west] {$c_o$};
+\draw (ha.south) node[anchor=south] {$s$} -- ++(down:1) node[anchor=north] {$s_0$};
+\foreach \i in {1,2,3}
+{
+\draw (va\i.north east) ++(left:0.5) -- ++(up:0.5) node [anchor=south] {$b_\i$} ++(down:1) node[anchor=south] {$b$};
+\draw (va\i.north west) ++(right:0.5) -- ++(up:0.5) node [anchor=south] {$a_\i$} ++(down:1) node[anchor=south] {$a$};
+\draw (va\i.west) node[anchor=west] {$c_o$};
+\draw (va\i.east) node[anchor=east] {$c_i$};
+\draw (va\i.south) node[anchor=south] {$s$} -- ++(down:1) node[anchor=north] {$s_\i$};
+\draw (va\i.east) -- node[above] {$c_\i$}++(right:1);
+}
+\end{tikzpicture} 
+\begin{block}{Komplexität Addition}
+Für eine Addition von zwei n-Bit Zahlen mit dem Carry Ripple Adder werden 5n-3 Gatter benötigt. Deshalb ist die Addition mit Carry Ripple bezüglich der Anzahl der benötigten Gatter in der Klasse  $\mathcal{O}(n)$. Bezüglich der Schaltungstiefe ist die Carry Ripple Addition in der Klasse  $\mathcal{O}(n)$, da bei einer Verdopplung der Anzahl der Bits die Anzahl der Volladdierer, die für das Carry durchlaufen werden müssen, sich auch in etwas verdoppelt.
+\end{block}
+\end{frame}
+
+\begin{frame}
+\frametitle{Komplexität Multiplikaton}
+\includegraphics[width=0.7\textwidth]{complexity/multiplier}
+\begin{block}{Komplexität Multiplikation}
+Für eine Multiplikation von zwei n-Bit Zahlen mit dem Matrixmultipizieren werden n Carry Ripple Addierer benötigt. Deshalb ist die Multiplikation mit Carry Ripple bezüglich der Anzahl der benötigten Gatter in der Klasse  $\mathcal{O}(n^2)$. Bezüglich der Schaltungstiefe ist der Matrix Multiplizierer in der Klasse  $\mathcal{O}(n)$.
+\end{block}
+\tiny{source: Dirk Hoffmann, Grundlagen der Technischen Informatik, Hanser, 2023}
+
+\end{frame}
+
+
+