\documentclass[12pt,a4paper]{article}
\usepackage{german}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -15mm
\textheight    240mm

\begin{document}

%-----------------------------------------------------------------------

\noindent
{\bf Data Mining 2: Finden h"aufiger Muster} \hfill Sommer 2018 \\
Christian Borgelt \hfill ab 03.05.2018

%-----------------------------------------------------------------------

\vskip3ex
\centerline{\bf 2.~"Ubungsblatt}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 5 \quad\rm Suchen nach h"aufigen Mustern}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie gro\3 ist der Suchraum der Suche nach h"aufigen Itemmengen? \\
     Wie w"achst die Gr"o\3e des Suchraums mit der Anzahl der Items?
\item[b)\hfill]
     Warum ist eine ersch"opfende Suche "uber alle
     Itemmengen nicht ratsam? \\
     Was ist die (asymptotische) Zeitkomplexit"at einer
     ersch"opfenden Suche? \\
     Ist die gestutze/reduzierte Suche grunds"atzlich effizienter? \\
     Wenn ja, in welcher Weise? Wenn nein, warum k"onnte sie trotzdem
     hilfreich sein?
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 6 \quad\rm Suchen nach h"aufigen Mustern}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie viele Teilmengen mit $k-1$ Items hat eine Itemmenge
     mit $k$ Items? \\
     Warum stellt dies ein Problem f"ur die Kandidatengenerierung dar?
\item[b)\hfill]
     Zeigen Sie, warum jede h"aufige Itemmenge mit $k+1$ Items auf
     $j = (k+1)k/2$ Weisen mit der Originalversion des
     Apriori-Algorithmus erzeugt werden kann!
\item[c)\hfill]
     Auf wie viele Arten kann eine {\em nicht\/} h"aufige Itemmenge
     mit $k+1$ Items erzeugt\linebreak werden?
     Unterscheidet sich die Anzahl von der f"ur h"aufige Itemmengen?
     Warum?
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 7 \quad\rm Suchen nach h"aufigen Mustern}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Welche Struktur des Suchraums wird f"ur die Suche ausgenutzt? \\
     Warum ist diese Struktur vorteilhaft, gegeben die Eigenschaften
     des Support?
\item[b)\hfill]
     Was ist ein Hasse-Diagramm? Was stellt es dar? \\
     Wof"ur verwenden wir Hasse-Diagramme?
\item[c)\hfill]
     Wie wird das Hasse-Diagramm ver"andert/transformiert,
     um die Suche zu verbessern?
     Was ist der Zweck dieser Transformation?
\item[d)\hfill]
     Was erreichen wir durch die Zuordnung
     eindeutiger Elter-Itemmengen? \\
     K"onnten wir auch eindeutige Kind-Itemmengen zuordnen?
\item[e)\hfill]
     Gibt es Itemmengen, die immer eine eindeutige Elter-Itemmenge
     haben, \\ auch im unver"anderten Hasse-Diagramm?
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Aufgabe 8 \quad\rm Suchen nach h"aufigen Mustern}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie k"onnen wir eindeutige Elter-Itemmengen definieren
     (konkrete Methode)? \\
     Gibt es Alternativen? Wie helfen eindeutige Eltern bei der Suche?
\item[b)\hfill]
     Wenn eindeutige Elter-Itemmengen zugeordnet sind:
     Auf wie viele Weisen k"onnen wir eine Itemmenge der Gr"o\3e $k+1$
     aus Itemmengen der Gr"o\3e~$k$ erzeugen?
\item[c)\hfill]
     Wie sieht das allgemeine Schema der Suche mit eindeutigen
     Eltern aus?
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Aufgabe 9 \quad\rm Kanonische Form von Itemmengen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was ist eine kanonische Form einer Itemmenge?
     Wie kann man sie definieren? \\
     Braucht man dieses Konzept tats"achlich f"ur die Suche
     nach h"aufigen Itemmengen? \\
     Warum betrachten wir kanonische Formen f"ur Itemmengen trotzdem?
\item[b)\hfill]
     Was ist die Pr"afixeigenschaft?
     Wie wird sie ausgedr"uckt (zwei Varianten)? \\
     Welche Vorteile folgen aus der Pr"afixeigenschaft?
\item[c)\hfill]
     Beschreiben Sie, wie die rekursive Suche nach h"aufigen Mustern
     vereinfacht werden kann, wenn die gew"ahlte kanonische Form
     die Pr"afixeigenschaft hat!
\item[d)\hfill]
     Die Pr"afixeigenschaft ist eine notwendige Bedingung um
     sicherzustellen, da\3 die Suche durch Anh"angen von Items
     an kanonische Kodew"orter ersch"opfend ist.
     Was braucht man zus"atzlich, um eine hinreichende Bedingung
     zu erhalten?
\item[e)\hfill]
     Was ist eine kanonische Erweiterungsregel?
     Gibt es eine kanonische Erweiterungsregel f"ur die Suche
     nach h"aufigen Itemmengen?
\end{enumerate}

%-----------------------------------------------------------------------

\end{document}
