path: root/dt-complexity.tex

% !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}