Warenkorb
€ 0,00 0 Buch dabei,
portofrei
Algorithmische Informationstheorie als Buch
PORTO-
FREI

Algorithmische Informationstheorie

Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen. 'Teubner Texte zur…
Buch (kartoniert)
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 … weiterlesen
Buch

34,95*

inkl. MwSt.
Portofrei
Lieferbar innerhalb von zwei bis drei Werktagen
Algorithmische Informationstheorie als Buch

Produktdetails

Titel: Algorithmische Informationstheorie
Autor/en: Günther Hotz

ISBN: 3815423104
EAN: 9783815423103
Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen.
'Teubner Texte zur Informatik'.
Auflage 1997.
Book.
Vieweg+Teubner Verlag

1. Januar 1997 - kartoniert - 148 Seiten

Beschreibung

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.

Inhaltsverzeichnis

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.
Servicehotline
089 - 70 80 99 47

Mo. - Fr. 8.00 - 20.00 Uhr
Sa. 10.00 - 20.00 Uhr
Filialhotline
089 - 30 75 75 75

Mo. - Sa. 9.00 - 20.00 Uhr
Bleiben Sie in Kontakt:
Sicher & bequem bezahlen:
akzeptierte Zahlungsarten: Überweisung, offene Rechnung,
Visa, Master Card, American Express, Paypal
Zustellung durch:
* Alle Preise verstehen sich inkl. der gesetzlichen MwSt. Informationen über den Versand und anfallende Versandkosten finden Sie hier.
** Deutschsprachige eBooks und Bücher dürfen aufgrund der in Deutschland geltenden Buchpreisbindung und/oder Vorgaben von Verlagen nicht rabattiert werden. Soweit von uns deutschsprachige eBooks und Bücher günstiger angezeigt werden, wurde bei diesen kürzlich von den Verlagen der Preis gesenkt oder die Buchpreisbindung wurde für diese Titel inzwischen aufgehoben. Angaben zu Preisnachlässen beziehen sich auf den dargestellten Vergleichspreis.