245 lines
12 KiB
TeX
245 lines
12 KiB
TeX
\documentclass[10pt,landscape]{article}
|
|
\usepackage{multicol}
|
|
\usepackage{calc}
|
|
\usepackage{ifthen}
|
|
\usepackage[landscape]{geometry}
|
|
\usepackage{amsmath,amsthm,amsfonts,amssymb}
|
|
\usepackage{color,graphicx,overpic}
|
|
\usepackage{hyperref}
|
|
|
|
\pdfinfo{
|
|
/Title (Grundlagen und Diskrete Strukturen - Short Script)
|
|
/Creator (TeX)
|
|
/Producer (pdfTeX 1.40.0)
|
|
/Author (Robert Jeutter)
|
|
/Subject (Grundlagen und Diskrete Strukturen)
|
|
}
|
|
|
|
% This sets page margins to .5 inch if using letter paper, and to 1cm
|
|
% if using A4 paper. (This probably isn't strictly necessary.)
|
|
% If using another size paper, use default 1cm margins.
|
|
\ifthenelse{\lengthtest { \paperwidth = 11in}}
|
|
{ \geometry{top=.5in,left=.5in,right=.5in,bottom=.5in} }
|
|
{\ifthenelse{ \lengthtest{ \paperwidth = 297mm}}
|
|
{\geometry{top=1cm,left=1cm,right=1cm,bottom=1cm} }
|
|
{\geometry{top=1cm,left=1cm,right=1cm,bottom=1cm} }
|
|
}
|
|
|
|
% Turn off header and footer
|
|
\pagestyle{empty}
|
|
|
|
% Redefine section commands to use less space
|
|
\makeatletter
|
|
\renewcommand{\section}{\@startsection{section}{1}{0mm}%
|
|
{-1ex plus -.5ex minus -.2ex}%
|
|
{0.5ex plus .2ex}%x
|
|
{\normalfont\large\bfseries}}
|
|
\renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}%
|
|
{-1explus -.5ex minus -.2ex}%
|
|
{0.5ex plus .2ex}%
|
|
{\normalfont\normalsize\bfseries}}
|
|
\renewcommand{\subsubsection}{\@startsection{subsubsection}{3}{0mm}%
|
|
{-1ex plus -.5ex minus -.2ex}%
|
|
{1ex plus .2ex}%
|
|
{\normalfont\small\bfseries}}
|
|
\makeatother
|
|
|
|
% Define BibTeX command
|
|
\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
|
|
T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
|
|
|
|
% Don't print section numbers
|
|
\setcounter{secnumdepth}{0}
|
|
|
|
|
|
\setlength{\parindent}{0pt}
|
|
\setlength{\parskip}{0pt plus 0.5ex}
|
|
|
|
%My Environments
|
|
\newtheorem{example}[section]{Example}
|
|
% -----------------------------------------------------------------------
|
|
|
|
\begin{document}
|
|
\raggedright
|
|
\footnotesize
|
|
\begin{multicols}{3}
|
|
|
|
|
|
% multicol parameters
|
|
% These lengths are set only within the two main columns
|
|
%\setlength{\columnseprule}{0.25pt}
|
|
\setlength{\premulticols}{1pt}
|
|
\setlength{\postmulticols}{1pt}
|
|
\setlength{\multicolsep}{1pt}
|
|
\setlength{\columnsep}{2pt}
|
|
|
|
\paragraph{Relationen}
|
|
Sei $R\in AxA$ binäre Relation auf A
|
|
\begin{itemize}
|
|
\item Reflexiv $\leftrightarrow \text{ xRx } \forall x \in A$
|
|
\item symmetrisch $\leftrightarrow \text{ xRy } \rightarrow \text{ yRx }$
|
|
\item Antisymmetrisch $\leftrightarrow \text{ xRy } \wedge yRx \rightarrow x=y$
|
|
\item Transitiv $\leftrightarrow \text{ xRy } \wedge \text{ yRz } \rightarrow \text{ xRz }$
|
|
\item totale Relation $\leftrightarrow \text{ xRy } \vee \text{ yRx } \forall x,y \in A$
|
|
\end{itemize}
|
|
R heißt:
|
|
\begin{itemize}
|
|
\item Äquivalenzrelation $\leftrightarrow$ reflexiv, symmetrisch und transitiv
|
|
\item Ordnung $\leftrightarrow$ reflexiv, antisymmetrisch und transitiv
|
|
\item Totalordnung $\leftrightarrow$ Ordnung und total
|
|
\item Quasiordnung $\leftrightarrow$ reflexiv und transitiv
|
|
\end{itemize}
|
|
|
|
\paragraph{Partition/Klasse}
|
|
Sei $C\wp (A)$. C heißt Partition/Klasse von A, falls gilt:
|
|
\begin{itemize}
|
|
\item $\bigcup C=A$ d.h. jedes $x\in A$ liegt in (min) einem $y\in C$
|
|
\item $\emptyset \not \in C$ d.h. jedes $y\in C$ enthält (min) ein Element von A
|
|
\item $x \cap y = \emptyset$ f.a. $x\not \in y$ aus C
|
|
\end{itemize}
|
|
|
|
\paragraph{Ordnungen}
|
|
Sei $leq$ eine Ordnung auf X. Sei $A\subseteq X, b\in X$
|
|
\begin{itemize}
|
|
\item b minimal in A $\leftrightarrow b\in A$ und $(c\leq b \rightarrow c=b f.a. c\in A)$
|
|
\item b maximal in A $\leftrightarrow b\in A$ und $(b\leq c \rightarrow b=c f.a. c\in A)$
|
|
\item b kleinstes Element in A $\leftrightarrow b\in A$ und $(b\leq c f.a. c\in A)$
|
|
\item b größtes Element in A $\leftrightarrow b\in A$ und $(c\leq b f.a. c\in A)$
|
|
\item b untere Schranke von A $\leftrightarrow b\leq c f.a. c\in A$
|
|
\item b obere Schranke von A $\leftrightarrow c\leq b f.a. c\in A$
|
|
\item b kleinste obere Schranke $\leftrightarrow$ kleinstes Element von obere Schranke; Supremum $\lor A = b$
|
|
\item b größte untere Schranke $\leftrightarrow$ größte Element von untere Schranke; Infinum $\land A = b$
|
|
\end{itemize}
|
|
|
|
\paragraph{Induktion I}
|
|
Sei $p(n)\in \mathbb{N}$. Gelte $p(0)$ und $p(n)\rightarrow p(n^{+})$ f.a. $n\in \mathbb{N}$ dann ist $p(n)$ wahr f.a. $n \in \mathbb{N}$.
|
|
|
|
\paragraph{Induktion II}
|
|
Sei $p(n)\in \mathbb{N}$, gelte $\{\forall x < n: p(x)\} \rightarrow p(n)$ f.a. $n\in \mathbb{N}$. Damit ist $p(n)$ wahr für alle $n\in \mathbb{N}$.
|
|
|
|
\section{Funktionen}
|
|
Eine Relation $f\subseteq A x B$ heißt Funktion $f:A\rightarrow B$ falls es zu jedem $x\in A$ genau ein $y\in B$ mit $(x,y)\in f$ gibt.
|
|
\begin{itemize}
|
|
\item injektiv $\leftrightarrow$ jedes y aus B hat höchstens ein Urbild $f(x)=f(y)\rightarrow x=y$
|
|
\item subjektiv $\leftrightarrow$ jedes y aus B hat wenigstens ein Urbild $f(x)=y$
|
|
\item bijektiv $\leftrightarrow$ jedes y aus B hat genau ein Urbild; injektiv und surjektiv
|
|
\end{itemize}
|
|
ist $f:A\rightarrow B$ bijektiv, so ist $f^{-1}$ eine Funktion B nach A und gleichmächtig.
|
|
|
|
\section{Gruppen, Ringe, Körper}
|
|
Eine Menge G mit einer Operation $\circ$ auf G heißt Gruppe, falls gilt:
|
|
\begin{itemize}
|
|
\item $a\circ (b\circ c) = (a\circ b)\circ c$ freie Auswertungsfolge
|
|
\item es gibt ein neutrales Element $e\in G$ mit $a\circ e=a$ und $e\circ a=a$ f.a. $a\in G$
|
|
\item $\forall a\in G \exists b\in G: \{a\circ b=e\} \vee \{b\circ a=e\}; b=a^{-1}$
|
|
\end{itemize}
|
|
kommutativ/abelsch, falls neben obigen gilt:
|
|
\begin{itemize}
|
|
\item $a\circ b = b\circ a$ f.a. $a,b \in G$
|
|
\end{itemize}
|
|
|
|
Zwei Gruppen $(G, \circ_G)$ und $(H,\circ_H)$ heißen isomorph, falls es einen Isomorphismus $(G,\circ_G)\cong (H,\circ_H)$ von $(G,\circ_G)$ nach $(H,\circ_H)$ gibt.
|
|
|
|
\paragraph{Addition \& Multiplikation}
|
|
$+: \mathbb{N} x \mathbb{N} \rightarrow \mathbb{N}$ wird definiert durch:
|
|
\begin{itemize}
|
|
\item $m+0:=m$ (0 ist neutral)
|
|
\item $m+n$ sei schon definiert
|
|
\item $m+n^+:=(m+n)^+$
|
|
\item $m*0:=0$
|
|
\item $m*n^+=m*n+m$
|
|
\item $[(a,b)]_{/\sim } + [(c,d)]_{/\sim } = [(a+c, b+d)]_{/\sim }$
|
|
\item $[(a,b)]_{/\sim } * [(c,d)]_{/\sim } = [(ac+bd, ad+bc)]_{/\sim }$
|
|
\end{itemize}
|
|
|
|
Ein Ring R ist eine Menge mit zwei Operationen $+,*: \mathbb{R} x \mathbb{R} \rightarrow \mathbb{R}$ mit:
|
|
\begin{itemize}
|
|
\item $a+(b+c) = (a+b)+c$ f.a. $a,b,c\in \mathbb{R}$
|
|
\item Es gibt ein neutrales Element $O\in \mathbb{R}$ mit $O+a=a+O=O$
|
|
\item zu jedem $a\in \mathbb{R}$ gibt es ein $-a\in \mathbb{R}$ mit $a+(-a)=-a+a=0$
|
|
\item $a+b=b+a$ f.a. $a,b\in\mathbb{R}$
|
|
\item $a*(b*c)=(a*b)*c)$ f.a. $a,b,c\in\mathbb{R}$
|
|
\item $a*(b+c)=a*b+a*c$ f.a. $a,b,c\in\mathbb{R}$
|
|
\item heißt Ring mit 1, falls: es gibt ein $1\in\mathbb{R}$ mit $a*1=1*a=a$
|
|
\item heißt kommutativ, falls: $a*b=b*a$ f.a. $a,b\in\mathbb{R}$
|
|
\item heißt Körper, falls: zu jedem $a\in\mathbb{R}$ gibt es ein $a^{-1}\in\mathbb{R}$ mit $a*a^{-1}=1$
|
|
\item Ist $\mathbb{R}$ ein Körper, so ist $\mathbb{R}*=\mathbb{R} /(0)$ mit $*$ eine abelsche Gruppe.
|
|
\item $\mathbb{Z}$ mit + und * ist ein kommutativer Ring mit $1 \not= 0$ aber kein Körper
|
|
\item $\mathbb{Q}, \mathbb{C}, \mathbb{R}$ mit + und * ist ein Körper
|
|
\end{itemize}
|
|
|
|
\paragraph{Konstruktion von rationalen Zahlen}
|
|
Definiere Operationen +,* auf $\mathbb{Q}$ wie folgt:
|
|
\begin{itemize}
|
|
\item $\frac{a}{b}+\frac{c}{d} = \frac{ad+bc}{b*d}$ (wohldefiniert)
|
|
\item $\frac{a}{b}*\frac{c}{d} = \frac{a*c}{b*d}$
|
|
\end{itemize}
|
|
|
|
\paragraph{Ring der formalen Potenzreihe}
|
|
Sei k ein Körper. Eine Folge $(a_0,...,a:n)\in K^{\mathbb{N}}$ mit Einträgen aus K heißt formale Potenzreihe $K[[x]]$.
|
|
\begin{itemize}
|
|
\item +: $(a_0,a_1,...) + (b_0,b_1,...) = (a_o+b_0, a_1+b_1, ...)$
|
|
\item *: $(a_0,a_1,...) + (b_0,b_1,...) = (c_0, c_1,...)$ mit $c_K=\sum_{j=a}^{k} a_j*b_{k-j}$
|
|
\end{itemize}
|
|
|
|
\section{Wahrscheinlichkeit}
|
|
Ein Wahrscheinlichkeitsraum ist ein Paar $(\Omega, p)$ aus einer endlichen Menge $\Omega$ und einer Funktion $p:\Omega \rightarrow [0,1]\in \mathbb{R}$
|
|
Es gilt für Ereignisse $A,B,A_1,...,A_k$:
|
|
\begin{itemize}
|
|
\item $A\subseteq B \rightarrow p(A)\leq p(B)$
|
|
\item $p(A\cup B) \rightarrow p(A)+p(B)-p(A\cap B)$
|
|
\item disjunkt($A_i \cap A_J=\emptyset$ für $i\not =j$) so gilt $p(A_1 \cup ... \cup A_k)= p(A_1)+...+p(A_k)$
|
|
\item $p(\Omega / A):=$ Gegenereignis von $A=1-p(A)$
|
|
\item $p(A_1,...,A_k) \leq p(A_1)+...+p(A_k)$
|
|
\item (stochastisch) unabhängig, falls $p(A\cap B) = p(A)*p(B)$
|
|
\end{itemize}
|
|
|
|
\paragraph{Bedingte Wahrscheinlichkeiten}
|
|
$A,B\subseteq \Omega$ für $p_B(A\cap B)= \frac{p(A\cap B)}{p(B)}:= p(A|B)$\
|
|
Erwartungswert $E(X) = \sum_{\omega \in \Omega} X(\omega)p(\omega)$\
|
|
Linearität von E: $E(x+y)=E(x)+E(y)$ und $E(\alpha x)=\alpha E(x)$\
|
|
Varianz von X: $Var(X)=E((X^2)-E(X))^2)$\
|
|
Covarianz: $Cov(X,Y)=E((X-E(X))*(Y-E(Y)))$\
|
|
Verschiebungssatz: $Cov(X,Y)=E(X*Y)-E(X)*E(Y)$\
|
|
Bernoulliverteilt falls $p(X=1)=p$ und $p(X=0)=1-p$\
|
|
Bernoulli $P=\binom{n}{k}*p^k*(1-p)^{n-k}$\
|
|
$\binom{N}{0}=(\emptyset), \binom{N}{n}={N}, \binom{n}{0}=\binom{n}{n}=1$ $\binom{n}{0}=1, \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}=\frac{n!}{k!(n-k)!}$
|
|
|
|
\paragraph{Hypergeometrische Verteilung}
|
|
Beispiel: Urne mit zwei Sorten Kugeln; N Gesamtzahl der Kugeln, M Gesamtzahl Kugeln Sorte 1, N-M Gesamtzahl Kugeln Sorte 2, $n\leq N$ Anzahl Elemente einer Stichprobe. X Anzahl der Kugeln Sorte 1 in einer zufälligen n-elementigen Stichprobe.
|
|
$p(X=k)=\frac{\binom{M}{k}\binom{N-M}{n-k}}{\binom{N}{n}}$\
|
|
$E(X)=\sum_{x=0}^M \frac{\binom{M}{k}\binom{N-M}{n-k}}{\binom{N}{n}}=n*\frac{M}{N}$\
|
|
$Var(X)=E(X^2)-E(X)^2 = n*\frac{M}{N}(1-\frac{M}{N})\binom{N-n}{N-1}$
|
|
|
|
\section{Elementare Graphentheorie}
|
|
$G=(V,E)$ heißt Graph mit Eckenmenge $V(G)=V$ und Kantenmenge $E(G)=E\subseteq {{x,y}:x\not=y \in V}$.\
|
|
Für $(a,b)\in V(G)$ heißt $d_G(a,b)=min(l: \text{ es gibt einen a,b-Weg der Länge l} )$ Abstand von a nach b.\
|
|
G heißt zusammenhängend, wenn G höchstens eine Komponente besitzt.
|
|
\begin{itemize}
|
|
\item $d_G(x,y)=0 \leftrightarrow x=y$
|
|
\item $d_G(x,y)=d_G(y,x)$
|
|
\item $d_G(x,z)\leq d_G(x,y) + d_G(y,z))$
|
|
\end{itemize}
|
|
|
|
Ein Graph ist ein Baum wenn "G ist minimal zusammenhängend und kreisfrei"
|
|
\begin{itemize}
|
|
\item G ist kreisfrei und zusammenhängend
|
|
\item G kreisfrei und $|E(G)|=|V(G)|-1$
|
|
\item G zusammenhängend und $|E(G)|=|V(G)|-1$
|
|
\end{itemize}
|
|
Breitensuchbaum von G falls $d_F(z,x)=d_G(z,x)$ f.a. $z\in V(G)$.\
|
|
Tiefensuchbaum von G falls für jede Kante zy gilt: z liegt auf dem y,x-Weg in T oder y liegt auf dem z,t-Weg in T.
|
|
|
|
\paragraph{Spannbäume minimaler Gewichte}
|
|
Sei G zuständiger Graph, $\omega:E(G)\rightarrow \mathbb{R}$; Setze $F=\emptyset$. Solange es eine Kante $e\in E(G)/F$ gibt so, dass $F \vee (e)$ kreisfrei ist, wähle e mit minimalem Gewicht $\omega(e)$, setzte $F=F\vee {e}$, iterieren. Das Verfahren endet mit einem Spannbaum $T=G(F)$ minimalen Gewichts.
|
|
|
|
\paragraph{Das Traveling Salesman Problem}
|
|
Konstruiere eine Folge$x_0,...,x_m$ mit der Eigenschaft, dass jede Kante von T genau zweimal zum Übergang benutzt wird, d.h. zu $e\in E(T)$ existieren $i\not = j$ mit $e=x_i x_{i+1}$ und $e=x_j x_{j+1}$ und zu jedem k existieren $e\in E(T)$ mit $e=x_k x_{k+1}$. Das Gewicht dieser Folge sei $\sum \omega(x_i x_{i+1})= 2\omega(T)$. Eliminiere Mehrfachnennungen in der Folge. Durch iteration erhält man einen aufspannenden Kreis mit $\omega(X) \leq 2 \omega(T)$.
|
|
|
|
\paragraph{Färbung \& bipartit}
|
|
Eine Funktion $f:V(G)\rightarrow C$ mit $|C|\leq k$ heißt k-Färbung, falls $f(x)\not = f(y)$ für $xy\in E(G)$.
|
|
Ein Graph heißt bipartit mit den Klassen A,B falls $(x\in A \wedge y\in B)\vee (x\in B \wedge y\in A)$.
|
|
Mit Bipartitheit gilt G hat ein Matching von A $\leftrightarrow |N_G(X)|\leq |X|$ für alle $X\subseteq A$.
|
|
|
|
\end{multicols}
|
|
\end{document} |