Overview

Das vorliegende Buch entha, lt den Tei11 meiner Vorlesung ""Algorithmische In formationstheorie"" im WS 1996/97. Dieser Teil beinhaltet eine Einfiihrung in die statistische Informationstheorie, die von Shannon 1948 begriindet wurde. Ich gebe dieses Buch heraus, da die Vorlesung auch den Anwendungen dieser Theorie auf algorithmische Probleme nachgeht. DaB die Entropie einer Quelle als untere Schranke fiir die Laufzeit von Suchprogrammen verwendet werden kann, ist seit 20 Jahren bekannt, ohne daB aber die Konzepte der Informati- 0Ilstheorie eine systematische Anwendung in dies em Bereich erfahren haben. So wurden Markovquellen im Zusammenhang mit effizienten Suchverfahren bei geordneten Schliisseln erstmals 1992 yom Autor diskutiert. Die Vorlesung geht auf die Frage der Gewinnung unterer Schranken fiir die mittlere Laufzeit von Algorithmen ein und versucht die Kodierungstheoreme zur Konstruktion effizienter Algorithmen zu nutzen. Frau Susanne Balzert hat das Manuskript in J5.'TEXgeschrieben. Herr Frank Schulz, der auch die Ubungen zu der Vorlesung betreute, und Herr Hein Rohrig haben das Manuskript gelesen und durch kritische Kommentare zu Verbesse rungen beigetragen. Ihnen und meinen kritischen Horern danke ich dafiir herz lich. Herrn Frank Schulz bin ich dariiber hinaus auch Dank schuldig fiir die Endredaktion des zuniichst nur als technischer Bericht vorliegenden Textes.""

Full Product Details

Author:   Günther Hotz
Publisher:   Springer Fachmedien Wiesbaden
Imprint:   Vieweg+Teubner Verlag
Edition:   1997 ed.
Volume:   23
Weight:   0.271kg
ISBN:  

9783815423103

ISBN 10:   3815423104
Pages:   143
Publication Date:   01 January 1997
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.
Language:   German

Table of Contents

1 Statistische Informationstheorie im Falle diskreter ungestoerter Kanale.- 1.1 Definition der Entropie einer Quelle.- 1.2 Der Kodierungssatz im stoerungsfreien Fall.- 1.3 Ordnungserhaltende Kodierungen.- 1.4 Anwendungen des Kodierungstheorems.- 1.4.1 Suchprobleme.- 1.4.2 Unvollstandige Suchbaume bei gedachtnislosen Quellen.- 1.4.3 Sortieren bei gedachtnisloser Quelle.- 1.4.4 Suchen und Sortieren in Linearzeit bei Quellen (A,p) mit unbekanntem p.- 1.4.5 Abschatzung der Laufzeit bei anderen Suchverfahren.- 1.4.6 Die Entropie als untere Schranke fur die Groesse von Schaltkreisen.- 1.4.7 Die Entropie als untere Schranke fur Sortierverfahren.- 1.4.8 Die Entropie als untere Schranke fur beliebige Berechnungen.- 1.4.9 Anwendungen in der Kryptographie.- 1.5 Kritische Wurdigung des Kodierungstheorems.- 2 Informationstheorie bei Markovketten.- 2.1 Quellen mit Gedachtnis.- 2.2 Definition von Markovketten.- 2.3 Entropie von Markovprozessen.- 2.4 Das Kodierungstheorem fur Markovprozesse.- 2.5 Suchgraphen.- 2.6 ?-Zerlegungen von Markovquellen.- 2.7 ?-UEberdeckungen von Markovprozessen.- 2.8 Sortieren und andere Anwendungen.- 2.8.1 Sortieren.- 2.8.2 Andere Anwendungen.- 3 Die Kapazitat von diskreten Kanalen.- 3.1 Gestoerte diskrete Kanale ohne Gedachtnis.- 3.1.1 Definitionen.- 3.1.2 Kanalerweiterungen und Entscheidungsschemata.- 3.2 Der Satz von Fano.- 3.3 Das Kodierungstheorem fur Kanale ohne Gedachtnis.- Ausblick.- Historische Bemerkungen.- Aufgaben.- zu Kapitel 1.- zu Kapitel 2.- zu Kapitel 3.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions