Buch, Deutsch, Band 23, 143 Seiten, Paperback, Format (B × H): 162 mm x 235 mm, Gewicht: 247 g
Reihe: Teubner Texte zur Informatik
Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen
Buch, Deutsch, Band 23, 143 Seiten, Paperback, Format (B × H): 162 mm x 235 mm, Gewicht: 247 g
Reihe: Teubner Texte zur Informatik
ISBN: 978-3-8154-2310-3
Verlag: Vieweg+Teubner Verlag
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.
Zielgruppe
Upper undergraduate
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Daten / Datenbanken Informationstheorie, Kodierungstheorie
- Interdisziplinäres Wissenschaften Wissenschaften: Forschung und Information Informationstheorie, Kodierungstheorie
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
Weitere Infos & Material
1 Statistische Informationstheorie im Falle diskreter ungestörter Kanäle.- 1.1 Definition der Entropie einer Quelle.- 1.2 Der Kodierungssatz im störungsfreien Fall.- 1.3 Ordnungserhaltende Kodierungen.- 1.4 Anwendungen des Kodierungstheorems.- 1.5 Kritische Würdigung des Kodierungstheorems.- 2 Informationstheorie bei Markovketten.- 2.1 Quellen mit Gedächtnis.- 2.2 Definition von Markovketten.- 2.3 Entropie von Markovprozessen.- 2.4 Das Kodierungstheorem für Markovprozesse.- 2.5 Suchgraphen.- 2.6 ?-Zerlegungen von Markovquellen.- 2.7 ?-Überdeckungen von Markovprozessen.- 2.8 Sortieren und andere Anwendungen.- 3 Die Kapazität von diskreten Kanälen.- 3.1 Gestörte diskrete Kanäle ohne Gedächtnis.- 3.2 Der Satz von Fano.- 3.3 Das Kodierungstheorem für Kanäle ohne Gedächtnis.- Ausblick.- Historische Bemerkungen.- Aufgaben.- zu Kapitel 1.- zu Kapitel 2.- zu Kapitel 3.
