Logo - springer
Slogan - springer

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

Berechenbarkeit Komplexität Logik

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

Börger, Egon

3., verb. und erw. Aufl. 1992, XX, 499S.

Formate:
eBook
Information

Springer eBooks sind ausschließlich für den persönlichen Gebrauch bestimmt und werden ohne Kopierschutz verkauft (DRM-frei). Statt dessen sind sie mit einem personalisierten Wasserzeichen versehen. Sie können die Springer eBooks auf gängigen Endgeräten, wie beispielsweise Laptops, Tablets oder eReader, lesen.

Springer eBooks können mit Visa, Mastercard, American Express oder Paypal bezahlt werden.

Nach dem Kauf können Sie das eBook direkt downloaden. Ihr eBook ist außerdem in MySpringer gespeichert, so dass Sie Ihre eBooks jederzeit neu herunterladen können.

 
$49.95

(net) Preis für USA

ISBN 978-3-322-83227-6

versehen mit digitalem Wasserzeichen, kein DRM

Erhältliche Formate: PDF

sofortiger Download nach Kauf


mehr Information zu Springer eBooks

add to marked items

Softcover
Information

Broschierte Ausgabe

Springer-Bücher können mit Visa, Mastercard, American Express, Paypal sowie auf Rechnung bezahlt werden.

Standard-Versand ist für Individualkunden kostenfrei.

 
$69.95

(net) Preis für USA

ISBN 978-3-528-28928-7

kostenfreier Versand für Individualkunden

gewöhnlich versandfertig in 3-5 Werktagen


add to marked items

  • Über dieses Lehrbuch

VI VORWORT Thema dieses Buches sind zwei schon vort Leibniz als zusammengehorend erkannte Begriffe, deren mathematische Entwicklung von Frege bis Turing das theoretische Fundament der Computerwissenschaft gelegt hat: der Be­ griff formaler Sprache als Trager prazisen Ausdrucks von Bedeutungen, Sach­ verhalten, Problemen und der des Algorithmus oder Kalkuls, d. h. formal ope­ rierender Verfahren zur Losung prazis beschriebener Fragen und Probleme. Das Buch gibt eine einheitliche EinfUhrung in die moderne Theorie dieser Begriffe, wie sie sich zuerst in der mathematischen Logik und der Berechen­ barkeitstheorie und weiter in der Automatentheorie, der Theorie formaler Sprachen und der Komplexitatstheorie entwickelt hat. Neben der Berucksich­ tigung eines schon klassisch gewordenen Grundkanons dieser Gebiete ist die Stoffauswahl mit der Absicht getrof. fen worden, durchgangig Erneuerungen traditioneller Fragestellungen, Ergebnisse und Methoden den Vorrang zu ge­ ben, die sich aus Bedurfnissen oder Erkenntnissen der Informatik und hier besonders der Komplexitatstheorie heraus entwickelt haben. Die Zielsetzung dieses Buches ist eine doppelte: Lehrbuch zu sein fur Anfangervorlesungen zu den genannten Gebieten, wie sie in fast allen Curri­ cula der Informatik, der Logik und der Mathematik he ute auftreten, aber daruberhinaus auch Monographie, indem in systematischer Absicht in jedem der angesprochenen Gebiete weiterfuhrende Ergebnisse neuerer Forschungen (groBenteils erstmalig in lehrbuchartiger Form) vorgefuhrt werden und Uber­ all versucht wird, Analogien und Zusammenhange zwischen verschiedenen Be­ griffen und Konstruktionen explizit herauszuarbeiten.

Content Level » Upper undergraduate

Stichwörter » Informatik - Komplexität - Logik - Maschine - Modell - Netzwerk - Norm - Programmierung - Signalverarbeitung - Simulation - Systeme

Verwandte Fachbereiche » Technik

Inhaltsverzeichnis 

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.

Beliebte Inhalte dieser Publikation 

 

Articles

Dieses Buch auf Springerlink lesen

Service für dieses Buch

Neuerscheinungen

Registrieren Sie sich hier wenn Sie regelmäßig Informationen über neue Bücher erhalten wollen im Fachbereich Technik (allgemein).