Willkommen, schön sind Sie da!
Logo Ex Libris

Algorithmische Informationstheorie

  • Kartonierter Einband
  • 143 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
Die statistische Informationstheorie besitzt wichtige Anwendungen in der Abschätzung der mittleren Laufzeit von Algorithmen, deren... Weiterlesen
20%
48.90 CHF 39.10
Auslieferung erfolgt in der Regel innert 2 bis 3 Wochen.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

Die statistische Informationstheorie besitzt wichtige Anwendungen in der Abschätzung der mittleren Laufzeit von Algorithmen, deren Probleme online erzeugt werden. Es werden die grundlegenden Kodierungstheoreme für Quellen ohne Gedächtnis und Quellen mit kurzem Gedächtnis bei ungestörten Kanälen und schließlich bei gestörten Kanälen ohne Gedächtnis bewiesen.

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.

Klappentext
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

Inhalt
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.4.1 Suchprobleme.- 1.4.2 Unvollständige Suchbäume bei gedächtnislosen Quellen.- 1.4.3 Sortieren bei gedächtnisloser Quelle.- 1.4.4 Suchen und Sortieren in Linearzeit bei Quellen (A,p) mit unbekanntem p.- 1.4.5 Abschätzung der Laufzeit bei anderen Suchverfahren.- 1.4.6 Die Entropie als untere Schranke für die Größe von Schaltkreisen.- 1.4.7 Die Entropie als untere Schranke für Sortierverfahren.- 1.4.8 Die Entropie als untere Schranke für beliebige Berechnungen.- 1.4.9 Anwendungen in der Kryptographie.- 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.- 2.8.1 Sortieren.- 2.8.2 Andere Anwendungen.- 3 Die Kapazität von diskreten Kanälen.- 3.1 Gestörte diskrete Kanäle ohne Gedächtnis.- 3.1.1 Definitionen.- 3.1.2 Kanalerweiterungen und Entscheidungsschemata.- 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.

Produktinformationen

Titel: Algorithmische Informationstheorie
Untertitel: Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen
Autor:
EAN: 9783815423103
ISBN: 978-3-8154-2310-3
Format: Kartonierter Einband
Herausgeber: Vieweg + Teubner
Genre: Informatik
Anzahl Seiten: 143
Gewicht: 265g
Größe: H235mm x B161mm x T9mm
Jahr: 1997
Auflage: 1997

Weitere Produkte aus der Reihe "Teubner Texte zur Informatik"