uni/ws2019/ipi/uebungen/ipi3.tex

\documentclass{../../../lecture}

\usepackage{enumerate}

\begin{document}

\begin{aufgabe} Algorithmische Komplexität
\begin{enumerate}[a)] 
    \item Laufzeiten der verschiedenen algorithmischen Komplexitäten $f(n)$ für $2n$ in Abhängigkeit von
        der Ausgangslaufzeit für $n$.

        \begin{tabular}{|l|l|l|l|}
            \hline
            $f(n)$ & 4 Sekunden & 10 Sekunden & 100 Sekunden \\ \hline
            $\text{ld}(2n)$ & 5s & 11s & 101s \\ \hline
            $2n$ & 8s & 20s & 200s \\ \hline
            $2n \text{ ld}(2n)$ & 13,49s & 29,13s & 244,64s\\ \hline
            $(2n)^{3}$ & 32s & 80s & 800s \\ \hline
            $2^{2n}$ & 16s & 100s & 10000s\\ \hline
        \end{tabular}

    \item
        \begin{enumerate}[1.]
            \item $1$
            \item $\log \log n$
            \item $\log n$
            \item $n^{\epsilon}$
            \item $n^{c}$
            \item $n^{\log n}$
            \item $c^{n}$
            \item $n^{n}$
            \item $c^{\left( c^{n} \right) }$
        \end{enumerate}

    \item Beweisen Sie folgende Behauptungen
        \begin{enumerate}
            \item $x^{a} = O(x^{b}) \iff a -b \le 0$
                \begin{proof}
                    Seien $a, b, x \in \R$ mit $x > 1 $

                    Zu zeigen: $\exists c \in \R$: $x^{a} \le c x^{b} \iff a \le b$

                    Wegen $x > 1$ ist $\ln(x) > 0$ und $\ln(x)$ streng monoton steigend, wähle $c \ge  1$, dann
                    folgt:
                    \begin{align*}
                        &a \le b \\
                        \iff &\ln(x) \cdot a \le \ln(x) \cdot b \le \ln(c) + \ln(x) \cdot b \\
                        \iff &\ln(x^{a}) \le \ln(c\cdot b^{x})\\
                        \iff & x^{a} \le c x^{b}
                    .\end{align*}
                \end{proof}
            \item $\log_a(x) = \Theta(\log_b(x))$ $\forall a, b \in \R^{+}$ 
                \begin{proof}
                    Seien $a, b, x \in \R^{+}$.

                    Zu zeigen: $\exists c \in \R$: $\log_a(x) = c \cdot \log_b(x)$.
                    \begin{align*}
                        &\log_a(x) = \log_a(x) \\
                        \implies & \log_a(x) = \log_a(b) \cdot \frac{\log_a(x)}{\log_a(b)} \\
                        \implies & \log_a(x) = \log_a(b) \cdot \log_b(x)
                    .\end{align*}
                    Mit $c := \log_a(b)$ folgt damit:
                    \[
                        \log_a(x) = c \cdot \log_b(x)
                    .\] 
                \end{proof}
            \item $a^{x} = O(b^{x}) \iff 0 \le a \le b$
                \begin{proof}
                    Seien $a, b, x \in \R$ mit $x \ge 0$

                    Zu zeigen: $\exists c \in \R$: $a^{x} \le c b^{x} \iff 0 \le a \le b$
                    \begin{align*}
                        &0 \le a \le b \\
                        \iff &a^{x} \le b^{x} \le b^{x+1} = b \cdot b^{x}
                    .\end{align*}
                    Mit $c := b$ folgt damit:
                    \[
                    a^{x} \le c \cdot b^{x} \iff 0 \le a \le b
                    .\] 
                \end{proof}
        \end{enumerate}
\end{enumerate}
    
\end{aufgabe}

