Theoretische Informatik

Description

Die Theoretische Informatik untersucht die der Informatik zugrundeliegenden Konzepte, Modelle und Vorgehensweisen. Es ist ein Fachgebiet, das durch seine formalen Definitionen und vielen Beweise Parallelen zur Mathematik aufweist. Dieses Buch führt umfassend in die Theoretische Informatik ein. Dabei legen die Autoren besonderen Wert auf Verständlichkeit und gute Lesbarkeit. Zu Beginn stellen sie die mathematischen Konzepte mit ihren Begriffen und Notationen vor. In den folgenden drei Hauptabschnitten führt das Buch in die Theorie der formalen Sprachen und in die Theorie der Berechenbarkeit ein und gibt einen Überblick über die Komplexitätstheorie. Mit ihren verschiedenen Sprachklassen, Grammatiken und den Automaten werden die formalen Sprachen einerseits eingesetzt, um Compiler zu bauen und andererseits um Programme zu analysieren. Bei der Anwendung der Theorie der Berechenbarkeit werden Modelle eines Computers wie etwa die Registermaschine betrachtet. Weil sie einfacher aufgebaut sind als ein konkreter Computer, kann an ihnen untersucht werden, ob ein Problem überhaupt mit einem Computer gelöst werden kann. Auch alternative Rechenmodelle wie Zwei-Register-Maschinen, Tag-Systeme, Wang-Maschinen, Rödding-Netze, Splicing und reversible Rechnungen kommen in einem eigenen umfangreichen Kapitel zur Sprache. Abschließend wird die Komplexitätstheorie betrachtet, anhand derer sich herausfinden lässt, wie viel Rechenzeit für die Lösung eines Problems aufgewendet werden muss. Das Buch basiert auf Vorlesungen, die die Autoren für Studierende der Informatik im Grundstudium an den Universitäten Paderborn und Koblenz gehalten haben. Sämtliche Beweise werden in dem Buch detailliert ausgeführt. Und gerade die besonders schwierigen werden nicht abgekürzt, sondern umso eingehender betrachtet. Damit bietet dieses Buch zugleich eine Einführung in die Technik des Beweisens. Mit der ausführlichen Behandlung aller Beweise eignet sich das Lehrbuch besonders für Einsteiger in das Gebiet der Theoretischen Informatik. Aber auch Dozenten profitieren insbesondere von der Vorstellung alternativer Berechnungsmodelle. Front Matter ....Pages I-XVI Einleitung (Lutz Priese, Katrin Erk)....Pages 1-1 Begriffe und Notationen (Lutz Priese, Katrin Erk)....Pages 3-34 Eine kurze Einführung in die Aussagenlogik (Lutz Priese, Katrin Erk)....Pages 35-49 Front Matter ....Pages 51-51 Grammatiken und formale Sprachen (Lutz Priese, Katrin Erk)....Pages 53-61 Reguläre Sprachen und endliche Automaten (Lutz Priese, Katrin Erk)....Pages 63-107 Kontextfreie Sprachen (Lutz Priese, Katrin Erk)....Pages 109-163 Turing-Maschinen (Lutz Priese, Katrin Erk)....Pages 165-193 Die Sprachklassen \( \boldsymbol{\mathcal{L}}, \boldsymbol{{\mathcal{L}}_0} \) und \( \boldsymbol{{\mathcal{L}}_1} \) (Lutz Priese, Katrin Erk)....Pages 195-214 Abschlusseigenschaften von Sprachklassen (Lutz Priese, Katrin Erk)....Pages 215-223 Front Matter ....Pages 225-225 Einleitung (Lutz Priese, Katrin Erk)....Pages 227-231 Registermaschinen (Lutz Priese, Katrin Erk)....Pages 233-251 Rekursive Funktionen (Lutz Priese, Katrin Erk)....Pages 253-289 Unentscheidbare Probleme (Lutz Priese, Katrin Erk)....Pages 291-325 Alternative Berechnungsmodelle (Lutz Priese, Katrin Erk)....Pages 327-452 Komplexität (Lutz Priese, Katrin Erk)....Pages 453-486 Back Matter ....Pages 487-499