Algorithmische Informationstheorie: Statistische by Günther Hotz

By Günther Hotz

Dieses Buch beinhaltet eine Einführung in die statistische Informationstheorie, die von Shannon 1948 begründet wurde. Ich gebe dieses Buch heraus, da die Vorlesung auch den Anwendungen dieser Theorie auf algorithmische Probleme nachgeht. Daß die Entropie einer Quelle als untere Schranke für die Laufzeit von Suchprogrammen verwendet werden kann, ist seit 20 Jahren bekannt, ohne daß aber die Konzepte der Informationstheorie eine systematische Anwendung in diesem Bereich erfahren haben. So wurden Markovquellen im Zusammenhang mit effizienten Suchverfahren bei geordneten Schlüsseln erstmals 1992 vom Autor diskutiert. Die Vorlesung geht auf die Frage der Gewinnung unterer Schranken für die mittlere Laufzeit von Algorithmen ein und versucht die Kodierungstheoreme zur Konstruktion effizienter Algorithmen zu nutzen. Günter Hotz

Show description

Read or Download Algorithmische Informationstheorie: Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen PDF

Best german_4 books

Bodenmechanik der Stützbauwerke, Straßen und Flugpisten: Anwendungsbeispiele und Aufgaben

Wie die Erfahrung immer wieder zeigt, fallt es dem jungen Ingenieur am Anfang seiner beruflimen Laufbahn smwer, das erworbene Smulwissen zur Losung von praktismen, temnismen Aufgaben anzuwenden. Aum der erfahrene Ingenieur steht in der Praxis oft vor dem challenge, Fragen beantwor ten zu mussen, die nimt in den Rahmen seiner taglimen Routinearbeit fallen.

Soziale Kosten des Energieverbrauchs: Externe Effekte des Elektrizitätsverbrauchs in der Bundesrepublik Deutschland

In diesem Buch werden in systematischer Weise verschiedene Arten von externen Kosten und Nutzen konkurrierender Technologien zur Elektrizit? tserzeugung verglichen. Behandelt werden verschiedene Umwelteffekte, Besch? ftigungs- und Produktionseffekte, die Ausbeutung ersch? pfbarer Ressourcen wie auch die unterschiedlichen Arten ?

Additional resources for Algorithmische Informationstheorie: Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen

Sample text

3 Ordnungserhaltende Kodierungen 1st (5, <) eine geordnete Menge, dann kann man diese Ordnung auf S* ubertragen, indem man die Elemente von S* lexikographisch anordnet. Die lexikographisehe Ordnung wird dureh die drei folgenden Axiome definiert: Fur u, v, w, w' E S* gilt • c < u fUr u i= c, • u

Nun sieht man wie folgt, daB die Folge begin al, ... , aT zusammen mit der sortierten Folge auch die Eingabefolge eindeutig bestimmt: Der Stand der Indexregister list unabhiingig von der speziellen Eingabe zu jedem Zeitpunkt derc Berechnung eindeutig bestimmt. Somit sind alle Befehle zu jedem Zeitpunkt eindeutig bestimmt, wenn wir wissen, welcher Befehl aktuell ist. Da uns die Programmverzweigungen alle durch (Y vorgegeben sind, konnen wir den zu jedem Zeitpunkt aktuellen Befehl eindeutig bestimmen.

Es ist klar, daB diese Kodierungen fiir Quellen (A, p) die Ungleichung H(A) S E(A, c) logm erfiillen. Es ist aber nicht sicher, daB auch die obere Schranke E(A, c) s IH(A) +1 ogm durch prafixfreie ordnungserhaltende Kodierungen erfiillt werden kann. Wir geben ein Beispiel an, das zeigt, daB sich aus der Giiltigkeit der Kraft'schen Ungleichung eine solche Kodierung nicht ableiten laBt. 4= {al,a2,a3}, al < a2 < a3. Weiter sei i(al) = 3,i(a2) 1, i(a3) = 3 vorgegeben. h. die Kraft'sche Ungleichung ist erfiillt, so daB es also einen prafixfreien binaren Kode emit lc(al)1 = 3, Ic(a2)1 = 1 und lc(a3) I = 3 gibt.

Download PDF sample

Rated 4.12 of 5 – based on 48 votes