2. Adventsüberraschung: 10% Rabatt auf alle Spiele! Jetzt mehr erfahren.
Willkommen, schön sind Sie da!
Logo Ex Libris

Elementare Berechenbarkeitstheorie

  • E-Book (pdf)
  • 166 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
Das Buch führt in leicht verständlicher und dennoch präziser Form in die Grundlagen der Berechenbarkeitstheorie ein. Es richtet si... Weiterlesen
CHF 16.20
Download steht sofort bereit
Informationen zu E-Books
E-Books eignen sich auch für mobile Geräte (sehen Sie dazu die Anleitungen).
E-Books von Ex Libris sind mit Adobe DRM kopiergeschützt: Erfahren Sie mehr.
Weitere Informationen finden Sie hier.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

Das Buch führt in leicht verständlicher und dennoch präziser Form in die Grundlagen der Berechenbarkeitstheorie ein. Es richtet sich an Informatikstudenten, ist aber für alle an der algorithmischen Berechenbarkeit Interessierten geeignet; vom Leser wird nur eine gewisse Vertrautheit mit formaler Argumentation erwartet. Der Darstellung liegt das Modell der Registermaschine zugrunde, das dem Umgang mit realen Computern und Programmiersprachen entlehnt ist. Daneben werden auch die klassischen Berechenbarkeitsmodelle betrachtet und die Gleichwertigkeit der Ansätze untereinander gezeigt. Darüber hinaus werden nicht-berechenbare Funktionen und unentscheidbare Probleme nachgewiesen. Als weiterführendes Thema wird die Unentscheidbarkeit der Prädikatenlogik und einiger Probleme aus dem Bereich der formalen Sprachen behandelt.

Die Beschäftigung mit den Grundprinzipien und Grenzen der Berechenbarkeit ist für die Informatik von zentraler Bedeutung. Um dieses Verständnis zu vermitteln, werden in diesem Buch Ansätze vorgestellt, die dem Umgang mit realen Computern und Programmiersprachen entlehnt sind. Es werden vor allem Registermaschinen und eine einfach while-basierte Programmiersprache verwendet.
Diese kompakte, an den entscheidenden Punkten aber ausführliche Einführung setzt nur elementare mathematische Kenntnisse voraus. Erfahrungen mit einer konventionellen Programmiersprache wie Pascal oder Modula erleichtern das Verständnis, sind aber nicht unbedingt erforderlich.

Inhalt
1 Einleitung.- Übersicht.- Mathematische Grundlagen.- 2 Registermaschinen.- 3 Berechenbare Funktionen.- 3.1 Programm-Makros.- 3.2 Weitere berechenbare Funktionen.- 4 Zeichenketten und Gödelnummern.- 5 Universelle Programme.- 5.1 Das Aufzählungstheorem.- 5.2 Rekursion.- 5.3 Indirekte Adressierung.- 6 Beschränkte und unbeschränkte Schleifen.- 6.1 For-berechenbare Funktionen.- 6.2 Nicht-for-berechenbare Funktionen.- 6.3 Die Kleenesche Normalform.- 7 Das Halteproblem und der Satz von Rice.- 7.1 Einführung: Das Halteproblem in Modula.- 7.2 Das Halteproblem der Registermaschine.- 7.3 Der Satz von Rice.- 8 Rekursive Funktionen.- 8.1 Primitiv-rekursive Funktionen.- 8.2 µ-rekursive Funktionen.- 9 Turhig-Maschinen.- 9.1 Grundlegende Definitionen.- 9.2 Äquivalenz von Tiring- und Registermaschinen.- 9.3 Allgemeine Tiring-Maschinen.- 10 Berechenbarkeit, Entscheidbarkeit, Aufzählbarkeit.- 10.1 Berechenbarkeit und die Churchsche These.- 10.2 Entscheidbarkeit.- 10.3 Semi-Entscheidbarkeit und Aufzählbarkeit.- 11 Das Postsche Korrespondenzproblem.- 12 Unentscheidbarkeit der Prädikatenlogik.- 13 Unentscheidbare Probleme in den formalen Sprachen.- 13.1 Kontextfreie Sprachen.- 13.2 Allgemeine Regelgrammatiken.- Literatur.

Produktinformationen

Titel: Elementare Berechenbarkeitstheorie
Autor:
EAN: 9783642582837
Format: E-Book (pdf)
Hersteller: Springer Berlin
Genre: Grundlagen
Veröffentlichung: 02.07.2013
Digitaler Kopierschutz: Wasserzeichen
Anzahl Seiten: 166
Auflage: 1996

Weitere Bände aus der Buchreihe "Springer-Lehrbuch"