UID:
almahu_9948191529702882
Umfang:
286 S.
,
online resource.
Ausgabe:
1st ed. 2001.
ISBN:
9783322911315
Serie:
XLeitfäden der Informatik,
Inhalt:
Das Buch versteht sich als eine einfache Einführung in die grundlegenden algorithmischen Konzepte der Informatik. Die Konzepte werden in ihrer historischen Entwicklung und größeren Zusammenhängen dargestellt, um so die eigentliche Faszination der Informatik, die viel kontraintuitive Überraschungen bereithält, zu wecken.
Anmerkung:
1 Einleitung -- 1.1 Informatik als wissenschaftliche Disziplin -- 1.2 Eine faszinierende Theorie -- 1.3 Für die Studierenden -- 1.4 Aufbau des Lehrmaterials -- 2 Alphabete, Wörter, Sprachen und Aufgaben -- 2.1 Zielsetzung -- 2.2 Alphabete, Wörter und Sprachen -- 2.3 Algorithmische Probleme -- 2.4 Kolmogorov-Komplexität -- 2.5 Zusammenfassung und Ausblick -- 3 Endliche Automaten -- 3.1 Zielsetzung -- 3.2 Die Darstellungen der endlichen Automaten -- 3.3 Simulationen -- 3.4 Beweise der Nichtexistenz -- 3.5 Nichtdeterminismus -- 3.6 Zusammenfassung -- 4 Turingmaschinen -- 4.1 Zielsetzung -- 4.2 Das Modell der Turingmaschine -- 4.3 Mehrband-Turingmaschinen und Church’sche These -- 4.4 Nichtdeterministische Turingmaschinen -- 4.5 Kodierung von Turingmaschinen -- 4.6 Zusammenfassung -- 5 Berechenbarkeit -- 5.1 Zielsetzung -- 5.2 Die Methode der Diagonalisierung -- 5.3 Die Methode der Reduktion -- 5.4 Satz von Rice -- 5.5 Das Post’sche Korrespondenzproblem -- 5.6 Die Methode der Kolmogorov-Komplexität -- 5.7 Zusammenfassung -- 6 Komplexitätstheorie -- 6.1 Zielsetzung -- 6.2 Komplexitätsmaße -- 6.3 Komplexitätsklassen und die Klasse P -- 6.4 Nichtdeterministische Komplexitätsmaße -- 6.5 Die Klasse NP und Beweisverifikation -- 6.6 NP-Vollständigkeit -- 6.7 Zusammenfassung -- 7 Algorithmik für schwere Probleme -- 7.1 Zielsetzung -- 7.2 Pseudopolynomielle Algorithmen -- 7.3 Approximationsalgorithmen -- 7.4 Lokale Suche -- 7.5 Simulated Annealing -- 7.6 Zusammenfassung -- 8 Randomisierung -- 8.1 Zielsetzung -- 8.2 Elementare Wahrscheinlichkeitstheorie -- 8.3 Ein randomisiertes Kommunikationsprotokoll -- 8.4 Die Methode der häufigen Zeugen und der randomisierte Primzahltest -- 8.5 Zusammenfassung -- 9 Kommunikation und Kryptographie -- 9.1 Einleitung -- 9.2 Klassische Kryptosysteme -- 9.3 Public-Key-Kryptosysteme und RSA -- 9.4 Interaktive Beweissysteme und Zero-Knowledge-Beweise -- 9.5 Zusammenfassung.
In:
Springer eBooks
Weitere Ausg.:
Printed edition: ISBN 9783519003328
Sprache:
Deutsch
DOI:
10.1007/978-3-322-91131-5
URL:
https://doi.org/10.1007/978-3-322-91131-5
Bookmarklink
