% 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