/ en / Traditional / mobile

Beats Biblionetz - Bücher

Berechnungstheorie für Informatiker

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

iconZusammenfassungen

Der 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

Zum 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)
Der 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, Modellmodel, Rekursionrecursion, Semantiksemantics, Sprachelanguage, Strukturstructure, Theorietheory, Turing-Maschineturing machine
icon
Texte
Jahr UmschlagTitelAbrufeIBOBKBLB
1931    Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Kurt Gödel) 3, 3, 3, 2, 2, 1, 3, 3, 3, 1, 2, 622366025

iconDieses Buch erwähnt 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.

icon
Nicht erwähnte Begriffe
Church-Turing-These, Lambda-Kalkül, Syntax

iconTagcloud

Diese Grafik fensterfüllend anzeigen als Pixelgrafik (PNG) Vektorgrafik (SVG)

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 FormatBez.Aufl.JahrISBN      
Berechnungstheorie für InformatikerDPaperback-219923519122588SwissbibWorldcatBestellen bei Amazon.deBestellen bei ebook.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.

Verweise auf Dieses Buch 112
Verweise von diesem Buch 1339
Webzugriffe auf Dieses Buch 
200020012002200320042005200620072008200920102011201220132014201520162017