\documentclass[a4paper,12pt]{scrartcl}
\usepackage[ngerman]{babel}
\usepackage{graphicx} %BIlder einbinden
\usepackage{amsmath} %erweiterte Mathe-Zeichen
\usepackage{amsfonts} %weitere fonts
\usepackage[utf8]{inputenc} %Umlaute & Co
\usepackage{hyperref} %Links
\usepackage{ifthen} %ifthenelse
\usepackage{enumerate}

\usepackage{algpseudocode} %Pseudocode
\usepackage{dsfont} % schöne Zahlenräumezeichen
\usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen
\usepackage{tikz} %TikZ ist kein Zeichenprogramm
\usetikzlibrary{trees,automata,arrows,shapes}

\pagestyle{empty}


\topmargin-50pt

\newcounter{aufgabe}
\def\tand{&}

\newcommand{\makeTableLine}[2][0]{%
  \setcounter{aufgabe}{1}%
  \whiledo{\value{aufgabe} < #1}%
  {%
    #2\tand\stepcounter{aufgabe}%
  }
}

\newcommand{\aufgTable}[1]{
  \def\spalten{\numexpr #1 + 1 \relax}
  \begin{tabular}{|*{\spalten}{p{1cm}|}}
    \makeTableLine[\spalten]{A\theaufgabe}$\Sigma$~~\\ \hline
    \rule{0pt}{15pt}\makeTableLine[\spalten]{}\\
  \end{tabular}
}

\def\header#1#2#3#4#5#6#7{\pagestyle{empty}
\begin{minipage}[t]{0.47\textwidth}
\begin{flushleft}
{\bf #4}\\
#5
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
#6 \vspace{0.5cm}\\
%                 Number of Columns    Definition of Columns      second empty line
% \begin{tabular}{|*{5}{C{1cm}|}}\hline A1&A2&A3&A4&$\Sigma$\\\hline&&&&\\\hline\end{tabular}\\\vspace*{0.1cm}
\aufgTable{#7}
\end{flushright}
\end{minipage}
\vspace{1cm}
\begin{center}
{\Large\bf Übungsblatt #1}

{(Abgabe #3)}
\end{center}
}



%counts the exercisenumber
\newcounter{n}

%Kommando für Aufgaben
%\Aufgabe{AufgTitel}{Punktezahl}
\newcommand{\Aufgabe}[2]{\stepcounter{n}
\textbf{Aufgabe \arabic{n}: #1} (#2 Punkte)}


\begin{document}
    %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben}
    \header{2}{}{2015-05-05}{Evolutionäre Algorithmen}{
    	\textit{Jan-Peter Hohloch}\\ \textit{Maximus Mutschler}
    }{SS 15}{4}
    \vspace{0.5cm} \Aufgabe{Bit-Climber}{7}
        \begin{enumerate}[(a)]
            \item $\left|N_1(x)\right|=1+n=1+6=7$, $\left|N_4(x)\right|=1+6+{6\choose 2}+{6\choose 3}+{6\choose 4}=57$\\
            $\left|N_k(x)\right|=\sum\limits_{i=0}^{k}{n\choose i}=\sum\limits_{i=0}^{k} \frac{n!}{i!\cdot (n-i)!}=1+n+\frac{n(n-1)}{2}+\frac{n(n-1)(n-2)}{3!}+\dots \Rightarrow\mathcal{O}(n^k)$; für kleine $k$ also effizient, für $k$ fest polynomiell.
            \item Die Fitness wächst, wenn der Abstand zu 23 verringert wird:\\
            $x_0=101101_2,\ f(x_0)=484$\\
            $x_1=001101_2,\ f(x_1)=100$\\
            $x_2=011101_2,\ f(x_2)=36$\\
            $x_3=010101_2,\ f(x_3)=4$\\
            $x_4=010111_2,\ f(x_4)=0$
            \item Lokales Maximum: $000000_2 \rightarrow f(x) = 529_{10}$\\
                Globales Maximum : $111111_2 = 63_{10} \rightarrow f(x) = 1600_{10}$\\
                Gute Werte liegen möglichst weit am Rand des möglichen Bereiches. Wir betrachten also jeweils die höchste und kleinste mutierbare Zahl.\\
                Startlösung $x_b = 000001_2 \rightarrow f(x)= 484_{10}$
                \begin{itemize}
                    \item Sei $k=1$
                        \begin{itemize}
                            \item In erster Iteration mutierter kleinster
                                Wert:  $ 000000_2\rightarrow f(x)=529_{10}$\\
                                In  erster Iteration mutierter höchster Wert: $100001_2 \rightarrow f(x)=100_{10} $\\
                                $\rightarrow f(000000_2) > f(000001_2) \rightarrow$ übernehme $000000_2$
                            \item In zweiter Iteration mutierter kleinster
                                Wert:  $ 000000_2\rightarrow f(x)=529_{10}$\\
                                In  erster Iteration mutierter höchster Wert: $100000_2 \rightarrow f(x)=81_{10} $\\
                                $\rightarrow f(000000_2) > f(100000_2) \rightarrow$ behalte $000000_2$
                        \end{itemize}
                    \item Sei $k=2$
                        \begin{itemize}
                            \item In erster Iteration mutierter kleinster Wert:  $ 000000_2\rightarrow f(x)=529_{10}  $  \\
                            In erster Iteration mutierter höchster Wert: $110001_2 \rightarrow f(x)=676_{10} $\\
                        $\rightarrow$ da $110001_2$ bereits größer als das lokale Maximum bei $0$ ist, wird kein kleinerer Wert mehr gewählt werden $\rightarrow$ Konvergenz gegen globales Maximum ($63$).\\
                        \end{itemize}
                \end{itemize}
        \end{enumerate}
\pagebreak
    \Aufgabe{Monte-Carlo-Algorithmus}{6}
        \begin{enumerate}[(a)]
            \item Suchraum $\left|\{0,1\}\right|^6=2^6=64$, $p=\frac{1}{64}$\\
                $P(a^*\text{ nach n Würfen})=\sum\limits_{k=0}^{n-1}(1-p)^kp=p\cdot\frac{1-(1-p)^n}{1-(1-p)}=1-(1-p)^n$\\
                gefordert: $P\geq 0.95$\\
                \begin{align*}
                    &1-(1-p)^n &\geq& 0.95\\
                    \Leftrightarrow &(1-p)^n &\leq& 0.05\\
                    \Leftrightarrow &\left(\frac{63}{64}\right)^n &\leq& 0.05\\
                    \Leftrightarrow &n\log\left(\frac{63}{64}\right) &\leq& \log(0.05)\\
                    \Leftrightarrow &n&\geq& \frac{\log 0.05}{\log \frac{63}{64}}
                \end{align*} $\Rightarrow n\geq 194$\\
                Codiert man Zahlen im Zehnersystem, so vergrößert sich der Suchraum bei gleichbleibender Stellenzahl: $\left|\{0,1,\dots, 9\}\right|=10^6$ (sollten auch negative Zahlen berücksichtigt werden, so vergrößert sich der Suchraum auf $2\cdot 10^6$)\\Dadurch verringert sich die Wahrscheinlichkeit das Optimum zu ziehen $p=10^{-6}$\\
                Für $n$ gilt dann: $n\geq\frac{\log 0.05}{\log \frac{10^6-1}{10^6}}\approx 2.996\cdot 10^6$ (bzw. $\geq\frac{\log 0.05}{\log \frac{2\cdot 10^6-1}{2\cdot 10^6}}\approx5.991\cdot 10^6$)
            \item Man kann manuell würfeln. Mögliche Zufallsfolge: $46,33,14$\\
                Das Optimum wurde nicht gefunden. Auch könnte der Algorithmus noch viele Iterationen benötigen, bis er terminiert. Darin besteht schon ein Gegensatz zum Bit-Climber. Dieser hält bereits nach dem vierten Versuch. Bei einer anderen Zufallsfolge ($23$ enthalten) würde der Monte-Carlo-Algorithmus jedoch schneller terminieren.\\
                Außerdem muss für den aus der VL bekannten Monte-Carlo-Algorithmus das Optimum bereits bekannt sein, während der Bit-Climber lediglich die Fitnessfunktion benötigt. Im gegebenen Beispiel ergibt jedoch die Suche nach einem bekannten Optimum keinen Sinn.
            \item Ein bekanntes Beispiel ist die Berechnung der Kreiszahl $\pi$
                mittels eines two-sided Monte-Carlo-Algorithmus. Hierbei werden zufällig Punkte in einem Quadrat (Seitenlänge $a$) erzeugt, in dem ein Kreis (Durchmesser $a$) liegt. Aus der Häufigkeit mit der die Punkte im Kreis liegen, lässt sich seine Fläche und damit $\pi$ schätzen. ($A=\pi\cdot \frac{a^2}{4}$ vs. $A=a^2$ $\Rightarrow P(\text{Kreis})=\frac{\pi}{4}$) (vgl. \href{https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus#Probabilistische_Bestimmung_der_Zahl_Pi}{Wikipedia})
        \end{enumerate}
\pagebreak
    \Aufgabe{Gradientenverfahren}{7}
        \begin{enumerate}[(a)]
            \item $f'(x)=-\sin(x+2)+\frac{1}{2}$. Lokale Extrema in
                Nullstellen der Ableitung:\\
                $f'(x)=0\Leftrightarrow -\sin(x+2)+\frac{1}{2}=0\Leftrightarrow \sin(x+2)=\frac{1}{2},\ \alpha=x+2$\\
                $\sin(\alpha)=\frac{1}{2}\Rightarrow \alpha=\frac{1}{6}\pi + k\cdot 2\pi \text{ oder } \alpha=\frac{5}{6}\pi + k\cdot 2\pi,\ k\in\mathds{Z}$\\
                $\alpha \in [-2\pi+2,2\pi+2]\Rightarrow \alpha_1=-\frac{7}{6}\pi,\ \alpha_2=\frac{1}{6}\pi,\ \alpha_3=\frac{5}{6}\pi,\ \alpha_4=\frac{13}{6}\pi$\\
                $\Rightarrow x_1=-\frac{7}{6}\pi-2\approx -5.665$, $x_2\approx -1.476$, $x_3\approx 0.618$, $x_4\approx 4.807$\\
                $f''(x)=-\cos(x+2) \Rightarrow$ Maxima: $x_2,x_4$, Minima: $x_1,x_3$\\
                $f(x_1)<f(x_3)\Rightarrow$ globales Minimum $x_1$\\
                $f(x_2)<f(x_4)\Rightarrow$ globales Maximum $x_4$
            \item Minimum bei Startpunkt $x_0 = x_3$ \\
                Werte für globales Minimum: $x\in [-2*\pi, \frac{\pi}{6} -2=x_2 [$ \\
                Begründung: Dieses Gradientenverfahren folgt bei der Bestimmung eines Minimum immer dem Gradienten abwärts.
        \end{enumerate}
\end{document}