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