1 \select@language {ngerman}
2 \contentsline {section}{\numberline {1}Einleitung}{3}{section.1}
3 \contentsline {subsection}{\numberline {1.1}Themen:}{3}{subsection.1.1}
4 \contentsline {subsection}{\numberline {1.2}Problem-/Anwendungsbereiche:}{3}{subsection.1.2}
5 \contentsline {subsection}{\numberline {1.3}Literatur:}{3}{subsection.1.3}
6 \contentsline {section}{\numberline {2}Divide and Conquer}{4}{section.2}
7 \contentsline {subsection}{\numberline {2.1}Formulierung des Divide and Conquer Prinzips}{4}{subsection.2.1}
8 \contentsline {subsection}{\numberline {2.2}Quicksort}{4}{subsection.2.2}
9 \contentsline {subsubsection}{\numberline {2.2.1}Algorithmus}{4}{subsubsection.2.2.1}
10 \contentsline {subsubsection}{\numberline {2.2.2}Analyse}{4}{subsubsection.2.2.2}
11 \contentsline {subsection}{\numberline {2.3}N\"achste Paare}{5}{subsection.2.3}
12 \contentsline {subsubsection}{\numberline {2.3.1}Algorithmus}{5}{subsubsection.2.3.1}
13 \contentsline {subsubsection}{\numberline {2.3.2}Analyse}{5}{subsubsection.2.3.2}
14 \contentsline {subsection}{\numberline {2.4}Segmentschnitt}{6}{subsection.2.4}
15 \contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{6}{subsubsection.2.4.1}
16 \contentsline {subsubsection}{\numberline {2.4.2}Analyse}{6}{subsubsection.2.4.2}
17 \contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation (TODO)}{6}{subsection.2.5}
18 \contentsline {section}{\numberline {3}Randomisierung}{7}{section.3}
19 \contentsline {subsection}{\numberline {3.1}Randomisierter Quicksort}{7}{subsection.3.1}
20 \contentsline {subsubsection}{\numberline {3.1.1}Analyse}{7}{subsubsection.3.1.1}
21 \contentsline {subsection}{\numberline {3.2}Randomisierter Primzahltest (TODO)}{7}{subsection.3.2}
22 \contentsline {subsection}{\numberline {3.3}RSA (TODO)}{7}{subsection.3.3}
23 \contentsline {subsection}{\numberline {3.4}Treaps (TODO)}{7}{subsection.3.4}
24 \contentsline {subsection}{\numberline {3.5}Hashing (TODO)}{7}{subsection.3.5}
25 \contentsline {section}{\numberline {4}Amortisierte Analyse (TODO)}{8}{section.4}
26 \contentsline {subsection}{\numberline {4.1}Binomial Heaps (TODO)}{8}{subsection.4.1}
27 \contentsline {subsection}{\numberline {4.2}Fibonacci Heaps (TODO)}{8}{subsection.4.2}
28 \contentsline {subsection}{\numberline {4.3}Union Find (TODO)}{8}{subsection.4.3}
29 \contentsline {section}{\numberline {5}Greedy}{9}{section.5}
30 \contentsline {subsection}{\numberline {5.1}K\"urzeste (billigste) Wege}{9}{subsection.5.1}
31 \contentsline {subsubsection}{\numberline {5.1.1}Single Source Shortest Paths}{9}{subsubsection.5.1.1}
32 \contentsline {subsection}{\numberline {5.2}Spannb\"aume minimalen Gewichts}{11}{subsection.5.2}
33 \contentsline {subsubsection}{\numberline {5.2.1}Das Wachsen von min. Spannb\"aumen}{11}{subsubsection.5.2.1}
34 \contentsline {subsubsection}{\numberline {5.2.2}Schnitte}{12}{subsubsection.5.2.2}
35 \contentsline {subsubsection}{\numberline {5.2.3}Sichere Kanten}{12}{subsubsection.5.2.3}
36 \contentsline {subsubsection}{\numberline {5.2.4}Der Graph $G_A$}{12}{subsubsection.5.2.4}
37 \contentsline {subsubsection}{\numberline {5.2.5}Algorithmus von Kruskal}{12}{subsubsection.5.2.5}
38 \contentsline {subsubsection}{\numberline {5.2.6}Algorithmus von Prim}{13}{subsubsection.5.2.6}
39 \contentsline {section}{\numberline {6}Bin Packing}{14}{section.6}
40 \contentsline {subsection}{\numberline {6.1}Online Verfahren}{14}{subsection.6.1}
41 \contentsline {subsubsection}{\numberline {6.1.1}Next Fit (NF)}{14}{subsubsection.6.1.1}
42 \contentsline {subsubsection}{\numberline {6.1.2}First-Fit (FF)}{14}{subsubsection.6.1.2}
43 \contentsline {subsubsection}{\numberline {6.1.3}Best-Fit (BF)}{15}{subsubsection.6.1.3}
44 \contentsline {subsection}{\numberline {6.2}Offline Verfahren}{15}{subsection.6.2}
45 \contentsline {subsubsection}{\numberline {6.2.1}First Fit Decreasing (FFD oder FFNI)}{15}{subsubsection.6.2.1}
46 \contentsline {subsubsection}{\numberline {6.2.2}Best Fit Decreasing (BFD)}{15}{subsubsection.6.2.2}
47 \contentsline {section}{\numberline {7}Dynamische Programmierung}{16}{section.7}
48 \contentsline {subsection}{\numberline {7.1}Matrixkettenprodukt (TODO)}{16}{subsection.7.1}
49 \contentsline {subsection}{\numberline {7.2}Optimale Suchb\"aume (TODO)}{16}{subsection.7.2}
50 \contentsline {subsection}{\numberline {7.3}Editierdistanz}{16}{subsection.7.3}
51 \contentsline {section}{\numberline {8}Suche in Texten}{17}{section.8}
52 \contentsline {section}{\numberline {A}Landau-Symbole}{19}{appendix.A}