Berechenbarkeit, Komplexität und Algorithmische Informationstheorie

Eine mathematisch präzise Einführung in die Theoretische Informatik
2., überarbeitete und erweitert Auflage 2027
ISBN: 978-3-662-74790-2
Verlag: Springer

Buch, Deutsch, Format (B × H): 155 mm x 235 mm

Dieses Lehrbuch behandelt zunächst zentrale Themen der klassischen Theoretischen Informatik und führt darauf aufbauend in die Grundlagen der Algorithmischen Informationstheorie ein. Behandelt werden insbesondere die Fragestellungen:

• Was sind Algorithmen? Was können sie und wo liegen ihre Grenzen?
• Welche Aussagen sind über die Laufzeit möglich? Welches sind die wichtigsten Komplexitätsklassen? Was bedeuten diese für Theorie und Praxis?
• Wie kann die strukturelle Komplexität von Daten beschrieben und analysiert werden?

Die formalen Grundlagen werden mathematisch präzise dargestellt. Ausführliche Beweise, detaillierte Erklärungen und Querverweise erleichtern das Verständnis. Jedes Kapitel beginnt mit einer kurzen Motivation des folgenden Inhalts. Viele Beispiele und Aufgaben dienen der Festigung des Wissens und dem Einüben der dargestellten Methoden und Verfahren. Zu fast allen Aufgaben sind im Text oder am Ende des Buches Musterlösungen aufgeführt. Zusammenfassungen am Kapitelende bieten darüber hinaus Gelegenheit, den Stoff zu reflektieren.

Das Buch richtet sich an Studierende in Mathematik und Informatik an Universitäten und Hochschulen sowie an alle, die sich im Selbststudium weiterbilden möchten.

Für die vorliegende 2. Auflage wurde insbesondere das Kapitel zur Berechenbarkeit wesentlich erweitert – es berücksichtigt nun neben Turingmaschinen auch Queue-Automaten, (Zwei-)Kellerautomaten und endliche Automaten. Die Darstellung der Kolmogorov-Komplexität wurde verbessert und erweitert.

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Witt, Kurt-Ulrich

Müller, Martin Eric

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Theoretische Informatik
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Informationstheorie, Kodierungstheorie
• Interdisziplinäres Wissenschaften Wissenschaften: Forschung und Information Informationstheorie, Kodierungstheorie
• Mathematik | Informatik Mathematik Mathematik Allgemein

Inhaltsverzeichnis

Einführung und Übersicht.- Alphabete, Wörter, Sprachen.- Berechenbarkeit.- Laufzeit-Komplexität.- Universelle Berechenbarkeit.- Unentscheidbare Mengen.- Kolmogorov-Komplexität.- Anwendungen der Kolmogorov-Komplexität.

Über Autor(innen)

Prof. Dr. Kurt-Ulrich Witt lehrte und forschte über dreißig Jahre an verschiedenen Universitäten und Hochschulen, zuletzt am Fachbereich Informatik der Hochschule Bonn-Rhein-Sieg. Er ist Autor mehrerer Lehrbücher zu mathematischen und theoretischen Grundlagen der Informatik.

Prof. Dr. Martin E. Müller ist Privatdozent an der Universität Augsburg und Professor für mathematische und theoretische Grundlagen der Informatik an der Hochschule Bonn-Rhein-Sieg. Er lehrt und forscht seit über fünfzehn Jahren in verschiedenen Gebieten der Theoretischen Informatik, der Diskreten Mathematik sowie der Algebraischen Logik.