Read e-book online Algorithmische Informationstheorie: Statistische PDF

By Günther Hotz

ISBN-10: 3322810364

ISBN-13: 9783322810366

ISBN-10: 3815423104

ISBN-13: 9783815423103

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

Similar german_4 books

Download PDF by Max Bollwage: Typografie kompakt: Vom richtigen Umgang mit Schrift am

"Learning by means of doing", klappt das wirklich immer? Zumindest für die professionelle Textgestaltung am Bildschirm sind ein paar Grundkenntnisse der Typografie unerlässlich. Dieses Buch vermittelt typografisches Basiswissen auf knappe und anschauliche Weise. Es bietet Hilfe für alle, die am laptop Texte bearbeiten, Internetseiten entwerfen und Drucksachen gestalten wollen.

Ueber die Einwirkung des Ziehprozesses auf die wichtigsten - download pdf or read online

Dieser Buchtitel ist Teil des Digitalisierungsprojekts Springer e-book files 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.

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

Sample text

T Wir zeigen zunachst, daB es in My) hinsichtlich der Ordnung keine Lucken gibt. Der Beweis erfolgt durch Induktion. Wir zeigen also, daB aus u E My) und v E Sk - My) folgt, daB u < v gilt. 36 1. Statistiscbe Informationstbeorie Induktionsanfang: Fur j = 1 haben wir u = Prafix(c(ad,i z)' w. Fur v = Priifix( v, iz) gilt offensichtlich Priifix(c(ad, iz) < woraus die Behauptung fur j v, = 1 folgt. Induktionsschritt: Sei die Behauptung fur die Behauptung fUr My) bewiesen. Es genugt dann, zu zeigen.

Die SchluBsequenz wird also stets als solche erkennbar sein. Wir erhalten damit aus al, .. ,at keinen Anhalt iiber C, auBer daB C Folgen enthalt, deren Lange kleiner als t ist. Ein Gegner kann damit fiir einen Angriff auf den Kode nur statistische Tests verwenden, urn Abweichungen von al, ... , at von zufalligen Mustern zu beurteilen. h. wie nahe die mittlere Kodelange pro Zeichen an H(A) herankommt. In realistischen Fallen konnen wir nicht AT fUr groBere r nahezu optimal kodieren; selbst A2 ist zu groB, wenn A ein akzeptabler deutscher Wort schatz ist.

Mit unserer Konvention uber die Prafixnotation umfaBt die zweite Bedingung auch die erste. Wir setzen Ml := Prafix(c(al),i 2 )· S* und wahlen also c(a2) = min{u E ((S* - M 1 ) n Si2 )lu, S* n Ml = 0} Aufgrund der gleichen Uberlegung wie in Schritt 1 sehen wir, daB diese Wahl ohne Beschrankung der Allgemeinheit moglich ist. Schritt j + 1: Sei j < n und seien c(al),"" c(aj) bereits bestimmt und M j := M j - 1 U Prafix(c(aj), ij+d . S* sei als fUr die Wahl von c(aj+l) verbotene Region erkannt. Wir wahlen also ohne Beschrankung der Allgemeinheit c(aj+l) = min{u E ((S* - Mj ) n SiJ+1)lu.

Download PDF sample

Algorithmische Informationstheorie: Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen by Günther Hotz


by Christopher
4.3

Rated 4.55 of 5 – based on 31 votes