Download e-book for iPad: 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 Online or Download Algorithmische Informationstheorie: Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen PDF

Best german_4 books

Kritische Untersuchung der Entwickelung der by Friedrich Janssen PDF

Dieser Buchtitel ist Teil des Digitalisierungsprojekts Springer publication data mit Publikationen, die seit den Anfängen des Verlags von 1842 erschienen sind. Der Verlag stellt mit diesem Archiv Quellen für die historische wie auch die disziplingeschichtliche Forschung zur Verfügung, die jeweils im historischen Kontext betrachtet werden müssen.

Der Bauratgeber: Handbuch für das gesamte Baugewerbe und by Leopold Herzka PDF

Dieser Buchtitel ist Teil des Digitalisierungsprojekts Springer ebook information mit Publikationen, die seit den Anfängen des Verlags von 1842 erschienen sind. Der Verlag stellt mit diesem Archiv Quellen für die historische wie auch die disziplingeschichtliche Forschung zur Verfügung, die jeweils im historischen Kontext betrachtet werden müssen.

New PDF release: Stahlbeton: Einführung in die Berechnung nach DIN 1045 2:

Prof. Dipl. -Ing. Otfrid Homann - Fachhochschule Nordostniedersachsen

Download e-book for iPad: Dynamische Systeme in der Ökologie: Mathematische Modelle by Wolfgang Metzler, Dieter Gockert

". .. Das vorliegende Buch ist leicht lesbar und anschaulich geschrieben und kann daher mit gutem Gewissen sowohl interessierten Mathematikern als auch Biologen empfohlen werden. " ok. Karigl. Internationale Mathematische Nachrichten, Wien

Extra info for Algorithmische Informationstheorie: Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen

Example text

1 -log(l - C:I· 221 - 1 )) 1=1 (2l _ 1) . 21- 1 221 . 1 (l-log(l- 2c:D) 1=1 C:I = wenn wIr c:~. 2- 21 setzen. Nehmen wir weiter an 1c:;1 :::; 1, dann erhalten wir f 1c:~12~I:l1 (2 -log(2 - c:D) :::; 3. 1=1 Also haben wir H(A) S 6. Das bleibt auch richtig, wenn wir aIle Mengen D" mit lal > k zu einer Menge iJ~ zusammenfassen. Somit erhalten wir die untere Schranke t . H(A) fur die mittlere Suchzeit, wenn un sere Quelle Folgen der Lange t produziert t· H(A) :::; 6· t. Nun stellt sich die Frage, ob man zu gegebenem p die Mengen D" so wahlen kann, wie wir es voraussetzen und ob man diese Menge D" dann auch hinreichend schnell berechnen kann.

Dieser Kode sei mit c' bezeichnet. Wir haben also aufgrund von (*) auf Seite 32 E(A,c') ~ H(A) -log(l + logn) + 1 Gehen wir von A zu AT uber und ist CT eine injektive Abbildung auf AT, dann erhalten wir E(AT, cT) ~ r . H(A) -log(l + rlog n). Wegen folgt E(A,c') ~ H(A) _ log(l + rlogn) r Rieraus folgt fur die mittlere Suchzeit, wenn wir r E(A, c') ~ ~ 00 gehen lassen, H(A) fur alle moglichen Ablagen c' des Lexikons in unserem baumartig organisierten Speicher. Insbesondere spielt die Anordnung '<' von A hierbei keine Rolle.

K. c( al) = Oil. c(al)! c'(al)! = i 1 stets c(at) :::; c'(at). 1st c(at) i- c'(at), dann erhalten wir also wieder einen Kode, der unsere Forderungen erfullt, wenn wir c' so abandern, daB c'(al) = Oil gilt; denn aus c(at} < c'(at) < c'(ai) fUr i > 1 folgt, daB kein c' (ai), i = 2, ... , n Prafix von c( al) ist; ware umgekehrt c(at) Prafix von c'(ai), i > 1, dann hatten wir c'(al) < c(at) . U = c'(ai), woraus c' (at) < c( at) folgen wurde, was nicht sein kann. Wir durfen also ohne Einschrankung der Allgemeinheit annehmen, daB c(al) = Oil ist.

Download PDF sample

Rated 4.43 of 5 – based on 27 votes