Grundbegriffe der theoretischen Informatik (Q4040541)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 193738
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Grundbegriffe der theoretischen Informatik |
scientific article; zbMATH DE number 193738 |
Statements
5 June 1993
0 references
computability
0 references
unsolvability
0 references
grammars
0 references
formal languages
0 references
automata
0 references
complexity of computation
0 references
0.8432436585426331
0 references
Grundbegriffe der theoretischen Informatik (English)
0 references
Inhalt des auf Vorlesungen basierenden Buches: 1. Grundlagen (stark motivierende Fragen: Ist ``alles'' berechenbar? Beweise für die Undurchführbarkeit gewisser Berechnungen) 2. Programme (Berechenbarkeit; verschiedene Programmiersprachen und ihre Äquivalenz; Halteprobleme in PASCAL als (mitreißend knapp, streng, einleuchtend durchgeführter) Beweis für Nichtberechenbarkeit einer Funktion 3. Funktionen (begeisternd formalisiert vorgetragenes klassisches Wissen über arithmetische Funktionen) 4. Regelsprachen 5. Reguläre Sprachen und Automaten 6. Kontextfreie Sprachen (klassisches Grundwissen über Regelsprachen - bis auf einige Ausnahmen im holpernden Duktus bekannter Literatur; der Ansatz: ``Produktionssysteme und Automaten definieren Relationen über Wortmengen'' bleibt Abbreviatur statt zum Formalismus der Relationen ausgebaut zu werden.) 7. Berechenbarkeit (Übersichtliche Einführung der Turingmaschinen; der Beweis ihrer Äquivalenz zu MiniPascal-Programmen ist die wesentliche didaktische Leistung des Buches - so werden bereits bewiesene Resultate nutzbar und der bekannte ``Turing-Wust'' wird vermieden. Durch geschickte Reduktion auf bereits Bewiesenes können das PKP und die anderen klassischen Entscheidbarkeitsfragen auf wenigen Seiten abgehandelt werden.) 8. Komplexität (guter, in seiner arithmetischen Betrachtung wiederum begeisternder Überblick über Zeitschranken, Komplexitätsmaße und -klassen. Reduzibilität und Vollständigkeit werden auf kleinstem Raum anschaulich abgehandelt.) Durch dies Buch weist sich Verf. vor allem als passionierter Mathematiker mit Vorlieben im Bereich des klassisch-arithmetischen Kalküls aus. Dort gelingt ihm jene Eleganz der Beweisführung, die den Leser seine Umgebung vergessen läßt. Ohne es explizit zu intendieren - sozusagen als Seiteneffekt - führt er außerdem den beweisfähigen Umgang mit der ``PEANO-Datenstruktur'' vor. Die Unvollkommenheit des klassischen Einstiegs in die Theorie der Regel erinnern zwar schmerzhaft an das Vorlesungsmanuskript als Urbild dieses Buches, können jedoch als Anreiz verstanden werden, den Relationskalkül über Halbgruppen in Richtung jener Herleitungsfähigkeit auszubauen, die ohne ``Prosa'' auskommt. Kurzum: Eine in jeder Hinsicht anregende Lektüre.
0 references