From 1da5f4a88a84c3a6bd134be5ef244d0f3d14aab5 Mon Sep 17 00:00:00 2001 From: Friedrich Beckmann Date: Tue, 8 Sep 2026 10:09:59 +0200 Subject: initial version --- dt-complexity.tex | 656 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 656 insertions(+) create mode 100644 dt-complexity.tex (limited to 'dt-complexity.tex') 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} + + + -- cgit v1.2.3