sammlung/DiMa/dima.tex

\documentclass[a4paper,parskip=half,12pt]{scrartcl}
\input{../env/packages}
\input{../env/commands}
\input{../env/meta}

\begin{document}
\renewcommand{\thepage}{\Roman{page}}% Roman numerals for page counter

\title{Zusammenfassung Diskrete Mathematik}

\maketitle

\section*{Vorwort}
Dieses Dokument dient zur kurzen Zusammenfassung der wichtigsten Sätze und Definitionen.
Ich füge hier nur nach Lust und Laune Dinge ein, so dass dies in keinster Weise als vollständig oder stets korrekt angesehen werden darf.
Die Quelldateien sind öffentlich unter \url{https://git.webschneider.org/uni/sammlung} einsehbar.
Jeder ist dazu aufgerufen, sich an der Entwicklung zu beteiligen!
\tableofcontents

\vspace*{\fill} % show license on bottom of page
\doclicenseThis{}

\clearpage
\setcounter{page}{1}
\renewcommand{\thepage}{\arabic{page}}% Arabic numerals for page counter

\section{Abbildungen}
    Man beachte auch das \href{https://git.webschneider.org/uni/sammlung/src/master/MafIA1/mafia.pdf}{Mafia-Skript}.

    \subsection{Kompositionen}
    Kompositionen von Funktionen sind \emph{assoziativ}.

    Sei $f: X \rightarrow Y$ eine Funktion:
    \begin{enumerate}[i.]
        \item $f $ ist injektiv $\lrarr \exists g: Y \rightarrow X$, sodass $g \circ f = id_x$
        \item $f$ ist surjektiv $\lrarr \exists g: Y \rightarrow X$, sodass $f \circ g = id_y$
        \item $f$ ist bijektiv $\lrarr \exists g: Y \rightarrow X$, sodass $g \circ f = id_x, f \circ g = id_y$
    \end{enumerate}

    \subsection{Umkehrfunktion}\label{abb:umkehr}
    Seien $X,Y$ Mengen und die Abbildungen $f: X \rightarrow Y$ eine Bijektion.
    Dann gibt es eine eindeutige Funktion $g:Y \rightarrow X$ mit $g(y)=x$, wobei
    $f^{-1}(y) = \{x\}$.
    Diese wird \idx{Umkehrfunktion} oder \idx{Inverse} von $f$ bezeichnet.

\section{Zählen und Kombinatorik}
    \subsection{Schubfachprinzip}\label{kombi:schubfach}
    Das Schubfachprinzip besagt, wenn $m$ Objekte in $n$ Kategorien (\emph{Schubfächer}\index{Schubfach})
    eingeteilt werden, gibt es mindestens eine Kategorie, in der mindestens
    zwei Objekte eingeteilt sind.

    \subsection{Zählformen}\label{kombi:counting}
        Bei endlichen Mengen gibt $|A|$ die Anzahl der Elemente (\idx{Kardinalität}) an.

        \subsubsection{Summenformel und Produktformel}
        Bei endlichen Mengen $A,B$ gilt die \idx{Summenformel}:
        \[|A\cup B| = |A|+|B| - |A \cap B| \]
        Ausserdem gilt die \idx{Produktformel}, auch für eine endliche Menge
        von Mengen:
        \[|A \times B| = |A| \cdot |B| \]

        \subsubsection{Binomialkoeffizient}\label{kombi:binomial}
        Der \idx{Binomialkoeffizient}
        dient dazu, die möglichen Kombinationen von $k$ Objekten aus insgesamt
        $n$ verschiedenen Elementen zu ermitteln.
        Dabei ist die Reihenfolge unerheblich und es wird nicht zurückgelegt.
        Die Definition ist wie folgt:
        \[\binom{n}{k} = \frac{n!}{k! \cdot (n - k)!} \]
        \begin{satz}
            Seien $k, n \in \N$. Dann gilt:
            \[\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\]
        \end{satz}

        \subsubsection{Binomialsatz}\label{kombi:binomsatz}
        Seien $x, y \in \R$ und $n \in \N$. Es gilt:
        \[{(x+y)}^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k} \]

        \begin{satz}
            \begin{enumerate}
                \item \[\sum_{k=0}^n \binom{n}{k} = 2^n, \; \forall k,n \in \N_0\]
                \item \[\sum_{k=0}^n {(-1)}^k \binom{n}{k} = \binom{n}{0} - \binom{n}{1} 
                + \binom{n}{2} \ldots = 0\]
            \end{enumerate}
        \end{satz}

        \subsubsection{Siebformel}\label{kombi:sieb}
        Mithilfe der \idx{Siebformel} kann die Kardinalität einer Menge durch
        die Kardinalitäten ihrer Teilmengen bestimmt werden.
        \[|A_1 \cup A_2 \cup \ldots \cup A_s| = \alpha_1 - \alpha_2 + \alpha_3 - \alpha_4 \pm \ldots + {(-1)}^{s-1}\cdot \alpha_s \]
        Dabei werden die $\alpha$ berechnet, indem man den Durchschnitt von je $i$ Mengen
        bildet und deren Mächtigkeit summiert.

        \subsubsection{Permutationen}\label{kombi:perm}
        Eine \idx{Permutation} von $n \in \N$ Elementen $\pi:\{1, \ldots, n\} \mapsto \{1, \ldots, n\}$
        ist eine Bijektion.
        Ein Element $k$ daraus heißt \idx{Fixpunkt}, wenn $\pi(k) = k$ ist.

        \paragraph{Anzahl der Permutationen}
        Von $n$ Elementen gibt es genau $n!{}$ Permutationen, und ${(n-1)}!{}$ Permutationen
        mit dem Fixpunkt $k$.
        Die Anzahl der fixpunktfreien Permutationen ist
        \[n!\frac{n!}{1!} + \frac{n!}{2} - \frac{n!}{3!} + \cdots + {(-1)}^n\frac{n!}{n!} = \sum_{k=0}^{n} {(-1)}^k \frac{n!}{k!} \]

        \newcommand*{\fkn}{f: \{1, \ldots, k\} \rightarrow{} \{1, \ldots, n\}}
        \begin{satz}
            Die Anzahl der nicht-surjektiven Abbildungen $ \fkn$ ist gleich
            \[\sum_{m=1}^k {(-1)}^{m-1} \binom{n}{m} (n-m). \] Die Anzahl
            der Surjektionen beträgt
            \[\sum_{m=0}^n {(-1)}^m \binom{n}{m} {(n-m)}^k \]
        \end{satz}

        \subsubsection{Kombination mit Wiederholung}\label{kombi:mitWiederholung}
        Wenn die Reihenfolge egal ist und Wiederholungen erlaubt sind, wird
        eine angepasste Version des Binomialkoeffizienten genutzt:
        \[ \binom{n+k-1}{k} \]

        \subsubsection{Wann nehme ich was?}\label{kombi:wannwas}
        \begin{tabular}{ll}
            \textbf{Reihenfolge egal, ohne Zurücklegen} & \nameref{kombi:binomial}\\
            \textbf{Reihenfolge egal, mit Zurücklegen} & \nameref{kombi:mitWiederholung}\\
        \end{tabular}

\section{Rekursion}
    \subsection{Lineare Rekursion}
    Angenommen $T : \N_0 \rightarrow \R $ erfüllt die \idx{lineare Rekursion}
    \begin{align*}
        T(n) &= r \cdot T(n-1) + a, \; a,r \in \R, n \in \N\\
        T(0) &= b.
    \end{align*}
    Dann ist die Lösung:
    \begin{align*}
        T(n) &= r^n T(1) + a \sum_{i=0}^{a-1} r^i, \; n \in \N_0, r = 1 \\
        T(n) &= r^a T(1) + a \frac{1-r^n}{1-r}, \text{\ für } r \ne 1
    \end{align*}

        \subsubsection{Geometrische Summenformel}
            Es gilt:
            \[ \sum_{k=0}^n q^k = \frac{1-q^{n+1}}{1-q} \]

    \subsection{Wachstum von Funktionen}
    Seien $f,g : \N_0 \rightarrow \R$.\\
    \idx{Abschätzung nach oben}\\
    Eine Funktion kann nach oben asymptotisch abgeschätzt werden, wenn
    $\exists c > 0$, s.d. $|f(n)| \le c \cdot |g(n)|, \text{\ für } n \ge n_0$.
    Man schreibt dann $f(n) = O(g(n))$, $O(g(n))$ enthält also alle Funktionen,
    durch die $f(n)$ nach oben asymptotisch abgeschätzt wird.

    \idx{Abschätzung nach unten}\\
    Wenn $\exists c > 0$, so dass $|f(n)| \ge c \cdot |g(n)|$, schreibt man
    $f(n) = \Omega(g(n))$. So wächst $f(n)$ also schneller als $g(n)$.

    \idx{Abschätzung nach oben und unten}
    Die Kombination von $O$ und $\Omega$ heißt $\Theta$.
    Also ist $f(n) = \Theta$, wenn $\exists c_1, c_2$, so dass
    $c_1 \cdot |g(n)| \le |f(n)| \le |c_2 \cdot g(n)|$.

    \subsection{Master-Theorem}
    Das \idx{Master-Theorem} lässt sich auf Rekursionen der folgenden Struktur
    anwenden:
    \begin{alignat*}{2}
        T(n) &= a \cdot T\left(\ceil{\rfrac{n}{b}}\right) + c(n) \; &&, n > n_0\\
        T(n) &= \Theta(1) &&, n \le n_0
    \end{alignat*}
    $c$ muss dabei monoton wachsend sein. Nun gilt:
    \begin{enumerate}
        \item Ist $c(n) = \O\left(n^{\log_b a - \epsilon}\right)$ für ein
            $\epsilon $ mit $ 0 < \epsilon < \log_b a$, so ist
            \[T(n) = \O\left(n^{\log_b a}\right)\]
        \item Ist $c(n) = \Theta(n^{\log_b a})$, so ist
            \[T(n) = \Theta\left(n^{\log_b a} \cdot \log_b n\right)\]
        \item Erfüllt $c$ die Bedingung $\exists \gamma \in (0, 1)$, so dass
            $ac(\ceil{\frac{n}{b}}) \le \gamma c(n)$ für ein hinreichend großes
            $n$ und ist $c(n) = \Omega\left(n^{\log_b a + \epsilon}\right)$, so
            ist
            \[T(n) = \Theta\left(c\left(n\right)\right)\]
    \end{enumerate}
    Zahlreiche Übungen lassen sich im Internet
    finden\footnote{\url{http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf}}.


\section{Graphentheorie}
    \subsection{Ungerichtete Graphen}
        \subsubsection{Kreis}\label{graph:kreis}
        Ein geschlossener Kantenzug mit $k_1, k_2, \dots, k_s$, der die Ecken
        $e_1, e_2,\ldots,e_s=e_0$ miteinander verbindet.
        Alle Kanten müssen dabei unterschiedlich sein.
        Die Länge des Kreises beschreibt die Anzahl der Kanten oder Ecken.

        \subsubsection{Eulerscher Kreis}\label{graph:eulerschKreis}
        Ein \nameref{graph:kreis} $C$ in einem Graph $G$ heißt eulersch, wenn
        jede Kante aus G in ihm genau einmal vorkommt.

        \subsubsection{Eulerscher Graph}\label{graph:eulersch}
        Ein Graph heißt eulersch, wenn er einen \hyperref[subsec:eulerschKreis]{eulerschen Kreis} besitzt.
        Jede Ecke eines eulerschen Graphen hat geraden Grad.
        Besitzt also eine Ecke des Graphen ungeraden Grad, so ist es kein eulerscher Graph.

        \subsubsection{Zusammenhangskomponente}\label{graph:komponente}
        Ein maximaler, zusammenhängender Teilgraph $G^*$ eines Graphen $G$.

        \subsubsection{Offene Eulersche Linie}
        Ein Weg in einem Graph $G$ heißt \idx{offene Eulersche Linie}, wenn
        jede Kante genau einmal enthalten ist und \emph{keinen} Kreis enthält.
        \begin{satz}
            Sei $G$ ein Graph.
            \begin{enumerate}
                \item Besitzt $G$ eine offene eulersche Linie, so hat $G$
                    genau zwei Ecken ungeraden Grades.
                \item Ist $G$ zusammenhängend und hat genau zwei Ecken ungeraden
                    Grades, so hat $G$ eine offene eulersche Linie.
            \end{enumerate}
        \end{satz}

        \begin{satz}
            Ein Graph $G$ ist genau dann bipartit, wenn alle Kreise in $G$ eine
            gerade Länge haben.
        \end{satz}

    \subsection{Bäume}
        \subsubsection{Definition}
        Ein \idx{Baum} ist ein zusammenhängender Graph $G$, der keine Kreise
        positiver Länge enthält. Als \idx{Blatt} wird eine Endecke mit Grad 1
        bezeichnet.

        \begin{satz}
            Jeder Baum mit mindestens 2 Ecken hat eine Endecke.
        \end{satz}

        \begin{satz}
            Ist $G$ ein Baum mit $n$ Ecken und $m$ Kanten, so ist $m = n-1$
        \end{satz}

        \begin{satz}
            Sei $G$ ein zusammenhängender Graph mit $n$ Ecken und $M$ Kanten.
            Dann ist $m \ge n- 1 $ mit Gleicheit genau dann, wenn $G$ ein Baum
            ist.
        \end{satz}

        \subsubsection{Binärer Baum}
        Ein \idx{binärer Baum} ist ein Baum $G$ mit den Eigenschaften
        \begin{enumerate}[i.]
            \item Es gibt eine eindeutige Ecke \idx{Wurzel}, mit dem Grad 2
            \item alle andere Ecken haben entweder den Grad 3 oder 1 (Blätter).
        \end{enumerate}
        Die Höhe des Baumes ist die maximale Länge eines Weges, der die Wurzel
        als eine Endecke hat.

        \begin{satz}
            \begin{enumerate}
                \item Ein binärer Baum der Höhe $h$ hat höchstens $2^h$ Blätter.
                \item Ein binärer Baum $G$ mit $b$ Blättern hat die Höhe
                    $h \ge \ceil{\log_2 b} $
            \end{enumerate}
        \end{satz}

    \subsection{Wurzelbaum und Suchtheorie}
        \newcommand*{\T}{\mathcal{T}}
        \newcommand*{\Lquer}{\overline{L}}
        \subsubsection{Wurzelbaum}
        Ein \idx{Wurzelbaum} ist ein Paar $(T,v)$, wobei $T$ ein Baum ist und 
        $v$ eine ausgezeichnete Ecke, als so genannte \idx{Wurzel}.\\
        Die \idx{Länge einer Ecke} $l(e), e \in E$ bezeichnet den eindeutigen Weg
        von $v$ nach $e$.
        Die Länge des gesamten Baumes ist die maximale Länge einer Ecke.

        \subsubsection{(n, q)-Baum}
        Besitzt ein Baum $n$ Blätter und hat die Wurzel höchstens $q$ direkte
        Nachfolger, spricht man von einem \idx{(n,q)-Baum}.
        Besitzt die Wurzel und jede innere Ecke genau $q$ direkte Nachfolger,
        ist dies ein \idx{vollständiger (n, q)-Baum}

        \begin{satz}
            Sei $T$ ein (n, q)-Baum, wobei $n \ge 1, q \ge 2$.
            Dann ist $l(T) = \ceil{\log_q n}$
        \end{satz}

        \subsubsection{Informationstheoretische Schranke}
        Die Menge $\T (n,q)$ beschreibt alle (n, q)-Bäume.
        Die Zahl $\log_q n = \min\{l(T)|T\in \T(n,q)\}$ heisst die 
        \idx{informationstheoretische Schranke} bzgl. (n, q).

        \subsubsection{Die Kraftsche Ungleichung}
        \begin{enumerate}
            \item Sei $T$ ein (n, q)-Baum mit Blättern $1, \ldots, n$ der Längen
                $l_1, l_2, \ldots, l_n \in \N_0$. Dann ist $\sum_{i=1}^n
                q^{-l_i} \le 1$ und die Gleicheit gilt genau dann, wenn $T$
                vollständig ist.
            \item Sind $l_1, \ldots, l_n \in \N_0$, so dass $\sum_{i=1}^n
                q^{-l_i} \le 1$, so existiert ein (n,q)-Baum mit Blättern $b_1,
                \ldots, b_n$, so dass $l(b_i) = l_i, i=1,\ldots,n$
        \end{enumerate}

        \subsubsection{Erwartete Länge}
        Sei $T$ ein (n,q)-Baum mit den Blättern $1, \ldots, n$ und sei $l_i =
        l(i)$ die Länge des i-ten Blattes.
        Sei weiter $(p_1, \ldots, p_n) \in \R^n$ eine Wahrscheinlichkeitsverteilung
        auf den Blättern, d.h. $p_i \in [0,1]$ für $i = 1, \ldots, n$ und
        $\sum_{i=0}^n p_i = 1$.
        Die \idx{erwartete Länge} $\Lquer(T)$ von $T$ ist definiert als
        \[\Lquer (T) = \sum_{i=1}^n p_i l_i.\]
        Weiter sei
        \[\Lquer (p_1, \ldots, p_n) := \min \left\{\Lquer(t) | T \in \T(n,q)\right\}\]
        Ein Baum heißt \idx{optimal}, falls
        $\Lquer(T) = \Lquer(p_1, \ldots, p_n)$

        \subsubsection{Der Hauptsatz der Informationstheorie}
        Sei $n \ge 1$ und sei $q \ge 2$. Sei weiter $(p_1, \ldots, p_n)$ eine
        Wahrscheinlichkeitsverteilung auf $\{1, \ldots, n\}$.
        Dann gilt
        \[- \sum_{i=1}^n p_i \log_q p_i \le \Lquer (p_1, \ldots, p_n)
        \le - \sum_{i=1}^n p_i \log_q p_i + 1, \]
        wobei $0 \cdot \log_q 0$ als $0$ zu interpretieren ist.
        (Da $\linf x \cdot \log_q x = 0$)

    \subsection{Der Huffman-Algorithmus}
        \subsubsection{Vorbereitungen}
        Sei $n \ge 1, q\ge 2$ Sei $(p_1, \ldots, p_n)$ eine
        Wahrscheinlichkeitsverteilung auf $\{1, \ldots, n\}$, so dass
        $p_1 \ge p_2\ge p_n \ge 0$. Dann existiert ein optimaler (n, q)-Baum $T$
        für $(p_1, \ldots, p_n)$, so dass
        \begin{enumerate}
            \item für die Blätter $b_1, \ldots, b_n$ gilt $l(b_1) \le l(b_2) \le
                l(b_n)$. Weiter sind die letzten $q$ Blätter $b_{n-q+1}, \ldots,
                b_n$ von der maximalen Länge $L(T)$.
            \item $T$ ist vollständig.
        \end{enumerate}

\printindex
\end{document}