diff --git a/is/ub8/is8.pdf b/is/ub8/is8.pdf new file mode 100644 index 0000000..78a66e0 --- /dev/null +++ b/is/ub8/is8.pdf Binary files differ diff --git a/is/ub8/is8.tex b/is/ub8/is8.tex new file mode 100644 index 0000000..907ed54 --- /dev/null +++ b/is/ub8/is8.tex @@ -0,0 +1,148 @@ +\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}{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 Sheet #1} + +{(Hand in #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 Points)} + + +\begin{document} + %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben} + \header{8}{}{2015-07-02}{Intelligent Systems I}{\textit{Maximus Mutschler}\\ \textit{Jan-Peter Hohloch} + }{SS 15}{4} + \vspace{1cm} + \Aufgabe{Kidney Stones}{25} + \begin{align*} + P(\text{large stone})&=\frac{343}{343+357}=0.49\\ + P_A(R=1)&=\sum\limits_Z P(R=1|Z=z,T=A)P(Z=z)\\ + &=0.73\cdot 0.49 + 0.93\cdot 0.51\approx 0.832\\ + P_B(R=1)&=\sum\limits_Z P(R=1|Z=z,T=A)P(Z=z)\\ + &=0.69\cdot 0.49 + 0.87\cdot 0.51\approx 0.782 + \end{align*} + (Formula from the lecture)\\ + \Aufgabe{PC}{25} + \begin{itemize} + \item Assume X and Y are directly connected.\\ + There can't exists a set d-seperating them, because they are always linked over the direct connection.\checkmark + \item Assume X,Y are not directly connected, i.e. $X\not\in N(Y)\wedge Y\not\in N(X)$.\\ + Any non-direct path between X and Y can be blocked:\begin{itemize} + \item directed paths are blocked by taking one of the intermediate nodes in the separation set + \item common ancestors can also be blocked + \item common descendants are not taken in the separation set + \end{itemize} + Because the graph is acyclic each path belongs clearly to one of the above categories and so can be blocked. + \end{itemize} + \Aufgabe{IC}{25}\\ + \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto, node distance=2cm] + \node[circle, draw] (A) {A}; + \node[circle, draw] (B) [right of=A] {B}; + \node[circle, draw] (C) [below of=A] {C}; + \node[circle, draw] (D) [below of=B] {D}; + + \draw (A) -- (B); + \draw (B) -- (D); + \draw (C) -- (D); + \draw (A) -- (C); + \end{tikzpicture} + \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto, node distance=2cm] + \node[circle, draw] (A) {A}; + \node[circle, draw] (B) [right of=A] {B}; + \node[circle, draw] (C) [below of=A] {C}; + \node[circle, draw] (D) [below of=B] {D}; + + \draw (B) -- (A); + \draw (B) -- (D); + \draw (C) -- (D); + \draw (A) -- (C); + \end{tikzpicture} + \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto, node distance=2cm] + \node[circle, draw] (A) {A}; + \node[circle, draw] (B) [right of=A] {B}; + \node[circle, draw] (C) [below of=A] {C}; + \node[circle, draw] (D) [below of=B] {D}; + + \draw (A) -- (B); + \draw (B) -- (D); + \draw (C) -- (D); + \draw (C) -- (A); + \end{tikzpicture}\\ + \Aufgabe{IC Performance}{25}\\ + \begin{itemize} + \item worst case:\\ + All nodes are dependent of each other, so it has to check all possible subsets (the powerset) for all pairs of nodes: + $$\frac{p\cdot (p-1)}{2}\cdot 2^{p-2}\in\mathcal{O}(2^p)$$ + \item best case:\\ + first test shows independence, so we need only one test per pair: + $$\frac{p\cdot (p-1)}{2}\cdot 1\in\mathcal{O}(p^2)$$ + \end{itemize} + %TODO Graphs +\end{document} +