54 lines
5.9 KiB
TeX
54 lines
5.9 KiB
TeX
\relax
|
|
\providecommand\hyper@newdestlabel[2]{}
|
|
\providecommand\HyField@AuxAddToFields[1]{}
|
|
\providecommand\HyField@AuxAddToCoFields[2]{}
|
|
\@writefile{toc}{\contentsline {section}{\textbf {Teil A -- Die Grundlagen}}{4}{part*.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {1}Ein Problem, das sich wehrt}{4}{section.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {2}Effizient lösbar: die Klasse P}{4}{section.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {3}Effizient überprüfbar: die Klasse NP}{5}{section.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Die erste Sicht: Zertifikat und Verifizierer}{5}{subsection.3.1}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Die zweite Sicht: nichtdeterministisches Raten}{6}{subsection.3.2}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}P steckt in NP}{6}{subsection.3.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {4}Reduktionen: Probleme vergleichen}{7}{section.4}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {5}NP-schwer, NP-vollständig, und der Anker}{7}{section.5}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\textbf {Teil B -- Der Problem-Katalog}}{9}{part*.3}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {6}SAT}{9}{section.6}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {7}3-SAT}{11}{section.7}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {8}$k$-Clique}{13}{section.8}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {9}Independent Set}{15}{section.9}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {10}Vertex Cover}{16}{section.10}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {11}Feedback Vertex Set}{18}{section.11}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {12}$\Delta $-Cover (Dreiecksüberdeckung)}{19}{section.12}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {13}$k$-Color (Färbung)}{20}{section.13}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {14}Hamiltonkreis}{22}{section.14}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {15}TSP (Traveling Salesman)}{23}{section.15}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {16}3-dimensionales Matching}{24}{section.16}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {17}3-Exact Cover}{26}{section.17}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {18}SubSet Sum}{27}{section.18}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {19}Partition}{30}{section.19}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {20}Knapsack (Rucksackproblem)}{31}{section.20}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {21}$P\|C_{\max }$ (Scheduling)}{32}{section.21}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {22}Hitting Set}{33}{section.22}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {23}Set Cover}{34}{section.23}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {24}Dominating Set}{35}{section.24}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {25}Longest Path}{36}{section.25}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {26}Das Halteproblem -- schwer, aber nicht in NP}{37}{section.26}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\textbf {Teil C -- Untere Schranken: die ETH}}{38}{part*.63}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {27}Die Bausteine der ETH}{38}{section.27}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {28}Untere Schranken für die einzelnen Probleme}{40}{section.28}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\textbf {Teil D -- Approximation}}{41}{part*.76}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {29}Der Gütebegriff}{41}{section.29}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {30}TSP ist im Allgemeinen nicht approximierbar}{42}{section.30}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {31}$\Delta $TSP$_1$: der Algorithmus als Bilderfolge}{43}{section.31}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {32}Christofides: schlauer verdoppeln}{44}{section.32}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {33}Knapsack: Greedy}{46}{section.33}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {34}Knapsack: Modified Greedy}{47}{section.34}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {35}Knapsack: Sahni-Algorithmus}{47}{section.35}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {36}Knapsack: FPTAS}{47}{section.36}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {37}Scheduling: List Scheduling}{48}{section.37}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {38}Scheduling: LPT}{49}{section.38}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {39}MAX-3-SAT: Güte 2 mit zwei Belegungen}{49}{section.39}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {40}2-Approximation für Vertex Cover}{50}{section.40}\protected@file@percent }
|
|
\@writefile{toc}{\contentsline {section}{\numberline {41}Zum Schluss}{50}{section.41}\protected@file@percent }
|
|
\gdef \@abspage@last{51}
|