\documentclass[12pt,a4paper]{article}
\usepackage{german}
\usepackage{graphicx}
\graphicspath{{eps/}{pdf/}}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -15mm
\textheight    242mm

\begin{document}

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

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

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

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

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

\subsubsection*{Aufgabe 36 \quad\rm Molek"ulbeschreibungssprachen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Zeichnen Sie das durch die folgende SMILES-Zeichenkette
     beschriebene Molek"ul: \par
     \centerline{\tt
     S2c1c4c(ccc1N(c3c2cccc3)C(=O)C)cccc4}
\item[b)\hfill]
     Zeichnen Sie das durch die folgende SLN-Zeichenkette
     beschriebene Molek"ul: \par
     \centerline{\tt\ \ \ 
     NH2C[1]:N:C(:C(:N:C:@1C(=O)OCH3)C(=O)C[2]:CH:CH:CH:CH:CH:@2)NH2}
\item[c)\hfill]
     \parbox[t]{90mm}{Erzeugen Sie eine SMILES-Beschreibung
     dieses Molek"uls:}\hskip12mm
     \lower5.2ex\hbox{\includegraphics{fpmex-0}}
\item[d)\hfill]
     \parbox[t]{90mm}{Finden sie mindestens drei verschiedene
     SMILES-Beschreibungen von Phenol, d.h., dieses Molek"uls:}%
     \hskip12mm
     \lower2.7ex\hbox{\includegraphics{fpmex-1}}
\end{enumerate}

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

\subsubsection*{Aufgabe 37 \quad\rm Molek"ulbeschreibungssprachen}

\newsavebox\mybox
\begin{lrbox}{\mybox}
\begin{minipage}{\textwidth}
\begin{verbatim}
4728
          1016 111283D                        4728

  9  9        0                 1 V2000
   -0.0965    1.3884    0.0104 N   0  0  0  0  0  0  0  0  0
    1.8297   -0.2821   -0.0166 S   0  0  0  0  0  0  0  0  0
    1.0302    2.1371    0.0038 N   0  0  0  0  0  0  0  0  0
    0.1607    0.0664    0.0009 C   0  0  0  0  0  0  0  0  0
    2.1519    1.3924   -0.0108 C   0  0  0  0  0  0  0  0  0
    3.3971    1.9238   -0.0196 N   0  0  0  0  0  0  0  0  0
   -0.5873   -0.6698    0.0040 H   0  0  0  0  0  0  0  0  0
    3.5072    2.8871   -0.0156 H   0  0  0  0  0  0  0  0  0
    4.1746    1.3453   -0.0300 H   0  0  0  0  0  0  0  0  0
  1  4  2  0  0  0  0
  1  3  1  0  0  0  0
  2  4  1  0  0  0  0
  2  5  1  0  0  0  0
  3  5  2  0  0  0  0
  4  7  1  0  0  0  0
  5  6  1  0  0  0  0
  6  8  1  0  0  0  0
  6  9  1  0  0  0  0
M  END
$$$$
\end{verbatim}
\end{minipage}
\end{lrbox}

Zeichnen Sie das durch das folgende SDfile
beschriebene Molek"ul: \\[.7ex]
\scalebox{0.62}{\usebox\mybox}

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

\subsubsection*{Aufgabe 38 \quad\rm Teilgraphisomorphismen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie oft tritt das Fragment {\tt C-C-C} in Phenol auf
     (siehe Aufgabe~36d)? \\
     Mit anderen Worten: Wie viele Teilgraph-Isomorphismen gibt es?
\item[b)\hfill]
     Besitzt Phenol (siehe Aufgabe~36d) einen von der Identit"at
     verschiedenen Automorphismus?
     Wie viele verschiedene Automorphismen besitzt Phenol?
\item[c)\hfill]
     Erzeugen Sie alle zusammenh"angenden Teilgraphen von Phenol
     (siehe 36d)!
\item[d)\hfill]
     Finden Sie alle Br"ucken in Phenol (siehe Aufgabe~36d)! \\
     Sind irgendwelche dieser Br"ucken echte Br"ucken?
\item[e)\hfill]
     Finden Sie alle Br"ucken in dem Graphen/Molek"ul
     aus Aufgabe~36c)! \\
     Welche dieser Br"ucken sind echte Br"ucken?
\end{enumerate}

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

\subsubsection*{Aufgabe 39 \quad\rm Suche nach h"aufigen Teilgraphen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     \parbox[t]{86mm}{Finden Sie in der rechts gezeigten Datenbank
     (SMILES) alle h"aufigen (Teil-)Graphen, die Schwefel enthalten;
     minimaler Support~$s_{\min} = 3$:}\hfill
     \begin{minipage}[t]{49mm}
     \begin{verbatim}
CCS(O)(O)N    CCS(=N)N
CCS(O)(C)N    CS(=N)N
CS(O)(C)N     CS(=N)O\end{verbatim}%
     \end{minipage}
\item[b)\hfill]
     Warum ist es bei der Suche nach h"aufigen Teilgraphen schwieriger,
     redundante Suche zu vermeiden, als bei der Suche nach h"aufigen
     Itemmengen? Worin bestehen die Hauptprobleme?
\item[c)\hfill]
     Was ist der Zweck der Konstruktion von kanonischen Kodew"ortern
     von \hbox{(Teil-)} Graphen?
     Was ist ein kanonisches Kodewort? Was brauchen wir tats"achlich?
\item[d)\hfill]
     Wie werden mit Hilfe eines kanonischen Kodewortes
     (Teil-)Graphen eindeutige Elterngraphen zugewiesen?
     Welche Information des Kodewortes wird benutzt?
\end{enumerate}

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

\end{document}
