/ en / Traditional / help

Beats Biblionetz - Bücher

Berechnungstheorie für Informatiker

Erwin Engeler, Peter Läuchli ,  
Buchcover
Diese Seite wurde seit 16 Jahren inhaltlich nicht mehr aktualisiert. Unter Umständen ist sie nicht mehr aktuell.

iconZusammenfassungen

Berechnungstheorie für InformatikerDer erste Teil, im allgemeinen elementarer formuliert, entspricht ungefähr der oben erwähnten ersten Vorlesung ("Berechnungstheorie", 4. Semester), in welcher vor allem der Berechenbarkeitsbegriff herausgearbeitet und eine erste Bekanntschaft mit der Erzeugung, bzw. Erkennung von formalen Sprachen anhand der ausführlich diskutierten regulären Sprachen vermittelt wird. Die anschliessend eingeführte Fixpunkttheorie soll dem Studenten ein theoretisches Werkzeug in die Hand geben, welches ihm erlaubt, verschiedene Gegenstände von einem einheitlichen Standpunkt aus zu betrachten. Schliesslich liefert der "Hauptsatz über syntaktische Strukturen" eine Grundlage für die strenge Definition der Semantik formaler Sprachen.
Im zweiten Teil, der in der Darstellung konzentrierter und anspruchsvoller gehalten ist, kommt zumindest teilweise der Inhalt unserer zweiten Vorlesung ("Theoretische Informatik", 6. Semester) zur Sprache. Hier wird zunächst für die Konstruktion eines Universalprogramms, das alle partiell-rekursiven Funktionen berechnen kann, eine Gödel-Numerierung der Programme und Wertbelegungen eingeführt und die effektive Aufzählung der erwähnten Funktionsklasse dann gleich in der Rekursionstheorie angewendet. Verschiedene Maschinenmodelle (Turing-, Tag-Maschine, k-Kellerautomat) werden als äquivalent erkannt und zur Diskussion von einigen klassischen unentscheidbaren Problemen herangezogen. Schliesslich kommt als wichtige Datenstruktur (zu den bisherigen Zahlen und Zeichenreihen) diejenige der Listen ins Spiel, wo die Identifikation von Daten und Programmen beide als Listen zu LISP-artiger Rekursion fuhrt. Dabei ergeben sich natürliche Verwendungen der Hauptsätze der Rekursionstheorie sowohl für die Semantik rekursiver Definitionen als auch für die Grundlegung einer Theorie von Interpretern und Compilern.
Von Erwin Engeler, Peter Läuchli im Buch Berechnungstheorie für Informatiker (1988)

iconBemerkungen zu diesem Buch

Berechnungstheorie für InformatikerZum ganzen Buch ist zu sagen, dass darin keineswegs alles behandelt wird, was zu einem Minimum an Theorie in die Ausbildung zum Diplom-Informatiker gehört. So fehlen z.B. konkret folgende Gegenstände: kontextfreie Sprachen, Automatentheorie (ausser den endlichen Akzeptoren für reguläre Sprachen), Komplexitätstheorie, Logik-Programmierung. Für diese Gebiete muss auf entsprechende Literatur hingewiesen werden.
Von Erwin Engeler, Peter Läuchli im Buch Berechnungstheorie für Informatiker (1988)
Berechnungstheorie für InformatikerDer Inhalt dieses Buches entspricht weitgehend dem Stoff, den die beiden Autoren seit mehreren Jahren in einem zweisemestrigen Kurs für Informatiker an der ETH Zürich vermitteln. Vieles davon ist bereits früher in der Form von provisorischen Notizen von E. EngeIer als "Kleines Repetitorium der Berechnungstheorie" an die Studenten abgegeben worden. [...] Für die Lektüre des Buches wird vorausgesetzt, dass der Leser über das mathematische Rüstzeug verfugt, welches etwa in einem elementaren Kurs "Diskrete Mathematik" , in den unteren Semestern eines Hochschulstudiums, Richtung Inforrnatik oder Elektrotechnik, angeboten wird. Dazu gehören jedenfalls Grundbegriffe bezügJich Mengen, Funktionen, Relationen etc.
Von Erwin Engeler, Peter Läuchli im Buch Berechnungstheorie für Informatiker (1988)

iconDieses Buch erwähnt ...


Personen
KB IB clear
Noam Chomsky, Alonzo Church, Kurt Gödel, Marvin Minsky, Alan Turing

Begriffe
KB IB clear
Algorithmusalgorithm, Automatautomat, BerechenbarkeitComputability, Compiler, Determinismusdeterminism, Gödelsches Theorem, Halteproblem, Informatikcomputer science, Interpreter, LISP, Mathematikmathematics, Modellemodel, Rekursionrecursion, Semantiksemantics, Sprachelanguage, Strukturstructure, Theorietheory, Turing-Maschineturing machine
icon
Texte
Jahr  Umschlag Titel Abrufe IBOBKBLB
1931 local web  Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Kurt Gödel) 8, 14, 13, 2, 7, 13, 2, 5, 2, 6, 2, 424346478

iconDieses Buch erwähnt vermutlich nicht ... Eine statistisch erstelle Liste von nicht erwähnten (oder zumindest nicht erfassten) Begriffen, die aufgrund der erwähnten Begriffe eine hohe Wahrscheinlichkeit aufweisen, erwähnt zu werden.

iconTagcloud

iconStandorte  Eine Liste von Orten, wo das Objekt physisch vorhanden ist.

Beat, D-INFK (Lehrbuch AD.92.3 )

iconBibliographisches Hier finden Sie Angaben um das gewählte Werk zu kaufen oder in einer Bibliothek auszuleihen.

Titel   Format Bez. Aufl. Jahr ISBN          
Berechnungstheorie für Informatiker D Paperback - 2 1992 3519122588 Swissbib Worldcat Bestellen bei Amazon.de

iconBeat und dieses Buch

Beat hat dieses Buch während seiner Assistenzzeit an der ETH Zürich ins Biblionetz aufgenommen. Die bisher letzte Bearbeitung erfolgte während seiner Zeit am Institut für Medien und Schule. Beat besitzt ein physisches, aber kein digitales Exemplar. Es gibt bisher nur wenige Objekte im Biblionetz, die dieses Werk zitieren.

iconBiblionetz-History Dies ist eine graphische Darstellung, wann wie viele Verweise von und zu diesem Objekt ins Biblionetz eingetragen wurden und wie oft die Seite abgerufen wurde.