Theoretische Informatik
Einführung in Berechenbarkeit, Komplexität und formale Sprachen
1st Edition
Published on 28. July 2019
432 pages
978-3-86326-664-6 (ISBN)
Description
Online-Tipp von informit.de: Dieser Titel ist jetzt als Online-eBook zum sofortigen Herunterladen in unserem eBook-Shop erhältlich.
Bitte hier klicken.
Zum Buch:
Eine anschauliche Einführung in die klassischen Themenbereiche der Theoretischen Informatik für Studierende der Informatik im Haupt- und Nebenfach. Die Autoren wählen einen Ansatz, der durch zahlreiche ausgearbeitete Beispiele auch LeserInnen mit nur elementaren Mathematikkenntnissen den Zugang zu Berechenbarkeit, Komplexitätstheorie und formalen Sprachen ermöglicht. Die mathematischen Konzepte werden sowohl formal eingeführt als auch informell erläutert und durch grafische Darstellungen veranschaulicht. Das Buch umfasst den Lehrstoff einführender Vorlesungen in die Theoretische Informatik und bietet zahlreiche Übungsaufgaben zu jedem Kapitel an.
Aus dem Inhalt:
Berechenbarkeit
Über die Autoren:
Christel Baier ist Professorin an der Rheinischen Friedrich Wilhelms-Universität Bonn und bietet Vorlesungen zur Einführung in die Theoretische Informatik und zur Verifikation an. Alexander Asteroth ist inzwischen in der Industrie tätig.
Companion Website zum Buch unter pearson-studium.de
Auf der Website:
Zum Buch:
Eine anschauliche Einführung in die klassischen Themenbereiche der Theoretischen Informatik für Studierende der Informatik im Haupt- und Nebenfach. Die Autoren wählen einen Ansatz, der durch zahlreiche ausgearbeitete Beispiele auch LeserInnen mit nur elementaren Mathematikkenntnissen den Zugang zu Berechenbarkeit, Komplexitätstheorie und formalen Sprachen ermöglicht. Die mathematischen Konzepte werden sowohl formal eingeführt als auch informell erläutert und durch grafische Darstellungen veranschaulicht. Das Buch umfasst den Lehrstoff einführender Vorlesungen in die Theoretische Informatik und bietet zahlreiche Übungsaufgaben zu jedem Kapitel an.
Aus dem Inhalt:
Berechenbarkeit
- Abstrakte Rechnermodelle
- Entscheidungsprobleme
- Komplexitätsklassen
- Das P-NP-Problem
- Grammatiken
- Reguläre Sprachen
- Kontextfreie Sprachen
- Deterministisch kontextfreie Sprachen
- Entscheidungsprobleme für formale Sprachen
Über die Autoren:
Christel Baier ist Professorin an der Rheinischen Friedrich Wilhelms-Universität Bonn und bietet Vorlesungen zur Einführung in die Theoretische Informatik und zur Verifikation an. Alexander Asteroth ist inzwischen in der Industrie tätig.
Companion Website zum Buch unter pearson-studium.de
Auf der Website:
- Rund 100 Übungsaufgaben und
- Lösungsvorschläge
- Vorlesungsfolien
- Alle Abbildungen des Buches
More details
Other editions
Additional editions
Christel Baier | Alexander Asteroth
Theoretische Informatik
Einführung in Berechenbarkeit, Komplexität und formale Sprachen
Book
10/2002
1st Edition
Addison Wesley
€29.95
Article exhausted; check different version
Persons
Christel Baier ist Professorin für Informatik an der Rheinischen Friedrich-Wilhelms-Universität Bonn. Sie bietet Vorlesungen zu verschiedenen Themen der theoretischen Informatik an.
Content
- Theoretische Informatik - Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen
- Inhaltsverzeichnis
- Teil I Berechenbarkeit
- 1 Abstrakte Rechnermodelle
- 2 Entscheidungsprobleme
- Teil II Komplexität
- 3 Komplexitätsklassen
- 4 Das P-NP-Problem
- Teil III Formale Sprachen
- 5 Grammatiken
- 6 Reguläre Sprachen
- 7 Kontextfreie Sprachen
- 8 Deterministisch kontextfreie Sprachen
- 9 Entscheidungsprobleme für formale Sprachen
- 10 Zusammenfassung
- A Die Güte von Algorithmen
- B Aussagenlogik
- C Formale Sprachen
- Literaturverzeichnis
- Register
- Vorwort
- Teil I Berechenbarkeit
- 1 Abstrakte Rechnermodelle
- 1.1 Registermaschinen
- 1.2 Turingmaschinen
- 1.2.1 Deterministische Turingmaschinen
- 1.2.2 Turing-Berechenbarkeit
- 1.2.3 Mehrband-Turingmaschinen
- 1.2.4 Kostenmaße für DTMs
- 1.2.5 Turingmaschinen mit linksseitig beschränktem Band
- 1.2.6 »Programmierung« von DTMs
- 1.3 Äquivalenz der Berechenbarkeitsbegriffe
- 1.3.1 Simulation von Registermaschinen durch Turingmaschinen
- 1.3.2 Simulation von Turingmaschinen durch Registermaschinen
- 1.3.3 Churchsche These
- 1.4 Übungen
- 2 Entscheidungsprobleme
- 2.1 Entscheidbarbeit und Semientscheidbarkeit
- 2.2 Das Halteproblem
- 2.3 Nichtdeterminismus
- 2.4 Übungen
- Teil II Komplexität
- 3 Komplexitätsklassen
- 3.1 Zeitkomplexität
- 3.2 Platzkomplexität
- 3.3 Übungen
- 4 Das P-NP-Problem
- 4.1 NP-Vollständigkeit
- 4.2 Der Satz von Cook
- 4.2.1 Die NP-Vollständigkeit von SAT
- 4.3 Weitere NP-vollständige Probleme
- 4.3.1 3SAT
- 4.3.2 Das Cliquenproblem
- 4.3.3 Das Rucksackproblem
- 4.3.4 0/1 Integer Linear Programming
- 4.4 Die Klasse coNP
- 4.5 PSPACE-Vollständigkeit
- 4.6 Übungen
- Teil III Formale Sprachen
- 5 Grammatiken
- 5.1 Die Chomsky-Hierarchie
- 5.2 Sprachen vom Typ 0
- 5.3 Kontextsensitive Sprachen
- 5.4 Das Wortproblem für Sprachen vom Typ 0 und vom Typ 1
- 5.5 Übungen
- 6 Reguläre Sprachen
- 6.1 Endliche Automaten
- 6.1.1 Deterministische endliche Automaten
- 6.1.2 Nichtdeterministische endliche Automaten
- 6.2 Eigenschaften regulärer Sprachen
- 6.2.1 Konstruktion endlicher Automaten
- 6.2.2 Algorithmen für den Nachweis von Eigenschaften regulärer Sprachen
- 6.2.3 Das Pumping Lemma für reguläre Sprachen
- 6.3 Reguläre Ausdrücke
- 6.4 Minimierung von endlichen Automaten
- 6.4.1 Der Satz von Myhill & Nerode
- 6.4.2 Der Minimierungsalgorithmus
- 6.5 Übungen
- 7 Kontextfreie Sprachen
- 7.1 Grundbegriffe
- 7.2 Die Chomsky-Normalform
- 7.3 Der Cocke-Younger-Kasami-Algorithmus
- 7.4 Eigenschaften kontextfreier Sprachen
- 7.4.1 Das Pumping Lemma für kontextfreie Sprachen
- 7.4.2 Abschlusseigenschaften kontextfreier Sprachen
- 7.5 Die Greibach-Normalform
- 7.6 Kellerautomaten
- 7.7 Übungen
- 8 Deterministisch kontextfreie Sprachen
- 8.1 Deterministische Kellerautomaten
- 8.2 LR(0)-Grammatiken
- 8.2.1 Die LR(0)-Bedingung
- 8.2.2 Ein nichtdeterministischer LR(0)-Parser
- 8.2.3 LR(0)-Items
- 8.2.4 Berechnung der Itemmengen
- 8.2.5 DKAs für LR(0)-Grammatiken
- 8.3 LR(k)-Grammatiken
- 8.3.1 Die LR(k)-Bedingung
- 8.3.2 LR(k)-Items
- 8.3.3 Die Parsetabellen
- 8.3.4 Der LR(k)-Parser
- 8.4 Übungen
- 9 Entscheidungsprobleme für formale Sprachen
- 9.1 Das Postsche Korrespondenzproblem
- 9.2 Unentscheidungsergebnisse für formale Sprachen
- 9.2.1 Unentscheidbarkeitsergebnisse für deterministisch kontextfreie Sprachen
- 9.2.2 Unentscheidbarkeitsergebnisse für kontextfreie Sprachen
- 9.2.3 Unentscheidbarkeitsergebnisse für kontextsensitive Sprachen
- 9.3 »Schwierige« Probleme für reguläre Sprachen
- 9.4 Übungen
- 10 Zusammenfassung
- A Die Güte von Algorithmen
- B Aussagenlogik
- Syntax der Aussagenlogik
- Semantik der Aussagenlogik
- C Formale Sprachen
- Literaturverzeichnis
- Register
- !
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- Z
- Copyright
