Grundkurs Theoretische Informatik
Aus der Buchreihe »Informatik verstehen«. Ideal zum Studium als Vorlesungsbegleiter
Grundkurs Theoretische Informatik
Aus der Buchreihe »Informatik verstehen«. Ideal zum Studium als Vorlesungsbegleiter
- Broschiertes Buch
- Merkliste
- Auf die Merkliste
- Bewerten Bewerten
- Teilen
- Produkt teilen
- Produkterinnerung
- Produkterinnerung
Theoretische Informatik - der Vorlesungsbegleiter. Berechenbarkeit, formale Sprachen, Algorithmik und Komplexitätstheorie sind theoretische Themen mit praktischer Relevanz, zu denen es ebenso praktische Zugänge gibt. Freuen Sie sich auf eine moderene Didaktik, die streng Formales mit Ihrer Intuition verknüpft, lernfreundlich ausarbeitet und schließlich zu jedem Thema Anwendungsfelder der Informatik vorstellt. Stefan Neubert hat nicht nur selbst Freude an der theoretischen Informatik, sondern widmet sich auch mit Leidenschaft ihrer Vermittlung zu Beginn und im Laufe des Bachelorstudiums. Eine…mehr
- Kaspar RiesenJava in 14 Wochen44,99 €
- Hermann KampEinführung in die Programmiersprache PL/I54,99 €
- Jürgen WolfGrundkurs C++14,90 €
- Uwe MeyerGrundkurs Compilerbau29,90 €
- Arne BoockmeyerFit fürs Studium - Informatik24,90 €
- Erich J. SchreiberJAVA Aufgaben und Übungen39,99 €
- Jürgen WolfGrundkurs C16,90 €
-
-
-
Aus dem Inhalt:
Grundlegende mathematische NotationModelle und Grenzen der BerechenbarkeitFormale Sprachen: Endliche Automaten, kontextfreie Grammatiken, Pumping Lemmata und mehrBeweisverfahren für Korrektheit und Laufzeit von AlgorithmenParadigmen für den AlgorithmenentwurfAmortisierte Analyse und untere Schranke für LaufzeitenNP-Vollständigkeit und Reduktion
Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.
- Produktdetails
- Informatik verstehen
- Verlag: Rheinwerk Verlag
- Artikelnr. des Verlages: 459/07588
- Seitenzahl: 416
- Erscheinungstermin: April 2021
- Deutsch
- Abmessung: 229mm x 171mm x 24mm
- Gewicht: 766g
- ISBN-13: 9783836275880
- ISBN-10: 3836275880
- Artikelnr.: 60438057
- Informatik verstehen
- Verlag: Rheinwerk Verlag
- Artikelnr. des Verlages: 459/07588
- Seitenzahl: 416
- Erscheinungstermin: April 2021
- Deutsch
- Abmessung: 229mm x 171mm x 24mm
- Gewicht: 766g
- ISBN-13: 9783836275880
- ISBN-10: 3836275880
- Artikelnr.: 60438057
1.1 ... Kompetenzen für die theoretische Arbeit ... 16
1.2 ... Themen der theoretischen Informatik ... 18
1.3 ... Anleitung fürs Buch ... 20
1.4 ... Danksagungen ... 21
2. Mathematische Notation ... 23
2.1 ... Logische Aussagen ... 24
2.2 ... Mengen ... 27
2.3 ... Relationen und Funktionen ... 32
2.4 ... Graphen ... 37
2.5 ... Unendlichkeiten und Abzählbarkeit ... 40
2.6 ... Beweistechniken ... 42
2.7 ... Aufgaben ... 57
2.8 ... Lösungen ... 58
TEIL I. Berechenbarkeit und formale Sprachen ... 65
3. Einführung in die Berechenbarkeitstheorie ... 67
3.1 ... Algorithmus ... 68
3.2 ... Zu viele Funktionen ... 69
3.3 ... Das Halteproblem ... 70
3.4 ... Kontrollfragen ... 72
3.5 ... Antworten ... 72
4. Problemtypen ... 73
4.1 ... Formalisierung von Problemen ... 73
4.2 ... Funktionen berechnen ... 75
4.3 ... Datencodierung ... 75
4.4 ... Sprachen entscheiden ... 78
4.5 ... Problemklassen der Berechenbarkeitstheorie ... 79
4.6 ... Aufgaben ... 82
4.7 ... Lösungen ... 83
5. Einführung in formale Sprachen ... 85
5.1 ... Definition ... 85
5.2 ... Die Chomsky-Hierarchie ... 88
5.3 ... Aufgaben ... 89
5.4 ... Lösungen ... 90
6. Reguläre Sprachen ... 91
6.1 ... Deterministische endliche Automaten ... 92
6.2 ... Nichtdeterministische endliche Automaten ... 103
6.3 ... Grammatiken ... 111
6.4 ... Reguläre Ausdrücke ... 120
6.5 ... Abschlusseigenschaften ... 127
6.6 ... Entscheidungsprobleme auf regulären Sprachen ... 132
6.7 ... Äquivalenzklassenzerlegung ... 134
6.8 ... Nichtreguläre Sprachen ... 139
6.9 ... Ausblick ... 144
6.10 ... Aufgaben ... 144
6.11 ... Lösungen ... 149
7. Kontextfreie Sprachen ... 161
7.1 ... Kontextfreie Grammatiken ... 162
7.2 ... Eindeutige Ableitungsbäume ... 164
7.3 ... Chomsky-Normalform ... 166
7.4 ... Exkurs: Kellerautomaten ... 170
7.5 ... Abschlusseigenschaften ... 175
7.6 ... Entscheidungsprobleme auf kontextfreien Sprachen ... 176
7.7 ... Nicht-kontextfreie Sprachen ... 181
7.8 ... Ausblick ... 183
7.9 ... Aufgaben ... 184
7.10 ... Lösungen ... 186
8. Kontextsensitive Sprachen ... 193
8.1 ... Kontextsensitive und monotone Grammatiken ... 194
8.2 ... Das Wortproblem auf kontextsensitiven Sprachen ... 195
9. Aufzählbare Sprachen ... 197
9.1 ... Turingmaschinen ... 199
9.2 ... While-Programme ... 202
9.3 ... Gödelnummern ... 218
9.4 ... Das universelle While-Programm ... 220
9.5 ... Das schrittbeschränkte universelle While-Programm ... 223
9.6 ... Diagonalisierung und min-Suche ... 224
9.7 ... Prädikate für semi-entscheidbare Sprachen ... 226
9.8 ... Semi-Entscheidbarkeit vs. Aufzählbarkeit ... 227
9.9 ... Das S-m-n-Theorem ... 228
9.10 ... Das kleenesche Rekursionstheorem ... 230
9.11 ... Weitere Modelle und Charakterisierungen ... 233
9.12 ... Aufgaben ... 233
9.13 ... Lösungen ... 235
10. Nicht Berechenbares ... 241
10.1 ... Beweise mit KRT ... 243
10.2 ... Der Satz von Rice ... 244
10.3 ... Reduktionen ... 246
10.4 ... RE-Vollständigkeit ... 250
10.5 ... Ausblick: Die arithmetische Hierarchie ... 251
10.6 ... Aufgaben ... 252
10.7 ... Lösungen ... 254
TEIL II. Algorithmik ... 259
11. Einführung in Algorithmik ... 261
12. Obere Schranken für Laufzeiten ... 263
12.1 ... Das Maschinenmodell ... 264
12.2 ... Die Laufzeit eines Algorithmus ... 267
12.3 ... Die Größe einer Eingabe ... 268
12.4 ... Die Landau-Notation ... 268
12.5 ... Aufgaben ... 271
12.6 ... Lösungen ... 272
13. Laufzeiten von Datenstrukturen ... 275
13.1 ... Arrays ... 275
13.2 ... Listen ... 277
13.3 ... Verschachtelte Datenstrukturen und Graphen ... 279
13.4 ... Aufgaben ... 281
13.5 ... Lösungen ... 282
14. Brute-Force-Algorithmen ... 285
14.1 ... Lineare Suche ... 286
14.2 ... Backtracking/Tiefensuche ... 288
14.3 ... Aufgaben ... 292
14.4 ... Lösungen ... 293
15. Greedy-Algorithmen ... 295
15.1 ... Beweis mit Austauschargument ... 296
15.2 ... Greedy stays ahead ... 302
15.3 ... Aufgaben ... 304
15.4 ... Lösungen ... 306
16. Divide and Conquer ... 313
16.1 ... Mergesort ... 314
16.2 ... Binäre Suche ... 319
16.3 ... Multiplikation großer Zahlen ... 321
16.4 ... Das Mastertheorem ... 325
16.5 ... Ausblick ... 326
16.6 ... Aufgaben ... 327
16.7 ... Lösungen ... 329
17. Dynamische Programmierung ... 335
17.1 ... Fibonacci-Zahlen ... 336
17.2 ... Rückgeld geben ... 337
17.3 ... Der Algorithmus von Dijkstra ... 341
17.4 ... Aufgaben ... 344
17.5 ... Lösungen ... 346
18. Amortisierte Analyse ... 351
18.1 ... Dynamische Arrays ... 351
18.2 ... Guthabenmethode ... 353
18.3 ... Ausblick ... 353
TEIL III. Komplexitätstheorie ... 355
19. Einführung in die Komplexitätstheorie ... 357
19.1 ... Die Komplexität eines Problems ... 358
19.2 ... Bedingte Schranken ... 358
19.3 ... Auswege für schwierige Probleme ... 359
20. Beweistechniken für untere Schranken ... 361
20.1 ... Die Ausgabegröße ... 362
20.2 ... Das informationstheoretische Argument ... 363
20.3 ... Das Adversary-Argument ... 367
20.4 ... Reduktionen ... 370
20.5 ... Aufgaben ... 372
20.6 ... Lösungen ... 374
21. P vs. NP: Bedingte untere Schranken ... 377
21.1 ... Die Komplexitätsklasse P ... 378
21.2 ... Die Komplexitätsklasse NP ... 380
21.3 ... Polynomialzeitreduktionen ... 388
21.4 ... NP-schwere und NP-vollständige Probleme ... 392
21.5 ... Ausblick: Mehr NP-vollständige Probleme ... 404
21.6 ... Aufgaben ... 405
21.7 ... Lösungen ... 406
22. Ausblick: Parametrisierte Analyse ... 408
Index ... 410
1.1 ... Kompetenzen für die theoretische Arbeit ... 16
1.2 ... Themen der theoretischen Informatik ... 18
1.3 ... Anleitung fürs Buch ... 20
1.4 ... Danksagungen ... 21
2. Mathematische Notation ... 23
2.1 ... Logische Aussagen ... 24
2.2 ... Mengen ... 27
2.3 ... Relationen und Funktionen ... 32
2.4 ... Graphen ... 37
2.5 ... Unendlichkeiten und Abzählbarkeit ... 40
2.6 ... Beweistechniken ... 42
2.7 ... Aufgaben ... 57
2.8 ... Lösungen ... 58
TEIL I. Berechenbarkeit und formale Sprachen ... 65
3. Einführung in die Berechenbarkeitstheorie ... 67
3.1 ... Algorithmus ... 68
3.2 ... Zu viele Funktionen ... 69
3.3 ... Das Halteproblem ... 70
3.4 ... Kontrollfragen ... 72
3.5 ... Antworten ... 72
4. Problemtypen ... 73
4.1 ... Formalisierung von Problemen ... 73
4.2 ... Funktionen berechnen ... 75
4.3 ... Datencodierung ... 75
4.4 ... Sprachen entscheiden ... 78
4.5 ... Problemklassen der Berechenbarkeitstheorie ... 79
4.6 ... Aufgaben ... 82
4.7 ... Lösungen ... 83
5. Einführung in formale Sprachen ... 85
5.1 ... Definition ... 85
5.2 ... Die Chomsky-Hierarchie ... 88
5.3 ... Aufgaben ... 89
5.4 ... Lösungen ... 90
6. Reguläre Sprachen ... 91
6.1 ... Deterministische endliche Automaten ... 92
6.2 ... Nichtdeterministische endliche Automaten ... 103
6.3 ... Grammatiken ... 111
6.4 ... Reguläre Ausdrücke ... 120
6.5 ... Abschlusseigenschaften ... 127
6.6 ... Entscheidungsprobleme auf regulären Sprachen ... 132
6.7 ... Äquivalenzklassenzerlegung ... 134
6.8 ... Nichtreguläre Sprachen ... 139
6.9 ... Ausblick ... 144
6.10 ... Aufgaben ... 144
6.11 ... Lösungen ... 149
7. Kontextfreie Sprachen ... 161
7.1 ... Kontextfreie Grammatiken ... 162
7.2 ... Eindeutige Ableitungsbäume ... 164
7.3 ... Chomsky-Normalform ... 166
7.4 ... Exkurs: Kellerautomaten ... 170
7.5 ... Abschlusseigenschaften ... 175
7.6 ... Entscheidungsprobleme auf kontextfreien Sprachen ... 176
7.7 ... Nicht-kontextfreie Sprachen ... 181
7.8 ... Ausblick ... 183
7.9 ... Aufgaben ... 184
7.10 ... Lösungen ... 186
8. Kontextsensitive Sprachen ... 193
8.1 ... Kontextsensitive und monotone Grammatiken ... 194
8.2 ... Das Wortproblem auf kontextsensitiven Sprachen ... 195
9. Aufzählbare Sprachen ... 197
9.1 ... Turingmaschinen ... 199
9.2 ... While-Programme ... 202
9.3 ... Gödelnummern ... 218
9.4 ... Das universelle While-Programm ... 220
9.5 ... Das schrittbeschränkte universelle While-Programm ... 223
9.6 ... Diagonalisierung und min-Suche ... 224
9.7 ... Prädikate für semi-entscheidbare Sprachen ... 226
9.8 ... Semi-Entscheidbarkeit vs. Aufzählbarkeit ... 227
9.9 ... Das S-m-n-Theorem ... 228
9.10 ... Das kleenesche Rekursionstheorem ... 230
9.11 ... Weitere Modelle und Charakterisierungen ... 233
9.12 ... Aufgaben ... 233
9.13 ... Lösungen ... 235
10. Nicht Berechenbares ... 241
10.1 ... Beweise mit KRT ... 243
10.2 ... Der Satz von Rice ... 244
10.3 ... Reduktionen ... 246
10.4 ... RE-Vollständigkeit ... 250
10.5 ... Ausblick: Die arithmetische Hierarchie ... 251
10.6 ... Aufgaben ... 252
10.7 ... Lösungen ... 254
TEIL II. Algorithmik ... 259
11. Einführung in Algorithmik ... 261
12. Obere Schranken für Laufzeiten ... 263
12.1 ... Das Maschinenmodell ... 264
12.2 ... Die Laufzeit eines Algorithmus ... 267
12.3 ... Die Größe einer Eingabe ... 268
12.4 ... Die Landau-Notation ... 268
12.5 ... Aufgaben ... 271
12.6 ... Lösungen ... 272
13. Laufzeiten von Datenstrukturen ... 275
13.1 ... Arrays ... 275
13.2 ... Listen ... 277
13.3 ... Verschachtelte Datenstrukturen und Graphen ... 279
13.4 ... Aufgaben ... 281
13.5 ... Lösungen ... 282
14. Brute-Force-Algorithmen ... 285
14.1 ... Lineare Suche ... 286
14.2 ... Backtracking/Tiefensuche ... 288
14.3 ... Aufgaben ... 292
14.4 ... Lösungen ... 293
15. Greedy-Algorithmen ... 295
15.1 ... Beweis mit Austauschargument ... 296
15.2 ... Greedy stays ahead ... 302
15.3 ... Aufgaben ... 304
15.4 ... Lösungen ... 306
16. Divide and Conquer ... 313
16.1 ... Mergesort ... 314
16.2 ... Binäre Suche ... 319
16.3 ... Multiplikation großer Zahlen ... 321
16.4 ... Das Mastertheorem ... 325
16.5 ... Ausblick ... 326
16.6 ... Aufgaben ... 327
16.7 ... Lösungen ... 329
17. Dynamische Programmierung ... 335
17.1 ... Fibonacci-Zahlen ... 336
17.2 ... Rückgeld geben ... 337
17.3 ... Der Algorithmus von Dijkstra ... 341
17.4 ... Aufgaben ... 344
17.5 ... Lösungen ... 346
18. Amortisierte Analyse ... 351
18.1 ... Dynamische Arrays ... 351
18.2 ... Guthabenmethode ... 353
18.3 ... Ausblick ... 353
TEIL III. Komplexitätstheorie ... 355
19. Einführung in die Komplexitätstheorie ... 357
19.1 ... Die Komplexität eines Problems ... 358
19.2 ... Bedingte Schranken ... 358
19.3 ... Auswege für schwierige Probleme ... 359
20. Beweistechniken für untere Schranken ... 361
20.1 ... Die Ausgabegröße ... 362
20.2 ... Das informationstheoretische Argument ... 363
20.3 ... Das Adversary-Argument ... 367
20.4 ... Reduktionen ... 370
20.5 ... Aufgaben ... 372
20.6 ... Lösungen ... 374
21. P vs. NP: Bedingte untere Schranken ... 377
21.1 ... Die Komplexitätsklasse P ... 378
21.2 ... Die Komplexitätsklasse NP ... 380
21.3 ... Polynomialzeitreduktionen ... 388
21.4 ... NP-schwere und NP-vollständige Probleme ... 392
21.5 ... Ausblick: Mehr NP-vollständige Probleme ... 404
21.6 ... Aufgaben ... 405
21.7 ... Lösungen ... 406
22. Ausblick: Parametrisierte Analyse ... 408
Index ... 410