\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{pdfpages}
\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}
\usepackage{qtree}

\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 Assignment #1}

{(Hand-in date #3)}
\end{center}
}



%counts the exercisenumber
\newcounter{n}

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




\begin{document}
    %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben}
    \header{7}{}{2015-06-16}{Mobile Robots}{
        \textit{Jan-Peter Hohloch}\\ \textit{Maximus Mutschler}
    }{SS 15}{3}
    \vspace{1cm}

    \Aufgabe{Occupancy Gridmap}{9}
    \begin{enumerate}[(a)]
        \item $\frac{p(m_i|z_{1,\dots,t})}{1-p(m_i|z_{1,\dots,t})}=\frac{p(m_i|z_t)}{1-p(m_i|z_t)}\frac{p(m_i|z_{1,\dots,t-1})}{1-p(m_i|z_{1,\dots,t-1})}\frac{1-p(m_i)}{p(m_i)}$\\
        $\Leftrightarrow\frac{A}{1-A}=\underbrace{\frac{B}{1-B}\frac{C}{1-C}\frac{1-D}{D}}_F$\\
        $\Leftrightarrow A=(1-A)F$\\
        $\Leftrightarrow A=\left(1+\frac{1}{F}\right)^{-1}=\left(1+\frac{1-B}{B}\frac{1-C}{C}\frac{D}{1-D}\right)^{-1}=\left(1+\frac{1-p(m_i|z_t)}{p(m_i|z_t)}\frac{1-p(m_i|z_{1,\dots,t-1})}{p(m_i|z_{1,\dots,t-1})}\frac{p(m_i)}{1-p(m_i)}\right)^{-1}\\ 
        $
        \item $\left(1+\frac{1-p(m_i|z_t)}{p(m_i|z_t)}\frac{1-a}{a}\cdot b \right)^{-1}$\\ 3 Add/Sub, 5 Div/Mult
        \item $o(m_i|z_{t,\dots,1})=\frac{p(m_i|z_t)}{1-p(m_i|z_t)}\frac{p(m_i|z_{1,\dots,t-1})}{1-p(m_i|z_{1,\dots,t-1})}\frac{1-p(m_i)}{p(m_i)}=\frac{p(m_i|z_t)}{1-p(m_i|z_t)}\frac{a}{1-a}b$\\
        2 Add/Sub, 4 Div/Mult\\
        $ log(o(m_i|z_{t,\dots,1}))= log(p(m_i|z_t))-log(1-p(m_i|z_t))+log(a)-log(1-a)+c $\\
        6 Add/Sub, 4 logs  \\
      
        \item
          grids are evaluated clockwise  \\
        $ p(m_1|z_{1,\dots,5})=0.9942$\\
        $ p(m_2|z_{1,\dots,5})=0.9660$\\
        $ p(m_3|z_{1,\dots,5})=0.1164$\\
        $ p(m_4|z_{1,\dots,5})=0.8258$\\
        
        $ o(m_1|z_{1,\dots,5})=170.6667$\\
        $ o(m_2|z_{1,\dots,5})=28.4444 $\\
        $ o(m_3|z_{1,\dots,5})=0.1317$\\
        $ o(m_4|z_{1,\dots,5})=4.7407$\\
        
         $ lo(m_1|z_{1,\dots,5})=5.1397$\\
         $ lo(m_2|z_{1,\dots,5})=3.3480 $\\
         $ lo(m_3|z_{1,\dots,5})=-2.0273 $\\
         $ lo(m_4|z_{1,\dots,5})=1.5562$\\
       
     
        Rechenweg Matlab  siehe Abbildung \ref{fig:1dMatlab}:
        \begin{figure}
		\centering
		\includegraphics[width=0.7\linewidth]{1dMatlab}
		\caption{Rechnung 1d}
		\label{fig:1dMatlab}
		\end{figure}

    \end{enumerate}
    \Aufgabe{Quadtree}{6}
    \begin{enumerate}[(a)]
        \item
%            \Tree [.g
%                    [.g
%                        [.g b w b b ]
%                        w
%                        [.g b b b w ]
%                        b
%                    ]
%                    [.g
%                        [.g w b b w ]
%                        g
%                        [.g b g w b ]
%                        [.g b b b w ]
%                    ]
%                    [.g g g g w ]
%                    [.g w w w b ]
%                ]
			\resizebox{\linewidth}{!}{%
            \Tree [.g
		            [.g g b g w ]
                    [.g
                        [.g w g b b ]
                        g
                        [.g b b w w ]
                        [.g w b w w ]
                    ]
                    [.g
                        [.g b b b w ]
                        w
                        [.g b w b b ]
                        b 
                    ]                    
                    [.g w w w b ]
                ]
          }  
        \item 
%Die meisten nötigen Änderungen am Baum verursacht eine Änderung in einem zusammenhängenden Quadrat, also beispielsweise links oben in der Ecke. Eine Änderung dort bewirkt vier neue Knoten und einen geänderten.\\
%        Die wenigsten nötigen ergeben sich, wenn ein ohnehin einzelnes Gridfeld geändert wird. Dabei darf jedoch der Baum nicht kleiner werden. Dies ist beispielsweise der Fall bei dem Feld links unten.\\
		Grid cells with as many operations as possible to have their values changed are those belonging to a leaf node with the lowest depth and holding the value occupied or free. One example in this qtree is the quadrad in the upper left corner. Changing the value of one grid cell of this quadrad results in 4 new nodes and the change of the value of their parent node to grey. 
        \\Grid cells with as few operations as possible to have their value changed are all leaf nodes with the highest depth. Here only the color value of the nodes has to be changed. E.g the black cell in the lower left corner.
        \item $256^2=\left(2^8\right)^2=4^8$\\
        $\Rightarrow$ maxdepth: 8 \\ According to the definition of the  depths of a general tree it has to be 9
        
       % $\Rightarrow$ maxnodes: $\sum\limits_{i=0}^9\frac{4^9-1}{4-1}=87381$
          $\Rightarrow$ maxnodes: $\sum\limits_{i=0}^8 4^{i}=\frac{4^9-1}{4-1}=87381$
    \end{enumerate}
    \Aufgabe{Topological Maps}{5}
        \begin{enumerate}[(a)]
            \item \includegraphics[width=\textwidth]{voroni.jpg}
            \item[(c)] \begin{tikzpicture}[auto,node distance=2.0cm]
                \node[state] (A) {};
                \node[state] (B) [right of=A] {};
                \node[state] (C) [right of=B] {};
                \node[state] (D) [right of=C] {};
                \node[state] (E) [above of=D] {};
                \node[state] (F) [right of=E] {};
                \node (help) [below of=F] {};
                \node[state] (G) [below of=help] {};
                \node[state] (H) [left of=G] {};
                \node[state] (I) [below of=G] {};
                \node[state] (J) [left of=I] {};
                \node[state] (K) [below of=C] {};
                \node[state] (L) [below of=K] {};
                \node[state] (M) [left of=K] {};
                \node[state] (N) [below of=M] {};
                \node[state] (O) [left of=N] {};

                \path
                    (A)edge(B)(B)edge(C)(C)edge(D)(D)edge(E)(E)edge(F)(F)edge(G)(G)edge(I)(I)edge(J)(J)edge(H)(H)edge(D)
                    (C)edge(K)
                    (K)edge(L)
                    (K)edge(M)
                    (M)edge(N)
                    (N)edge(O);
            \end{tikzpicture}
        \end{enumerate}
\end{document}

