Please use this identifier to cite or link to this item:
doi:10.22028/D291-25802
Title: | Algorithmische Informationstheorie Teil 1 : Vorlesung an der Universität des Saarlandes WS 1996/97 |
Author(s): | Hotz, Günter |
Language: | German |
Year of Publication: | 1997 |
SWD key words: | Technische Informatik |
Free key words: | Algorithmische Informationstheorie effiziente Algorithmen |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
Abstract: | 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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-3555 hdl:20.500.11880/25858 http://dx.doi.org/10.22028/D291-25802 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 1997/01 |
Date of registration: | 23-Jun-2005 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
fb14-97-01.pdf | 717,12 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.