Theoretische Informatik : Formale Sprachen, Berechenbarkeit, Komplexitatstheorie,Algorithmik, Kommunikation und Kryptographie

Cover......Page 1
Leitfäden der Informatik......Page 3
Theoretische
Informatik,
4. Auflage......Page 4
ISBN 9783834806505......Page 5
Vorwort......Page 7
Vorwort zur zweiten Auflage......Page 10
Vorwort zur dritten Auflage......Page 12
Vorwort zur vierten Auflage......Page 14
Inhalt......Page 15
1.1 Informatik als wissenschaftliche Disziplin......Page 18
1.2 Eine faszinierende Theorie......Page 23
1.3 F¨ur die Studierenden......Page 27
1.4 Aufbau des Lehrmaterials......Page 30
2.1 Zielsetzung......Page 33
2.2 Alphabete, W¨orter und Sprachen......Page 34
2.3 Algorithmische Probleme......Page 46
2.4 Kolmogorov-Komplexit¨at......Page 57
2.5 Zusammenfassung und Ausblick......Page 72
3.1 Zielsetzung......Page 76
3.2 Die Darstellungen der endlichen Automaten......Page 77
3.3 Simulationen......Page 94
3.4 Beweise der Nichtexistenz......Page 100
3.5 Nichtdeterminismus......Page 109
3.6 Zusammenfassung......Page 122
4.1 Zielsetzung......Page 126
4.2 Das Modell der Turingmaschine......Page 127
4.3 Mehrband-Turingmaschinen und Church’sche These......Page 138
4.4 Nichtdeterministische Turingmaschinen......Page 149
4.5 Kodierung von Turingmaschinen......Page 155
4.6 Zusammenfassung......Page 158
5.1 Zielsetzung......Page 162
5.2 Die Methode der Diagonalisierung......Page 163
5.3 Die Methode der Reduktion......Page 173
5.4 Satz von Rice......Page 186
5.5 Das Post’sche Korrespondenzproblem......Page 191
5.6 Die Methode der Kolmogorov-Komplexit¨at......Page 200
5.7 Zusammenfassung......Page 204
6.1 Zielsetzung......Page 207
6.2 Komplexit¨atsmaße......Page 209
6.3 Komplexit¨atsklassen und die Klasse P......Page 216
6.4 Nichtdeterministische Komplexit¨atsmaße......Page 225
6.5 Die Klasse NP und Beweisverifikation......Page 232
6.6 NP-Vollst¨andigkeit......Page 237
6.7 Zusammenfassung......Page 260
7.1 Zielsetzung......Page 263
7.2 Pseudopolynomielle Algorithmen......Page 265
7.3 Approximationsalgorithmen......Page 272
7.4 Lokale Suche......Page 280
7.5 Simulated Annealing......Page 286
7.6 Zusammenfassung......Page 290
8.1 Zielsetzung......Page 293
8.2 Elementare Wahrscheinlichkeitstheorie......Page 295
8.3 Ein randomisiertes Kommunikationsprotokoll......Page 299
8.4 Die Methode der h¨aufigen Zeugen und der randomisierte Primzahltest......Page 303
8.5 Die Methode der Fingerabdr¨ucke und die ¨Aquivalenz von zwei Polynomen......Page 309
8.6 Zusammenfassung......Page 316
9.1 Zielsetzung......Page 319
9.2 Klassische Kryptosysteme......Page 320
9.3 Public-Key-Kryptosysteme und RSA......Page 322
9.4 Digitale Unterschriften......Page 328
9.5 Interaktive Beweissysteme und Zero-Knowledge-Beweise......Page 332
9.6 Entwurf eines Kommunikationsnetzes......Page 337
9.7 Zusammenfassung......Page 347
10.1 Zielsetzung......Page 349
10.2 Das Konzept der Grammatiken......Page 351
10.3 Regul¨are Grammatiken und endliche Automaten......Page 363
10.4 Kontextfreie Grammatiken und Kellerautomaten......Page 377
10.5 Allgemeine Grammatiken und Turingmaschinen......Page 403
10.6 Zusammenfassung......Page 406
Literaturverzeichnis......Page 409
Sachverzeichnis......Page 414