\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{1cm}
    \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}$, dies ist linear in $n$, exponentiell in $k$. Für $k << n$ also recht effizient.
            \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 Lokale Maxima liegen in $0$ und $63$. %TODO
        \end{enumerate}

    \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$ 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.99\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}$)
        \end{enumerate}

    \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}$\\
            $\sin(a)=\frac{1}{2}\Rightarrow a=\frac{1}{6}\pi + k\cdot 2\pi \text{ oder } a=\frac{5}{6}\pi + k\cdot 2\pi,\ k\in\mathds{Z}$\\
            $a \in [-2\pi+2,2\pi+2]\Rightarrow a_1=-\frac{7}{6}\pi,\ a_2=\frac{1}{6}\pi,\ a_3=\frac{5}{6}\pi,\ a_4=\frac{13}{6}\pi$\\
            $\Rightarrow x_1=$
        \end{enumerate}
\end{document}