Theoretische Informatik - ganz praktisch (eBook)
428 Seiten
De Gruyter Oldenbourg (Verlag)
978-3-11-041208-6 (ISBN)
Die theoretische Informatik ist für viele Studierende ein Schreckgespenst, weil formale Einstiegshürden die Bezüge zur Praxis verschleiern. In diesem Lehrbuch wird das Theoretische aufgerollt, wie es ursprünglich entstanden ist: zur Lösung ganz praktischer Probleme. So ergeben sich Formalismen als logische Notwendigkeit, mathematische Eigenarten werden greifbar, komplexe Theorien verlieren ihren Schrecken. Radikal studierendenorientiert führt das Buch in Automatentheorie, Grammatiken, Berechenbarkeits- und Komplexitätstheorie ein.
Die Autoren erhielten 2013 gemeinsam den Fakultätslehrpreis für herausragende Lehre am Karlsruher Institut für Technologie (KIT).
Lukas König studierte Informatik an der Universität Stuttgart und promovierte 2014 am Institut für angewandte Informatik und formale Beschreibungsverfahren (AIFB) des KIT. Derzeit forscht er zum Einsatz computergestützter Methoden im Informatikunterricht.
Friederike Pfeiffer-Bohnen studierte Wirtschaftsingenieurwesen am KIT. Am Institut AIFB promoviert sie derzeit im Bereich Hochschuldidaktik mit Schwerpunkt eLearning. Im Jahr 2016 erlangte sie das Baden-Württemberg-Zertifikat für Hochschuldidaktik.
Hartmut Schmeck hat seit 1991 eine Professur am Institut AIFB des KIT. Er forscht und lehrt über Algorithmen und Architekturen, in den letzten Jahren vor allem für selbstorganisierende, adaptive Systeme mit Anwendungen in Energie- und Verkehrssystemen.
Prof. Schmeck, Institutsleiter KIT und Mitarbeiter
Vorwort und Lesehinweise?????????????????????????????????????????????????????????????? 5
Inhalt?????????????????????????? 17
1 Auf dem Weg zur theoretischen Informatik?????????????????????????????????????????????????????????????????????????????????????????????????? 19
1.1 Information: der Stoff der Informatik???????????????????????????????????????????????????????????????????????????????????????????????? 20
1.2 Formale Sprachen, Funktionen und Probleme???????????????????????????????????????????????????????????????????????????????????????????????????????? 27
1.3 Zusammenfassung???????????????????????????????????????????????????? 38
2 Deterministische Automaten?????????????????????????????????????????????????????????????????????? 41
2.1 Turingmaschinen???????????????????????????????????????????????????? 42
2.2 Linear beschränkte Turingmaschinen (LBA)?????????????????????????????????????????????????????????????????????????????????????????????????????? 63
2.3 Kellerautomaten???????????????????????????????????????????????????? 65
2.4 Endliche Automaten?????????????????????????????????????????????????????????? 83
2.5 Zusammenfassung???????????????????????????????????????????????????? 110
3 Nichtdeterminismus: Ratende Automaten??????????????????????????????????????????????????????????????????????????????????????????????? 117
3.1 Nichtdeterminismus bei Turingmaschinen?????????????????????????????????????????????????????????????????????????????????????????????????? 120
3.2 Nichtdeterminismus bei LBA?????????????????????????????????????????????????????????????????????????? 134
3.3 Nichtdeterminismus bei Kellerautomaten?????????????????????????????????????????????????????????????????????????????????????????????????? 135
3.4 Nichtdeterminismus bei endlichen Automaten?????????????????????????????????????????????????????????????????????????????????????????????????????????? 143
3.5 Zusammenfassung???????????????????????????????????????????????????? 154
4 Grammatiken und die Chomsky-Hierarchie?????????????????????????????????????????????????????????????????????????????????????????????? 161
4.1 Allgemeine Grammatiken (Chomsky-Typ 0)?????????????????????????????????????????????????????????????????????????????????????????????????? 173
4.2 Kontextsensitive Grammatiken (Chomsky-Typ 1)?????????????????????????????????????????????????????????????????????????????????????????????????????????????? 179
4.3 Monotone Grammatiken (noch einmal Chomsky-Typ 1)?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? 185
4.4 Kontextfreie Grammatiken (Chomsky-Typ 2)?????????????????????????????????????????????????????????????????????????????????????????????????????? 188
4.5 LR(k)-Grammatiken (eine Zwischenstufe)?????????????????????????????????????????????????????????????????????????????????????????????????? 198
4.6 Rechtslineare Grammatiken (Chomsky-Typ 3)???????????????????????????????????????????????????????????????????????????????????????????????????????? 201
4.7 Grammatiken mit endlicher Auswahl (Chomsky-Typ 4?)?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? 208
4.8 Zusammenfassung???????????????????????????????????????????????????? 210
5 Weitere strukturelle Eigenschaften der vorgestellten Sprachklassen?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? 215
5.1 Reguläre Ausdrücke (Chomsky-Typ 3)?????????????????????????????????????????????????????????????????????????????????????????? 217
5.2 Die Pumping-Lemmata (Chomsky-Typen 2 und 3)???????????????????????????????????????????????????????????????????????????????????????????????????????????? 225
5.3 Normalformen für Grammatiken?????????????????????????????????????????????????????????????????????????????? 245
5.4 Zusammenfassung???????????????????????????????????????????????????? 268
6 Berechenbarkeitstheorie???????????????????????????????????????????????????????????????? 273
6.1 Was „empfinden“ wir als berechenbar??????????????????????????????????????????????????????????????????????????????????????????????? 275
6.2 Formalisierung der Berechenbarkeit durch Turingmaschinen?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? 283
6.3 Die Turingmaschine als universeller Rechner???????????????????????????????????????????????????????????????????????????????????????????????????????????? 286
6.4 Eigenschaften (semi-)entscheidbarer Sprachen?????????????????????????????????????????????????????????????????????????????????????????????????????????????? 304
6.5 Reduzierbarkeit: zur relativen Schwierigkeit von Problemen?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? 320
6.6 Zusammenfassung???????????????????????????????????????????????????? 327
7 Komplexitätstheorie???????????????????????????????????????????????????????? 331
7.1 Wie misst man die Komplexität von Problemen??????????????????????????????????????????????????????????????????????????????????????????????????????????????? 333
7.2 Die Klassen P und NP?????????????????????????????????????????????????????????????? 343
7.3 Die Klassen NP-schwer und NP-vollständig?????????????????????????????????????????????????????????????????????????????????????????????????????? 349
7.4 Wie findet man NP-vollständige Probleme??????????????????????????????????????????????????????????????????????????????????????????????????????? 358
7.5 Weitere Problemklassen und Reduktionen?????????????????????????????????????????????????????????????????????????????????????????????????? 381
7.6 Zusammenfassung???????????????????????????????????????????????????? 390
A Mathematische Grundlagen?????????????????????????????????????????????????????????????????? 395
A.1 Mengen und Funktionen???????????????????????????????????????????????????????????????? 395
A.2 Graphen???????????????????????????????????? 396
A.3 Alphabete, Zeichen, Wörter und Sprachen???????????????????????????????????????????????????????????????????????????????????????????????????? 397
A.4 Landau-Notation???????????????????????????????????????????????????? 398
A.5 Kodierung???????????????????????????????????????? 399
A.6 Klassifizierung von Sprachen?????????????????????????????????????????????????????????????????????????????? 401
B Skripte???????????????????????????????? 403
Literaturverzeichnis?????????????????????????????????????????????????????? 421
Stichwortverzeichnis?????????????????????????????????????????????????????? 425
| Erscheint lt. Verlag | 26.9.2016 |
|---|---|
| Sprache | deutsch |
| Themenwelt | Mathematik / Informatik ► Informatik |
| Technik ► Elektrotechnik / Energietechnik | |
| ISBN-10 | 3-11-041208-X / 311041208X |
| ISBN-13 | 978-3-11-041208-6 / 9783110412086 |
| Haben Sie eine Frage zum Produkt? |
PDF (Wasserzeichen)Größe: 3,1 MB
DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
