Algorithmen und Komplexitätstheorie

Verfügbarkeit:
nur noch 3 lieferbar
Artikelnummer:
551696
  • Produktbeschreibung

    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 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
  • Zusatzinformation

    Autor
    Bindung
    Taschenbuch
    Verlag
    GRIN Verlag
    ISBN / EAN
    9783640877638
  • Sie könnten auch an folgenden Produkten interessiert sein

    Art.Nr. 1028277

    Reiß:Praxisbuch IT-Dokumentation

    79,95
    Art.Nr. 1479181

    Ramirez Molina:Diseño de una arquitectu

    84,00
    Art.Nr. 1698114

    Quaschning,V.:Regenerative Energ.m.DVD

    53,90
  • 0 Kundenmeinungen

    Schreiben Sie selbst eine Rezension

    Ihre Meinung interessiert uns – und hilft anderen Kunden bei der Auswahl.