Algorithmen und Komplexitätstheorie

Nonfiction, Computers, Advanced Computing, Theory
Cover of the book Algorithmen und Komplexitätstheorie by Christoph Vogt, Kai Lingemann, GRIN Verlag
View on Amazon View on AbeBooks View on Kobo View on B.Depository View on eBay View on Walmart
Author: Christoph Vogt, Kai Lingemann ISBN: 9783638112574
Publisher: GRIN Verlag Publication: February 10, 2002
Imprint: GRIN Verlag Language: German
Author: Christoph Vogt, Kai Lingemann
ISBN: 9783638112574
Publisher: GRIN Verlag
Publication: February 10, 2002
Imprint: GRIN Verlag
Language: German
Skript aus dem Jahr 2000 im Fachbereich Informatik - Theoretische Informatik, Note: 1,7, Rheinische Friedrich-Wilhelms-Universität Bonn, 6 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: Dieses Dokument hat das Ziel, den Leser bei der Vorbereitung für die Informatik-Diplomprüfung zu unterstützen. Dieses Skript basiert auf Literatur und Vorlesungen. Die Vorlesungen wurden an der Universität Bonn von Prof. Dr. Lengauer gehalten. Die Basis für den größten Teil der Vorlesungen bilden dabei ein neues Werk von Mehlhorn und Näher sowie Werke von Reischuk und Papadimitriou. Inhaltsverzeichnis: I Algorithmen 1 Graphen 1.1 Grundlegende Notationen 1.2 Speicherung von Graphen 1.3 Graphenisomorphie 1.4 Planarität 1.5 Büme 1.6 Zusammenhang 1.7 Depth-First-Search 1.8 kürzeste Wege in Graphen 1.9 Minimale Spannbäume 1.10 Matching in Graphen 1.11 Netzwerkflüsse 2 Geometrie 2.1 Konvexe Hülle 2.2 Triangulierungen 2.3 Die Delaunay-Triangulierung 2.4 Segmentschnitte II Komplexitätstheorie 3 Einleitung 4 Turingmaschinen 4.1 Allgemeines 4.2 Turingmaschinen als Algorithmen 4.3 Linearer Speedup 4.4 Aufwand beim Akzeptieren der Palindromsprachen 4.5 Die Registermaschine (Random Access Machine) 4.6 Nichtdeterminismus 5 Unentscheidbarkeit 5.1 Halteproblem 5.2 Abgeschlossenheit 5.3 Rekursive Trennbarkeit 6 Aussagenlogik 6.1 Erfüllbarkeit & Wahrheit 6.2 Logik{Funktionen 7 Logik erster Stufe 7.1 Syntax 7.2 Semantik 7.3 Modelle für die Zahlentheorie 7.4 Gültige Sätze 7.5 Konsistenz der Logik erster Ordnung 8 Unentscheidbarkeit in der Logik 8.1 Berechnung als zahlentheoretisches Konzept 9 Beziehungen zwischen Komplexitätsklassen 9.1 Komplexitätsklassen 9.2 Hierarchiesätze 9.3 Erreichbarkeitsmethode 10 Reduktion und Vollständigkeit 10.1 Reduktion 10.2 Vollständigkeit 10.3 Charakterisierung mittels Logik 11 NP-vollständige Probleme 11.1 Varianten von SAT 11.2 Varianten von 2SAT 11.3 Graphenprobleme 11.4 Zahlenprobleme 12 coNP und Funktionsprobleme 12.1 PRIMES 12.2 Function Problems 13 Randomisierte Berechnungen 13.1 Randomisierte Algorithmen 13.2 Randomisierte Komplexitätsklassen 13.3 Zufallsgeneratoren 13.4 Schaltkreiskomplexität 14 Kryptographie 14.1 Public Key-Kryptographie 14.2 Kryptographie und Komplexität 14.3 Interaktives Beweisen 14.4 Zero Knowledge 15 Approximierbarkeit 15.1 Approximationsalgorithmen 15.2 Polyzeit{Approximationsschema 15.3 Vollständigkeit bei Approximationsalgorithmen 16 P vs. NP 16.1 Was ist zwischen P und NPC? 16.2 Beweise für P!=NP? 17 Parallelität 17.1 Beispiel-Algorithmen 17.2 Prä x-Summen-Berechnung 17.3 Parallele Maschinenmodelle 17.4 Die Klasse NC 18 Logarithmischer Platzverbrauch 18.1 L=NL? 18.2 Alternierung 19 Polynomielle Hierarchie
View on Amazon View on AbeBooks View on Kobo View on B.Depository View on eBay View on Walmart
Skript aus dem Jahr 2000 im Fachbereich Informatik - Theoretische Informatik, Note: 1,7, Rheinische Friedrich-Wilhelms-Universität Bonn, 6 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: Dieses Dokument hat das Ziel, den Leser bei der Vorbereitung für die Informatik-Diplomprüfung zu unterstützen. Dieses Skript basiert auf Literatur und Vorlesungen. Die Vorlesungen wurden an der Universität Bonn von Prof. Dr. Lengauer gehalten. Die Basis für den größten Teil der Vorlesungen bilden dabei ein neues Werk von Mehlhorn und Näher sowie Werke von Reischuk und Papadimitriou. Inhaltsverzeichnis: I Algorithmen 1 Graphen 1.1 Grundlegende Notationen 1.2 Speicherung von Graphen 1.3 Graphenisomorphie 1.4 Planarität 1.5 Büme 1.6 Zusammenhang 1.7 Depth-First-Search 1.8 kürzeste Wege in Graphen 1.9 Minimale Spannbäume 1.10 Matching in Graphen 1.11 Netzwerkflüsse 2 Geometrie 2.1 Konvexe Hülle 2.2 Triangulierungen 2.3 Die Delaunay-Triangulierung 2.4 Segmentschnitte II Komplexitätstheorie 3 Einleitung 4 Turingmaschinen 4.1 Allgemeines 4.2 Turingmaschinen als Algorithmen 4.3 Linearer Speedup 4.4 Aufwand beim Akzeptieren der Palindromsprachen 4.5 Die Registermaschine (Random Access Machine) 4.6 Nichtdeterminismus 5 Unentscheidbarkeit 5.1 Halteproblem 5.2 Abgeschlossenheit 5.3 Rekursive Trennbarkeit 6 Aussagenlogik 6.1 Erfüllbarkeit & Wahrheit 6.2 Logik{Funktionen 7 Logik erster Stufe 7.1 Syntax 7.2 Semantik 7.3 Modelle für die Zahlentheorie 7.4 Gültige Sätze 7.5 Konsistenz der Logik erster Ordnung 8 Unentscheidbarkeit in der Logik 8.1 Berechnung als zahlentheoretisches Konzept 9 Beziehungen zwischen Komplexitätsklassen 9.1 Komplexitätsklassen 9.2 Hierarchiesätze 9.3 Erreichbarkeitsmethode 10 Reduktion und Vollständigkeit 10.1 Reduktion 10.2 Vollständigkeit 10.3 Charakterisierung mittels Logik 11 NP-vollständige Probleme 11.1 Varianten von SAT 11.2 Varianten von 2SAT 11.3 Graphenprobleme 11.4 Zahlenprobleme 12 coNP und Funktionsprobleme 12.1 PRIMES 12.2 Function Problems 13 Randomisierte Berechnungen 13.1 Randomisierte Algorithmen 13.2 Randomisierte Komplexitätsklassen 13.3 Zufallsgeneratoren 13.4 Schaltkreiskomplexität 14 Kryptographie 14.1 Public Key-Kryptographie 14.2 Kryptographie und Komplexität 14.3 Interaktives Beweisen 14.4 Zero Knowledge 15 Approximierbarkeit 15.1 Approximationsalgorithmen 15.2 Polyzeit{Approximationsschema 15.3 Vollständigkeit bei Approximationsalgorithmen 16 P vs. NP 16.1 Was ist zwischen P und NPC? 16.2 Beweise für P!=NP? 17 Parallelität 17.1 Beispiel-Algorithmen 17.2 Prä x-Summen-Berechnung 17.3 Parallele Maschinenmodelle 17.4 Die Klasse NC 18 Logarithmischer Platzverbrauch 18.1 L=NL? 18.2 Alternierung 19 Polynomielle Hierarchie

More books from GRIN Verlag

Cover of the book Vergleich von Europavorstellungen. Europabilder im Ost- und Westblock by Christoph Vogt, Kai Lingemann
Cover of the book Anreize und Anreizprobleme bei Unternehmenskooperationen, insbesondere in Supply Chains by Christoph Vogt, Kai Lingemann
Cover of the book Die verbale Entwicklungsdyspraxie. Eine praktische und theoretische Herausforderung by Christoph Vogt, Kai Lingemann
Cover of the book Politische Macht bei Niklas Luhmann und Pierre Bourdieu - ein Vergleich by Christoph Vogt, Kai Lingemann
Cover of the book Unternehmens-Insolvenz: Fortbestehensprognose und Insolvenzverwertung. Chancen und rechtliche Probleme bei der Verwertung durch E-Marketplaces by Christoph Vogt, Kai Lingemann
Cover of the book Die Finanzierung und das Kapitalgeber-Management von Sozialunternehmen by Christoph Vogt, Kai Lingemann
Cover of the book Kulturwissenschaft als Zeichen der Moderne by Christoph Vogt, Kai Lingemann
Cover of the book Die Zusammenlegung von Arbeitslosen- und Sozialhilfe by Christoph Vogt, Kai Lingemann
Cover of the book Sport, Kultur, Politik und Management - Eine EURO Nachlese by Christoph Vogt, Kai Lingemann
Cover of the book Konvergenz von Krylov-Verfahren für Eigenwertprobleme by Christoph Vogt, Kai Lingemann
Cover of the book Kann das Modell 'Prosper' der Bundesknappschaft Vorbild für Integrationsversorgung sein? by Christoph Vogt, Kai Lingemann
Cover of the book Vergleich der Erziehungstheorien von Schleiermacher und Herbart by Christoph Vogt, Kai Lingemann
Cover of the book Power and Authority in William Shakespeare's 'The Tempest' by Christoph Vogt, Kai Lingemann
Cover of the book Einflussmöglichkeiten der Arbeit auf die Persönlichkeitsentwicklung aus endogenistischer und exogenistischer Entwicklungsperspektive by Christoph Vogt, Kai Lingemann
Cover of the book Vorbereitung zum Anschluss einer Heizkreiswasserpumpe (Unterweisung Elekroinstallateur / -in) by Christoph Vogt, Kai Lingemann
We use our own "cookies" and third party cookies to improve services and to see statistical information. By using this website, you agree to our Privacy Policy