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

Best german_4 books

Die Praxis der induktiven Warmbehandlung

In der maschinenbauenden Industrie, vor allem im Kraftfahrzeugbau, in der Buromaschinenfertigung, im Werkzeugmaschinenbau usw. , zwin gen die Forderungen zur Leistungssteigerung, Rationalisierung und zur einfacheren Handhabung des Fertigungsablaufes, zum Teil grundlegend neue Methoden einzusetzen. So hat guy auch auf dem Gebiete der Warmbehandlung nach neuen Arbeitsverfahren, die sich in eine FlieB fertigung einfiigen lassen, gesucht.

Auswirkung rasch verlaufender Kräfte auf ausladende Pressengestelle

1. zero Natwendigkeit einer dynamischen Auffassungsweise bei der Berechnung van Pressengestellen Die aus betriebswirtschaftlichen Grunden angestrebte Verkurzung der Fertigungs zeiten fuhrt, wie bei den meisten \Verkzeugmaschinen so auch bei den Pressen zum Bau schnellaufender Maschinen. Die gleichzeitige Entwicklung von selbsttatigen Zufuhrvorrichtungen und schnell gesteuerten Kupplungen ermoglichen ho he Drehzahlen; es werden zur Zeit Ex zenterpressen mit Nennhubzahlen von 250-280 je min sowie selbsttatige Pressen mit Unterantrieb und Zufuhrvorrichtungen fur Bancler gebaut, die six hundred Hube je min machen.

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

Example text

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. Wie soll man also diese Konzepte dann verwenden? Zur Beantwortung dieser Frage betrachten wir zunachst das Schema der skizzierten Nachrichteniibertragung etwas genauer. Wir nehmen an, daB A ein Teil des deutschen Wortschatzes ist in allen seinen Abwandlungen, die er im Satzbau erfahrt.

Nun erfordert das Rotieren zur Wurzel die gleiche Zeit wie das Suchen, so dafi wir als obere Schranke fur die mittlere Suchzeit (2 + 4ln(2) . H(A)) . t erhalten. Rechnen wir das mit der Berechnung von ( verbundene Zahlen mit ein und das Abwartszahlen bei der Ausgabe der sortierten Eingabefolge, dann erhalten wir fUr mittlere LauJzeit Sort(A,p) des SortierverJahrens bei gediichtnisloser QueUe (A, p) mit unbekanntem p Sort(A,p) ~ (4 + 4ln(2) . H(A)) . t + 4m . Der Summand 4m ergibt sich aus dem Traversieren des Suchbaumes, wenn m die Anzahl der Blatter dieses Baumes ist.

H. ein beliebiges Fanout, dann konnen wir die Schaltkreise durch Graphen beschreiben, deren Knoten die Operationen aus {V, A, ---,} sind. Die Kanten des Graphen stellen nun die Variablen dar und somit zusammen mit den drei Operationen und den Klammern das Alphabet S dar. Gibt es N Kanten, dann erhalten wir also im Falle der Gleichverteilung 2k _ log(N + 5) :::; E(A, c), 1. Statistiscbe Informationstbeorie 50 wenn 2; die Kodierung in optimale Schaltkreise beschreibt. Nun kann man jeden Schaltkreis f : JRk ----+ JR, wie man leicht sieht, durch einen Graphen mit N = 2 .

Download PDF sample

Rated 4.07 of 5 – based on 49 votes