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

49,99 €

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

Ein neues Kapitel für Ihre Bücher

Ein neues Kapitel für Ihre Bücher

Schenken Sie Ihren alten Schätzen ein zweites Leben und erhalten dafür eine Thalia Geschenkkarte.

Jetzt verkaufen
Jetzt verkaufen

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.