Vor Ort
Merkzettel Warenkorb
Produktbild: Berechenbarkeit Komplexität Logik

Berechenbarkeit Komplexität Logik Algorithmen, Sprachen und Kalküle unter besonderer Berücksichtigung ihrer Komplexität

51,90 €

inkl. gesetzl. MwSt., Versandkostenfrei

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

01.03.1992

Verlag

Vieweg & Teubner

Seitenzahl

499

Maße (L/B/H)

22,9/16,2/2,9 cm

Gewicht

800 g

Auflage

3. verb. und erweiterte Auflage 1992

Sprache

Deutsch

ISBN

978-3-528-28928-7

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

01.03.1992

Verlag

Vieweg & Teubner

Seitenzahl

499

Maße (L/B/H)

22,9/16,2/2,9 cm

Gewicht

800 g

Auflage

3. verb. und erweiterte Auflage 1992

Sprache

Deutsch

ISBN

978-3-528-28928-7

Herstelleradresse

Vieweg+Teubner Verlag
Abraham-Lincoln-Straße 46
65189 Wiesbaden
DE

Email: ProductSafety@springernature.com

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)
  • Produktbild: Berechenbarkeit Komplexität Logik
  • Inhaltsübersicht.- Erstes Buch: Elementare Berechnungstheorie.- A: Mathematischer Algorithmusbegriff.- I Churchsche These.-
    1. Begriffsexplikation Umformungssystem, Rechensystem, Maschine (Syntax und Semantik von Programmen), Turingmaschine, strukturierte (Turing- und Registennaschinen-) Programme (TO, RO).-
    2. Äquivalensatz F??F (RO) ?F (TO)?F(TM), LOOP-Programm-Synthese für primitiv rekursive Funktionen, F (TM) ?F (RO) ?F?.-
    3. Exkurs über Semantik von Programmer Äquivalenz operationaler und denotationaler Semantik für RM-while-Programme, Fixpunktdeutung von Programmen, Beweis des Fixpunktsatzes.-
    4. Erweiterter Äquivalenzsatz simulation anderer Begriffs-explikationen: Modulare Maschinen, 2-Registermaschine, Thue-systeme, Markovalgorithmen, angeordnete Vektoradditionssysteme (Petrinetze), Postsche (kanonische bzw. reguläre) Kalküle, Wangsche nicht-löschende Halbbandmaschine, Wortregistermaschine.-
    5. These von Church.- II Universelle Programme und Rekurslonstheorem.-
    1. Universelle, Programme Kleene-Normalform, akzeptable universelle Programmiersysteme und effektive Programmtransformationen.-
    2. Diagonalisierungsmethode Rekursionstheorem: Fixpunktdeutung (Satz von Rice), Rekursionsdeutung (implizite Definition: rekursive Aufzählung von Fprim, injektive Übersetzungsfunktionen in Gödelnumerierungen, Isomorphiesatz für Gödelnumerierungen, sich selbst reproduzierende Programme), parametrische effektive Version mit unendlich vielen Fixpunkten.- B: Komplexität Algorithmischer Unlösbarkeit.- I Rekursiv Unlösbare Probleme (Reduktionsmethode).-
    1. Halteproblem K Spezialfälle des Satzes von Rice.-
    2. Einfache Reduktionen von K Entscheidungsprobleme berechnungs-universeller Systeme, Postsches Korrespondenzproblem, Dominoproblem, Röddingsches Wegeproblem.- *
    3. Exponentiell diophantische, Gleichungen simulation von RO.- *
    4. ? x, y, z.x=yz ist diophantisch Pell-Gleichungen.- II Arithmetische Hierarchie und Unlösbarkeitsgrade.-
    1. Rekursiv aufzählbare Prädikate Darstellungssätze, Universalität.-
    2. Arithmetische Hierarchie Aufzählungs- und Hierarchiesatz Darstellungssatz, Komplexitätsbestimmungen (Unendlichkeits-, Anzahlaussagen, arithmetischer Wahrheitsbegriff).- *
    3. Reduktionsbegriffe und Unlösbarkeitsgrade Reduktionsbegriffe (Satz von Post), Indexmengen (Satz von Rice & Shapiro, ?n -vollständige Programmeigenschaften), Kreativität und ?1-Vollständigkeit (Satz von Myhill), Einfache Mengen (?1. versus ?m versus ?tt, Satz von Decker und Yates), Prioritätsmethode (Satz von Friedberg & Muchnik), Komplexität des arithmetischen Wahrheitsbegriffs.- III Allgemeine Berechnungskomplexität.-
    1. Beschleunigungsphänomen Allg. Komplexitätsmaße, Blumscher Beschleunigungssatz, Unmöglichkeit effektiver Beschleunigung.-
    2. Beliebig komplizierte Funktionen Satz von Rabin-Blum-Meyer über Funktionen beliebig großer Programm- oder Rechenzeitkomplexität, Blumscher Programmverkürzungssatz, Lückensatz, Vereinigungssatz.- *
    3. Zerlrgungstheorie universeller Automaten Charakterisierung der Laufzeit-, Ein-, Ausgabe-, Übergangs- und Stopfunktionen universeller Automaten; Unmöglichkeit uniformer rekursiver Simulationsschranken bei universellen Automaten.- C: Rekursivität und Komplexität.- I Komplexitätsklassen Rekursiver Funktionen.-
    0. Das Modell der k-Band-Turingmaschine Bandreduktion, Band- und Zeitkompression, Simulationskomplexität eines universellen Programms.-
    1. Zeit- und Platzhierarchiesätze Satz von Fürer.-
    2. Komplexität nickt determinierter Programme Satz von savitch.- II Komplexitätsklassen Primitiv Rekursiver Funktionen.-
    1. Grzegorczyk-Hierarchiesatz Äquivalenz der Charakterisierungen durch Wachstum (beschränkte Rekursionen, Einsetzungen in Ackermannzweige), Rekursions- und Looptiefe, Rechenzeitkomplexität aus Kleene-Normalform mit polynomialbeschränkten bzw. R3-Kodierungsfunktionen.- *
    2. En-Basis- und En -Rechenzeithierarchiesatz.- *
    3. Ackermannfunktion und Goodstein-Folgen Satz von Goodstein & Kirby & Paris.- III Polynomial und Exponentiell Beschränkte Komplexitätsklassen.-
    1. NP-vollständige. Probleme. Halte-, Domino-, Partitions-, Rucksack-, Cliguen-, Handlungsreisenden- und ganz-zahliges Programmierungsproblem.-
    2. Vollständige Probleme für PBAND und exponentielle Klassen.- IV Endliche Automaten.-
    1. Charakterisierungen durch (in-) determinierte Akzeptoren und Akzeptoren und reguläre Ausdrücke Sätze von Rabin & Scott, Kleene.-
    2. Charakterisierung durch Kongruenzrelationen der Ununterscheid-barkeit Satz von Myhill & Nerode mit Korollaren (Zustands- minimalisierung, Beispiele nicht regulärer Sprachen, Schleifenlemma, 2-Weg-Automaten).- *
    3. Zerlegungssätze Produktzerlegung, Modulare Zerlegung (Röddingsche Normalform bei sequentieller und paralleler Signalverarbeitung).- *
    4. Kleine universelle Programme 2-dimensionale TM mit 2 Zuständen und 4 Buchstaben, 2-dimensionales Thuesystem mit 2 Regeln und 3 Buchstaben, PBAND-Vollständiges Schleifenproblem.- V; Kontextfreie Sprachen.-
    1. Normalformen von Chomsky- und Greibach, Herleitungbäume.-
    2. Periodizitätseigenschaften Schleifenlemma, Satz von Parikh, induktive Charakterisierung durch Substitutionsiteration.-
    3. Maschinencharakterisierung Kellerautomaten, Abschlußeigen Schäften.-
    4. Entscheidungsprobleme, Entscheidbarkeitssatz für kontextfreie und reguläre Grammatiken, Komplexität des Äquivalenzproblems regulärer Ausdrücke; Unentscheidbarkeitssatz für kontextfreie Grammatiken, Unmöglichkeit effektiver Minimalisierung.- *
    5. Abgrenzungen gegen Chomsky-Hierarchieklassen Durchschnitt regulärer mit Klammersprachen, L-R Herleitungsbeschränkung von Typ-O-Grammatiken, kontextabhängige Sprachen (Platzbedarfsatz und LBA-Problem).- Zweites Buch: Elementare Prädikatenlogik.- D: Logische Analyse Des Wahrheitsbegriffs.- I Syntax und Semantik.-
    1. Formale, Sprachen der 1. Stufe.-
    2. Interpretation formaler Sprachen.-
    3. Hilbert-Kalkül.- II Vollständigkeitssatz.-
    1. Herleitungen und Deduktionstheorem der Aussagenlogik.-
    2. Aussagenlogischer Vollständigkeitssatz (Lindenbaumscher Maximalisierungsprozeß; anaytische Tafeln, Resolution).-
    3. Herleitungen und Deduktionstheorem der Prädikatenlogik.-
    4. Prädikatenlogischer Vollständigkeitssatz.- III Folgerungen Aus Dem Vollständigkeitssatz.-
    1. Ausdrucksschwäche der PL 1 Satz von Skolem, Kompaktheits-satz, Nichtcharakterisierbarkeit des Endlichkeitsbegriffs, zahlentheoretische Nicht-Standard-Modelle.- *
    2. Prädikatenlogik der 2. stufe und Typentheorie Charakterisierung der Endlichkeit, der Abzählbarkeit und von (N;O,+1) in der 2. Stufe; Sprachen n-ter Stufe.-
    3. Kanonische Erfüllbarkeit Skolemsche Normalform, (minimale) Herbrand-Modelle, prädikatenlogische Resolution, prozedurals Interpretation von Hornformeln, Vollständigkeit der SLD-Resolution.- E: Logische Analyse Des Beweisbegriffs.- I: Gentzens Kalkül LK.-
    1. Der Kalkül LK (Klassische Logik).-
    2. Äquivalenz zum Hilbert-Kalkül.- * Teil II: Schnitteliminationssatz Für LK.- * Teil III: Folgerungen Aus Dem Schnitteliminationssatz.-
    1. Gentzens Hauptsatz (Kor: Satz von Herbrand).-
    2. Interpolatxonssatz Kor: Definierbarkeitssatz. Widerlegung von Interpolations- und Definierbarkeitssatz im Endlichen.- F: Komplexität Logischer Entscheidungsprobleme.- I: Unentscheidbarkeit & Reduktionsklassen.-
    1. Sätze von Church & Turing, Trachtenbrot, Aanderaa & Börger Kor: PROLOG-Programm als Axiom einer wesentlich unentscheid- baren Theorie bzw. erfüllbare Formel ohne rekursive Modelle, PROLOG-Definierbarkeit aller berechenbaren Funktionen, Unmöglichkeit rekursiver Interpolation und rekursiver Explikationsschranken impliziter Definitionen.- *
    2. Reduktionstyp von Kahr-Moore-Wang.- II: Unvollständigkeit Der Arithmetik.- Unvollständigkeitssatz von Gödel, Satz von Löb..- III: Rekursive Untere Komplexitätsschranken.-
    0. Reduktionsmethode.-
    1. Komplexität Boolescher Funktionen Satz von Cook, Satz von Henschen & Wos, polynomiale Äquivalenz von Horn- und Netzwerkkomplexität, Satz von Stockmeyer.- *
    2. Spektrumproblem Spektrumcharakterisierung der E3-Rechenzeithierarchie (Satz von Rödding & Schwichtenberg, Jones & Selman, Christen); Logische Charakterisierung von NP durch globale existentielle zweitstufige Prädikate (Satz von Fagin), von P durch PL1+LFP mit Ordnung (Satz von Immerman & Vardi), von PBAND durch PL2+TC (Satz von Immerman).- *
    3. Vollständige, Entscheidungsprobleme für polynomiale und exponentielle Komplexitätsklassen.- Satz von Lewis (NEXPZEIT-Vollständigkeit des Erfüllbarkeitsproblems der monadischen Gödel-Kalmar-Schütte-Klasse V?L2V?n Monad), Satz von Plaisted (EXPZEIT-Vollständigkeit des Erfüllbarkeitsproblems der Bernays-Schönfinkel-Klasse V?V? in Hornfomeln. Korollar: NEXPZEIT-Vollständigkeit für V?V?), Satz von Plaisted und Benenberg & Lewis (PBAND-Voll- ständigkeit des Erfüllbarkeitsproblems der Bernays-Schönfinkel- Klasse in Krom- (und Horn-)formein. Korollar: PBAND-Vollständigkeit von V?V? in determinierten Krom- und Hornformeln..- Bibliographie.- Symbolverzeichnis.