
Einführung in die Theoretische Informatik
Grundlagen und Modelle
Klaus W. Wagner(Author)
Springer (Publisher)
Published on 9. September 1994
Book
Paperback/Softback
X, 238 pages
978-3-540-58139-0 (ISBN)
Article exhausted; check for reprint
Description
Die vorliegende Einfuhrung in die Theoretische Informatik folgt einem Konzept, das sich mit den neun von mir zu diesem Gegenstand an den Uni versitiiten Jena, Augsburg und Wiirzburg gehaltenen Vorlesungen entwickelt hat. Der Stoff dieses Buches ist so ausgewiihlt, daB er die innerhalb eines Grundstudiums der Informatik notwendigen theoretischen Grundlagen um faBt. Bei etwa 20%iger Kurzung entspricht er dem Umfang einer einsemestri gen vierstundigen Vorlesung. Durch die vielen Beispiele und Ubungsaufgaben eignet sich das Buch auch zum Selbststudium. Dieses Lehrbuch hatte nicht ohne die vielfiiltige Hilfe von Kollegen, Mit arbeitern und Studenten entstehen k6nnen. Zu besonderem Dank bin ich Dr. Ulrich Hertrampf und Dr. Heribert Vollmer verpfiichtet, die mehrere Imple mentierungen dieses Konzeptes kritisch begleitet, verschiedene Versionen des Manuskripts kommentiert, mich bei der Definition von PASCALLI wesentlich unterstutzt und mich uberhaupt erst ermuntert haben, mein Vorlesungsma nuskript zu einem Lehrbuch umzuarbeiten. Frau Dipl.-Inf. Diana RooB ver danke ich viele interessante Diskussionen zu diesem Buch und die sch6nen Abbildungen. Frau Dipl.-Inf. Gundula Niemann hat mit einer sehr sorgfiilti gen Durchsicht der letzten Version noch eine ganze Reihe von Verbesserungen erm6glicht. Frau cando info Katja Jucht und Herr Dipl.-Inf. Herbert Baier Saip haben wertvolle technische Hilfe geleistet. SchlieBlich m6chte ich Herrn Dr. Hans W6ssner vom Springer-Verlag fur die sehr konstruktive Zusammen arbeit danken.
More details
Series
Language
German
Place of publication
Heidelberg
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Dimensions
Height: 23.5 cm
Width: 15.5 cm
Weight
390 gr
ISBN-13
978-3-540-58139-0 (9783540581390)
DOI
10.1007/978-3-642-97583-7
Schweitzer Classification
Other editions
New editions

Book
08/2003
2nd Edition
Springer
€32.99
Shipment within 10-15 days
Content
1 Mathematische Grundlagen.- 1.1 Mengen, Relationen, Funktionen und Graphen.- 1.2 Wörter und natürliche Zahlen.- 1.3 Algebraische Erzeugung und das Induktionsprinzip.- 1.4 Aufgaben.- 2 Modelle der Computer-Berechenbarkeit.- 2.1 Random-Access-Maschinen.- 2.2 Die Programmiersprache PASCALLI.- 2.3 PASCALLINO und der Compiler.- 2.4 Aufgaben.- 3 Andere Berechenbarkeitsmodelle.- 3.1 Zur Geschichte des Algorithmenbegriffes.- 3.2 Turingmaschinen.- 3.3 Partiell-rekursive Funktionen.- 3.4 Der Hauptsatz der Algorithmentheorie. Die These von Church.- 3.5 Aufgaben.- 4 Entscheidbarkeit und Aufzählbarkeit.- 4.1 Einfache Beziehungen.- 4.2 Das Halteproblem.- 4.3 Aufgaben.- 5 Berechnungskomplexität.- 5.1 Die Laufzeit von Algorithmen.- 5.2 Die Klasse P.- 5.3 Die Klasse NP.- 5.4 NP-vollständige Mengen.- 5.5 Der Speicherplatzbedarf von Algorithmen.- 5.6 Wie schwierig können Probleme sein?.- 5.7 Aufgaben.- 6 Boolesche Funktionen.- 6.1 Einfache Eigenschaften boolescher Funktionen.- 6.2 Aussagenlogik.- 6.3 Kombinatorische Schaltkreise.- 6.4 Das Postsche Vollständigkeitskriterium.- 6.5 Aufgaben.- 7 Endliche Automaten.- 7.1 Endliche Automaten mit Ausgabe.- 7.2 Logische Schaltkreise.- 7.3 Endliche Automaten und reguläre Mengen.- 7.4 Aufgaben.- 8 Grammatiken und Formale Sprachen.- 8.1 Die Chomsky-Hierarchie.- 8.2 Sprachen vom Typ 3.- 8.3 Kontextfreie Sprachen.- 8.4 Kontextsensitive Sprachen.- 8.5 Sprachen vom Typ 0.- 8.6 Aufgaben.- Weiterführende Literatur.