Blick ins Buch

Grundbegriffe der Theoretischen Informatik

Franz Stetter (Autor)

Buch | Softcover

VIII, 233 Seiten

1988
Springer Berlin (Verlag)
978-3-540-19362-3 (ISBN)

Lese- und Medienproben

Inhaltsverzeichnis (PDF)

Artikel merken

In diesem Lehrbuch werden die grundlegenden Begriffe der Theoretischen Informatik - Berechenbarkeit, Entscheidbarkeit, rekursive Funktionen, Regelsprachen, Turingmaschinen, Komplexität - auf der Basis der Programmiersprache PASCAL motiviert, abgeleitet und in einer einheitlichen Betrachtungsweise dargestellt. Ferner wird die Äquivalenz verschiedener Ansätze zu einer Theorie der Berechenbarkeit - Programme, rekursive Funktionen, Regelsprachen und Turingmaschinen - als weiteres zentrales Konzept herausgestellt. Während in den Kapiteln 1-7 qualitative Aspekte der Berechenbarkeit behandelt werden, ist Kapitel 8 den quantitativen Aspekten gewidmet. Die Komplexität, d.h. Zeit- bzw. Speicheraufwand für eine Berechnung, ist sowohl abhängig von dem zugrundeliegenden Berechnungsmodell als auch von dem zu lösenden Problem, da für ein bestimmtes Problem gewisse Schranken nicht unterschritten werden können. Bei einem so weitgespannten Gebiet wie der Theoretischen Informatik müssen zwangsläufig manche Einschränkungen bei der Stoffauswahl gemacht werden. So wird z.B. Semantik nur informell behandelt, Parallelität nur ansatzweise betrachtet oder Automatentheorie nur am Rand gestreift. Ziel der Stoffauswahl war es, ein möglichst umfassendes Bild der Theoretischen Informatik zu bieten und ein Fundament für weitergehende Studien zu legen. Das Buch setzt Grundkenntnisse aus den Anfängervorlesungen über Analysis und Lineare Algebra voraus. Um den Leser mit der Terminologie in diesem Buch vertraut zu machen, sind im Anhang diese mathematischen Grundlagen in knapper Form zusammengestellt.

1. Grundlagen.- 1.1 Algorithmen.- 1.2 Wortmengen.- 1.3 Gödelisierungen.- 1.4 Entscheidbarkeit und Aufzählbarkeit.- 2. Programme.- 2.1 Berechenbar keit.- 2.2 Minipascal.- 2.3 PASCAL.- 2.4 RAM.- 2.5 Halteproblem.- 3. Funktionen.- 3.1 Primitiv-rekursive Funktionen.- 3.2 Ackermannfunktion.- 3.3 Minimalisierung.- 3.4 Universelle Funktionen.- 3.5 Nichtberechenbare Funktionen.- 4. Regelsprachen.- 4.1 Produktionssysteme.- 4.2 Regelgrammatiken.- 4.3 Chomsky-Hierarchie.- 4.4 Entscheidungsprobleme.- 5. Reguläre Sprachen und Automaten.- 5.1 Akzeptoren.- 5.2 Reguläre Ausdrücke.- 5.3 Charakteristische Gleichungen.- 5.4 Endliche Automaten.- 5.5 Anwendungen.- 6. Kontextfreie Sprachen.- 6.1 Darstellungen und Transformationen.- 6.2 Struktureigenschaften.- 6.3 Kellerautomaten.- 6.4 Syntaxanalyse.- 7. Berechenbarkeit.- 7.1 Turingmaschinen.- 7.2 Regelsprachen.- 7.3 Postsches Korrespondenzproblem.- 7.4 Entscheidungsprobleme bei Regelsprachen.- 7.5 Churchsche These.- 8. Komplexität.- 8.1 LOOP-Programme.- 8.2 Turingmaschinen.- 8.3 Minipascal und Turingmaschinen.- 8.4 Komplexitätsklassen.- 8.5 Vollständigkeit.- 8.6 Abstrakte Komplexität.- Anhang A: Mathematische Grundlagen.- A.l Relationen.- A.2 Funktionen.

Erscheint lt. Verlag	10.10.1988
Reihe/Serie	Studienreihe Informatik
Zusatzinfo	VIII, 233 S.
Verlagsort	Berlin
Sprache	deutsch
Maße	170 x 244 mm
Gewicht	408 g
Themenwelt	Informatik ► Software Entwicklung ► User Interfaces (HCI)
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
Schlagworte	Algorithm analysis and problem complexity • Automaten • Automatentheorie • Berechenbarkeit • Entscheidbar • Entscheidbarkeit • Informatik • Komplexität • Kontextfreie Sprache • Mathematische Grundlagen • Parallelität • PASCAL • Programmiersprache • Reguläre Sprache • Rekursive Funktion • Semantik • Turingmaschine
ISBN-10	3-540-19362-6 / 3540193626
ISBN-13	978-3-540-19362-3 / 9783540193623
Zustand	Neuware