\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\noindent TEIL F: STOCHASTIK \\[0.8cm]
§61: GRUNDBEGRIFFE \\[0.8cm]
61.1 Motivation \\
Stochastik (aus Griechischen: vermuten, erwarten) ist die Mathematik des Zufalls. Sie ist von großer Bedeutung in der Informatik. \\
Beispiel:
\begin{itemize}
	\item Analyse der Auslastung von Datennetzen
	\item Modellierung von Antwortzeiten im Rechner
	\item Zuverlässigkeitsanalyse von Hardware
	\item Raytracing in der Computergrafik (Monte-Carlo-Simulationen)
	\item Optimierungsalgorithmen (genetische Algorithmen, simulated annealing)
	\item Analyse der Laufzeit von Algorithmen
	\item kombinatorische Probleme in der Bioinformatik
\end{itemize}
61.2 Gebietsabgrenzung \\
Stochastik gliedert sich in 2 Gebiete:
\begin{enumerate}[(a)]
	\item Wahrscheinlichkeitstheorie \\
		Ausgehend von einem stochastischen Modell werden Wahrscheinlichkeiten berechnet. \\
		Beispiel: Modellannahme \\
		Beim Wurf eines Würfels habe jede der Augenzahlen 1 bis 6 die Wahrscheinlichkeit $\frac{1}{6}$. \\
		Folgerung: Wahrscheinlichkeit für Augenzahl 1 oder 3 ist $\frac{1}{6} + \frac{1}{6} = \frac{1}{3}$.
	\item Statistik \\
		Ausgehend von realen Daten/Messungen möchte man Schlussfolgerungen ziehen. \\
		Beispiele:
		\begin{itemize}
			\item möglichst gute Approximationsgerade durch fehlerbehaftete Messwerte legen.
			\item Hypothesentest: Ist ein neues Medikament wirksam?
		\end{itemize}
\end{enumerate}
61.3 Def.: \\
Die Wahrscheinlichkeit eines Ereignisses beschreibt die zu erwartende relative Häufigkeit, mit der dieses Ereignis eintritt, wenn man den zu Grunde liegenden Prozess immer wieder unter den gleichen Bedingungen wiederholt. \\[0.5cm]
Beispiel: \\
Bei einer \glqq fairen\grqq\ Münze beträgt die Wahrscheinlichkeit (WS), Zahl zu erhalten, $\frac{1}{2}$. \\[0.5cm]
61.4 Def.: \\
Ein Experiment heißt Laplace-Experiment, wenn es endlich viele, einander ausschließende Ausgänge hat, die alle gleich wahrscheinlich sind. \\[0.3cm]
Beispiel:
\begin{itemize}
	\item Der Wurf eines Würfels hat 6 gleich berechtigte Ausgänge $\Rightarrow$ Laplace-Experiment
	\item Fällt ein Marmeladenbrot zu Boden, gibt es zwei Ausgänge, die nach Murphy nicht gleich wahrscheinlich sind $\Rightarrow$ kein Laplace-Experiment, falls dies stimmt
\end{itemize}
61.5 Mengentheoretische Wahrscheinlichkeitsbeschreibung \\
Def.: \\
Wir betrachten ein Zufallsexperiment mit endlich vielen Ausgängen und definieren 3 Begriffe:
\begin{enumerate}[(a)]
	\item Ergebnismenge $\Omega$ (Stichprobenraum, Grundraum) \\
		endliche, nicht leere Menge, deren Elemente $\omega_i$ die Versuchsausgänge beschreiben. \\
		Bsp.: Würfelexperiment $\Omega = \{1,2,...,6\}$
	\item Ereignis \\
		Teilmenge von $\Omega$. \\
		Bsp.: Ergebnisse, bei denen 2 oder 5 gewürfelt wird. $\Rightarrow$ Ereignis $A = \{2,5\}$.
	\item Wahrscheinlichkeitsverteilung, Wahrscheinlichkeitsmaß \\
		Abbildung $P$ von der Potenzmenge $\mathcal{P}(\Omega)$ nach $[0,1]$ mit folgenden Eigenschaften:
		\begin{enumerate}[(i)]
			\item Normiertheit: $P(\Omega) = 1$
			\item Nichtnegativität: $P(A) \ge 0 \quad \forall A \in \mathcal{P}(\Omega)$
			\item Additivität: $P(A \cup B) = P(A) + P(B)$ für alle disjunkten $A,B \in \mathcal{P}(\Omega)$
		\end{enumerate}
