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

      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references