Theoretische Informatik: Eine Umfassende Einführung

ISBN-13: 9783662574089 / Niemiecki / Miękka / 2018 / 499 str.

Lutz Priese; Katrin Erk

Opis

Verständlich und gut lesbar: Diese fundierte Einführung eignet sich insbesondere für Anfänger, da sie Beweise im Detail ausführt und insofern auch in die Technik des Beweisens einführt. Zusätzlich stellen die Autoren Nicht-Standard-Berechnungsmodelle vor...

Das Lehrbuch führt in verständlicher Sprache in die theoretische Informatik ein. Es umfasst die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und gibt einen Überblick zur Komplexitätstheorie. Das Buch eignet sich insbesondere für Einsteiger: Alle Beweise sind im Detail ausgeführt. Für Dozenten ist das Buch ebenfalls interessant, da auch Nicht-Standard-Berechnungsmodelle vorgestellt werden. Das Buch basiert auf Vorlesungen der letzten zehn Jahre für Studierende der Informatik im Grundstudium.

Spis treści

Begriffe und Notationen - Eine kurze Einführung in die Aussagenlogik - Grammatiken und formale Sprachen - Reguläre Sprachen und endliche Automaten - Kontextfreie Sprachen - Turing-Maschinen - Die Sprachklassen ℒ, ℒ₀ und ℒ₁ - Abschlusseigenschaften von Sprachklassen - Berechenbarkeit - Registermaschinen - Rekursive Funktionen - Unentscheidbare Probleme - Alternative Berechnungsmodelle - Komplexität

O autorze

Lutz Priese: Studium der Mathematik an der Westfälischen Wilhelms-Universität Münster, Promotion 1974; Habilitation in Informatik 1979 an der Universität Dortmund; C3-Professor für Informatik an der Universität-Gesamthochschule Paderborn 1980 – 1991; seit 1991 C4-Professor für Theoretische Informatik an der Universität Koblenz-Landau, Gründungsleiter des Instituts für Computervisualistik, Gründung einer Firma zur industriellen Bildverarbeitung, 1. Innovationspreis des Landes Rheinland-Pfalz 2000.

Katrin Erk: Studium der Informatik an der Universität Koblenz-Landau, Promotion an der Universität des Saarlandes 2002; wissenschaftliche Mitarbeiterin am Institut für Computerlinguistik, Universität des  Saarlandes 2002 – 2006; seit 2006 Professorin für Computerlinguistik an der University of Texas at Austin im Linguistics Department.

Blurb

Diese Einführung umfasst die Theorie der formalen Sprachen sowie die Theorie der Berechenbarkeit und gibt einen Überblick über die Komplexitätstheorie. Alle Beweise werden ausführlich behandelt und speziell schwierige Beweise nicht etwa abgekürzt, sondern eingehender betrachtet. Damit bietet das Buch zugleich eine Einführung in die Technik des Beweisens und ist somit sowohl für Anfänger als auch Dozenten geeignet. Ein größeres Kapitel behandelt alternative Rechenmodelle, einschließlich Zwei-Register-Maschinen, Tag-Systeme, Wang-Maschinen, Rödding-Netze, Splicing und reversible Rechnungen.

Der Inhalt

Begriffe und Notationen - Eine kurze Einführung in die Aussagenlogik - Grammatiken und formale Sprachen - Reguläre Sprachen und endliche Automaten - Kontextfreie Sprachen - Turing-Maschinen - Die Sprachklassen ℒ, ℒ₀ und ℒ₁ - Abschlusseigenschaften von Sprachklassen - Berechenbarkeit - Registermaschinen - Rekursive Funktionen - Unentscheidbare Probleme - Alternative Berechnungsmodelle - Komplexität

Die Autoren

Lutz Priese: Studium der Mathematik an der Westfälischen Wilhelms-Universität Münster, Promotion 1974; Habilitation in Informatik 1979 an der Universität Dortmund; C3-Professor für Informatik an der Universität-Gesamthochschule Paderborn 1980 – 1991; seit 1991 C4-Professor für Theoretische Informatik an der Universität Koblenz-Landau, Gründungsleiter des Instituts für Computervisualistik, Gründung einer Firma zur industriellen Bildverarbeitung, 1. Innovationspreis des Landes Rheinland-Pfalz 2000.

Katrin Erk: Studium der Informatik an der Universität Koblenz-Landau, Promotion an der Universität des Saarlandes 2002; wissenschaftliche Mitarbeiterin am Institut für Computerlinguistik, Universität des  Saarlandes 2002 – 2006; seit 2006 Professorin für Computerlinguistik an der University of Texas at Austin im Linguistics Department.