Vor Ort
Merkzettel Warenkorb
  • Produktbild: Theoretische Informatik
  • Produktbild: Theoretische Informatik

Theoretische Informatik Eine kompakte Einführung

Aus der Reihe Springer-Lehrbuch

34,50 €

inkl. gesetzl. MwSt., Versandkostenfrei

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

11.08.2003

Verlag

Springer Berlin

Seitenzahl

227

Maße (L/B/H)

23,5/15,5/1,4 cm

Gewicht

371 g

Auflage

2. Auflage 2003

Sprache

Deutsch

ISBN

978-3-540-01313-6

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

11.08.2003

Verlag

Springer Berlin

Seitenzahl

227

Maße (L/B/H)

23,5/15,5/1,4 cm

Gewicht

371 g

Auflage

2. Auflage 2003

Sprache

Deutsch

ISBN

978-3-540-01313-6

Herstelleradresse

Springer-Verlag KG
Sachsenplatz 4-6
1201 Wien
AT

Email: GPSR Kontakt

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)

Weitere Artikel finden Sie in
  • Produktbild: Theoretische Informatik
  • Produktbild: Theoretische Informatik
  • 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.1.1 Definition und Beispiele.- 2.1.2 RAM-Berechenbarkeit.- 2.2 Die Programmiersprache RIES.- 2.2.1 Die Syntax und Semantik von RIES.- 2.2.2 RIES-Berechenbarkeit.- 2.2.3 MINI-RIES und der Compiler.- 2.3 Zur Geschichte des Algorithmenbegriffes.- 2.4 Turingmaschinen.- 2.4.1 Definition und Beispiele.- 2.4.2 Turing-Berechenbarkeit.- 2.4.3 Äquivalenz zu anderen Berechenbarkeitsbegriffen.- 2.5 Partiell-rekursive Funktionen.- 2.5.1 Primitiv-rekursive Funktionen.- 2.5.2 Die Ackermannfunktion.- 2.5.3 Partiell-rekursive Funktionen.- 2.5.4 Äquivalenz zu anderen Berechenbarkeitsbegriffen.- 2.6 Der Hauptsatz der Algorithmentheorie.- 2.7 Entscheidbarkeit und Aufzählbarkeit.- 2.7.1 Definitionen und einfache Resultate.- 2.7.2 Das Halteproblem.- 2.8 Aufgaben.- 3 Komplexität.- 3.1 Die Laufzeit von Algorithmen.- 3.2 Die Klasse P.- 3.2.1 Polynomialzeit ist vom Maschinentyp unabhängig.- 3.2.2 Abschlußeigenschaften der Klassen P und FP.- 3.2.3 Spezielle Polynomialzeitfunktionen und -mengen.- 3.3 Die Klasse NP.- 3.3.1 Das Durchmustern eines Lösungsraumes.- 3.3.2 Abschlußeigenschaften der Klassen NP.- 3.3.3 NP und exponentielle Laufzeit.- 3.3.4 Nichtdeterministische Polynomialzeitmaschinen.- 3.4 NP-vollständige Mengen.- 3.4.1 Polynomialzeit-Reduzierbarkeit.- 3.4.2 NP-Vollständigkeit.- 3.4.3 Eine Liste NP-vollständiger Probleme.- 3.5 Speicherplatzkomplexität.- 3.5.1 Der Speicherplatzbedarf von Algorithmen.- 3.5.2 Die Klassen LIN und NLIN.- 3.6 Wie schwierig können Probleme sein?.- 3.7 Aufgaben.- 4 Boolesche Funktionen.- 4.1 Einfache Eigenschaften boolescher Funktionen.- 4.1.1 Definition und Besipiele.- 4.1.2 Erzeugung und Vollständigkeit.- 4.2 Aussagenlogik.- 4.2.1 Syntax und Semantik.- 4.2.2 Äquivalenz, Allgemeingültigkeit und Erfüllbarkeit.- 4.2.3 Wichtige aussagenlogische Äquivalenzen.- 4.3 Kombinatorische Schaltkreise.- 4.3.1 Definition und Beispiele.- 4.3.2 Welche Funktionen werden durch kombinatorische Schaltkreise berechnet?.- 4.4 Das Postsche Vollständigkeitskriterium.- 4.4.1 Die Postschen Klassen.- 4.4.2 Das Kriterium.- 4.5 Aufgaben.- 5 Endliche Automaten.- 5.1 Endliche Automaten mit Ausgabe.- 5.1.1 Definition und Beispiele.- 5.1.2 Welche Funktionen werden von endlichen Automaten berechnet?.- 5.2 Logische Schaltkreise.- 5.2.1 Definition und Beispiele.- 5.2.2 Logische Schaltkreise und endliche Automaten.- 5.3 Endliche Automaten ohne Ausgabe.- 5.3.1 Deterministische endliche Automaten.- 5.3.2 Nichtdeterministische endliche Automaten.- 5.3.3 Die Äquivalenz deterministischer und nichtdeterministischer endlicher Automaten.- 5.3.4 Die Klasse EA der von endlichen Automaten akzeptierten Mengen.- 5.4 Reguläre Mengen.- 5.4.1 Definition und Beispiele.- 5.4.2 Reguläre Mengen und endliche Automaten.- 5.5 Aufgaben.- 6 Formale Sprachen.- 6.1 Die Chomsky-Hierarchie.- 6.2 Sprachen vom Typ 3.- 6.2.1 Reguläre Sprachen und Sprachen vom Typ 3.- 6.2.2 Das Pumping-Lemma für reguläre Sprachen.- 6.3 Kontextfreie Sprachen.- 6.3.1 Die Hinzunahme von e-Regeln.- 6.3.2 Grammatiken in Chomsky-Normalform.- 6.3.3 Das Pumping-Lemma für kontextfreie Sprachen.- 6.3.4 Abschlußeigenschaften der Klasse der kontextfreien Sprachen.- 6.3.5 Die Zeitkomplexität kontextfreier Sprachen.- 6.3.6 Kellerautomaten.- 6.4 Kontextsensitive Sprachen.- 6.4.1 Nichtverkürzende Grammatiken.- 6.4.2 Kontextsensitive Sprachen und linearer Speicherplatz.- 6.4.3 Abschlußeigenschaften der Klasse der kontextsensitiven Sprachen.- 6.5 Sprachen vom Typ 0.- 6.5.1 Sprachen vom Typ 0 und aufzählbare Mengen.- 6.5.2 Abschlußeigenschaften der Klasse der Sprachen vom Typ 0.- 6.6 Zusammenfassung.- 6.7 Aufgaben.- Weiterführende Literatur.