diff --git a/ea/ub8/ea8.pdf b/ea/ub8/ea8.pdf new file mode 100644 index 0000000..51d82dc --- /dev/null +++ b/ea/ub8/ea8.pdf Binary files differ diff --git a/ea/ub8/ea8.tex b/ea/ub8/ea8.tex new file mode 100644 index 0000000..eb35f39 --- /dev/null +++ b/ea/ub8/ea8.tex @@ -0,0 +1,97 @@ +\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{listings} +\lstset{language=Python} + +\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}{22}%TODO update + \whiledo{\value{aufgabe} < 25}%TODO update + {% + #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} +\setcounter{n}{21} %TODO update + +%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{8}{}{2015-06-09}{Evolutionäre Algorithmen}{ + \textit{Jan-Peter Hohloch}\\ \textit{Maximus Mutschler} + }{SS 15}{3}%TODO update + \vspace{0.5cm} + \Aufgabe{Baumstrukturen}{6}\\ + \begin{enumerate}[(a)] + \item Sei $k=0$. Ein Baum der Tiefe $0$ hat ein Blatt, $m^0=1\checkmark$\\ + Sei nun $k>0$. Jeder Baum hat höchstens $m$ Kinder, die selbst Bäume der Tiefe $<= k-1$ sind. Für ein beliebiges aber festes $k$ haben diese Teilbäume nun höchstens $m^{k-1}$ Blätter (IV). Es existieren wiederum höchstes $m$ dieser Teilbäume, ein Baum der Tiefe $k$ hat also höchstens $m\cdot m^{k-1}=m^k$ Blätter. \qed + \item Ein Baum der Höhe $h$ hat mindestens $h+1$ Knoten. Ansonsten ist kein Pfad der Länge $h$ im Baum vorhanden. Mit $h+1$ Konten die genau den Pfad von Wurzel zu Blatt bilden, erreichen wir jedoch eine Höhe von $h$. + \item Sei $h=0$. Ein Baum der Höhe $0$ hat einen Knoten: $\frac{m^{0+1}-1}{m-1}=\frac{m-1}{m-1}=1\checkmark$\\ + Sei nun $h>0$. Für ein beliebiges aber festes $h$ habe ein Baum $\frac{m^{h+1}-1}{m-1}$ Knoten. Die Blätter eines vollständigen Baumes der Höhe $h+1$ haben die Tiefe $h+1$. Es gibt also $m^{h+1}$ Blätter (Baum ist vollständig). Ein vollständiger Baum der Höhe $h+1$ hat also $\frac{m^{h+1}-1}{m-1}+m^{h+1}=\frac{m^{h+1}-1+m^{h+2}-m^{h+1}}{m-1}=\frac{m^{h+2}-1}{m-1}$ Knoten. \qed + \item alter Baum: $x2\cdot (1+ x1^2) \cdot \sqrt{\frac{x1 +x2}{\sqrt{x1}}}\cdot \sin(x1+x2)$\\ + nach Crossover: $x2\cdot\sqrt{\frac{x1 +x2}{\sqrt{x1}}}\cdot (1+ x1^2) \cdot \sin(x1+x2)$\\ + Da die Multiplikation assoziativ und kommutativ ist, verändert die Formel sich nicht tatsächlich. + \end{enumerate} +\end{document} +