Download Algorithmische Informationstheorie: Statistische by Günther Hotz PDF

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

Similar german_4 books

Das Netzwerkunternehmen: Strategien und Prozesse zur Steigerung der Wettbewerbsfähigkeit in der „Networked economy“

Die Vielzahl scheinbar neuer betriebswirtschaftlicher Konzepte rund um das e-Business steigert sich schon zur "e-Manie". Anders dieses Buch: Das hier pr? sentierte Modell des Netzwerkunternehmens integriert die vielf? ltigen Formen der ? berbetrieblichen Zusammenarbeit wie offer Chain administration, shopper courting administration, digital trade, disbursed Engineering in einem einfach handhabbaren Modell, das erstmals die Ableitung von gesamtheitlichen e-Business-Strategien zul?

Aktive Sterne: Laboratorien der solaren Astrophysik

Die Sonne ist ein ziemlich durchschnittlicher Stern, der sich vor allem durch seine geringe Entfernung zur Erde auszeichnet. Bei näherer Betrachtung entpuppt sich die Sonnenoberfläche jedoch als wahrer "Hexenkessel" mit Magnetfeldern aller artwork, Sonnenflecken, Plasmaeruptionen und plötzlichen Explosionen, die alle einen fundamentalen Einfluß auf unseren Planeten haben, einen Einfluß, den wir erst mit modernster Astronomie messen und verstehen gelernt haben.

Thermosbau: Konstruktionsgrundlagen und Anwendungen

Dieser Buchtitel ist Teil des Digitalisierungsprojekts Springer ebook documents 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

Example text

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. 3 beschreibt einen solchen Kode. 3: Nicht ordnungserhaltender Kode 34 1. Statistiscbe Informationstbeorie Diese Kodierung ist aber nicht ordnungserhaltend, da hier ist. Man sieht leicht, daB es keine ordnungserhaltende prafixfreie Kodierung gibt, die die Langenbedingung erfullt: Wir konnen ohne Beschrankung der Abbildung c(al) = 000 wahlen. c(a2)! = 1 folgt als einzige Moglichkeit c( a2) = 1.

Die einfachste Weise, diesen Storungen entgegenzuwirken, besteht in der Verabredung eines Protokolles fUr den Nachrichtenaustausch, der die Bestatigung empfangener Nachrichten und die Wiederholung gestorter Nachrichten vorsieht. 1 Quellen mit Gedachtnis Wir haben in Kapitell die grundlegenden Definitionen iiber die Entropie von QuelIen, ihre Kodierung und verschiedene Perspektiven ihrer Anwendung behandelt, und zwar alles unter der Annahme, daB die Quellen gedachtnislos sind. 1m letzten Paragraphen von Kapitell haben wir gezeigt, daB diese Annahme einschrankend ist.

Statistische Informationstheorie In diesem Fall bezeiehnen wir r als Multiplizitiitenjunktion von b und sehreiben r = l1(b). Wir set zen A~t) = {b E Atll1(b) = r}. Offensiehtlieh kodiert ( j = begin al, ... , daB die Signaturen ( j einen Kode fur A~t) bei festem b bilden. Nun gilt Da die Laufzeit des Programmes nieht von a, sondern nur von (t, n) abhiingt, genugt es, die Laufzeit fur den ungunstigsten Fall von unten abzusehiitzen. Dazu betraehten wir Pr : A~t) -+ [0,1] mit Pr(a) = p(a) p(A~t)) und bezeiehnen die zugehorige Entropie dureh H(A~t)).

Download PDF sample

Rated 4.92 of 5 – based on 15 votes