kanonischer Greedy-Algorithmus für Teilmengensysteme:\pause

\begin{programm}
\bfseries\em
Ordne die Elemente in $E=\{e_1,...,e_n\}$,\pause\\
\hspace*{2em} so dass $w(e_1)\geq w(e_2)\geq ...\geq w(e_n)$\pause\\
Setze $T:=\emptyset$\pause\\
FOR $k:=1$ TO n DO\pause\\
\hspace*{2em}IF $T\cup \{e_k\}\in {\cal U}$ THEN $T:=T\cup \{e_k\}$\pause\\
ENDFOR\pause\\
Ausgabe von $T$ als Lösung
\end{programm}

\pause
Charakterisierung der Probleme, die Greedy-Algorithmus optimal  löst:\pause
\begin{definition}
Ein Teilmengensystem $(E,{\cal U})$ heißt \Fb{Matroid}\pause, wenn zusätzlich die
Austauscheigenschaft gilt:\pause
\begin{itemize}
\item $A,B\in{\cal U}\pause\wedge |A|<|B|~~~ \pause\Rightarrow~~~ (\exists x\in B\setminus A)~ A\cup\{x\}\in{\cal U}$
\end{itemize}
\end{definition}
\pause
\begin{itemize}
\item  `Matroid' verallgemeinert Begriff `(lineare) Unabhängigkeit' \pause
\item  In Matroiden haben maximale Mengen gleiche Mächtigkeit!
\end{itemize}