|
|
|
|
| LEADER |
04319nmm a2200301 u 4500 |
| 001 |
EB000648066 |
| 003 |
EBX01000000000000000501148 |
| 005 |
00000000000000.0 |
| 007 |
cr||||||||||||||||||||| |
| 008 |
140122 ||| ger |
| 020 |
|
|
|a 9783322940049
|
| 245 |
0 |
0 |
|a Theoretische Informatik
|h Elektronische Ressource
|b Eine algorithmenorientierte Einführung
|
| 250 |
|
|
|a 2nd ed. 1993
|
| 260 |
|
|
|a Wiesbaden
|b Vieweg+Teubner Verlag
|c 1993, 1993
|
| 300 |
|
|
|a X, 238 S.
|b online resource
|
| 505 |
0 |
|
|a 3.9 Die Struktur von NP und die polynomielle Hierarchie -- Übungen -- 4 Endliche Automaten -- 4.1 Schaltwerke und endliche Automaten -- 4.2 Die Minimierung endlicher Automaten -- 4.3 Das Pumping-Lemma für endliche Automaten -- 4.4 Nichtdeterministische endliche Automaten -- 4.5 Zwei-Wege Automaten -- 4.6 Effiziente Algorithmen für die Konstruktion endlicher Automaten und die Entscheidung von Eigenschaften regulärer Sprachen -- Übungen -- 5 Grammatiken, die Chomsky-Hierarchie und das Wortproblem -- 5.1 Grammatiken und die Chomsky-Hierarchie -- 5.2 Chomsky-O-Grammatiken und rekursiv aufzählbare Sprachen -- 5.3 Chomsky-3-Grammatiken, reguläre Sprachen und Ausdrücke, lexikalische Analyse -- 5.4 Kontextsensitive Grammatiken und Sprachen -- Übungen -- 6 Kontextfreie Grammatiken und Sprachen -- 6.1 Beispiele kontextfreierSprachen und Syntaxbäume -- 6.2 Die Chomsky-Normalform für kontextfreie Grammatiken -- 6.3 Der Cocke-Younger-Kasami Algorithmus --
|
| 505 |
0 |
|
|a 1 Einleitung -- 2 Turingmaschinen, Churchsche These und Entscheidbarkeit -- 2.1 Registermaschinen und deterministische Turingmaschinen -- 2.2 Techniken zur Programmierung von Turingmaschinen -- 2.3 Simulationen zwischen Turingmaschinen und Registermaschinen -- 2.4 Universelle Turingmaschinen -- 2.5 Die Churchsche These -- 2.6 Die Unentscheidbarkeit des Halteproblems -- 2.7 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen -- 2.8 Die Unentscheidbarkeit des Postschen Korrespondenzproblems -- Übungen -- 3 Die NP-Vollständigkeitstheorie -- 3.1 Die Klasse P -- 3.2 Nichtdeterministische Turingmaschinen und die Klasse NP -- 3.3 NP-Vollständigkeit -- 3.4 Die NP-Vollständigkeit wichtiger Probleme -- 3.5 Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit -- 3.6 Turing-Reduzierbarkeit, NP-harte, NP-leichte und NP-äquivalente Probleme -- 3.7 Eine Komplexitätstheorie für Approximationsalgorithmen -- 3.8 Eine Komplexitätstheorie für probabilistische Algorithmen --
|
| 505 |
0 |
|
|a 6.4 Das Pumping-Lemma und Ogden's Lemma für kontextfreie Sprachen -- 6.5 Effiziente Algorithmen für die Konstruktion kontextfreier Grammatiken und die Entscheidung von Eigenschaften kontextfreier Sprachen -- 6.6 Unentscheidbare Probleme -- 6.7 Eine inhärent mehrdeutige kontextfreie Sprache -- Übungen -- 7 Kellerautomaten und kontextfreie Sprachen -- 7.1 Die Greibach-Normalform für kontextfreie Grammatiken -- 7.2 Kellerautomaten -- 7.3 Kellerautomaten und kontextfreie Sprachen -- 7.4 Weitere effiziente Algorithmen im Zusammenhang mit kontextfreien Sprachen -- Übungen -- 8 Deterministisch kontextfreie Sprachen -- 8.1 Deterministische Kellerautomaten -- 8.2 Bottom-up Syntaxanalysealgorithmen -- 8.3 Eine weitere Charakterisierung von LR(k)-Grammatiken -- 8.4 Die Konstruktion eines LR(k)-Parsers -- 8.5 Deterministische Kellerautomaten und LR(k)-Grammatiken -- Übungen -- 9 Zusammenfassung und Testfragen -- 9.1 Zusammenfassung -- 9.2 Testfragen -- Schriftenverzeichnis
|
| 653 |
|
|
|a Computer science
|
| 653 |
|
|
|a Theory of Computation
|
| 710 |
2 |
|
|a SpringerLink (Online service)
|
| 041 |
0 |
7 |
|a ger
|2 ISO 639-2
|
| 989 |
|
|
|b SBA
|a Springer Book Archives -2004
|
| 490 |
0 |
|
|a XLeitfäden der Informatik
|
| 028 |
5 |
0 |
|a 10.1007/978-3-322-94004-9
|
| 856 |
4 |
0 |
|u https://doi.org/10.1007/978-3-322-94004-9?nosfx=y
|x Verlag
|3 Volltext
|
| 082 |
0 |
|
|a 004.0151
|
| 520 |
|
|
|a Diese Einführung in die zentralen Gebiete der Theoretischen Informatik kann als Text für eine Vorlesung im Grundstudium dienen. Es wird konsequent eine algorithmenorientierte Sichtweise eingenommen, d.h. die konstruktiven Ergebnisse werden in Algorithmen umgesetzt, die praktisch und theoretisch effizient sind. Damit wird eine Brücke zwischen Theorie und Anwendungen geschlagen und der Nutzen theoretischer Betrachtungen verdeutlicht
|