Einführung in Formale Sprachen, Berechenbarkeit, Informations- Und Lerntheorie

ISBN-13: 9783486274332 / Niemiecki / Miękka / 2006 / 268 str.

Norbert Blum

Opis

Die Theoretische Informatik wird an deutschen Universitaten ublicherweise in zwei Blocken angeboten. Der Autor tragt diesem Umstand Rechnung und bietet in zwei Banden eine systematische und umfassende Einfuhrung in dieses Themengebiet an. Der vorliegende 2. Band behandelt gut verstandlich und anwendungsbezogen die Theorie "einfacher" Automaten und den mit diesen eng verknupften formalen Sprachen, die theoretische Berechenbarkeit von Funktionen, den Begriff der praktischen Berechenbarkeit, die Theorie der NP-Vollstandigkeit wie auch grundlegende Themen der Kryptographie. Zu den groten Herausforderungen unserer Zeit gehort die Erforschung von Information in Bezug auf ihre Generierung, ihre Extraktion und ihre Behandlung. Daher ist der zweite Teil des Buches einer Einfuhrung in die Informations- und Lerntheorie gewidmet. Besprochen wird sowohl die klassische als auch die algorithmische Informationstheorie, die Theorie der Zufallsfolgen und die Inferenzsysteme. Das Buch enthalt zahlreiche Ubungsaufgaben verschiedener Schwierigkeitsgrade, die bestens geeignet sind, um den Stoff zu vertiefen. Ausfuhrliche Literaturhinweise runden das Buch ab.

"Teil 1-3 sind super, weil in ihnen der tyische der Theorie entrümpelt wird und Herr Blum sich auf Themen konzentriert die jeder Student parat haben sollte." Prof. Dr. H. Vollmer, Universität Hannover "Sowohl klassischer Stoff, wie Automaten, formale Sprachen, Berechenbarkeit, als auch neues, wie Lerntheorie und Seltenes, wie Kolmgorov-Komplexität etc. werden erstklaaig behandelt. Super, erste Sahne!" Peter Widmayer, ETH Zürich "

Recenzje

"Teil 1-3 sind super, weil in ihnen der tyische der Theorie entrümpelt wird und Herr Blum sich auf Themen konzentriert die jeder Student parat haben sollte." Prof. Dr. H. Vollmer, Universität Hannover "Sowohl klassischer Stoff, wie Automaten, formale Sprachen, Berechenbarkeit, als auch neues, wie Lerntheorie und Seltenes, wie Kolmgorov-Komplexität etc. werden erstklaaig behandelt. Super, erste Sahne!" Peter Widmayer, ETH Zürich "

Spis treści

reguläre Menge, regulärer Ausdruck, endlicher Automat, kontextfreie Grammatik, Kellerautomat, Normalformen und Eigenschaften. rekursive Funktionen, Turingmaschine, Church'sche These, Entscheidbarkeit, Aufzählbarkeit, Random Access Maschine, P, NP, NP-vollständige Probleme, Public-Key Kryptosysteme und Zero-Knowledge Beweise. Entropie, Huffman-Kode, Kolmogorov-Komplexität, Zufallsfolge, induktive Inferenzsysteme, MDL, MML, Ähnlichkeit, Lernen von Konzepten, PAC-Lernbarkeit und Samplekomplexität.