Klaus W. Wagner

Theoretische Informatik (eBook, PDF)

Eine kompakte Einführung

• Format: PDF

Produktbeschreibung

Die kompakte Einführung stellt Modelle für zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt: Welche Probleme sind algorithmisch lösbar? (Theorie der Berechenbarkeit und Entscheidbarkeit). Wie schwierig ist es algorithmische Probleme zu lösen? (Theorie der Berechnungskomplexität, NP-Theorie). Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten). Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen). Viele Beispiele und Aufgaben erleichtern das Verständnis und ermöglichen die Aneignung des Stoffes auch im Selbststudium.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer Berlin Heidelberg
• Seitenzahl: 227
• Erscheinungstermin: 11. März 2013
• Deutsch
• ISBN-13: 9783642554520
• Artikelnr.: 53394591

Autorenporträt

Klaus W. Wagner, Universität Würzburg

Inhaltsangabe

1 Mathematische Grundlagen.- 1.1 Mengen, Relationen, Funktionen und Graphen.- 1.2 Wörter und natürliche Zahlen.- 1.3 Algebraische Erzeugung.- 1.4 Das Induktionsprinzip.- 1.5 Aufgaben.- 2 Berechenbarkeit.- 2.1 Random-Access-Maschinen.- 2.2 Die Programmiersprache RIES.- 2.3 Zur Geschichte des Algorithmenbegriffes.- 2.4 Turingmaschinen.- 2.5 Partiell-rekursive Funktionen.- 2.6 Der Hauptsatz der Algorithmentheorie.- 2.7 Entscheidbarkeit und Aufzählbarkeit.- 2.8 Aufgaben.- 3 Komplexität.- 3.1 Die Laufzeit von Algorithmen.- 3.2 Die Klasse P.- 3.3 Die Klasse NP.- 3.4 NP-vollständige Mengen.- 3.5 Speicherplatzkomplexität.- 3.6 Wie schwierig können Probleme sein?.- 3.7 Aufgaben.- 4 Boolesche Funktionen.- 4.1 Einfache Eigenschaften boolescher Funktionen.- 4.2 Aussagenlogik.- 4.3 Kombinatorische Schaltkreise.- 4.4 Das Postsche Vollständigkeitskriterium.- 4.5 Aufgaben.- 5 Endliche Automaten.- 5.1 Endliche Automaten mit Ausgabe.- 5.2 Logische Schaltkreise.- 5.3 Endliche Automaten ohne Ausgabe.- 5.4 Reguläre Mengen.- 5.5 Aufgaben.- 6 Formale Sprachen.- 6.1 Die Chomsky-Hierarchie.- 6.2 Sprachen vom Typ 3.- 6.3 Kontextfreie Sprachen.- 6.4 Kontextsensitive Sprachen.- 6.5 Sprachen vom Typ 0.- 6.6 Zusammenfassung.- 6.7 Aufgaben.- Weiterführende Literatur.