SciDok

Eingang zum Volltext in SciDok

Hinweis zum Urheberrecht

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-3555
URL: http://scidok.sulb.uni-saarland.de/volltexte/2005/355/


Algorithmische Informationstheorie Teil 1 : Vorlesung an der Universität des Saarlandes WS 1996/97

Hotz, Guenter

pdf-Format:
Dokument 1.pdf (717 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Technische Informatik
Freie Schlagwörter (Deutsch): Algorithmische Informationstheorie , effiziente Algorithmen
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Bandnummer: 1997/01
Sprache: Deutsch
Erstellungsjahr: 1997
Publikationsdatum: 23.06.2005
Kurzfassung auf Deutsch: Das vorliegende Skript enthält den Teil 1 meiner Vorlesung "Algorithmische
Informationstheorie" im WS 1996/97. Dieser Teil beinhaltet eine Einführung
in die statistische Informationstheorie, die von Shannon 1948 begründet wurde.
Ich gebe dieses Skript 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 die versucht die Kodierungstheoreme
zur Konstruktion effizienter Algorithmen zu nutzen.

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English