Zuletzt geändert: Mi, 15.11.2006

«K12/K13» Handout.latexs «PDF», «POD»



Download
% 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}