Produktbeschreibung

Erscheinungsjahr: 2008
5. Aufl.
m. Abb.
Gewicht: 295 gr / Abmessung: 21 cm
Von Schöning, Uwe

Dieses in der 5. Auflage vorliegende Standardwerk macht Sie in kompakter Form mit den wesentlichen Grundzügen der Theoretischen Informatik vertraut. Der erste und größte Teil behandelt Formale Sprachen, Grammatiken und Automaten. Prof. Schöning gelingt durch seinen verständlichen Beweisstil und viele Beispiele eine übersichtliche und im Detail gut nachvollziehbare Darstellung dieses grundlegenden Gebietes der Theoretischen Informatik. Es schließt sich die Behandlung der Berechenbarkeitstheorie an. Hier werden beginnend mit dem intuitiven Berechenbarkeitsbegriff und der Churchschen These die wichtigsten Theoreme bis hin zum Gödelschen Unvollständigkeitssatz bewiesen. Der dritte Teil führt in dieKomplexitätstheorie ein und legt hierbei den Schwerpunkt auf die Theorie der NP-Vollständigkeit. Zahlreiche Querbezüge und Bemerkungen erleichtern das Verständnis und vertiefen das Gelernte.

Inhaltsverzeichnis:
Einleitung.- 1 Automatentheorie und Formale Sprachen.- 1.1 Allgemeines. 1.2 Reguläre Sprachen. 1.3 Kontextfreie Sprachen. 1.4 Kontextsensitive und Typ 0-Sprachen. 1.5 Tabellarischer Überblick.- 2 Berechenbarkeitstheorie.- 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These. 2.2 Turing-Berechenbarkeit. 2.3 LOOP-, WHILE- und GOTO-Berechenbarkeit. 2.4 Primitiv rekursive und mü-rekursive Funktionen. 2.5 Die Ackermannfunktion. 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit. 2.7 Das Postsche Korrespondenzprinzip. 2.8 Unentscheidbare Grammatik-Probleme. 2.9 Der Gödelsche Satz.- 3 Komplexitätstheorie.- 3.1 Komplexitätsklassen und P-NP-Problem. 3.2 NP-Vollständigkeit. 3.3 Weitere NP-vollständige Probleme.- Anhang: Mathematische Grundlagen.- Literaturverzeich

Produktinformation

• Amazon-Verkaufsrang: #51805 in Bücher
• Veröffentlicht am: 2008-05
• Abmessungen: .0 Pfund
• Einband: Taschenbuch
• 190 Seiten

Kundenrezensionen

Hilfreichste Kundenrezensionen

3 von 3 Kunden fanden die folgende Rezension hilfreich.
Kurz und bündig - aber trotzdem verständlich und gut
Von Andreas Koch
Wer einen Blick ins Inhaltsverzeichnis des Buches wirft, wird schnell feststellen, dass der Hauptfokus bei Grammatiken, Automaten, Turing-Maschinen etc liegt. An unserer Uni umfasst das Buch genau die Vorlesung "Grundlagen Theoretische Informatik II" - und ich finde, dass es die perfekte Begleitlektüre zu diesen Themen ist. An einfachen und verständlichen Beispielen werden die Inhalte gut vermittelt. Formale Definitionen sind natürlich auch enthalten, allerdings sind diese auch für Leute die mit Formalismen auf Kriegsfuß stehen ganz gut verständlich.
Was das Buch nicht bietet sind beispielsweise tiefe Einblicke in die NP-Komplexität sowie in Approximationsalgorithmen für harte Probleme etc.

Falls man allerdings Lektüre zu Automaten, Grammatiken, Sprachen, Berechenbarkeitstheorie sucht, ist man hier genau richtig.
BTW: Der Preis ist auch vollkommen in Ordnung!

5 von 6 Kunden fanden die folgende Rezension hilfreich.
TI kurzgefasst ...zu kurz
Von Phil
Anfängliche Themen wie Grammatiken werden in diesem Buch gut beschrieben und auch durch ausreichend Beispielen unterlegt. Desto weiter man jedoch liest, desto schwieriger wird es die Inhalte des Buches zu begreifen.
Erklärungen für komplexe Themen wie "Das Halteproblem" fallen der Kompaktheit des Buches zum Opfer. Mit Aussagen wie "Man sieht leicht" oder "Es ist klar" fühlt sich der Leser schnell allein gelassen.

Ohne einen kompetenten Übungsleiter oder gut gehaltener Vorlesung ist meiner Meinung nach die Hälfte des Buches nicht nachvollziehbar.

1 von 1 Kunden fanden die folgende Rezension hilfreich.
Kompakt und gut!
Von Reinhard Weyand
Uwe Schönings "Theoretische Informatik - kurzgefasst" ist so ziemlich das kompakteste Buch zu diesem Themengebiet. Die Angst, es sei zu wenig erklärt, ist bei solch kurzen Büchern über sehr theoretische Themengebiete zwar immer berechtigt, in diesem Fall jedoch unnötig.
Prof. Schöning beschreibt alle Aspekte einer Grundvorlesung (Automaten/Grammatiken, Berechenbarkeit, Komplexitätstheorie) in knappen aber verständlich nachvollziehbaren und durchaus anschaulichen Beispielen, sodass ich mich zu keiner Zeit genötgit sah, irgendwelche andere Literatur zu konsultieren.
Wer im Grundstudium der theoretischen Informatik ausgesetzt ist und ein Buch haben möchte, mit dem er (auch vollkommen autonom) den Stoff bewältigen kann, der ist hier definitiv richtig aufgehoben.