1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
\section{Das Paket sets}\label{sets}
Wie schon in der Einleitung beschrieben ist sets dazu konzipiert, Mengenoperationen zu unterstützen. Die Elemente einer Menge sind normalerweise einfacher Text, Sie können aber auch Kommandos in Mengen einfügen. Diese werden -- außer
bei der Ausgabe -- nicht ausgepackt. Die Verwendung von geschweiften Klammern in Mengen funktioniert leider nicht. In diesem Fall müssen Sie sich eine Abkürzung definieren, die ohne Parameter auskommt. Parameter ohne Klammern funktionieren jedoch. "`\verb|H"agar|"' wäre also ein gültiges Element einer Menge. Die Elemente "`\verb|\endset|"' und "`\verb|\empty|"' dürfen nicht in einer Menge enthalten sein.
Da ein Dokument nur wenige Autoren hat, wurde auf Effizienz kein besonderer Wert gelegt. Die Mengen sollten deshalb relativ klein sein. Sollten Sie dennoch eine Menge mit hunderten oder gar tausenden von Elementen anlegen wollen, kann es passieren, dass der Stack von \TeX\ überläuft.
Normalerweise ist bei einer Menge die Reihenfolge der Elemente egal. Dies ist auch hier bei den meisten Befehlen der Fall. Bei Abweichungen wird darauf hingewiesen.
Das Paket sets benötigt \LaTeXe.
\subsection{Verwendung}\label{sets-verwendung}
In diesem Unterabschnitt soll die Verwendung des Pakets sets vorgestellt werden. Dabei werden einige Beispielmengen verwendet werden:
\begin{eqnarray*}
A &=& \{Alice, Bob, Charly\}\\
B &=& \{Alice, Bob\}\\
C &=& \{Bob, Dean\}\\
D &=& \{Dean\}\\
L &=& \emptyset
\end{eqnarray*}
%-----------------------------------------------------------------------------
\subsubsection{Konstruktoren}\label{konstruktoren}
Um eine Menge anzulegen, gibt es die Befehle\\
\mbox{}\hspace{2em}\verb$\newset{<Menge>}{<Inhalt>}$\\
und\\
\mbox{}\hspace{2em}\verb$\newsetsimple{<Menge>}{<Inhalt>}$.\\
\texttt{<Menge>} ist ein Kommandoname, unter dem die Menge später erreichbar sein soll. Die Elemente einer Menge werden durch \texttt{|} getrennt. Die Menge $A$ ließe sich also wie folgt definieren:\\
\mbox{}\hspace{2em}\verb$\newset{\mA}{Alice|Bob|Charly}$\\
Die Menge $L$ wird mit\\
\mbox{}\hspace{2em}\verb$\newset{\mL}{}$\\
definiert.
\verb$\newset$ legt also eine neue Menge an. Diese wird dabei alphabetisch sortiert und Duplikate werden entfernt. Es wäre also egal gewesen, wenn bei der Definition von $A$ nach "`Charly"' ein weiteres Mal "`Alice"' gestanden hätte.
Der Aufwand für Sortierung und Duplikatentfernung ist an dieser Stelle unnötig. Will man diese Schritte nicht durchführen lassen, kann man eine Menge auch mit \verb$\newsetsimple$ definieren.
Da sie später noch benötigt werden, werden wir nun alle oben genannten Mengen anlegen:\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mA}{Alice|Bob|Charly}$ \newsetsimple{\mA}{Alice|Bob|Charly}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mD}{Alice|Bob}$ \newsetsimple{\mB}{Alice|Bob}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mC}{Bob|Dean}$ \newsetsimple{\mC}{Bob|Dean}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mD}{Dean}$ \newsetsimple{\mD}{Dean}\\
\mbox{}\hspace{2em}\verb$\newsetsimple{\mL}{}$ \newsetsimple{\mL}{}
%-----------------------------------------------------------------------------
\subsubsection{Inspektoren}\label{inspektoren}
Inspektoren dienen dazu, Eigenschaften von Mengen herauszufinden oder diese auszugeben.
\paragraph{Ausgabe:}Eine Menge lässt sich über\\
\mbox{}\hspace{2em}\verb$\listset$\\
ausgeben. Die Elemente werden in der Reihenfolge, in der sie in der Menge stehen, ausgegeben. Als Trennzeichen zwischen den Elementen wird das Komma verwendet.
\verb$\listset{\mA}$ ergibt also folgende Ausgabe:\\
\centerline{\listset{\mA}}
Manchmal möchte man die Elemente einer Menge vielleicht auf andere Art und Weise trennen, z.\,B. mit einem \texttt{\&} zur Darstellung in einer Tabelle. Hier hilft einem die (temporäre) Umdefinition des Kommandos\\
\mbox{}\hspace{2em}\verb$\setseparator$\\
weiter. Normalerweise hat dieses Makro den Ersetzungstext `\verb*$,\ $'.
\paragraph{Größenbestimmung:} Der nächste Inspektor hat die Syntax\\
\mbox{}\hspace{2em}\verb$\sizeofset{$$M$\verb$}\is{<Zähler>}$\\
\texttt{<Zähler>} ist dabei der Name eines \LaTeX-Zählers, in dem die Anzahl der Elemente der Menge $M$ gespeichert wird. Die Kommandosequenz\\
\mbox{}\hspace{2em}\verb$\newcounter{mycounter}$\newcounter{mycounter}\\
\mbox{}\hspace{2em}\verb$\sizeofset{\mB}\is{mycounter}$\sizeofset{\mB}\is{mycounter}\\
\mbox{}\hspace{2em}\verb$\arabic{mycounter}$\\
führt zur Ausgabe: "`\arabic{mycounter}"'
Wird die Größe der Menge $L$ bestimmt, ist das Ergebnis \sizeofset{\mL}\is{mycounter}wie erwartet "`\arabic{mycounter}"'.
\paragraph{Prüfung auf Mitgliedschaft:}Mit dem Befehl\\
\mbox{}\hspace{2em}\verb$\iselementofset{$$e$\verb$}{$$M$\verb$}$\\
kann überprüft werden, ob $e \in M$ gilt. Der Aufwand ist $O(1)$, da alle Arbeit durch die Mustererkennung von \TeX\ übernommen wird. Die Befehlssequenz\\
\mbox{}\hspace{2em}\verb$\if \iselementofset{Bob}{\mC}Ja\else Nein\fi$\\
würde zur Ausgabe "`\if \iselementofset{Bob}{\mC}Ja\else Nein\fi"' führen, der gleiche Test mit Menge $D$ zu "`\if \iselementofset{Bob}{\mD}Ja\else Nein\fi"'.
%-----------------------------------------------------------------------------
\subsubsection{Modifikatoren}\label{modifikatoren}
\paragraph{Mengenvereinigung:}Die Operation $R := M_1 \cup M_2$ wird durch den Befehl\\
\mbox{}\hspace{2em}\verb|\unionsets{|$M_1$\verb|}{|$M_2$\verb|}\to{|$R$\verb|}|\\
realisiert. Ein paar Beispiele sind in Tabelle \ref{tab:ops} aufgeführt. Das Ergebnis der Operation ist eine sortierte Menge ohne Duplikate, die die Elemente der Mengen $M_1$ und $M_2$ enthält.
\paragraph{Mengendifferenz:}Die Operation $R := M_1 - M_2$ (auch $R := M_1 \backslash M_2$ geschrieben) lässt sich mit dem Befehl\\
\mbox{}\hspace{2em}\verb|\minussets{|$M_1$\verb|}\minus{|$M_2$\verb|}\to{|$R$\verb|}|\\
durchführen. Ist $M_1$ eine sortierte Menge, wird auch $R$ sortiert sein. Enthält $M_1$ Duplikate, enthält $R$ eventuell ebenfalls diese Duplikate. Tabelle \ref{tab:ops} enthält einige Beispiele für die Verwendung dieses Befehls.
Die Operation kann man umgangssprachlich wie folgt formulieren: Prüfe für jedes Element $e$ aus $M_1$, ob $e \in M_2$ gilt. Wenn nein, füge $e$ zu $R$ hinzu. Und genau so wurde es auch straight forward implementiert!
\paragraph{Mengendurchschnitt:} Die Operation $R := M_1 \cap M_2$ wird durch den Befehl\\
\mbox{}\hspace{2em}\verb|\intersectsets{|$M_1$\verb|}{|$M_2$\verb|}\to{|$R$\verb|}|\\
ermöglicht. Auch hier gilt: Ist $M_1$ eine sortierte Menge, wird auch $R$ sortiert sein. Enthält $M_1$ Duplikate, enthält $R$ eventuell ebenfalls diese Duplikate.
Tabelle \ref{tab:ops} enthält auch Beispiele für die Verwendung dieser Operation.
Die Operation kann man umgangssprachlich wie folgt formulieren: Prüfe für jedes Element $e$ aus $M_1$, ob $e \in M_2$ gilt. Wenn ja, füge $e$ zu $R$ hinzu. Wenn man dies mit der Formulierung der Mengendifferenz vergleicht, fällt auf, dass der einzige Unterschied im Wörtchen "`ja"' besteht. In der Implementierung drückt sich dies durch ein fehlendes \verb|\else| aus. Eigentlich verblüffend einfach, wenn man bedenkt, dass formal $M_1 \cap M_2 \equiv M_1 \backslash (M_1\backslash M_2)$ gilt, was eine deutlich höhere Komplexität erwarten lässt.
\begin{table}%[htb]
\begin{center}
\begin{tabular}{ll}\hline
\textbf{Befehl} & \textbf{Ergebnis} \\ \hline
\unionsets{\mA}{\mC}\to{\mR}\global\let\mR\mR
\verb$\unionsets{\mA}{\mC}\to{\mR}$ & "`\listset{\mR}"' \\
\unionsets{\mB}{\mD}\to{\mR}\global\let\mR\mR
\verb$\unionsets{\mB}{\mD}\to{\mR}$ & "`\listset{\mR}"' \\
\unionsets{\mL}{\mC}\to{\mR}\global\let\mR\mR
\verb$\unionsets{\mL}{\mC}\to{\mR}$ & "`\listset{\mR}"' \\
\unionsets{\mL}{\mL}\to{\mR}\global\let\mR\mR
\verb$\unionsets{\mL}{\mL}\to{\mR}$ & "`\listset{\mR}"' \\\hline
%
\minussets{\mA}\minus{\mC}\to{\mR}\global\let\mR\mR
\verb$\minussets{\mA}\minus{\mC}\to{\mR}$ & "`\listset{\mR}"' \\
\minussets{\mD}\minus{\mC}\to{\mR}\global\let\mR\mR
\verb$\minussets{\mD}\minus{\mC}\to{\mR}$ & "`\listset{\mR}"' \\
\minussets{\mD}\minus{\mB}\to{\mR}\global\let\mR\mR
\verb$\minussets{\mD}\minus{\mB}\to{\mR}$ & "`\listset{\mR}"' \\
\minussets{\mA}\minus{\mL}\to{\mR}\global\let\mR\mR
\verb$\minussets{\mA}\minus{\mL}\to{\mR}$ & "`\listset{\mR}"' \\\hline
%
\intersectsets{\mA}{\mB}\to{\mR}\global\let\mR\mR
\verb$\intersectsets{\mA}{\mB}\to{\mR}$ & "`\listset{\mR}"' \\
\intersectsets{\mC}{\mB}\to{\mR}\global\let\mR\mR
\verb$\intersectsets{\mC}{\mB}\to{\mR}$ & "`\listset{\mR}"' \\
\intersectsets{\mB}{\mD}\to{\mR}\global\let\mR\mR
\verb$\intersectsets{\mB}{\mD}\to{\mR}$ & "`\listset{\mR}"' \\
\intersectsets{\mA}{\mL}\to{\mR}\global\let\mR\mR
\verb$\intersectsets{\mA}{\mL}\to{\mR}$ & "`\listset{\mR}"' \\\hline
\end{tabular}
\caption{Mengenoperationen, Beispiele}
\label{tab:ops}
\end{center}
\end{table}
\paragraph{Sortieren:} Eine Menge $M$ kann alphabetisch sortiert werden. Dazu verwendet man den Befehl\\
\mbox{}\hspace{2em}\verb|\sortset{|$M$\verb|}{|$R$\verb|}|.\\
$R$ enthält danach die sortierte Menge. Die Sortierung erfolgt nach dem Sortierverfahren Bubblesort, einem Verfahren, das sich auch mit \TeX\ ohne größere Verrenkungen umsetzen lässt.
Bei der Sortierung werden die Elemente so verglichen, wie Sie sie angegeben haben, d.\,h. eventuell enthaltene Kommandos werden nicht expandiert, sondern nach ihrem Namen verglichen (inklusive des Backslash).
\paragraph{Duplikatentfernung:} Diese Operation funktioniert \emph{nur} auf sortierten Mengen! Man benötigt sie aber eigentlich auch kaum, da die Erstellung einer neuen Menge mit \verb|\newset| diese Aufgabe automatisch übernimmt (indem sie dieses Makro verwendet). Ich habe mich aber dazu entschlossen, die Operation trotzdem verfügbar zu machen; vielleicht benötigt sie ja tatsächlich einmal jemand.
Aufgerufen wird die Duplikateleminierung mit:\\
\mbox{}\hspace{2em}\verb|\deleteduplicates{|$M$\verb|}{|$R$\verb|}|,\\
wobei $R$ die Ergebnis-Menge darstellt und $M$ die sortierte Menge, deren Duplikate entfernt werden sollen.
%------------------------------------------------------------------------------
\subsection{Aufwandsabschätzung}
Tabelle \ref{tab:komplexitaet} beschreibt die Komplexität der Operationen in O-Notation. Dabei werden folgende Annahmen getroffen:
\begin{itemize}
\item Die Länge eines Elements einer Menge sei $m$.
\item Die Anzahl der Elemente einer Menge sei $n$. Werden für eine Operation zwei Mengen benötigt, gibt $n_1$ die Kardinalität der ersten und $n_2$ die Kardinalität der zweiten Menge an.
\item Zur Vereinfachung sei der Aufwand für die Mustererkennung bei der Parameterübergabe konstant.
\end{itemize}
Die angegebenen Komplexitätsklassen können dazu dienen, eine Reihe von Mengenoperationen möglichst günstig anzuordnen. Beispielsweise ist es besser, bei \verb@\intersectsets@ und \verb@\minussets@ als erste Menge die kleinere Menge zu übergeben.
\begin{table}[htb]
\begin{center}
\begin{tabular}{lc}\hline
\textbf{Operation} & \textbf{Komplexitätsklasse}\\ \hline
Element-Vergleich & $m$\\
\verb@\sizeofset@ & $n$\\
\verb@\listset@ & $n$\\
\verb@\iselementofset@ & $1$\\%\hline
\verb@\sortset@ & $m \cdot n^2$\\
\verb@\deleteduplicates@ & $n$\\%\hline
\verb@\newset@ & $m \cdot n^2$\\
\verb@\newsetsimple@ & $1$\\%\hline
\verb@\unionsets@ & $m \cdot (n_1 + n_2)^2$\\
\verb@\intersectsets@ & $n_1$\\
\verb@\minussets@ & $n_1$\\ \hline
\end{tabular}
\caption{Komplexitätsklassen der Mengenoperationen}%
\label{tab:komplexitaet}%
\end{center}
\end{table}
|
