Blick ins Buch

Theoretische Informatik

Eine problemorientierte Einführung

Volker Sperschneider, Barbara Hammer (Autoren)

Buch | Softcover

VIII, 193 Seiten

1996
Springer Berlin (Verlag)
978-3-540-60860-8 (ISBN)

Lese- und Medienproben

Inhaltsverzeichnis (PDF)

Artikel merken

Das vorliegende Lehrbuch basiert auf einer vierstündigen Vorlesung mit dem Titel "Grundlagen der Theoretischen Informatik". Die Autoren führen an exemplarischen Problemstellungen der Theoretischen Informatik deren Lösungen mit Rechnern von der Analyse des Problems bis zu seiner Implementation in einer prozeduralen Programmiersprache mit syntaktischer und semantischer Analyse vor, auch unter dem Aspekt der Verbindung von theoretischer Strenge und Praxisrelevanz. Mit Aufgaben und Lösungshinweisen bzw. Lösungen.

1 Einleitung -; der rote Faden.- 2 Notationen.- 2.1 Bezeichnungen.- 2.2 Kalküle.- 3 Semantik von Programmiersprachen - Spezifizieren, Implementieren, Verifizieren.- 3.1 Datenstrukturen.- 3.2 Prädikatenlogik als Spezifikationssprache.- 3.3 Programme.- 3.4 Programmverifikation.- 3.5 Rekursive Programme.- 4 Berechenbarkeitstheorie - auf den Punkt gebracht.- 4.1 Primitiv rekursive Funktionen.- 4.2 ?-rekursive Funktionen.- 4.3 Universalität der ?-rekursiven Funktionen.- 4.4 Arithmetisierung der Semantik rekursiver Programme.- 4.5 Grundzüge der Rekursionstheorie.- 4.6 Die Churchsche These.- 4.7 Berechenbarkeit auf Zeichenreihen.- 4.8 Komplexitätsmaße.- 5 Komplexitätstheorie - das Wichtigste für den praktischen Informatiker.- 5.1 Problemtypen.- 5.2 NP-Theorie.- 5.3 Ausblick auf weitere Komplexitätsklassen.- 6 Chomsky-Hierarchie - nur ein kurzer Seitenblick.- 6.1 Grammatiken und Automaten.- 6.2 Chomsky-3: Reguläre Sprachen und endliche Automaten.- 6.3 Chomsky-2: Kontextfreie Sprachen.- 6.4 Chomsky-1: Kontextsensitive Sprachen.- 6.5 Chomsky-0: Allgemeine Grammatiken.- 7 Lösungen und Hinweise zu den Aufgaben.- Literaturangaben.- Symbolverzeichnis.

Erscheint lt. Verlag	6.3.1996
Reihe/Serie	Springer-Lehrbuch
Zusatzinfo	VIII, 193 S.
Verlagsort	Berlin
Sprache	deutsch
Maße	155 x 235 mm
Gewicht	334 g
Themenwelt	Informatik ► Theorie / Studium ► Theoretische Informatik
Schlagworte	Algorithmen • Automaten • Berechenbarkeitstheorie • Chomsky-Hierarchie • Informatik • Informatik; Handbuch/Lehrbuch • Komplexität • Komplexitätstheorie • Kontextfreie Sprache • Kontextsensitive Sprache • Programmiersprache • Programmverifikation • Reguläre Sprache • Rekursive Funktion • SE • Semantik • Semantische Analyse • Syntaktische Analyse • Theoretische Informatik
ISBN-10	3-540-60860-5 / 3540608605
ISBN-13	978-3-540-60860-8 / 9783540608608
Zustand	Neuware