Warenkorb
€ 0,00 0 Buch dabei,
portofrei
Theoretische Informatik als Buch
PORTO-
FREI

Theoretische Informatik

Eine kompakte Einführung. 'Springer-Lehrbuch'. 2. , überarbeitete Auflage 2003. 50 Abbildungen.
Buch (kartoniert)
Diese kompakte Einführung in die Theoretische Informatik stellt die wichtigsten Modelle für zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt:

Welche Probleme sind algorithmisch lösbar? (Theorie der Berechenbar … weiterlesen
Dieses Buch ist auch verfügbar als:
Buch

29,99*

inkl. MwSt.
Portofrei
Sofort lieferbar
Theoretische Informatik als Buch

Produktdetails

Titel: Theoretische Informatik
Autor/en: Klaus W. Wagner

ISBN: 354001313X
EAN: 9783540013136
Eine kompakte Einführung.
'Springer-Lehrbuch'.
2. , überarbeitete Auflage 2003.
50 Abbildungen.
Springer-Verlag GmbH

11. August 2003 - kartoniert - X

Beschreibung

Diese kompakte Einführung in die Theoretische Informatik stellt die wichtigsten 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)

In der Erarbeitung dieser Themen wird der Abstraktionsprozeß von den realen Gegenständen der Informatik zu den in der Theoretischen Infromatik etabliertern Modellen, wie z.B. Random-Access-Maschinen, Turingmaschinen und endliche Automaten, nachvollzogen und umgekehrt verdeutlicht, was diese Modelle aufgrund der über sie gewonnenen Erkenntnisse für die Praxis leisten können.

Inhaltsverzeichnis

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.

Mehr aus dieser Reihe

zurück
Mathematische Formelsammlung
Buch (kartoniert)
von Lothar Papula
Forschungsmethoden in Psychologie und Sozialwissenschaften - für Bachelor
Buch (kartoniert)
von Walter Hussy, Ma…
Elektrische Messtechnik
Buch
von Reinhard Lerch
Basiswissen Pharmakologie
Buch (kartoniert)
von Roland Seifert
Biologie von Parasiten
Buch (kartoniert)
von Richard Lucius, …
vor
Servicehotline
089 - 70 80 99 47

Mo. - Fr. 8.00 - 20.00 Uhr
Sa. 10.00 - 20.00 Uhr
Filialhotline
089 - 30 75 75 75

Mo. - Sa. 9.00 - 20.00 Uhr
Bleiben Sie in Kontakt:
Sicher & bequem bezahlen:
akzeptierte Zahlungsarten: Überweisung, offene Rechnung,
Visa, Master Card, American Express, Paypal
Zustellung durch:
* Alle Preise verstehen sich inkl. der gesetzlichen MwSt. Informationen über den Versand und anfallende Versandkosten finden Sie hier.
** Deutschsprachige eBooks und Bücher dürfen aufgrund der in Deutschland geltenden Buchpreisbindung und/oder Vorgaben von Verlagen nicht rabattiert werden. Soweit von uns deutschsprachige eBooks und Bücher günstiger angezeigt werden, wurde bei diesen kürzlich von den Verlagen der Preis gesenkt oder die Buchpreisbindung wurde für diese Titel inzwischen aufgehoben. Angaben zu Preisnachlässen beziehen sich auf den dargestellten Vergleichspreis.