\documentclass[12pt,compress]{beamer}
\usepackage{amsmath}
\usepackage{url}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{ulem} % sout
\usepackage{multicol}
\usepackage{comment}
\usepackage{setspace}
% Manual syntax highlighting
\newcommand{\synfunc} [1]{\color{blue!50!black}#1\color{black}}
\newcommand{\synstr} [1]{\color{red!50!black}#1\color{black}}
\newcommand{\synvar} [1]{\color{purple!50!black}#1\color{black}}
\newcommand{\synclass} [1]{\color{green!50!black}#1\color{black}}
\newcommand{\syncomment}[1]{\color{blue!20!black}#1\color{black}}
\newcommand{\syncool} [1]{\color{beamer@blendedblue}#1\color{black}}
\newcommand{\synoder} {\ \ \color{black}$\vee$\ \ }
\newcommand{\hr} {\rule[4pt]{\textwidth}{0.1pt}\\}
\newcommand{\hicolor} [1]{\color[rgb]{0.6,0.2,0.8}#1\color{black}}
\newcommand{\synhilight}[1]{\hicolor{\textbf{#1}}}
\newcommand{\doofcomment}{\ \ \syncomment{\# :-(}}
\newcommand{\gutcomment} {\ \ \syncomment{\# :)}}
\title{Entropie}
\author{Ingo~Blechschmidt, \\ Michael~Hartmann}
\date{15. November 2006}
\usetheme{Warsaw} %Warsaw, Berkeley?
\usecolortheme{seahorse}
\usefonttheme{serif}
\useinnertheme{rectangles}
\usepackage{bookman}
\setbeamercovered{transparent}
\begin{document}
\frame{\titlepage}
\frame[t]{
\frametitle{Inhalt}
\tableofcontents
}
\section{Information}
\subsection{Definition}
\frame[t]{
\begin{block}{Mögliche Definitionen}
Information \\ (v. lat.: informare $\hat{=}$ bilden, eine Form geben):
\begin{itemize}
\item
Muster von Materie oder Energieformen
%, das für einen Betrachter innerhalb
%eines bestimmten Kontextes relevant ist
% \end{itemize}
%
% \begin{itemize}
\item
Beseitigung von Ungewissheit
%durch Auskunft, Mitteilung, Benachrichtigung
%oder Kenntnis über Gegenstände und Phänomene
\end{itemize}
\end{block}
\vfill\hfill%
\includegraphics[scale=0.4]{images/library.jpg}
}
\subsection{Informationsebenen}
\frame[t]{
\frametitle{Informationsebenen}
\begin{enumerate}
\item Codierung
\item Syntax
\item Semantik
\item Pragmatik
\end{enumerate}
\vfill\hfill%
\includegraphics[scale=0.2]{images/schichten.jpg}
}
\frame[t]{
\frametitle{Codierung}
\begin{block}{Codierung}
Vorschrift, mit der Informationen zur Übertragung umgewandelt werden kann.
\end{block}
\vfill
Beispiele:
\begin{itemize}
\item Sprache
\item Schrift
\item Brailleschrift
\item Flaggenalphabet
\item Morsezeichen
\end{itemize}
\vfill\hfill%
\includegraphics[scale=0.25]{images/braille.png}
}
\frame[t]{
\frametitle{Syntax}
\begin{block}{Syntax}
Information als bloße Struktur, ohne "`Sinn"'.\\
Inhalt oder Bedeutung der Information sind irrelevant.
\end{block}
\vfill
Beispiele:
\begin{itemize}
\item Übertragung von Webseiten auf einen Computer
\item Übertragung von Bildern einer Überwachungskamera
\item Übertragung von Tönen beim Telefonieren
\end{itemize}
\vfill\hfill%
\includegraphics[scale=0.25]{images/telefon.jpg}
}
\frame[t]{
\frametitle{Semantik}
\begin{block}{Semantik}
Interpretierte, sinnbehaftete Information
\end{block}
\vfill
\begin{tabbing}
S. 251/29 \= → \= \kill
$\frac{1}{2} g h$ \> → \> Allgemeine Formel für den Flächeninhalt \\\>\> eines Dreiecks \\
S. 251/29 \> → \> Aufgabe 29 im Stochastik-Buch \\\>\> auf Seite 251 \\
4 \> → \> vier Personen im Raum; \\\>\> vier Stunden lange Klausur \\\>\> (kontextabhängige Interpretation)
\end{tabbing}
\vfill\hfill%
\includegraphics[scale=0.35]{images/tafel.jpg}
}
\frame[t]{
\frametitle{Pragmatik}
\begin{block}{Pragmatik}
"`Effektiver"' Informationsgehalt einer Information
\end{block}
\vfill
Beispiele:
\small
\begin{enumerate}
\item Situation: Person will gerade das Haus verlassen \\
"`Es ist kalt."' → Informationsgewinn (warme Kleidung anziehen)
\item Situation: Person wartet frierend auf den Bus \\
"`Es ist kalt."' → kein Informationsgewinn
\end{enumerate}
% Bild: Person wird von Wasser vollgespritzt, wegen Bus
% Bild: frierende Frau in Minirock vor Bushaltestelle (mit Schnee) ^^
}
% XXX memetik irgendwo? :O ^^
\section[Modellierung]{Mathematische Modellierung}
\frame[t]{
\frametitle{Modellierung nach Shannon}
\begin{block}{Informationsgehalt eines Zeichens}
\[
I(x) := -\log_2 P(x); \qquad [1 \,\mathrm{bit}]
\]
\end{block}
\begin{block}{Entropie: Zu erwartender Informationsgehalt}
\[
E(I) := \sum\limits_{x \in \Sigma} P(x) \cdot I(x);
\]
\end{block}
\vspace*{-1em}
\begin{tabbing}
asdfff \= \kill
$x$: \> ein bestimmtes Zeichen \\
$\Sigma$: \> Menge aller vorkommenden \\ \> Zeichen \\
$P(x)$: \> Wahrscheinlichkeit \\ \> des Auftretens von $x$ \\
\end{tabbing}
\vspace*{-8.92em}\hfill
\includegraphics[scale=0.15]{images/log.png}
}
\frame[t]{
\frametitle{Eigenschaften der Entropie}
\begin{itemize}
\item Je seltener ein Zeichen, desto höher der Informationsgehalt
\item Spezialfall bei gleicher Häufigkeit aller Zeichen: \\
$\underbrace{\begin{array}{@{}lclclcll}
P(x_1) &=& P(x_2) &=& \cdots &=& P(x_n); \\
I(x_1) &=& I(x_2) &=& \cdots &=& I(x_n) = -\log_2 P(x_n);
\end{array}}_{E(I) = -\log_2 P(x_n);}$
Beispiel: \\
$\renewcommand{\arraystretch}{1.1}\begin{array}{@{}rcl}
M &=& abcdabcdabcd; \\
P(x_n) &=& \frac{1}{4}; \\
E(I) &=& -\log_2 \frac{1}{4} = 2 \,\mathrm{bit};
\end{array}$
\item Maximale Entropie bei $\left|\Sigma\right| = 2^n$, $n \in \mathbb{N}$: \\
$E(I) = -\log_2 \frac{1}{2^n} = n \,\mathrm{bit};$
\end{itemize}
}
\subsection[Nachrichten]{Beispiel: Nachricht}
\frame[t]{
\frametitle{Beispiel: Nachricht}
\begin{block}{Definitionen}
\[
\renewcommand{\arraystretch}{1.2}
\begin{array}{rcl}
I(x) &:=& -\log_2 P(x); \\
E(I) &:=& \sum\limits_{x \in \Sigma} P(x) \cdot I(x);
\end{array}
\]
\end{block}
$
\begin{array}{@{}rcl}
M &=& \left(i,n,f,o,r,m,a,t,i,o,n\right); \\
\Sigma &=& \left\{i, n, f, o, r, m, a, t\right\};
\end{array}
$
\bigskip
% 2O, 2I, 2N, F, R, M, A, T
$
\renewcommand{\arraystretch}{1.2}
\begin{array}{@{}rcl}
I(f) = I(r) = I(m) = I(a) = I(t) &=& -\log_2 \frac{1}{11} \approx 3{,}46\,\mathrm{bit}; \\
I(o) = I(i) = I(n) &=& -\log_2 \frac{2}{11} \approx 2{,}46 \,\mathrm{bit};
\end{array}
$
\bigskip
$
E(I) \approx 5 \cdot \frac{1}{11} \cdot 3{,}46 \,\mathrm{bit} + 3 \cdot \frac{2}{11} \cdot 2{,}46 \,\mathrm{bit} \approx 2{,}91 \,\mathrm{bit};
$
}
\subsection[Münzwurf]{Beispiel: LAPLACEscher Münzwurf}
\frame[t]{
\frametitle{Beispiel: LAPLACEscher Münzwurf}
\begin{block}{Definitionen}
\[
\renewcommand{\arraystretch}{1.2}
\begin{array}{rcl}
I(x) &:=& -\log_2 P(x); \\
E(I) &:=& \sum\limits_{x \in \Sigma} P(x) \cdot I(x);
\end{array}
\]
\end{block}
$\Sigma = \left\{ \text{Kopf}, \text{Zahl} \right\};$
\bigskip
$P(\text{Kopf}) = P(\text{Zahl}) = \frac{1}{2};$
\bigskip
$I(\text{Kopf}) = I(\text{Zahl}) = -\log_2 \frac{1}{2} = 1 \,\mathrm{bit};$
\bigskip
$
\renewcommand{\arraystretch}{1.3}
\begin{array}{@{}rclcl}
E(I) &=& \frac{1}{2}\, I(\text{Kopf}) &+& \frac{1}{2}\, I(\text{Zahl}) = \\
&=& \frac{1}{2} \cdot 1 \,\mathrm{bit} &+& \frac{1}{2} \cdot 1 \,\mathrm{bit} = 1 \,\mathrm{bit};
\end{array}
$
}
\subsection[Gezinkter Münzwurf]{Beispiel: Gezinkter Münzwurf}
\frame[t]{
\frametitle{Beispiel: Gezinkter Münzwurf}
\begin{block}{Definitionen}
\[
\renewcommand{\arraystretch}{1.2}
\begin{array}{rcl}
I(x) &:=& -\log_2 P(x); \\
E(I) &:=& \sum\limits_{x \in \Sigma} P(x) \cdot I(x);
\end{array}
\]
\end{block}
$\Sigma = \left\{ \text{Kopf}, \text{Zahl} \right\};$
\bigskip
$P(\text{Kopf}) = p = 1 - P(\text{Zahl});$
\bigskip
$
\begin{array}{@{}rcl}
I(\text{Kopf}) &=& -\log_2 p; \\
I(\text{Zahl}) &=& -\log_2 \left(1 - p\right);
\end{array}
$
\bigskip
$
\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}
$
}
\frame[plain]{\centering
\includegraphics[scale=0.5]{images/entropie-muenzwurf.png}
}
\subsection[Musik]{Beispiel: Musikstücke}
\frame[t]{
\frametitle{Beispiel: Entropie von Musikstücken}
\begin{itemize}
\item Mozart, Bach: Klassische Komponisten -- \\
Harmonienlehre, Akkorde, Intervalle etc.
\item Schönberg (20. Jhd.): Zwölftonmusik -- \\
Wiederholung bestimmter zwölf Töne auf verschiedene Arten
→ subjektiv wirr, chaotisch
\vfill
\item Entropie von Zwölftonstücken höher als bei Mozart und Bach!
\item Kritik am Verfahren: \\
(Viel zu) kleiner Korpus, \\
"`willkürliche"' Kodierung der Musik zu Buchstaben
\end{itemize}
\vfill\hfill%
\includegraphics[scale=0.5]{images/musiknoten.jpg}
}
\frame[plain]{\centering\includegraphics[scale=0.7]{images/Bach_Praeludium.png}}
\frame[plain]{\centering\includegraphics[scale=0.7]{images/Mozart_Minuet.png}}
\frame[plain]{\centering\includegraphics[scale=0.7]{images/Schoenberg.png}}
% XXX irgendwo Entropie = Maß fürs Chaos einbringen:
% mehr Entropie -> weniger einfach, nächstes Zeichen vorherzusagen -> mehr
% Überraschungseffekt -> subjektives Chaos
% entropie und bedeutung bei zufallsgeneratoren
% XXX irgendwo auch entropie von deutsch/franz./englisch? (Wikipedia-Test)
% --> anwendungen der entropie
\section[Shannon--Fano]{Shannon--Fano-Kodierung}
\subsection{Grundideen}
\frame[t]{
\frametitle{Shannon--Fano-Kodierung}
\begin{block}{Shannon--Fano-Kodierung}
Entropiekodierung ("`Kompressionsverfahren"')
\end{block}
%Grundidee: Möglichst hohe Entropie durch effiziente Darstellung
\begin{itemize}
\item
\begin{tabbing}
Darstellung \= \textsl{häufiger} \= Zeichen durch \= \textsl{kurze} \= Bitfolgen \kill
Darstellung \> \textsl{häufiger} \> Zeichen durch \> \textsl{kurze} \> Bitfolgen; \\
Darstellung \> \textsl{seltener} \> Zeichen durch \> \textsl{lange} \> Bitfolgen
\end{tabbing}
\item Eindeutigkeit der Bitfolgen ("`Präfixfreiheit"')
\end{itemize}
Problembeispiel:
$A \mapsto 10 \quad B \mapsto 01 \quad C \mapsto 0$ \bigskip
$\left.\begin{array}{@{}l}
ABC \mapsto 10010 \\
ACA \mapsto 10010
\end{array}\right\}$ nicht eindeutig
}
\subsection{Algorithmus}
\frame[t]{
\frametitle{Algorithmus}
\begin{enumerate}
\item Sortierung der Zeichen nach rel. Häufigkeit
\item Einteilung der Zeichen in zwei Gruppen, sodass Summen der
Häufigkeiten etwa gleich
\item So lange fortfahren, bis Entsprechung jedes Zeichens durch einen Pfad
im Baum
\end{enumerate}
}
\subsection{Beispiel}
\frame[t]{
\frametitle{Beispiel}
Text (39 Zeichen): \\
{\small ABADDCCAABABEDAECBDDDAAAABAAAABBCAECECE}
\medskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5
\end{tabular}
\vspace*{5mm}%
\includegraphics[scale=0.3]{images/baum.png} % ausprobieren? wie meinst? kompilieren und anschauen. nein, auf keinen fall, wer weiss, was da nicht alles kaputt gehen kann. try 'n error
% wollen wir das bild um 90° grad drehen (geht einfach) aber dann muss man halt den kopf neigen
% oder wir schneiden die folie aus
}
\frame[t]{
\frametitle{Beispiel}
\hspace*{-1cm}%
\begin{minipage}{1.1\textwidth}\begin{multicols}{2}
\scriptsize
\begin{itemize}
\item Original \\ ($117 \,\mathrm{bit}$; Entropie $\approx 0{,}82 \,\mathrm{bit}$): \\
{\tiny
00000100001101101001000000000
10000011000110001000100010110
11011000000000000001000000000
000001001010000100010100010100
}\bigskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5 \\\hline
Benötigte Bits & 3 & 3 & 3 & 3 & 3
\end{tabular}\bigskip
\begin{tabular}{@{}l|rr}
Bit & 0 & 1 \\\hline
Abs. Häufigkeit & 87 & 30
\end{tabular}\bigskip
$A \mapsto 000$ \\
$B \mapsto 001$ \\
$C \mapsto 010$ \\
$D \mapsto 011$ \\
$E \mapsto 100$
\columnbreak
\item Komprimiert \\ ($89 \,\mathrm{bit}$; Entropie $\approx 0{,}99 \,\mathrm{bit}$ (!!)): \\
{\tiny
1110110010010101111110
1110000001110000110001
0010011111111110111111
11101001110000100001000
}\bigskip
\begin{tabular}{@{}l|rrrrr}
Zeichen & A & B & C & D & E \\\hline
Abs. Häufigkeit & 15 & 7 & 6 & 6 & 5 \\\hline
Benötigte Bits & 2 & 2 & 2 & 3 & 3
\end{tabular}\bigskip
% 11101100100101011111101110000001110000110001001001111111111011111111101001110000100001000 (0.99 WOW! fast 1!!!) die entropie koennte doch 8 sein? nicht bei einem alphabet von nur zwei zeichen, dort ist die maximale entropie ld 2 = 1 optimal
% 40/89*-l(40/89)/l(2) + 49/89*-l(49/89)/l(2) =
% .99261088987494049154
\begin{tabular}{@{}l|rr}
Bit & 0 & 1 \\\hline
Abs. Häufigkeit & 40 & 49
\end{tabular}\bigskip
% 11 B 10 C 01 D 001 E 000
$A \mapsto 11$ \\
$B \mapsto 10$ \\
$C \mapsto 01$ \\
$D \mapsto 001$ \\
$E \mapsto 000$
\end{itemize}
\end{multicols}\end{minipage}
}
\section[Praxis]{Entropie in der Praxis}
\subsection{Anwendungen}
\frame[t]{
\frametitle{Anwendung des Entropiekonzepts}
\begin{itemize}
\item Maß für die untere Schranke verlustfreier Kompression
\item Maß für die Zufälligkeit von Information (Zufallsgeneratoren)
\item Maß für "`Chaos"' \\
(hohe Entropie $\hat{=}$ hohe Überraschung)
\item Charakteristika für Autoren \\
(Entropienvergleiche → Schlüsse auf Autoren)
\end{itemize}
}
\subsection{Nachteile}
\frame[t]{
\frametitle{Nachteile}
\begin{itemize}
\item Keine Beachtung der Reihenfolge: \\
Entropien von \\
$00001111$ und \\
$01101000$ gleich! -- \\
(mögliche) Lösung: Algorithmische Information -- \\
Länge des kürzesten Beschreibung in einer bestimmten Sprache
\item Analyse nur auf syntaktischer Ebene -- \\
(mögliche) Lösung: Memetik: \\
Übertragung der Prinzipien der Evolutionstheorien auf Gedanken \\
(→ Mutation, Viren)
\end{itemize}
}
\appendix
\section{Bildnachweis}
\frame[t]{\frametitle{Bildnachweis} % fuer die online-version
\scriptsize
\begin{itemize}
\item \url{http://www.thewirelessreport.com/media/2006/06/library-books.jpg}
\item \url{http://www.borismatas.de/Schichten.jpg}
\item \url{http://www.library.upenn.edu/exhibits/rbm/music/2-6a.jpg}
\item \url{http://www.zappelfillip.de/wordpress/postimage/jahr2006/braillegoogle.gif}
\item \url{http://www.catch-artists.de/telefon.jpg}
\item \url{http://www.pixelplexus.co.za/blog/pics/MIA01.jpg}
\item \url{http://de.wikipedia.org/wiki/Bild:ShannonCodeAlg.png}
\end{itemize}
}
\end{document}
Download