Theoretische Informatik

More about the book

Die Theoretische Informatik untersucht grundlegende Konzepte, Modelle und Methoden der Informatik und zeigt Parallelen zur Mathematik durch formale Definitionen und Beweise. Dieses Buch bietet eine umfassende Einführung in die Theoretische Informatik und legt besonderen Wert auf Verständlichkeit und Lesbarkeit. Zunächst werden die mathematischen Konzepte, Begriffe und Notationen vorgestellt. In drei Hauptabschnitten behandelt das Buch die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und gibt einen Überblick über die Komplexitätstheorie. Formale Sprachen werden verwendet, um Compiler zu entwickeln und Programme zu analysieren. Die Theorie der Berechenbarkeit betrachtet Computer-Modelle wie Registermaschinen, die einfacher sind als konkrete Computer, um zu klären, ob ein Problem mit einem Computer lösbar ist. Alternative Rechenmodelle wie Zwei-Register-Maschinen, Tag-Systeme und reversible Rechnungen werden ebenfalls behandelt. Abschließend wird die Komplexitätstheorie untersucht, um den Rechenaufwand zur Problemlösung zu bestimmen. Das Buch basiert auf Vorlesungen für Informatikstudierende und bietet detaillierte Beweise, auch für komplexe Themen. Es eignet sich somit sowohl für Einsteiger als auch für Dozenten, die an alternativen Berechnungsmodellen interessiert sind.