Hromkovic Algorithmische Konzepte der Informatik

Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie. Eine Einführung
2001
ISBN: 978-3-322-91131-5
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 286 Seiten, eBook

Reihe: XLeitfäden der Informatik

Dieses Buch ist eine einfache Einführung in algorithmische Grundkonzepte der Theoretischen Informatik. Die Theoretische Informatik ist weltweit ein fester Bestandteil des Informatikstudiums. Im Unterschied zu den ingenieursmäßig geprägten Gebieten der Praktischen und der Technischen Informatik hebt die Theoretische Informatik mehr die naturwissenschaftlichen und mathemati schen Aspekte der Informatik hervor. Gerade die mathematische Prägung ist oft ein Grund dafür, dass die Theoretische Informatik für zu schwer gehal ten wird und dadurch ein nicht gerade beliebter Teil der Ausbildung ist. Der Schwierigkeitsgrad der Theoretischen Informatik ist aber meiner Meinung nach nicht der einzige Grund ihrer Unbeliebtheit, insbesondere wenn die Studieren den in ihrer Beurteilung ausserdem noch das Prädikat "schwach motiviert" oder sogar "langweilig" verwenden. Das könnte auch damit zusammenhängen, dass sich die Einführung in die Theoretische Informatik im Grundstudium an vielen deutschen Hochschulen auf den klassischen Stoff der Berechenbarkeit, der Theorie der formalen Sprachen und der abstrakten Komplexitätstheorie be man dabei überwiegend nur die Konzepte und Ansichten, die schränkt. Dass vor dem Jahr 1970 entstanden sind, vermittelt, dürfte alleine nicht schlimm sein. Es führt aber oft dazu, daß man mit einer einzigen Motivation zu viele Vorlesungen der Art Definition - Satz - Beweis absolvieren muß und so hal biert sich die Wichtigkeit dieser Motivation in den Augen der Studierenden mit jeder weiteren Vorlesung, die anknüpft, ohne eine eigene Motivation zu bringen. Um Abhilfe von diesem Zustand zu schaffen, muß man sich die Entwicklung der Theoretischen Informatik in den letzten 30 Jahren ansehen.

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Hromkovic, Juraj

Inhaltsverzeichnis

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 undRSA.- 9.4 Interaktive Beweissysteme und Zero-Knowledge-Beweise.- 9.5 Zusammenfassung.

Über Autor(innen)

Prof. Dr. Juraj Hromkovic, RWTH Aachen