\end{enumerate}
§62: KOMBINATORIK \\[0.8cm]
62.1 Motivation \\
Die Kombinatorik liefert wichtige Modelle zum Berechnen von Wahrscheinlichkeiten bei Laplace-Experimenten. Sie liefert eine grundlegende Rolle in der Informatik. \\[0.5cm]
62.2 Zwei grundlegende Sprechweisen \\
\begin{enumerate}[(a)]
	\item Stichprobensprechweise, Urnenmodell \\
		Aus einer Urne mit $n$ unterscheidbaren Kugeln werden $k$ Kugeln gezogen. Dabei kann das Ziehen mit oder ohne Zurücklegen erfolgen und die Reihefolge eine oder keine Rolle spielen.
	\item Zuordnungssprechweise, Schubladenmodell \\
		$k$ Objekte werden auf $n$ Schubladen verteilt. Dabei sind die Objekte entweder unterscheidbar oder nicht unterscheidbar und die Schubladen dürfen einfach oder mehrfach besetzt werden. \\
		Urnen- und Schubladenmodell sind äquivalent \\
		\begin{center}
		\begin{tabular}{c|c}
			Urnenmodell & Schubladenmodell \\ \hline
			mit / ohne Zurücklegen & mit / ohne Mehrfachbesetzung \\ \hline
			mit / ohne Berücksichtigung & unterscheidbare / ununterscheidbare \\
			der Reihenfolge & Objekte
		\end{tabular}
		\end{center}
\end{enumerate}
62.3 Produktregel der Kombinatorik \\
Bei einem $k$-stufigen Experiment habe der Ausgang einer Stufe keinen Einfluss auf die Anzahl der möglichen Ausgänge bei späteren Stufen. Haben die einzelnen Stufen $n_1,...,n_k$ Ausgänge, so hat das Gesamtexperiment $n_1 \cdot ... \cdot n_k$ Ausgänge. \\
Die Produktregel ist wichtig bei der Beschreibung der vier kombinatorischen Grundsituationen. \\[0.5cm]
62.4 Die vier kombinatorischen Grundsituationen
\begin{enumerate}[(a)]
	\item Geordnete Stichprobe mit Wiederholung \\
		Bei $k$ Ziehungen mit Zurücklegen aus einer Urne mit $n$ Objekten gibt es bei Berücksichtigung der Reihenfolge $n^k$ Möglichkeiten \\[0.2cm]
		Beispiel (aus einem älteren Stochastikbuch): \\
		Herr Meier will seinen ungezogenen Sohn mit 10 Ohrfeigen bestrafen. Auf wie viele Arten kann er das tun, wenn er bei jedem Schlag 1 von 2 Möglichkeiten hat (links oder rechts)? \\
		Es gibt $2^{10} = 1024$ Möglichkeiten.
	\item Geordnete Stichprobe ohne Wiederholung \\
		Urnenmodell: $k$ Ziehungen aus $n$ Objekten ohne Zurücklegen, aber mit Berücksichtigung der Reihenfolge. \\
		Möglichkeiten: $\displaystyle \underbrace{n}_{\text{1. Ziehung}} \cdot (n-1) \cdot (n-2) \cdot ... \cdot \underbrace{(n-k+1)}_{k\text{-te Fakultät}} = \frac{n!}{(n-k)!}$ \\
		Spezialfall: $k=n \Rightarrow n!$ Möglichkeiten \\
		Für große $n$ approximiert man $n!$ mit der Stirling-Formel.
		$$n! \approx \sqrt{2 \cdot \pi \cdot n} \cdot n^n \cdot e^{-n}$$ \\[0.2cm]
		Beispiel: \\
		Herr Meier will seine 5 Kinder in einer Reihe anordnen für eine Gruppenaufnahme. \\
		Es gibt $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ Möglichkeiten.
	\item Ungeordnete Stichprobe ohne Wiederholung \\
		Wie in (b), jedoch müssen die $k!$ Permutationen der $k$ gezogenen Elemente miteinander identifiziert werden. \\
		Daher gibt es nur $\displaystyle \frac{n!}{(n-k)! \cdot k!} = {n \choose k}$ Möglichkeiten. \\[0.2cm]
		Beispiel: \\
		Beim Lottospielen gibt es
		$${49 \choose 6} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6} = 13.983.816$$
		Möglichkeiten.
	\item Ungeordnete Stichprobe mit Wiederholung \\
		Hier ist das Schubladenmodell sinnvoll: Es sollen $k$ nicht unterscheidbare Objekte in $n$ Schubladen verstaut werden, wobei Mehrfachbesetzung möglich ist. \\
		Gesamtzustand ist beschrieben durch die Reihenfolge von $k$ Objekten und $n-1$ Trennungsstrichen.
		$$\Rightarrow \frac{(k+n-1)!}{k! (n-1)!} = {k+n-1 \choose k} = {k+n-1 \choose n-1} \text{ Möglichkeiten}$$\\[0.2cm]
		Beispiel: \\
		Auf wie viele Arten kann man 60 Parlamentssitze auf 3 Parteien verteilen?
		$$k=60, n=3: \Rightarrow {62 \choose 60} = {62 \choose 2} = \frac{62 \cdot 61}{2 \cdot 1} = 1891 \text{ Möglichkeiten}$$
\end{enumerate}

\end{document}