\begin{aufgabe} Klassischer Euklidischer Algorithmus

    Sei $a, b \in \N_0, a+b > 0$ gegeben.
    \[
        \text{ggT}(a, b) = \begin{cases}
            a & b =0 \\
            \text{ggT}(b,a) & a < b \\
            \text{ggT}(a - b, b) & a \ge b \\
        \end{cases}
    .\] 

    \begin{enumerate}
        \item Für $a \ge b > 0$ gilt:
            \[
                \text{ggT}(a,b) = \text{ggT}(a -b, b)
            .\] 
            \begin{proof}
                Wegen $b \neq 0$ und $a \ge b$ folgt nach Definition:
                \[
                    \text{ggT}(a, b) = \text{ggT}(a -b, b)
                .\] 
            \end{proof}
        \item Der klassische Euklidische Algorithmus terminiert.
            \begin{proof}
                Seien $(a_n)_{n\in\N} \in \N_0$ und $(b_n)_{n\in\N} \in \N_0$ Folgen mit $a_1 = a$ und
                 $b_1 = b$.

                Sei $n \in \N$ beliebig.
                
                \begin{itemize}
                    \item Falls $b_n = 0$ terminiert der Algorithmus direkt.
                    \item   
                        Falls $a_n < b_n$, folgt nach Definition:
                        \[
                            a_{n+1} = b_n \text{ und } b_{n+1} = a_n < b_n 
                        .\] Damit folgt:
                        \[
                            b_{n+1} < b_n
                        .\] 
                    \item Falls $a_n \ge b_n$ folgt nach Definition:
                        \[
                            a_{n+1} = (a_n - b_n) \in \N_0 \text{ und } b_{n+1} = b_n
                        .\] Wegen $a_{n+1} < a_n $ folgt, dass $\exists k \in \N$: $a_{n+k} < b_n$. Dann
                        tritt wieder der zweite Fall ein, d.h.
                        \[
                        b_{n+k+1} < b_n
                        .\] 
                \end{itemize}

                Damit folgt, dass $(b_n)_{n\in\N}$ für fast alle $n \in \N$ streng monoton fällt.
                Da $(b_n)_{n \in \N} \in \N_0$, folgt:
                \[
                    \exists k \in \N\text{: } b_k = 0
                .\] 
                Damit terminiert der \textit{klassische Euklidische Algorithmus} immer.
            \end{proof}
    \end{enumerate}
\end{aufgabe}

\begin{aufgabe} 
    Binomialkoeffizient
    \begin{enumerate}[a)]
        \item Programm siehe \textit{binomial.cc}

            Für $n = 35$ und $k = 18$  benötigt das Programm mehr als 20 Sekunden für die Berechnung.

            Für $n = 34$ und $k =  18$ liefert das Programm $-2091005866$. Das liegt an der
            begrenzten Größe des Datentyps \textbf{int}. Bei Überschreitung der maximalen Größe
            beginnt der Wert erneut bei dem Minimalwert des Datentyps \textbf{int}. Deshalb können
            wir dann negative Ergebnisse erhalten.
        \item Der Rechenaufwand für die rekursive Berechnung des Binomialkoeffizienten ist:
            \begin{align*}
                A_{n, 0} = A_{n, n} = A_{n, k>n} = 1  \\
                A_{n,k} = A_{n-1, k-1} + A_{n-1, k}
            .\end{align*}
        \item Programm siehe \textit{binomial\_fast.cc}

            Die schnellere Variante hat die Komplexität $O(n)$, da die Komplexität der Fakultätsfunktion 
            $O(n)$  ist und diese einfach dreimal ausgeführt wird.

            Programm (c) ist deutlich schneller als Programm (a) für größere Zahlen $n$ und $k$. Aufgrund
            der Verwendung der Fakultät, wird allerdings schneller die maximale Größe eines \textbf{int}'s
            erreicht. Dadurch erhalten wir bereits für recht kleine Werte für $n$ und $k$ falsche Ergebnisse.
        \item Ein effizienter Algorithmus berechnet jede Zeile linear iterativ, aus der vorhergehenden
            Zeile, damit ist die Komplexität $O(n)$.

            Der Unterschied entsteht daraus, dass bei (a) einzelne Binomialkoeffizienten mehrfach
            ausgerechnet werden müssen und bei (d) jeder Binomialkoeffizient genau einmal ausgerechnet wird.
    \end{enumerate}
\end{aufgabe}

\end{document}