Theoretische Informatik
Eine problemorientierte Einführung
1st Edition
Published on 6. March 1996
Book
Paperback/Softback
VIII, 193 pages
978-3-540-60860-8 (ISBN)
Description
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.
More details
Series
Language
German
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Professional/practitioner
Illustrations
VIII, 193 S.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 12 mm
Weight
324 gr
ISBN-13
978-3-540-60860-8 (9783540608608)
DOI
10.1007/978-3-642-80130-3
Schweitzer Classification
Other editions
Additional editions
E-Book
03/2013
Springer
€36.99
Available for download
Content
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.