Ebook: Komplexitätstheorie: Grenzen der Effizienz von Algorithmen
Author: Prof. Dr. Ingo Wegener (auth.)
- Tags: Algorithm Analysis and Problem Complexity, Logics and Meanings of Programs, Mathematical Logic and Formal Languages, Coding and Information Theory
- Series: Springer-Lehrbuch
- Year: 2003
- Publisher: Springer-Verlag Berlin Heidelberg
- Edition: 1
- Language: German
- pdf
Die Komplexitätstheorie untersucht die Mindestressourcen zur Lösung algorithmischer Probleme und damit die Grenzen des mit den vorhandenen Ressourcen Machbaren. Ihre Ergebnisse verhindern, dass sich die Suche nach effizienten Algorithmen auf unerreichbare Ziele konzentriert. Insofern hat die NP-Vollständigkeitstheorie die Entwicklung der gesamten Informatik beeinflusst. Die Komplexitätstheorie reagiert auf alle neuen algorithmischen Konzepte.
Dieses Lehrbuch wählt einen Einstieg in die Komplexitätstheorie, bei dem die Randomisierung als Schlüsselkonzept angesehen wird. Die Auswahl der Inhalte betont den Bezug zu konkreten Anwendungen und rückt die Bedeutung der Komplexitätstheorie für eine moderne Informatik in den Mittelpunkt.
Die Komplexit?tstheorie untersucht die Mindestressourcen zur L?sung algorithmischer Probleme und damit die Grenzen des mit den vorhandenen Ressourcen Machbaren. Ihre Ergebnisse verhindern, dass sich die Suche nach effizienten Algorithmen auf unerreichbare Ziele konzentriert. Insofern hat die NP-Vollst?ndigkeitstheorie die Entwicklung der gesamten Informatik beeinflusst. Die Komplexit?tstheorie reagiert auf alle neuen algorithmischen Konzepte.
Dieses Lehrbuch w?hlt einen Einstieg in die Komplexit?tstheorie, bei dem die Randomisierung als Schl?sselkonzept angesehen wird. Die Auswahl der Inhalte betont den Bezug zu konkreten Anwendungen und r?ckt die Bedeutung der Komplexit?tstheorie f?r eine moderne Informatik in den Mittelpunkt.
Die Komplexit?tstheorie untersucht die Mindestressourcen zur L?sung algorithmischer Probleme und damit die Grenzen des mit den vorhandenen Ressourcen Machbaren. Ihre Ergebnisse verhindern, dass sich die Suche nach effizienten Algorithmen auf unerreichbare Ziele konzentriert. Insofern hat die NP-Vollst?ndigkeitstheorie die Entwicklung der gesamten Informatik beeinflusst. Die Komplexit?tstheorie reagiert auf alle neuen algorithmischen Konzepte.
Dieses Lehrbuch w?hlt einen Einstieg in die Komplexit?tstheorie, bei dem die Randomisierung als Schl?sselkonzept angesehen wird. Die Auswahl der Inhalte betont den Bezug zu konkreten Anwendungen und r?ckt die Bedeutung der Komplexit?tstheorie f?r eine moderne Informatik in den Mittelpunkt.
Content:
Front Matter....Pages I-X
Einleitung....Pages 1-11
Algorithmische Probleme und ihre Komplexit?t....Pages 13-27
Die grundlegenden Komplexit?tsklassen....Pages 29-46
Reduktionen — algorithmische Beziehungen zwischen Problemen....Pages 47-67
Die NP-Vollst?ndigkeitstheorie....Pages 69-82
NP-vollst?ndige und NP-?quivalente Probleme....Pages 83-93
Die Komplexit?tsanalyse von Problemen....Pages 95-104
Die Komplexit?t von Approximationsproblemen — klassische Resultate....Pages 105-121
Die Komplexit?t von Black-Box-Problemen....Pages 123-134
Weitere Komplexit?tsklassen und Beziehungen zwischen den Komplexit?tsklassen....Pages 135-152
Interaktive Beweise....Pages 153-167
Das PCP-Theorem und die Komplexit?t von Approximationsproblemen....Pages 169-193
Weitere klassische Themen der Komplexit?tstheorie....Pages 195-211
Die Komplexit?t von nichtuniformen Problemen....Pages 213-230
Kommunikationskomplexit?t....Pages 231-263
Die Komplexit?t boolescher Funktionen....Pages 265-291
Schlussbemerkungen....Pages 293-294
Back Matter....Pages 293-321
Die Komplexit?tstheorie untersucht die Mindestressourcen zur L?sung algorithmischer Probleme und damit die Grenzen des mit den vorhandenen Ressourcen Machbaren. Ihre Ergebnisse verhindern, dass sich die Suche nach effizienten Algorithmen auf unerreichbare Ziele konzentriert. Insofern hat die NP-Vollst?ndigkeitstheorie die Entwicklung der gesamten Informatik beeinflusst. Die Komplexit?tstheorie reagiert auf alle neuen algorithmischen Konzepte.
Dieses Lehrbuch w?hlt einen Einstieg in die Komplexit?tstheorie, bei dem die Randomisierung als Schl?sselkonzept angesehen wird. Die Auswahl der Inhalte betont den Bezug zu konkreten Anwendungen und r?ckt die Bedeutung der Komplexit?tstheorie f?r eine moderne Informatik in den Mittelpunkt.
Content:
Front Matter....Pages I-X
Einleitung....Pages 1-11
Algorithmische Probleme und ihre Komplexit?t....Pages 13-27
Die grundlegenden Komplexit?tsklassen....Pages 29-46
Reduktionen — algorithmische Beziehungen zwischen Problemen....Pages 47-67
Die NP-Vollst?ndigkeitstheorie....Pages 69-82
NP-vollst?ndige und NP-?quivalente Probleme....Pages 83-93
Die Komplexit?tsanalyse von Problemen....Pages 95-104
Die Komplexit?t von Approximationsproblemen — klassische Resultate....Pages 105-121
Die Komplexit?t von Black-Box-Problemen....Pages 123-134
Weitere Komplexit?tsklassen und Beziehungen zwischen den Komplexit?tsklassen....Pages 135-152
Interaktive Beweise....Pages 153-167
Das PCP-Theorem und die Komplexit?t von Approximationsproblemen....Pages 169-193
Weitere klassische Themen der Komplexit?tstheorie....Pages 195-211
Die Komplexit?t von nichtuniformen Problemen....Pages 213-230
Kommunikationskomplexit?t....Pages 231-263
Die Komplexit?t boolescher Funktionen....Pages 265-291
Schlussbemerkungen....Pages 293-294
Back Matter....Pages 293-321
....