\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 1-Nachbarschaft: $ \binom{6}{1} = 6 $ vielleicht +1 wenn man x0 selbst als Teil der Nachbarschaft sieht??\\
      	4-Nachbarschaft:  $ \binom{6}{1}+\binom{6}{2}+\binom{6}{3}+\binom{6}{4} = 56 $\\
      	k-Nachbarschaft: $ \sum_{i=1}^{k} \frac{n!}{i!*(n-i)!}$\\
      	Rechenaufwand für $n \gg k$: $ \sum_{i=1}^{k} \frac{n!}{i!*(n-i)!} \leq k*\frac{n!}{k!*(n-k)!} $\\
      	$n \gg k \Rightarrow k=1$ Darf ich das ?\\
      	$\Rightarrow  \frac{n!}{(n-1)!} \Rightarrow O(n) $  \\
      \item $f(x) = (010111_2 -x)^2 = (23_{10}-x)^2$\\
      $x_0= 101101_2 = 45_{10} \rightarrow f(x_0)= 484_{10} \\
      x_1= 001101_2 = 13_{10} \rightarrow f(x_1)= 100_{10} \\
      x_2= 011101_2 = 29_{10} \rightarrow f(x_2)= 36_{10} \\
      x_3= 010101_2 = 21_{10} \rightarrow f(x_3)= 4_{10} \\
      x_4= 010111_2 = 23_{10} \rightarrow f(x_3)= 0_{10} \\
      $
      \item Lokales Maximum: $000000_b \rightarrow f(x) = 529_{10}$\\
      Globales Maximum : $111111_b = 63_{10} \rightarrow f(x) = 1600_{10}$\\
      Startlösung $x_b = 000001_b \rightarrow f(x)= 484_{10}$ \\
      Sei $k=1$\\
      In erster Iteration mutierter kleinster Wert:  $ 000001_2\rightarrow f(x)=529_{10}  $ \\
      In  erster Iteration mutierter höchster Wert: $100000_2 \rightarrow f(x)=81_{10} $\\
      $\rightarrow x_n > 000001_2 \rightarrow$ behalte $x_n$ und terminiere\\
      Sei $k=2$\\
      In erster Iteration mutierter kleinster Wert:  $ 000000_2\rightarrow f(x)=529_{10}  $  \\
      In erster Iteration mutierter höchster Wert: $110000_2 \rightarrow f(x)=625_{10} $\\
      $\rightarrow$ da $110000_2$ bereits größer als das globale Maximum ist, wird kein kleinerer Wert mehr gewählt werden $\rightarrow$ Konvergenz gegen globales Maximum.\\
    \end{enumerate}
    
    
     \Aufgabe{Monte-Carlo Suche}{6}
     \begin{enumerate}[(a)]
     	\item Suchraum  $n=6$ binär: $2^6 =64$ \\
     	 $P(a^*|k)= 0.95\rightarrow k = 64-5\% = 64-\frac{64*5}{100} = 60.8 \rightarrow $ 61 Ziehungen.\\
     	 \\ Suchraum $n=6 \in \mathbb{Z}$ = $10^{6}*2$ \\
     	  $P(a^*|k)= 0.95\rightarrow k$ = 1900000 Ziehungen
     	  \\ Der Suchraum wird ca. 32000x größer. TODO..
     	 \item JP das darfst du machen die Aufgabe find ich dumm.. soll ich einfach Würfeln.? TODO
     	 \item Eine weitere Version des Monte-Carlo-Algorithmus wird für Entscheidungsprobleme (Ja-Nein-Probleme) verwendet.\\
     	 http://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus  TODO
     \end{enumerate}


	 \Aufgabe{Gradientenverfahren}{7}
	 \begin{enumerate}[(a)]
	 	\item $f'(x) = -sin(x+2)+\frac{1}{2} \\
	 	f''(x) = -cos(x+2)$\\
	 	Extremwerte:\\
	 	$-sin(x+2)+1/2=0\\
	 	sin(x+2)= \frac{\pi}{2}\\
	 	(1) sin(\frac{\pi}{6}) = \frac{1}{2}\\
	 	(2) sin(\pi-\frac{\pi}{6}) = \frac{1}{2}\\
	 	(1) x+2= \frac{\pi}{6}+n2\pi\\
	 	(2) x+2= \pi-\frac{\pi}{6}+n2\pi\\
	 	x_1= \frac{\pi}{6} -2 \approx -1.48\\
	 	x_2= \frac{\pi}{6}-2 + 2\pi \approx 4.8 \\
	 	x_3= \pi- \frac{\pi}{6} -2 \approx 0.61\\
	 	x_4=\pi- \frac{\pi}{6} -2 -2\pi \approx -5.67$\\
	 	$f''(x_1) <0 \rightarrow x_1 =$ Maximum lokal TODO umschreiben\\
	 	$f''(x_2) >0 \rightarrow x_2=$ Minimum global\\
	 	$f''(x_3) <0 \rightarrow x_3=$ Maximum lokal\\
	 	$f''(x_4) >0 \rightarrow x_4=$ Minimum global\\
	 	\item  Minima bei Startpunkt $x_0 = x_3$ \\
				 x  Werte für globales Minimum: $[-2*PI, \frac{\pi}{6} -2 [$ \\
				 Begründung: Das Gradientenverfahren folgt bei der Bestimmung eines Extrema immer dem Gradienten abwärts.
	 	
	 	
	 \end{enumerate}
\end{document}