Algorithmen und Komplexitätstheorie

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 Algorithmen1 Graphen1.1 Grundlegende Notationen1.2 Speicherung von Graphen1.3 Graphenisomorphie1.4 Planarität1.5 Büme1.6 Zusammenhang1.7 Depth-First-Search1.8 kürzeste Wege in Graphen1.9 Minimale Spannbäume1.10 Matching in Graphen1.11 Netzwerkflüsse2 Geometrie2.1 Konvexe Hülle2.2 Triangulierungen2.3 Die Delaunay-Triangulierung2.4 SegmentschnitteII Komplexitätstheorie3 Einleitung4 Turingmaschinen4.1 Allgemeines4.2 Turingmaschinen als Algorithmen4.3 Linearer Speedup4.4 Aufwand beim Akzeptieren der Palindromsprachen4.5 Die Registermaschine (Random Access Machine)4.6 Nichtdeterminismus5 Unentscheidbarkeit5.1 Halteproblem5.2 Abgeschlossenheit5.3 Rekursive Trennbarkeit6 Aussagenlogik6.1 Erfüllbarkeit & Wahrheit6.2 Logik{Funktionen7 Logik erster Stufe7.1 Syntax7.2 Semantik7.3 Modelle für die Zahlentheorie7.4 Gültige Sätze7.5 Konsistenz der Logik erster Ordnung8 Unentscheidbarkeit in der Logik8.1 Berechnung als zahlentheoretisches Konzept9 Beziehungen zwischen Komplexitätsklassen9.1 Komplexitätsklassen9.2 Hierarchiesätze9.3 Erreichbarkeitsmethode10 Reduktion und Vollständigkeit10.1 Reduktion10.2 Vollständigkeit10.3 Charakterisierung mittels Logik11 NP-vollständige Probleme11.1 Varianten von SAT11.2 Varianten von 2SAT11.3 Graphenprobleme11.4 Zahlenprobleme12 coNP und Funktionsprobleme12.1 PRIMES12.2 Function Problems13 Randomisierte Berechnungen13.1 Randomisierte Algorithmen13.2 Randomisierte Komplexitätsklassen13.3 Zufallsgeneratoren13.4 Schaltkreiskomplexität14 Kryptographie14.1 Public Key-Kryptographie14.2 Kryptographie und Komplexität14.3 Interaktives Beweisen14.4 Zero Knowledge15 Approximierbarkeit15.1 Approximationsalgorithmen15.2 Polyzeit{Approximationsschema15.3 Vollständigkeit bei Approximationsalgorithmen16 P vs. NP16.1 Was ist zwischen P und NPC?16.2 Beweise für P!=NP?17 Parallelität17.1 Beispiel-Algorithmen17.2 Prä x-Summen-Berechnung17.3 Parallele Maschinenmodelle17.4 Die Klasse NC18 Logarithmischer Platzverbrauch18.1 L=NL?18.2 Alternierung19 Polynomielle Hierarchie