% Default LaTeX preambel follows...
\batchmode
\makeatletter
\makeatother
% We speak German...
% Change the header/footer-template if you are not, see above.
\documentclass[12pt,a4paper,ngerman]{article}
% Activate full utf-8 support.
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
% Default font is Bookman.
\usepackage{bookman}
% Yes, we do want our pages be numbered.
% XXX: No!
\pagestyle{empty}
% Some other packages...
\usepackage{babel} % Automatical hyphenation
\usepackage{latexsym} % Some nice symbols
\usepackage{url} % Breakable URLs
\usepackage{textcomp} % Some symbols (copyright, etc.)
\usepackage{graphics} % Support for images
\usepackage{amsmath} % Many mathematical symbols
\usepackage{stmaryrd} % Additional mathematical symbols
\usepackage{varioref} % Nice inner-document references
\usepackage{color} % Color support, may be needed by subclasses of
% MyBook::Output::LaTeX
\usepackage[official,right]{eurosym}
% Support for the euro sign
\usepackage{tabularx} % Nice tables
\usepackage{hyperref} % Clickable TOC
\usepackage{setspace} % User-settable line-height.
% DELETEME:
%\usepackage{rotating}
%\usepackage{shapepar}
%\usepackage{psfrag}
%\usepackage{array}
%\usepackage{lscape}
\usepackage{multicol}
% Allowing to have real IR, etc. in math mode:
% \mathds{C}
\usepackage{dsfont}
\DeclareMathAlphabet{\varmathds}{U}{dsss}{m}{n}
%\DeclareMathSymbol{,}{\mathord}{letters}{"3B} %"
% Support for "head level=4":
\newcommand{\MBsubsubsubsection}[1]{\paragraph{#1}\rule{0pt}{0pt}\par{}}
% MyBook::Output::LaTeX outputs "\MBem{...}" for emphasized text.
\newcommand{\MBem}[1]{\textbf{#1}}
% MyBook::Output::LaTeX outputs "\MBembcode{...}" for embedded sourcecode.
% For whatever reason, we have to define this command *after* \begin{document}.
% Don't ask me.
% MyBook::Output::LaTeX outputs "\MBsacode{...}" for stand-alone sourcecode.
\newcommand{\MBsacode}[1]{\texttt{#1}}
% Support for list type=listing and type=associative:
\newenvironment{MBlisting}{\begin{list}{}{}\small\item{}}{\end{list}}
\newcommand{\MBitem}[1]{#1\vspace{-2mm}}
\newenvironment{MBassoc}{\begin{description}}{\end{description}}
\newcommand{\MBassocitem}[2]{\item[#1]\rule{0pt}{0pt}\\#2}
% Nice inner-document references:
\newcommand{\MBref}[1]{\vpageref*{#1}}
% No single lines at the start of a paragraph (Schusterjungen)
\clubpenalty=10000
% No single lines at the end of a paragraph (Hurenkinder)
\widowpenalty=10000
\displaywidowpenalty=10000
\makeatletter
\makeatother
% Some other sensible defaults: We want our text to be formatted like
%
% This is the first paragraph. This is the first paragraph. This is the
% first paragraph. This is the first paragraph. This is the first
% paragraph.
%
% This is the second paragraph. This is the second paragraph. This is the
% second paragraph. This is the second paragraph. This is the second
% paragraph.
%
% instead of
%
% This is the first paragraph. This is the first paragraph. This is the
% first paragraph. This is the first paragraph. This is the first
% paragraph. This is the first paragraph.
%
% This is the second paragraph. This is the second paragraph. This is
% the second paragraph. This is the second paragraph. This is the second
% paragraph.
%
% Again, change the header/footer-template (see above) if our tastes differ...
% :)
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\usepackage{geometry}
\geometry{verbose,tmargin=1.5cm,bmargin=1.7cm,lmargin=1.0cm,rmargin=1.0cm}
\newcommand{\slide}[2]{
\newpage
\begin{center}\Huge\underline{#1}\end{center}
\Large#2
}
\newcommand{\textlt}[1]{\textsc{#1}}
% From http://help-csli.stanford.edu/tex/latex-footnotes.shtml
%\long\def\symbolfootnote[#1]#2{\begingroup%
\def\thefootnote{\fnsymbol{footnote}}
%\setstretch{1.2}
\begin{document}
\begin{center}
\Huge Entropie \\
\tiny Mathematikreferat von Ingo Blechschmidt und Michael Hartmann
\tiny am 15. November 2006
\end{center}
\vspace*{0.6em}
\newcommand{\za}[1]{} %(Z.~#1)}
\newcommand{\zb}[1]{} %(Z'.~#1)}
\newcommand{\zc}[1]{} %(Z{}'{}'{}.~#1)}
\setlength{\columnseprule}{1pt}
\setlength{\columnsep}{30pt}
\newenvironment{zitemize}{\begin{list}{--}{\addtolength{\leftmargin}{-1.5em}}}{\end{list}}
\begin{multicols}{2}
{\large \textbf{Definition}}
\begin{zitemize}
\item[--] Informationsgehalt eines Zeichens: \\
$I(x) := -\log_2 P(x); \qquad \left[1 \,\mathrm{bit}\right]$
\item[--] Entropie als Erwartungswert des Informationsgehalts: \\
$E(I) = \sum\limits_{x \in \Sigma} P(x) \cdot I(x);$
\end{zitemize}
wobei
\begin{tabbing}
asdfff \= \kill
$x$: \> ein bestimmtes Zeichen \\
$\Sigma$: \> Menge aller vorkommenden \\ \> Zeichen \\
$P(x)$: \> Wahrscheinlichkeit \\ \> des Auftretens von $x$ \\
\end{tabbing}
{\large \textbf{Eigenschaften}}
\begin{zitemize}
\item[--] Maximale Entropie bei $\left|\Sigma\right| = 2^n$, $n \in \mathds{N}$: \\
$E(I) = -\log_2 \frac{1}{2^n} = n \,\mathrm{bit};$
\item[--] Maß für Überraschung;
je seltener ein Zeichen, desto höher der Informationsgehalt
\item[--] Maß für die untere Schranke verlustfreier Kompression
\item[--] Maß für die Zufälligkeit von Information
\item[--] Maß für "`Chaos"'
\item[--] Charakteristika von Autoren und Komponisten
\end{zitemize}
{\large \textbf{Gezinkter Münzwurf}} \\
$\Sigma = \left\{ \text{Kopf}, \text{Zahl} \right\}\!;$
\medskip
$P(\text{Kopf}) = p = 1 - P(\text{Zahl});$
\medskip
$
\begin{array}{@{}rcl}
I(\text{Kopf}) &=& -\log_2 p; \\
I(\text{Zahl}) &=& -\log_2 \left(1 - p\right);
\end{array}
$
\medskip
$
\renewcommand{\arraystretch}{1.3}
\begin{array}{@{}rclcl}
E(I) &=& p \, I(\text{Kopf}) &+& \left(1 - p\right) I(\text{Zahl}) = \\
&=& p \cdot \left[-\log_2 p\right] &+& \left(1 - p\right) \cdot \left[-\log_2 \left(1 - p\right)\right];
\end{array}
$
\columnbreak
{\centering\scalebox{0.35}{\includegraphics{images/entropie-muenzwurf.png}}\par}
\vspace*{1em}
{\large \textbf{Shannon--Fano-Kodierung}} \\
\vspace*{-1em}
\begin{zitemize}
\item[--] Entropiekodierung ("`Kompressionsverfahren"')
\item[--] Darstellung \textsl{häufiger} Zeichen durch \textsl{kurze} Bitfolgen, \textsl{seltener} Zeichen durch \textsl{lange} Bitfolgen
\item[--] Eindeutigkeit der Bitfolgen ("`Präfixfreiheit"') notwendig
\bigskip
\item[1.] Sortierung der Zeichen nach rel. Häu\-fig\-keit
\item[2.] Einteilung der Zeichen in zwei Gruppen, sodass Summen der
Häufigkeiten etwa gleich
\item[3.] So lange fortfahren, bis Entsprechung jedes Zeichens durch einen
Pfad im Baum
\end{zitemize}
\scalebox{0.3}{\includegraphics{images/baum.png}}
{\large \textbf{Probleme}}
\vspace*{-1em}
\begin{zitemize}
\item[--] Keine Beachtung der Reihenfolge
\item[--] Analyse nur auf syntaktischer Ebene
\end{zitemize}
\end{multicols}
\end{document}
Download