Suchen und Finden

Service

Infos und Kontakt

Theoretische Informatik - ganz praktisch

Lukas König, Friederike Pfeiffer-Bohnen, Hartmut Schmeck

Verlag De Gruyter Oldenbourg, 2016

ISBN 9783110412086 , 428 Seiten

Format PDF, OL

Kopierschutz Wasserzeichen

Geräte

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

Mediengruppe Stein

Buchhandlungen

Öffentliche Hand

Education

Bibliotheken

RWS

Corporate

Medical

Service

Infos

Shop

Alle Preise verstehen sich inklusive der gesetzlichen MwSt.

Widerruf

Download-Voucher einlösen

Kopierschutz

= Kopierschutzfrei

= Wasserzeichen

= DRM Kopierschutz

Theoretische Informatik - ganz praktisch

Lukas König, Friederike Pfeiffer-Bohnen, Hartmut Schmeck

Vorwort und Lesehinweise??????????????????????????????????????????????????????????????

Inhalt??????????????????????????

1 Auf dem Weg zur theoretischen Informatik??????????????????????????????????????????????????????????????????????????????????????????????????

1.1 Information: der Stoff der Informatik????????????????????????????????????????????????????????????????????????????????????????????????

1.2 Formale Sprachen, Funktionen und Probleme????????????????????????????????????????????????????????????????????????????????????????????????????????

1.3 Zusammenfassung????????????????????????????????????????????????????

2 Deterministische Automaten??????????????????????????????????????????????????????????????????????

2.1 Turingmaschinen????????????????????????????????????????????????????

2.2 Linear beschränkte Turingmaschinen (LBA)??????????????????????????????????????????????????????????????????????????????????????????????????????

2.3 Kellerautomaten????????????????????????????????????????????????????

2.4 Endliche Automaten??????????????????????????????????????????????????????????

2.5 Zusammenfassung????????????????????????????????????????????????????

3 Nichtdeterminismus: Ratende Automaten???????????????????????????????????????????????????????????????????????????????????????????????

3.1 Nichtdeterminismus bei Turingmaschinen??????????????????????????????????????????????????????????????????????????????????????????????????

3.2 Nichtdeterminismus bei LBA??????????????????????????????????????????????????????????????????????????

3.3 Nichtdeterminismus bei Kellerautomaten??????????????????????????????????????????????????????????????????????????????????????????????????

3.4 Nichtdeterminismus bei endlichen Automaten??????????????????????????????????????????????????????????????????????????????????????????????????????????

3.5 Zusammenfassung????????????????????????????????????????????????????

4 Grammatiken und die Chomsky-Hierarchie??????????????????????????????????????????????????????????????????????????????????????????????

4.1 Allgemeine Grammatiken (Chomsky-Typ 0)??????????????????????????????????????????????????????????????????????????????????????????????????

4.2 Kontextsensitive Grammatiken (Chomsky-Typ 1)??????????????????????????????????????????????????????????????????????????????????????????????????????????????

4.3 Monotone Grammatiken (noch einmal Chomsky-Typ 1)??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

4.4 Kontextfreie Grammatiken (Chomsky-Typ 2)??????????????????????????????????????????????????????????????????????????????????????????????????????

4.5 LR(k)-Grammatiken (eine Zwischenstufe)??????????????????????????????????????????????????????????????????????????????????????????????????

4.6 Rechtslineare Grammatiken (Chomsky-Typ 3)????????????????????????????????????????????????????????????????????????????????????????????????????????

4.7 Grammatiken mit endlicher Auswahl (Chomsky-Typ 4?)??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

4.8 Zusammenfassung????????????????????????????????????????????????????

5 Weitere strukturelle Eigenschaften der vorgestellten Sprachklassen??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

5.1 Reguläre Ausdrücke (Chomsky-Typ 3)??????????????????????????????????????????????????????????????????????????????????????????

5.2 Die Pumping-Lemmata (Chomsky-Typen 2 und 3)????????????????????????????????????????????????????????????????????????????????????????????????????????????

5.3 Normalformen für Grammatiken??????????????????????????????????????????????????????????????????????????????

5.4 Zusammenfassung????????????????????????????????????????????????????

6 Berechenbarkeitstheorie????????????????????????????????????????????????????????????????

6.1 Was „empfinden“ wir als berechenbar???????????????????????????????????????????????????????????????????????????????????????????????

6.2 Formalisierung der Berechenbarkeit durch Turingmaschinen??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

6.3 Die Turingmaschine als universeller Rechner????????????????????????????????????????????????????????????????????????????????????????????????????????????

6.4 Eigenschaften (semi-)entscheidbarer Sprachen??????????????????????????????????????????????????????????????????????????????????????????????????????????????

6.5 Reduzierbarkeit: zur relativen Schwierigkeit von Problemen??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

6.6 Zusammenfassung????????????????????????????????????????????????????

7 Komplexitätstheorie????????????????????????????????????????????????????????

7.1 Wie misst man die Komplexität von Problemen???????????????????????????????????????????????????????????????????????????????????????????????????????????????

7.2 Die Klassen P und NP??????????????????????????????????????????????????????????????

7.3 Die Klassen NP-schwer und NP-vollständig??????????????????????????????????????????????????????????????????????????????????????????????????????

7.4 Wie findet man NP-vollständige Probleme???????????????????????????????????????????????????????????????????????????????????????????????????????

7.5 Weitere Problemklassen und Reduktionen??????????????????????????????????????????????????????????????????????????????????????????????????

7.6 Zusammenfassung????????????????????????????????????????????????????

A Mathematische Grundlagen??????????????????????????????????????????????????????????????????

A.1 Mengen und Funktionen????????????????????????????????????????????????????????????????

A.2 Graphen????????????????????????????????????

A.3 Alphabete, Zeichen, Wörter und Sprachen????????????????????????????????????????????????????????????????????????????????????????????????????

A.4 Landau-Notation????????????????????????????????????????????????????

A.5 Kodierung????????????????????????????????????????

A.6 Klassifizierung von Sprachen??????????????????????????????????????????????????????????????????????????????

B Skripte????????????????????????????????

Literaturverzeichnis??????????????????????????????????????????????????????

Stichwortverzeichnis??????????????????????????????????????????????????????