1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/AT_Exzerpt.aux Tue Feb 22 19:14:19 2011 +0100
1.3 @@ -0,0 +1,164 @@
1.4 +\relax
1.5 +\providecommand\BKM@entry[2]{}
1.6 +\catcode`"\active
1.7 +\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
1.8 +\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
1.9 +\global\let\oldcontentsline\contentsline
1.10 +\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
1.11 +\global\let\oldnewlabel\newlabel
1.12 +\gdef\newlabel#1#2{\newlabelxx{#1}#2}
1.13 +\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
1.14 +\AtEndDocument{\ifx\hyper@anchor\@undefined
1.15 +\let\contentsline\oldcontentsline
1.16 +\let\newlabel\oldnewlabel
1.17 +\fi}
1.18 +\fi}
1.19 +\global\let\hyper@last\relax
1.20 +\gdef\HyperFirstAtBeginDocument#1{#1}
1.21 +\providecommand*\HyPL@Entry[1]{}
1.22 +\bibstyle{alphadin}
1.23 +\HyPL@Entry{0<</S/D>>}
1.24 +\select@language{ngerman}
1.25 +\@writefile{toc}{\select@language{ngerman}}
1.26 +\@writefile{lof}{\select@language{ngerman}}
1.27 +\@writefile{lot}{\select@language{ngerman}}
1.28 +\BKM@entry{id=1,dest={73656374696F6E2E31}}{45696E6C656974756E67}
1.29 +\BKM@entry{id=2,dest={73756273656374696F6E2E312E31}}{5468656D656E3A}
1.30 +\BKM@entry{id=3,dest={73756273656374696F6E2E312E32}}{50726F626C656D2D2F416E77656E64756E677362657265696368653A}
1.31 +\BKM@entry{id=4,dest={73756273656374696F6E2E312E33}}{4C69746572617475723A}
1.32 +\bibdata{literatur}
1.33 +\bibcite{2}{PW02}
1.34 +\bibcite{1}{THC01}
1.35 +\citation{*}
1.36 +\@writefile{toc}{\contentsline {section}{\numberline {1}Einleitung}{3}{section.1}}
1.37 +\newlabel{sec:intro}{{1}{3}{Einleitung\relax }{section.1}{}}
1.38 +\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Themen:}{3}{subsection.1.1}}
1.39 +\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Problem-/Anwendungsbereiche:}{3}{subsection.1.2}}
1.40 +\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}Literatur:}{3}{subsection.1.3}}
1.41 +\BKM@entry{id=5,dest={73656374696F6E2E32}}{44697669646520616E6420436F6E71756572}
1.42 +\BKM@entry{id=6,dest={73756273656374696F6E2E322E31}}{466F726D756C696572756E67206465732044697669646520616E6420436F6E71756572205072696E7A697073}
1.43 +\BKM@entry{id=7,dest={73756273656374696F6E2E322E32}}{517569636B736F7274}
1.44 +\BKM@entry{id=8,dest={73756273756273656374696F6E2E322E322E31}}{416C676F726974686D7573}
1.45 +\BKM@entry{id=9,dest={73756273756273656374696F6E2E322E322E32}}{416E616C797365}
1.46 +\BKM@entry{id=10,dest={73756273656374696F6E2E322E33}}{4E5C3334346368737465205061617265}
1.47 +\@writefile{toc}{\contentsline {section}{\numberline {2}Divide and Conquer}{4}{section.2}}
1.48 +\newlabel{sec:div&conq}{{2}{4}{Divide and Conquer\relax }{section.2}{}}
1.49 +\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Formulierung des Divide and Conquer Prinzips}{4}{subsection.2.1}}
1.50 +\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Quicksort}{4}{subsection.2.2}}
1.51 +\newlabel{ch:qs}{{2.2}{4}{Quicksort\relax }{subsection.2.2}{}}
1.52 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1}Algorithmus}{4}{subsubsection.2.2.1}}
1.53 +\newlabel{lst:TTlookup}{{1}{4}{Algorithmus Quicksort\relax }{lstlisting.1}{}}
1.54 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {1}Algorithmus Quicksort}{4}{lstlisting.1}}
1.55 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.2}Analyse}{4}{subsubsection.2.2.2}}
1.56 +\BKM@entry{id=11,dest={73756273756273656374696F6E2E322E332E31}}{416C676F726974686D7573}
1.57 +\BKM@entry{id=12,dest={73756273756273656374696F6E2E322E332E32}}{416E616C797365}
1.58 +\BKM@entry{id=13,dest={73756273656374696F6E2E322E34}}{5365676D656E747363686E697474}
1.59 +\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}N\"achste Paare}{5}{subsection.2.3}}
1.60 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1}Algorithmus}{5}{subsubsection.2.3.1}}
1.61 +\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces N\"achste Paare: Pr\"uf Distanz}}{5}{figure.1}}
1.62 +\newlabel{cl_pair}{{1}{5}{Nächste Paare: Prüf Distanz\relax }{figure.1}{}}
1.63 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.2}Analyse}{5}{subsubsection.2.3.2}}
1.64 +\BKM@entry{id=14,dest={73756273756273656374696F6E2E322E342E31}}{416C676F726974686D7573}
1.65 +\BKM@entry{id=15,dest={73756273756273656374696F6E2E322E342E32}}{416E616C797365}
1.66 +\BKM@entry{id=16,dest={73756273656374696F6E2E322E35}}{506F6C796E6F6D70726F64756B7420756E64204661737420466F75726965722D5472616E73666F726D6174696F6E205C28544F444F5C29}
1.67 +\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Segmentschnitt}{6}{subsection.2.4}}
1.68 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{6}{subsubsection.2.4.1}}
1.69 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.2}Analyse}{6}{subsubsection.2.4.2}}
1.70 +\@writefile{toc}{\contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation (TODO)}{6}{subsection.2.5}}
1.71 +\BKM@entry{id=17,dest={73656374696F6E2E33}}{52616E646F6D6973696572756E67}
1.72 +\BKM@entry{id=18,dest={73756273656374696F6E2E332E31}}{52616E646F6D697369657274657220517569636B736F7274}
1.73 +\BKM@entry{id=19,dest={73756273756273656374696F6E2E332E312E31}}{416E616C797365}
1.74 +\BKM@entry{id=20,dest={73756273656374696F6E2E332E32}}{52616E646F6D6973696572746572205072696D7A61686C74657374205C28544F444F5C29}
1.75 +\BKM@entry{id=21,dest={73756273656374696F6E2E332E33}}{525341205C28544F444F5C29}
1.76 +\BKM@entry{id=22,dest={73756273656374696F6E2E332E34}}{547265617073205C28544F444F5C29}
1.77 +\BKM@entry{id=23,dest={73756273656374696F6E2E332E35}}{48617368696E67205C28544F444F5C29}
1.78 +\@writefile{toc}{\contentsline {section}{\numberline {3}Randomisierung}{7}{section.3}}
1.79 +\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Randomisierter Quicksort}{7}{subsection.3.1}}
1.80 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.1.1}Analyse}{7}{subsubsection.3.1.1}}
1.81 +\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Randomisierter Primzahltest (TODO)}{7}{subsection.3.2}}
1.82 +\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}RSA (TODO)}{7}{subsection.3.3}}
1.83 +\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}Treaps (TODO)}{7}{subsection.3.4}}
1.84 +\@writefile{toc}{\contentsline {subsection}{\numberline {3.5}Hashing (TODO)}{7}{subsection.3.5}}
1.85 +\BKM@entry{id=24,dest={73656374696F6E2E34}}{416D6F72746973696572746520416E616C797365205C28544F444F5C29}
1.86 +\BKM@entry{id=25,dest={73756273656374696F6E2E342E31}}{42696E6F6D69616C204865617073205C28544F444F5C29}
1.87 +\BKM@entry{id=26,dest={73756273656374696F6E2E342E32}}{4669626F6E61636369204865617073205C28544F444F5C29}
1.88 +\BKM@entry{id=27,dest={73756273656374696F6E2E342E33}}{556E696F6E2046696E64205C28544F444F5C29}
1.89 +\@writefile{toc}{\contentsline {section}{\numberline {4}Amortisierte Analyse (TODO)}{8}{section.4}}
1.90 +\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Binomial Heaps (TODO)}{8}{subsection.4.1}}
1.91 +\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Fibonacci Heaps (TODO)}{8}{subsection.4.2}}
1.92 +\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Union Find (TODO)}{8}{subsection.4.3}}
1.93 +\BKM@entry{id=28,dest={73656374696F6E2E35}}{477265656479}
1.94 +\BKM@entry{id=29,dest={73756273656374696F6E2E352E31}}{4B5C333734727A65737465205C2862696C6C69677374655C292057656765}
1.95 +\BKM@entry{id=30,dest={73756273756273656374696F6E2E352E312E31}}{53696E676C6520536F757263652053686F7274657374205061746873}
1.96 +\@writefile{toc}{\contentsline {section}{\numberline {5}Greedy}{9}{section.5}}
1.97 +\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}K\"urzeste (billigste) Wege}{9}{subsection.5.1}}
1.98 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.1.1}Single Source Shortest Paths}{9}{subsubsection.5.1.1}}
1.99 +\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Tree for Dijkstra Example}}{10}{figure.2}}
1.100 +\newlabel{fig:dijExT}{{2}{10}{Tree for Dijkstra Example\relax }{figure.2}{}}
1.101 +\newlabel{lst:TTlookup}{{2}{10}{Algorithmus von Dijkstra\relax }{lstlisting.2}{}}
1.102 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {2}Algorithmus von Dijkstra}{10}{lstlisting.2}}
1.103 +\newlabel{lst:TTlookup}{{3}{10}{Algorithmus von Belman-Ford\relax }{lstlisting.3}{}}
1.104 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {3}Algorithmus von Belman-Ford}{10}{lstlisting.3}}
1.105 +\BKM@entry{id=31,dest={73756273656374696F6E2E352E32}}{5370616E6E625C333434756D65206D696E696D616C656E204765776963687473}
1.106 +\BKM@entry{id=32,dest={73756273756273656374696F6E2E352E322E31}}{446173205761636873656E20766F6E206D696E2E205370616E6E625C333434756D656E}
1.107 +\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Dijkstra Example}}{11}{table.1}}
1.108 +\newlabel{tab:dijEx}{{1}{11}{Dijkstra Example\relax }{table.1}{}}
1.109 +\newlabel{lst:TTlookup}{{4}{11}{Algorithmus für Azyklische Netzwerke\relax }{lstlisting.4}{}}
1.110 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4}Algorithmus f\"ur Azyklische Netzwerke}{11}{lstlisting.4}}
1.111 +\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Spannb\"aume minimalen Gewichts}{11}{subsection.5.2}}
1.112 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.1}Das Wachsen von min. Spannb\"aumen}{11}{subsubsection.5.2.1}}
1.113 +\newlabel{lst:TTlookup}{{5}{11}{Greedy Algorithmus für Spannbäume\relax }{lstlisting.5}{}}
1.114 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {5}Greedy Algorithmus f\"ur Spannb\"aume}{11}{lstlisting.5}}
1.115 +\BKM@entry{id=33,dest={73756273756273656374696F6E2E352E322E32}}{5363686E69747465}
1.116 +\BKM@entry{id=34,dest={73756273756273656374696F6E2E352E322E33}}{53696368657265204B616E74656E}
1.117 +\BKM@entry{id=35,dest={73756273756273656374696F6E2E352E322E34}}{446572204772617068204741}
1.118 +\BKM@entry{id=36,dest={73756273756273656374696F6E2E352E322E35}}{416C676F726974686D757320766F6E204B7275736B616C}
1.119 +\BKM@entry{id=37,dest={73756273756273656374696F6E2E352E322E36}}{416C676F726974686D757320766F6E205072696D}
1.120 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.2}Schnitte}{12}{subsubsection.5.2.2}}
1.121 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.3}Sichere Kanten}{12}{subsubsection.5.2.3}}
1.122 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.4}Der Graph $G_A$}{12}{subsubsection.5.2.4}}
1.123 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.5}Algorithmus von Kruskal}{12}{subsubsection.5.2.5}}
1.124 +\newlabel{lst:TTlookup}{{6}{12}{Algorithmus von Kruskal\relax }{lstlisting.6}{}}
1.125 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {6}Algorithmus von Kruskal}{12}{lstlisting.6}}
1.126 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.6}Algorithmus von Prim}{13}{subsubsection.5.2.6}}
1.127 +\newlabel{lst:TTlookup}{{7}{13}{Algorithmus von Prim\relax }{lstlisting.7}{}}
1.128 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {7}Algorithmus von Prim}{13}{lstlisting.7}}
1.129 +\BKM@entry{id=38,dest={73656374696F6E2E36}}{42696E205061636B696E67}
1.130 +\BKM@entry{id=39,dest={73756273656374696F6E2E362E31}}{4F6E6C696E652056657266616872656E}
1.131 +\BKM@entry{id=40,dest={73756273756273656374696F6E2E362E312E31}}{4E65787420466974205C284E465C29}
1.132 +\BKM@entry{id=41,dest={73756273756273656374696F6E2E362E312E32}}{46697273742D466974205C2846465C29}
1.133 +\@writefile{toc}{\contentsline {section}{\numberline {6}Bin Packing}{14}{section.6}}
1.134 +\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Online Verfahren}{14}{subsection.6.1}}
1.135 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.1}Next Fit (NF)}{14}{subsubsection.6.1.1}}
1.136 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.2}First-Fit (FF)}{14}{subsubsection.6.1.2}}
1.137 +\BKM@entry{id=42,dest={73756273756273656374696F6E2E362E312E33}}{426573742D466974205C2842465C29}
1.138 +\BKM@entry{id=43,dest={73756273656374696F6E2E362E32}}{4F66666C696E652056657266616872656E}
1.139 +\BKM@entry{id=44,dest={73756273756273656374696F6E2E362E322E31}}{4669727374204669742044656372656173696E67205C28464644206F6465722046464E495C29}
1.140 +\BKM@entry{id=45,dest={73756273756273656374696F6E2E362E322E32}}{42657374204669742044656372656173696E67205C284246445C29}
1.141 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.3}Best-Fit (BF)}{15}{subsubsection.6.1.3}}
1.142 +\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Offline Verfahren}{15}{subsection.6.2}}
1.143 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.1}First Fit Decreasing (FFD oder FFNI)}{15}{subsubsection.6.2.1}}
1.144 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.2}Best Fit Decreasing (BFD)}{15}{subsubsection.6.2.2}}
1.145 +\BKM@entry{id=46,dest={73656374696F6E2E37}}{44796E616D69736368652050726F6772616D6D696572756E67}
1.146 +\BKM@entry{id=47,dest={73756273656374696F6E2E372E31}}{4D61747269786B657474656E70726F64756B74205C28544F444F5C29}
1.147 +\BKM@entry{id=48,dest={73756273656374696F6E2E372E32}}{4F7074696D616C652053756368625C333434756D65205C28544F444F5C29}
1.148 +\BKM@entry{id=49,dest={73756273656374696F6E2E372E33}}{4564697469657264697374616E7A}
1.149 +\@writefile{toc}{\contentsline {section}{\numberline {7}Dynamische Programmierung}{16}{section.7}}
1.150 +\@writefile{toc}{\contentsline {subsection}{\numberline {7.1}Matrixkettenprodukt (TODO)}{16}{subsection.7.1}}
1.151 +\@writefile{toc}{\contentsline {subsection}{\numberline {7.2}Optimale Suchb\"aume (TODO)}{16}{subsection.7.2}}
1.152 +\@writefile{toc}{\contentsline {subsection}{\numberline {7.3}Editierdistanz}{16}{subsection.7.3}}
1.153 +\BKM@entry{id=50,dest={73656374696F6E2E38}}{537563686520696E2054657874656E}
1.154 +\newlabel{lst:TTlookup}{{8}{17}{Algorithmus zur Editierdistanz\relax }{lstlisting.8}{}}
1.155 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {8}Algorithmus zur Editierdistanz}{17}{lstlisting.8}}
1.156 +\newlabel{lst:TTlookup}{{9}{17}{Algorithmus zum Spurgraphen\relax }{lstlisting.9}{}}
1.157 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {9}Algorithmus zum Spurgraphen}{17}{lstlisting.9}}
1.158 +\@writefile{toc}{\contentsline {section}{\numberline {8}Suche in Texten}{17}{section.8}}
1.159 +\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces next[j] Beispiel}}{17}{table.2}}
1.160 +\newlabel{tab:nextJ}{{2}{17}{next[j] Beispiel\relax }{table.2}{}}
1.161 +\newlabel{lst:TTlookup}{{10}{18}{KMP Algorithmus\relax }{lstlisting.10}{}}
1.162 +\@writefile{lol}{\contentsline {lstlisting}{\numberline {10}KMP Algorithmus}{18}{lstlisting.10}}
1.163 +\BKM@entry{id=51,dest={617070656E6469782E41}}{4C616E6461752D53796D626F6C65}
1.164 +\@writefile{toc}{\contentsline {section}{\numberline {A}Landau-Symbole}{19}{appendix.A}}
1.165 +\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Definition der Landau Symbole}}{19}{figure.3}}
1.166 +\newlabel{fig:landau_sym}{{3}{19}{Definition der Landau Symbole\relax }{figure.3}{}}
1.167 +\newlabel{LastPage}{{}{19}{}{page.19}{}}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/AT_Exzerpt.bbl Tue Feb 22 19:14:19 2011 +0100
2.3 @@ -0,0 +1,25 @@
2.4 +\begin{thebibliography}{THC01}
2.5 +
2.6 +% this bibliography is generated by alphadin.bst [8.2] from 2005-12-21
2.7 +
2.8 +\providecommand{\url}[1]{\texttt{#1}}
2.9 +\expandafter\ifx\csname urlstyle\endcsname\relax
2.10 + \providecommand{\doi}[1]{doi: #1}\else
2.11 + \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi
2.12 +
2.13 +\bibitem[PW02]{2}
2.14 +\textsc{Peter~Widmayer}, Thomas~O.:
2.15 +\newblock \emph{Algorithmen und Datenstrukturen}.
2.16 +\newblock 4. Auflage.
2.17 +\newblock Spektrum Akademischer Verlag, 2002. --
2.18 +\newblock ISBN 978--3827410290
2.19 +
2.20 +\bibitem[THC01]{1}
2.21 +\textsc{Thomas H.~Cormen}, Robert L. Rivest und Cliford~S. Charles
2.22 + E.~Leiserson~L. Charles E.~Leiserson:
2.23 +\newblock \emph{Introduction to Algorithms}.
2.24 +\newblock 2nd.
2.25 +\newblock Prentice Hall India, 2001. --
2.26 +\newblock ISBN 978--8120321410
2.27 +
2.28 +\end{thebibliography}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/AT_Exzerpt.blg Tue Feb 22 19:14:19 2011 +0100
3.3 @@ -0,0 +1,3 @@
3.4 +This is BibTeX, Version 0.99cThe top-level auxiliary file: AT_Exzerpt.aux
3.5 +The style file: alphadin.bst
3.6 +Database file #1: literatur.bib
4.1 Binary file AT_Exzerpt.dvi has changed
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/AT_Exzerpt.log Tue Feb 22 19:14:19 2011 +0100
5.3 @@ -0,0 +1,779 @@
5.4 +This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8) (preloaded format=latex 2011.1.19) 18 FEB 2011 13:35
5.5 +entering extended mode
5.6 +**AT_Exzerpt.tex
5.7 +
5.8 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.9 +t\src\AT_Exzerpt.tex
5.10 +LaTeX2e <2009/09/24>
5.11 +Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, ge
5.12 +rman, ngerman, german-x-2009-06-19, ngerman-x-2009-06-19, french, loaded.
5.13 +("C:\Program Files\MikTex\tex\latex\base\article.cls"
5.14 +Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
5.15 +("C:\Program Files\MikTex\tex\latex\base\size11.clo"
5.16 +File: size11.clo 2007/10/19 v1.4h Standard LaTeX file (size option)
5.17 +)
5.18 +\c@part=\count79
5.19 +\c@section=\count80
5.20 +\c@subsection=\count81
5.21 +\c@subsubsection=\count82
5.22 +\c@paragraph=\count83
5.23 +\c@subparagraph=\count84
5.24 +\c@figure=\count85
5.25 +\c@table=\count86
5.26 +\abovecaptionskip=\skip41
5.27 +\belowcaptionskip=\skip42
5.28 +\bibindent=\dimen102
5.29 +)
5.30 +("C:\Program Files\MikTex\tex\generic\babel\babel.sty"
5.31 +Package: babel 2008/07/06 v3.8l The Babel package
5.32 +
5.33 +*************************************
5.34 +* Local config file bblopts.cfg used
5.35 +*
5.36 +("C:\Program Files\MikTex\tex\latex\00miktex\bblopts.cfg"
5.37 +File: bblopts.cfg 2006/07/31 v1.0 MiKTeX 'babel' configuration
5.38 +)
5.39 +("C:\Program Files\MikTex\tex\generic\babel\ngermanb.ldf"
5.40 +Language: ngermanb 2008/07/06 v2.6n new German support from the babel system
5.41 +
5.42 +("C:\Program Files\MikTex\tex\generic\babel\babel.def"
5.43 +File: babel.def 2008/07/06 v3.8l Babel common definitions
5.44 +\babel@savecnt=\count87
5.45 +\U@D=\dimen103
5.46 +)
5.47 +\l@naustrian = a dialect from \language\l@ngerman
5.48 +Package babel Info: Making " an active character on input line 92.
5.49 +))
5.50 +("C:\Program Files\MikTex\tex\latex\base\fontenc.sty"
5.51 +Package: fontenc 2005/09/27 v1.99g Standard LaTeX package
5.52 +
5.53 +("C:\Program Files\MikTex\tex\latex\base\t1enc.def"
5.54 +File: t1enc.def 2005/09/27 v1.99g Standard LaTeX file
5.55 +LaTeX Font Info: Redeclaring font encoding T1 on input line 43.
5.56 +))
5.57 +("C:\Program Files\MikTex\tex\latex\base\inputenc.sty"
5.58 +Package: inputenc 2008/03/30 v1.1d Input encoding file
5.59 +\inpenc@prehook=\toks14
5.60 +\inpenc@posthook=\toks15
5.61 +
5.62 +("C:\Program Files\MikTex\tex\latex\base\latin1.def"
5.63 +File: latin1.def 2008/03/30 v1.1d Input encoding file
5.64 +))
5.65 +("C:\Program Files\MikTex\tex\latex\hyperref\hyperref.sty"
5.66 +Package: hyperref 2010/10/30 v6.81t Hypertext links for LaTeX
5.67 +
5.68 +("C:\Program Files\MikTex\tex\generic\oberdiek\ltxcmds.sty"
5.69 +Package: ltxcmds 2010/04/26 v1.7 LaTeX kernel commands for general use (HO)
5.70 +)
5.71 +("C:\Program Files\MikTex\tex\generic\oberdiek\infwarerr.sty"
5.72 +Package: infwarerr 2010/04/08 v1.3 Providing info/warning/message (HO)
5.73 +)
5.74 +("C:\Program Files\MikTex\tex\latex\graphics\keyval.sty"
5.75 +Package: keyval 1999/03/16 v1.13 key=value parser (DPC)
5.76 +\KV@toks@=\toks16
5.77 +)
5.78 +("C:\Program Files\MikTex\tex\generic\oberdiek\kvsetkeys.sty"
5.79 +Package: kvsetkeys 2010/03/01 v1.9 Key value parser (HO)
5.80 +
5.81 +("C:\Program Files\MikTex\tex\generic\oberdiek\etexcmds.sty"
5.82 +Package: etexcmds 2010/01/28 v1.3 Prefix for e-TeX command names (HO)
5.83 +Package etexcmds Info: Could not find \expanded.
5.84 +(etexcmds) That can mean that you are not using pdfTeX 1.50 or
5.85 +(etexcmds) that some package has redefined \expanded.
5.86 +(etexcmds) In the latter case, load this package earlier.
5.87 +))
5.88 +("C:\Program Files\MikTex\tex\generic\oberdiek\pdfescape.sty"
5.89 +Package: pdfescape 2010/03/01 v1.9 Provides hex, PDF name and string conversion
5.90 +s (HO)
5.91 +
5.92 +("C:\Program Files\MikTex\tex\generic\oberdiek\pdftexcmds.sty"
5.93 +Package: pdftexcmds 2010/04/01 v0.9 Utility functions of pdfTeX for LuaTeX (HO)
5.94 +
5.95 +
5.96 +("C:\Program Files\MikTex\tex\generic\oberdiek\ifluatex.sty"
5.97 +Package: ifluatex 2010/03/01 v1.3 Provides the ifluatex switch (HO)
5.98 +Package ifluatex Info: LuaTeX not detected.
5.99 +)
5.100 +Package pdftexcmds Info: LuaTeX not detected.
5.101 +Package pdftexcmds Info: \pdf@primitive is available.
5.102 +Package pdftexcmds Info: \pdf@ifprimitive is available.
5.103 +))
5.104 +("C:\Program Files\MikTex\tex\generic\oberdiek\ifpdf.sty"
5.105 +Package: ifpdf 2010/01/28 v2.1 Provides the ifpdf switch (HO)
5.106 +Package ifpdf Info: pdfTeX in pdf mode not detected.
5.107 +)
5.108 +("C:\Program Files\MikTex\tex\generic\oberdiek\ifvtex.sty"
5.109 +Package: ifvtex 2010/03/01 v1.5 Switches for detecting VTeX and its modes (HO)
5.110 +Package ifvtex Info: VTeX not detected.
5.111 +)
5.112 +("C:\Program Files\MikTex\tex\generic\ifxetex\ifxetex.sty"
5.113 +Package: ifxetex 2010/09/12 v0.6 Provides ifxetex conditional
5.114 +)
5.115 +("C:\Program Files\MikTex\tex\latex\oberdiek\hycolor.sty"
5.116 +Package: hycolor 2009/12/12 v1.6 Color options of hyperref/bookmark (HO)
5.117 +
5.118 +("C:\Program Files\MikTex\tex\latex\oberdiek\xcolor-patch.sty"
5.119 +Package: xcolor-patch 2009/12/12 xcolor patch
5.120 +))
5.121 +("C:\Program Files\MikTex\tex\latex\oberdiek\letltxmacro.sty"
5.122 +Package: letltxmacro 2008/06/24 v1.3 Let assignment for LaTeX macros (HO)
5.123 +)
5.124 +("C:\Program Files\MikTex\tex\latex\oberdiek\kvoptions.sty"
5.125 +Package: kvoptions 2010/02/22 v3.7 Keyval support for LaTeX options (HO)
5.126 +)
5.127 +\@linkdim=\dimen104
5.128 +\Hy@linkcounter=\count88
5.129 +\Hy@pagecounter=\count89
5.130 +
5.131 +("C:\Program Files\MikTex\tex\latex\hyperref\pd1enc.def"
5.132 +File: pd1enc.def 2010/10/30 v6.81t Hyperref: PDFDocEncoding definition (HO)
5.133 +)
5.134 +("C:\Program Files\MikTex\tex\generic\oberdiek\intcalc.sty"
5.135 +Package: intcalc 2007/09/27 v1.1 Expandable integer calculations (HO)
5.136 +)
5.137 +\Hy@SavedSpaceFactor=\count90
5.138 +
5.139 +("C:\Program Files\MikTex\tex\latex\00miktex\hyperref.cfg"
5.140 +File: hyperref.cfg 2002/06/06 v1.2 hyperref configuration of TeXLive
5.141 +)
5.142 +Package hyperref Info: Option `colorlinks' set `true' on input line 3872.
5.143 +Package hyperref Info: Hyper figures OFF on input line 3976.
5.144 +Package hyperref Info: Link nesting OFF on input line 3981.
5.145 +Package hyperref Info: Hyper index ON on input line 3984.
5.146 +Package hyperref Info: Plain pages OFF on input line 3991.
5.147 +Package hyperref Info: Backreferencing OFF on input line 3996.
5.148 +Package hyperref Info: Implicit mode ON; LaTeX internals redefined.
5.149 +Package hyperref Info: Bookmarks ON on input line 4211.
5.150 +\c@Hy@tempcnt=\count91
5.151 +
5.152 +("C:\Program Files\MikTex\tex\latex\ltxmisc\url.sty"
5.153 +\Urlmuskip=\muskip10
5.154 +Package: url 2006/04/12 ver 3.3 Verb mode for urls, etc.
5.155 +)
5.156 +LaTeX Info: Redefining \url on input line 4566.
5.157 +
5.158 +("C:\Program Files\MikTex\tex\generic\oberdiek\bitset.sty"
5.159 +Package: bitset 2007/09/28 v1.0 Data type bit set (HO)
5.160 +
5.161 +("C:\Program Files\MikTex\tex\generic\oberdiek\bigintcalc.sty"
5.162 +Package: bigintcalc 2007/11/11 v1.1 Expandable big integer calculations (HO)
5.163 +))
5.164 +\Fld@menulength=\count92
5.165 +\Field@Width=\dimen105
5.166 +\Fld@charsize=\dimen106
5.167 +Package hyperref Info: Hyper figures OFF on input line 5626.
5.168 +Package hyperref Info: Link nesting OFF on input line 5631.
5.169 +Package hyperref Info: Hyper index ON on input line 5634.
5.170 +Package hyperref Info: backreferencing OFF on input line 5641.
5.171 +Package hyperref Info: Link coloring ON on input line 5644.
5.172 +Package hyperref Info: Link coloring with OCG OFF on input line 5651.
5.173 +Package hyperref Info: PDF/A mode OFF on input line 5656.
5.174 +LaTeX Info: Redefining \ref on input line 5696.
5.175 +LaTeX Info: Redefining \pageref on input line 5700.
5.176 +
5.177 +("C:\Program Files\MikTex\tex\generic\oberdiek\atbegshi.sty"
5.178 +Package: atbegshi 2010/03/25 v1.12 At begin shipout hook (HO)
5.179 +)
5.180 +\Hy@abspage=\count93
5.181 +\c@Item=\count94
5.182 +\c@Hfootnote=\count95
5.183 +)
5.184 +
5.185 +Package hyperref Message: Driver (default): hdvips.
5.186 +
5.187 +("C:\Program Files\MikTex\tex\latex\hyperref\hdvips.def"
5.188 +File: hdvips.def 2010/10/30 v6.81t Hyperref driver for dvips
5.189 +
5.190 +("C:\Program Files\MikTex\tex\latex\hyperref\pdfmark.def"
5.191 +File: pdfmark.def 2010/10/30 v6.81t Hyperref definitions for pdfmark specials
5.192 +\pdf@docset=\toks17
5.193 +\pdf@box=\box26
5.194 +\pdf@toks=\toks18
5.195 +\pdf@defaulttoks=\toks19
5.196 +\Fld@listcount=\count96
5.197 +\c@bookmark@seq@number=\count97
5.198 +
5.199 +("C:\Program Files\MikTex\tex\latex\oberdiek\rerunfilecheck.sty"
5.200 +Package: rerunfilecheck 2010/03/16 v1.6 Rerun checks for auxiliary files (HO)
5.201 +
5.202 +("C:\Program Files\MikTex\tex\latex\oberdiek\atveryend.sty"
5.203 +Package: atveryend 2010/03/24 v1.5 Hooks at very end of document (HO)
5.204 +Package atveryend Info: \enddocument detected (standard).
5.205 +)
5.206 +("C:\Program Files\MikTex\tex\generic\oberdiek\uniquecounter.sty"
5.207 +Package: uniquecounter 2009/12/18 v1.1 Provides unlimited unique counter (HO)
5.208 +)
5.209 +Package uniquecounter Info: New unique counter `rerunfilecheck' on input line 2
5.210 +71.
5.211 +)
5.212 +\Hy@SectionHShift=\skip43
5.213 +))
5.214 +("C:\Program Files\MikTex\tex\latex\vaucanson-g\vaucanson-g.sty"
5.215 +Package: vaucanson-g 2008/10/27 package wrapper for VauCanSon-G v. 0.4
5.216 +
5.217 +("C:\Program Files\MikTex\tex\latex\base\ifthen.sty"
5.218 +Package: ifthen 2001/05/26 v1.1c Standard LaTeX ifthen package (DPC)
5.219 +)
5.220 +("C:\Program Files\MikTex\tex\latex\xcolor\xcolor.sty"
5.221 +Package: xcolor 2007/01/21 v2.11 LaTeX color extensions (UK)
5.222 +
5.223 +("C:\Program Files\MikTex\tex\latex\00miktex\color.cfg"
5.224 +File: color.cfg 2007/01/18 v1.5 color configuration of teTeX/TeXLive
5.225 +)
5.226 +Package xcolor Info: Package option `pst' ignored on input line 216.
5.227 +Package xcolor Info: Driver file: dvips.def on input line 225.
5.228 +
5.229 +("C:\Program Files\MikTex\tex\latex\graphics\dvips.def"
5.230 +File: dvips.def 1999/02/16 v3.0i Driver-dependant file (DPC,SPQR)
5.231 +)
5.232 +Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1337.
5.233 +Package xcolor Info: Model `RGB' extended on input line 1353.
5.234 +Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1355.
5.235 +Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1356.
5.236 +Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1357.
5.237 +Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1358.
5.238 +Package xcolor Info: Model `Gray' substituted by `gray' on input line 1359.
5.239 +Package xcolor Info: Model `wave' substituted by `hsb' on input line 1360.
5.240 +)
5.241 +("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCColor-names.def")
5.242 +("C:\Program Files\MikTex\tex\latex\pstricks\pstricks.sty"
5.243 +Package: pstricks 2010/08/28 v0.46 LaTeX wrapper for `PSTricks' (RN,HV)
5.244 +
5.245 +("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.tex"
5.246 +("C:\Program Files\MikTex\tex\generic\xkeyval\pst-xkey.tex"
5.247 +File: pst-xkey.tex 2005/11/25 v1.6 PSTricks specialization of xkeyval (HA)
5.248 +
5.249 +("C:\Program Files\MikTex\tex\latex\xkeyval\xkeyval.sty"
5.250 +Package: xkeyval 2008/08/13 v2.6a package option processing (HA)
5.251 +
5.252 +("C:\Program Files\MikTex\tex\generic\xkeyval\xkeyval.tex"
5.253 +\XKV@toks=\toks20
5.254 +\XKV@tempa@toks=\toks21
5.255 +\XKV@depth=\count98
5.256 +File: xkeyval.tex 2008/08/13 v2.6a key=value parser (HA)
5.257 +)))
5.258 +("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"
5.259 +`pst-fp' v0.05, 2010/01/17 (hv)
5.260 +\pstFP@xs=\count99
5.261 +\pstFP@xia=\count100
5.262 +\pstFP@xib=\count101
5.263 +\pstFP@xfa=\count102
5.264 +\pstFP@xfb=\count103
5.265 +\pstFP@rega=\count104
5.266 +\pstFP@regb=\count105
5.267 +\pstFP@regs=\count106
5.268 +\pstFP@times=\count107
5.269 +)
5.270 +\psLoopIndex=\count108
5.271 +
5.272 +`PSTricks' v2.12 <2010/09/16> (tvz)
5.273 +\pst@dima=\dimen107
5.274 +\pst@dimb=\dimen108
5.275 +\pst@dimc=\dimen109
5.276 +\pst@dimd=\dimen110
5.277 +\pst@dimg=\dimen111
5.278 +\pst@dimh=\dimen112
5.279 +\pst@dimm=\dimen113
5.280 +\pst@dimn=\dimen114
5.281 +\pst@dimo=\dimen115
5.282 +\pst@dimp=\dimen116
5.283 +\pst@hbox=\box27
5.284 +\pst@boxg=\box28
5.285 +\pst@cnta=\count109
5.286 +\pst@cntb=\count110
5.287 +\pst@cntc=\count111
5.288 +\pst@cntd=\count112
5.289 +\pst@cntg=\count113
5.290 +\pst@cnth=\count114
5.291 +\pst@cntm=\count115
5.292 +\pst@cntn=\count116
5.293 +\pst@cnto=\count117
5.294 +\pst@cntp=\count118
5.295 +\@zero=\count119
5.296 +\pst@toks=\toks22
5.297 +("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.con")
5.298 +\psunit=\dimen117
5.299 +\psxunit=\dimen118
5.300 +\psyunit=\dimen119
5.301 +\pslinewidth=\dimen120
5.302 +\psk@startLW=\dimen121
5.303 +\psk@endLW=\dimen122
5.304 +\pst@customdefs=\toks23
5.305 +\pslinearc=\dimen123
5.306 +\pst@symbolStep=\dimen124
5.307 +\pst@symbolWidth=\dimen125
5.308 +\everypsbox=\toks24
5.309 +\psframesep=\dimen126
5.310 +\pslabelsep=\dimen127
5.311 +\pst@shift=\dimen128
5.312 +\theoverlaybox=\box29
5.313 +)
5.314 +File: pstricks.tex 2010/09/16 v2.12 `PSTricks' (tvz,hv)
5.315 +
5.316 +("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex")
5.317 +File: pst-fp.tex 2010/09/16 v2.12 `PST-fp' (hv)
5.318 +)
5.319 +("C:\Program Files\MikTex\tex\latex\pst-node\pst-node.sty"
5.320 +Package: pst-node 2010/04/22 package wrapper for pst-node.tex
5.321 +
5.322 +("C:\Program Files\MikTex\tex\generic\pst-node\pst-node.tex"
5.323 + v1.13, 2010/06/06
5.324 +\psrow=\count120
5.325 +\pscol=\count121
5.326 +\psmatrixcnt=\count122
5.327 +\psrowsep=\skip44
5.328 +\pscolsep=\skip45
5.329 +\pst@args=\count123
5.330 +\num@pts=\count124
5.331 +\pst@argcnt=\count125
5.332 +)
5.333 +File: pst-node.tex 2010/06/06 1.13 `pst-node' (tvz)
5.334 +) ("C:\Program Files\MikTex\tex\latex\pst-plot\pst-plot.sty"
5.335 +Package: pst-plot 2010/01/22 package wrapper for pst-plot.tex
5.336 +("C:\Program Files\MikTex\tex\generic\pst-plot\pst-plot.tex"
5.337 +("C:\Program Files\MikTex\tex\generic\multido\multido.tex"
5.338 + v1.42, 2010/05/14 <tvz>
5.339 +\multido@count=\count126
5.340 +\multidocount=\count127
5.341 +\multido@stuff=\toks25
5.342 +) v1.21, 2010/09/28 (tvz,hv)
5.343 +\pstRadUnit=\dimen129
5.344 +\pstRadUnitInv=\dimen130
5.345 +\pst@linecnt=\count128
5.346 +\psk@subticksize=\dimen131
5.347 +\pst@xticksizeA=\dimen132
5.348 +\pst@xticksizeB=\dimen133
5.349 +\pst@xticksizeC=\dimen134
5.350 +\pst@yticksizeA=\dimen135
5.351 +\pst@yticksizeB=\dimen136
5.352 +\pst@yticksizeC=\dimen137
5.353 +\@digitcounter=\count129
5.354 +\psk@llx=\dimen138
5.355 +\psk@lly=\dimen139
5.356 +\psk@urx=\dimen140
5.357 +\psk@ury=\dimen141
5.358 +\pst@xunit=\dimen142
5.359 +\pst@yunit=\dimen143
5.360 +)
5.361 +File: pst-plot.tex 2010/09/28 1.21 `pst-plot' (tvz,hv)
5.362 +)
5.363 +("C:\Program Files\MikTex\tex\latex\pst-coil\pst-coil.sty"
5.364 +Package: pst-coil 2010/02/01 package wrapper for pst-coil.tex (hv)
5.365 +
5.366 +("C:\Program Files\MikTex\tex\generic\pst-coil\pst-coil.tex"
5.367 + v1.21, 2010/09/28)
5.368 +File: pst-coil.tex 2010/02/01 v1.03 `PST-coil' (tvz,hv)
5.369 +) ("C:\Program Files\MikTex\tex\latex\multido\multido.sty"
5.370 +Package: multido 2004/05/17 package wrapper for PSTricks `multido.tex', (HV/RN)
5.371 +
5.372 +)
5.373 +("C:\Program Files\MikTex\tex\latex\pst-3d\pst-3d.sty"
5.374 +Package: pst-3d 2009/07/28 package wrapper for pst-3d.tex (hv)
5.375 +
5.376 +("C:\Program Files\MikTex\tex\generic\pst-3d\pst-3d.tex"
5.377 +`PST-3d' v1.11, 2010/02/14 (tvz))
5.378 +File: pst-3d.tex 2010/02/14 v1.11 `PST-3d' (hv)
5.379 +)
5.380 +("C:\Program Files\MikTex\tex\latex\tools\calc.sty"
5.381 +Package: calc 2007/08/22 v4.3 Infix arithmetic (KKT,FJ)
5.382 +\calc@Acount=\count130
5.383 +\calc@Bcount=\count131
5.384 +\calc@Adimen=\dimen144
5.385 +\calc@Bdimen=\dimen145
5.386 +\calc@Askip=\skip46
5.387 +\calc@Bskip=\skip47
5.388 +LaTeX Info: Redefining \setlength on input line 76.
5.389 +LaTeX Info: Redefining \addtolength on input line 77.
5.390 +\calc@Ccount=\count132
5.391 +\calc@Cskip=\skip48
5.392 +)
5.393 +("C:\Program Files\MikTex\tex\generic\vaucanson-g\Vaucanson-G.tex"
5.394 +\MediumStateDiameter=\skip49
5.395 +\SmallStateDiameter=\skip50
5.396 +\LargeStateDiameter=\skip51
5.397 +\VerySmallStateDiameter=\skip52
5.398 +\StateLineWidth=\skip53
5.399 +\EdgeLineWidth=\skip54
5.400 +\EdgeArrowWidth=\skip55
5.401 +\EdgeDblArrowWidth=\skip56
5.402 +\ZZSize=\skip57
5.403 +\EdgeOffset=\skip58
5.404 +\EdgeNodeSep=\skip59
5.405 +\VaucArcOffset=\skip60
5.406 +\LoopOffset=\skip61
5.407 +\LoopVarOffset=\skip62
5.408 +\TransLabelSep=\skip63
5.409 +\VertShiftH=\skip64
5.410 +LaTeX Font Info: External font `cmex10' loaded for size
5.411 +(Font) <10.95> on input line 206.
5.412 +LaTeX Font Info: External font `cmex10' loaded for size
5.413 +(Font) <8> on input line 206.
5.414 +LaTeX Font Info: External font `cmex10' loaded for size
5.415 +(Font) <6> on input line 206.
5.416 +\VertShiftD=\skip65
5.417 +\VertShift=\skip66
5.418 +\StateLineWid=\skip67
5.419 +\StateDiam=\skip68
5.420 +\VaucAOS=\skip69
5.421 +\VaucAOSdiag=\skip70
5.422 +\VariableStateIntDiam=\skip71
5.423 +\VariableStateWidth=\skip72
5.424 +\VariableStateITPos=\skip73
5.425 +\ExtraSpace=\skip74
5.426 +\EdgeLineWid=\skip75
5.427 +\EdgeArrowSZDim=\skip76
5.428 +\EdgeLineBord=\skip77
5.429 +\ZZSiZ=\skip78
5.430 +\EdgeOff=\skip79
5.431 +\VaucArcOff=\skip80
5.432 +\LoopOff=\skip81
5.433 +\LoopVarOff=\skip82
5.434 +\EdgeNodeSP=\skip83
5.435 +\TransLabelSP=\skip84
5.436 +\c@anglea=\count133
5.437 +\c@angleb=\count134
5.438 +)
5.439 +\VaucMinHeight=\skip85
5.440 +\VaucMaxHeight=\skip86
5.441 +
5.442 +("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCPref-default.tex"))
5.443 +("C:\Program Files\MikTex\tex\latex\oberdiek\hypcap.sty"
5.444 +Package: hypcap 2008/09/08 v1.10 Adjusting anchors of captions (HO)
5.445 +)
5.446 +("C:\Program Files\MikTex\tex\latex\fancyhdr\fancyhdr.sty"
5.447 +\fancy@headwidth=\skip87
5.448 +\f@ncyO@elh=\skip88
5.449 +\f@ncyO@erh=\skip89
5.450 +\f@ncyO@olh=\skip90
5.451 +\f@ncyO@orh=\skip91
5.452 +\f@ncyO@elf=\skip92
5.453 +\f@ncyO@erf=\skip93
5.454 +\f@ncyO@olf=\skip94
5.455 +\f@ncyO@orf=\skip95
5.456 +)
5.457 +("C:\Program Files\MikTex\tex\latex\graphics\graphicx.sty"
5.458 +Package: graphicx 1999/02/16 v1.0f Enhanced LaTeX Graphics (DPC,SPQR)
5.459 +
5.460 +("C:\Program Files\MikTex\tex\latex\graphics\graphics.sty"
5.461 +Package: graphics 2009/02/05 v1.0o Standard LaTeX Graphics (DPC,SPQR)
5.462 +
5.463 +("C:\Program Files\MikTex\tex\latex\graphics\trig.sty"
5.464 +Package: trig 1999/03/16 v1.09 sin cos tan (DPC)
5.465 +)
5.466 +("C:\Program Files\MikTex\tex\latex\00miktex\graphics.cfg"
5.467 +File: graphics.cfg 2007/01/18 v1.5 graphics configuration of teTeX/TeXLive
5.468 +)
5.469 +Package graphics Info: Driver file: dvips.def on input line 91.
5.470 +)
5.471 +\Gin@req@height=\dimen146
5.472 +\Gin@req@width=\dimen147
5.473 +)
5.474 +("C:\Program Files\MikTex\tex\latex\lastpage\lastpage.sty"
5.475 +Package: lastpage 2010/09/24 v1.2f Refers to last page's name (HMM; JPG)
5.476 +)
5.477 +("C:\Program Files\MikTex\tex\latex\preprint\fullpage.sty"
5.478 +Package: fullpage 1999/02/23 1.1 (PWD)
5.479 +\FP@margin=\skip96
5.480 +)
5.481 +("C:\Program Files\MikTex\tex\latex\ams\classes\amsthm.sty"
5.482 +Package: amsthm 2004/08/06 v2.20
5.483 +\thm@style=\toks26
5.484 +\thm@bodyfont=\toks27
5.485 +\thm@headfont=\toks28
5.486 +\thm@notefont=\toks29
5.487 +\thm@headpunct=\toks30
5.488 +\thm@preskip=\skip97
5.489 +\thm@postskip=\skip98
5.490 +\thm@headsep=\skip99
5.491 +\dth@everypar=\toks31
5.492 +)
5.493 +("C:\Program Files\MikTex\tex\latex\ams\math\amsmath.sty"
5.494 +Package: amsmath 2000/07/18 v2.13 AMS math features
5.495 +\@mathmargin=\skip100
5.496 +
5.497 +For additional information on amsmath, use the `?' option.
5.498 +("C:\Program Files\MikTex\tex\latex\ams\math\amstext.sty"
5.499 +Package: amstext 2000/06/29 v2.01
5.500 +
5.501 +("C:\Program Files\MikTex\tex\latex\ams\math\amsgen.sty"
5.502 +File: amsgen.sty 1999/11/30 v2.0
5.503 +\@emptytoks=\toks32
5.504 +\ex@=\dimen148
5.505 +))
5.506 +("C:\Program Files\MikTex\tex\latex\ams\math\amsbsy.sty"
5.507 +Package: amsbsy 1999/11/29 v1.2d
5.508 +\pmbraise@=\dimen149
5.509 +)
5.510 +("C:\Program Files\MikTex\tex\latex\ams\math\amsopn.sty"
5.511 +Package: amsopn 1999/12/14 v2.01 operator names
5.512 +)
5.513 +\inf@bad=\count135
5.514 +LaTeX Info: Redefining \frac on input line 211.
5.515 +\uproot@=\count136
5.516 +\leftroot@=\count137
5.517 +LaTeX Info: Redefining \overline on input line 307.
5.518 +\classnum@=\count138
5.519 +\DOTSCASE@=\count139
5.520 +LaTeX Info: Redefining \ldots on input line 379.
5.521 +LaTeX Info: Redefining \dots on input line 382.
5.522 +LaTeX Info: Redefining \cdots on input line 467.
5.523 +\Mathstrutbox@=\box30
5.524 +\strutbox@=\box31
5.525 +\big@size=\dimen150
5.526 +LaTeX Font Info: Redeclaring font encoding OML on input line 567.
5.527 +LaTeX Font Info: Redeclaring font encoding OMS on input line 568.
5.528 +\macc@depth=\count140
5.529 +\c@MaxMatrixCols=\count141
5.530 +\dotsspace@=\muskip11
5.531 +\c@parentequation=\count142
5.532 +\dspbrk@lvl=\count143
5.533 +\tag@help=\toks33
5.534 +\row@=\count144
5.535 +\column@=\count145
5.536 +\maxfields@=\count146
5.537 +\andhelp@=\toks34
5.538 +\eqnshift@=\dimen151
5.539 +\alignsep@=\dimen152
5.540 +\tagshift@=\dimen153
5.541 +\tagwidth@=\dimen154
5.542 +\totwidth@=\dimen155
5.543 +\lineht@=\dimen156
5.544 +\@envbody=\toks35
5.545 +\multlinegap=\skip101
5.546 +\multlinetaggap=\skip102
5.547 +\mathdisplay@stack=\toks36
5.548 +LaTeX Info: Redefining \[ on input line 2666.
5.549 +LaTeX Info: Redefining \] on input line 2667.
5.550 +)
5.551 +("C:\Program Files\MikTex\tex\latex\amsfonts\amsfonts.sty"
5.552 +Package: amsfonts 2009/06/22 v3.00 Basic AMSFonts support
5.553 +\symAMSa=\mathgroup4
5.554 +\symAMSb=\mathgroup5
5.555 +LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold'
5.556 +(Font) U/euf/m/n --> U/euf/b/n on input line 96.
5.557 +)
5.558 +("C:\Program Files\MikTex\tex\latex\float\float.sty"
5.559 +Package: float 2001/11/08 v1.3d Float enhancements (AL)
5.560 +\c@float@type=\count147
5.561 +\float@exts=\toks37
5.562 +\float@box=\box32
5.563 +\@float@everytoks=\toks38
5.564 +\@floatcapt=\box33
5.565 +)
5.566 +("C:\Program Files\MikTex\tex\latex\paralist\paralist.sty"
5.567 +Package: paralist 2002/03/18 v2.3b Extended list environments (BS)
5.568 +\pltopsep=\skip103
5.569 +\plpartopsep=\skip104
5.570 +\plitemsep=\skip105
5.571 +\plparsep=\skip106
5.572 +\pl@lab=\toks39
5.573 +)
5.574 +("C:\Program Files\MikTex\tex\latex\listings\listings.sty"
5.575 +\lst@mode=\count148
5.576 +\lst@gtempboxa=\box34
5.577 +\lst@token=\toks40
5.578 +\lst@length=\count149
5.579 +\lst@currlwidth=\dimen157
5.580 +\lst@column=\count150
5.581 +\lst@pos=\count151
5.582 +\lst@lostspace=\dimen158
5.583 +\lst@width=\dimen159
5.584 +\lst@newlines=\count152
5.585 +\lst@lineno=\count153
5.586 +\lst@maxwidth=\dimen160
5.587 +
5.588 +("C:\Program Files\MikTex\tex\latex\listings\lstmisc.sty"
5.589 +File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz)
5.590 +\c@lstnumber=\count154
5.591 +\lst@skipnumbers=\count155
5.592 +\lst@framebox=\box35
5.593 +)
5.594 +("C:\Program Files\MikTex\tex\latex\listings\listings.cfg"
5.595 +File: listings.cfg 2007/02/22 1.4 listings configuration
5.596 +))
5.597 +Package: listings 2007/02/22 1.4 (Carsten Heinz)
5.598 +
5.599 +("C:\Program Files\MikTex\tex\latex\oberdiek\bookmark.sty"
5.600 +Package: bookmark 2010/04/08 v1.12 PDF bookmarks (HO)
5.601 +
5.602 +("C:\Program Files\MikTex\tex\latex\oberdiek\auxhook.sty"
5.603 +Package: auxhook 2009/12/14 v1.2 Hooks for auxiliary files (HO)
5.604 +)
5.605 +("C:\Program Files\MikTex\tex\latex\oberdiek\bkm-dvips.def"
5.606 +File: bkm-dvips.def 2010/04/08 v1.12 bookmark driver for dvips (HO)
5.607 +\BKM@id=\count156
5.608 +))
5.609 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.610 +t\src\AT_Exzerpt.aux
5.611 +
5.612 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.613 +
5.614 +
5.615 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.616 +
5.617 +
5.618 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.619 +
5.620 +
5.621 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.622 +
5.623 +
5.624 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.625 +
5.626 +
5.627 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.628 +
5.629 +
5.630 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.631 +
5.632 +
5.633 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.634 +
5.635 +
5.636 +LaTeX Warning: Label `lst:TTlookup' multiply defined.
5.637 +
5.638 +)
5.639 +LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 27.
5.640 +LaTeX Font Info: ... okay on input line 27.
5.641 +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 27.
5.642 +LaTeX Font Info: ... okay on input line 27.
5.643 +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 27.
5.644 +LaTeX Font Info: ... okay on input line 27.
5.645 +LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 27.
5.646 +LaTeX Font Info: ... okay on input line 27.
5.647 +LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 27.
5.648 +LaTeX Font Info: ... okay on input line 27.
5.649 +LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 27.
5.650 +LaTeX Font Info: ... okay on input line 27.
5.651 +LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 27.
5.652 +LaTeX Font Info: ... okay on input line 27.
5.653 +\AtBeginShipoutBox=\box36
5.654 +Package hyperref Info: Link coloring ON on input line 27.
5.655 + ("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
5.656 +Package: nameref 2010/04/30 v2.40 Cross-referencing by name of section
5.657 +
5.658 +("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty"
5.659 +Package: refcount 2008/08/11 v3.1 Data extraction from references (HO)
5.660 +)
5.661 +("C:\Program Files\MikTex\tex\generic\oberdiek\gettitlestring.sty"
5.662 +Package: gettitlestring 2009/12/18 v1.3 Cleanup title references (HO)
5.663 +)
5.664 +\c@section@level=\count157
5.665 +)
5.666 +LaTeX Info: Redefining \ref on input line 27.
5.667 +LaTeX Info: Redefining \pageref on input line 27.
5.668 +LaTeX Info: Redefining \nameref on input line 27.
5.669 +Package lastpage Info: Have a look at the pagesLTS package at
5.670 +(lastpage) http://www.ctan.org/tex-archive/
5.671 +(lastpage) macros/latex/contrib/pagesLTS/
5.672 +(lastpage) or
5.673 +(lastpage) http://www.ctan.org/tex-archive/
5.674 +(lastpage) install/macros/latex/contrib/pagesLTS.tds.zip
5.675 +(lastpage) ! on input line 27.
5.676 +\c@lstlisting=\count158
5.677 +LaTeX Font Info: Try loading font information for U+msa on input line 29.
5.678 +
5.679 +("C:\Program Files\MikTex\tex\latex\amsfonts\umsa.fd"
5.680 +File: umsa.fd 2009/06/22 v3.00 AMS symbols A
5.681 +)
5.682 +LaTeX Font Info: Try loading font information for U+msb on input line 29.
5.683 +
5.684 +("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd"
5.685 +File: umsb.fd 2009/06/22 v3.00 AMS symbols B
5.686 +)
5.687 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.688 +t\src\AT_Exzerpt.toc [1
5.689 +
5.690 +])
5.691 +\tf@toc=\write3
5.692 + [2]
5.693 +LaTeX Font Info: Try loading font information for T1+cmtt on input line 34.
5.694 + ("C:\Program Files\MikTex\tex\latex\base\t1cmtt.fd"
5.695 +File: t1cmtt.fd 1999/05/25 v2.5h Standard LaTeX font definitions
5.696 +)
5.697 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.698 +t\src\AT_Exzerpt.bbl) [3]
5.699 +("C:\Program Files\MikTex\tex\latex\listings\lstlang1.sty"
5.700 +File: lstlang1.sty 2004/09/05 1.3 listings language file
5.701 +)
5.702 +Package hyperref Info: bookmark level for unknown lstlisting defaults to 0 on i
5.703 +nput line 88.
5.704 +
5.705 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.706 +t\src\code\quicksort.code
5.707 +LaTeX Font Info: Try loading font information for OMS+cmr on input line 6.
5.708 + ("C:\Program Files\MikTex\tex\latex\base\omscmr.fd"
5.709 +File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions
5.710 +)
5.711 +LaTeX Font Info: Font shape `OMS/cmr/m/it' in size <9> not available
5.712 +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 6.
5.713 +) [4]
5.714 +File: img/cl_pair.eps Graphic file (type eps)
5.715 + <img/cl_pair.eps> [5] [6]
5.716 +LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <10.95> not available
5.717 +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 181.
5.718 + [7] [8] [9]
5.719 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.720 +t\src\code\dijkstra.code)
5.721 +File: img/dijkstraExT.eps Graphic file (type eps)
5.722 + <img/dijkstraExT.eps>
5.723 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.724 +t\src\code\BelmanFord.code [10])
5.725 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.726 +t\src\code\AzyklischeNetzwerke.code)
5.727 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.728 +t\src\code\spannbaeumeGreedy.code [11])
5.729 +
5.730 +Package hyperref Warning: Token not allowed in a PDF string (PDFDocEncoding):
5.731 +(hyperref) removing `math shift' on input line 374.
5.732 +
5.733 +
5.734 +Package hyperref Warning: Token not allowed in a PDF string (PDFDocEncoding):
5.735 +(hyperref) removing `subscript' on input line 374.
5.736 +
5.737 +
5.738 +Package hyperref Warning: Token not allowed in a PDF string (PDFDocEncoding):
5.739 +(hyperref) removing `math shift' on input line 374.
5.740 +
5.741 +
5.742 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.743 +t\src\code\spannbaeumeKruskal.code) [12]
5.744 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.745 +t\src\code\spannbaeumePrim.code) [13] [14] [15]
5.746 +Underfull \hbox (badness 10000) in paragraph at lines 556--558
5.747 +
5.748 + []
5.749 +
5.750 +
5.751 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.752 +t\src\code\editierdistanz.code) [16]
5.753 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.754 +t\src\code\spurgraph.code)
5.755 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.756 +t\src\code\kmp.code [17]) [18]
5.757 +File: img/landau_sym.eps Graphic file (type eps)
5.758 + <img/landau_sym.eps>
5.759 +AED: lastpage setting LastPage
5.760 +[19]
5.761 +Package atveryend Info: Empty hook `BeforeClearDocument' on input line 624.
5.762 +Package atveryend Info: Executing hook `AfterLastShipout' on input line 624.
5.763 +\BKM@file=\write4
5.764 +
5.765 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\Exzerp
5.766 +t\src\AT_Exzerpt.aux)
5.767 +Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 624.
5.768 +
5.769 +
5.770 +LaTeX Warning: There were multiply-defined labels.
5.771 +
5.772 + )
5.773 +Here is how much of TeX's memory you used:
5.774 + 12117 strings out of 495270
5.775 + 172004 string characters out of 3180477
5.776 + 338892 words of memory out of 3000000
5.777 + 15029 multiletter control sequences out of 15000+200000
5.778 + 24142 words of font info for 67 fonts, out of 3000000 for 9000
5.779 + 14 hyphenation exceptions out of 8191
5.780 + 44i,10n,75p,593b,1910s stack positions out of 5000i,500n,10000p,200000b,50000s
5.781 +
5.782 +Output written on AT_Exzerpt.dvi (19 pages, 152592 bytes).
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/AT_Exzerpt.out.ps Tue Feb 22 19:14:19 2011 +0100
6.3 @@ -0,0 +1,223 @@
6.4 +%!
6.5 +/pdfmark where{pop}
6.6 +{/globaldict where{pop globaldict}{userdict}ifelse/pdfmark/cleartomark load put}
6.7 +ifelse
6.8 +[
6.9 +/Title(Einleitung)
6.10 +/Count -3
6.11 +/Action/GoTo/Dest(section.1)cvn
6.12 +/OUT pdfmark
6.13 +[
6.14 +/Title(Themen:)
6.15 +/Action/GoTo/Dest(subsection.1.1)cvn
6.16 +/OUT pdfmark
6.17 +[
6.18 +/Title(Problem-/Anwendungsbereiche:)
6.19 +/Action/GoTo/Dest(subsection.1.2)cvn
6.20 +/OUT pdfmark
6.21 +[
6.22 +/Title(Literatur:)
6.23 +/Action/GoTo/Dest(subsection.1.3)cvn
6.24 +/OUT pdfmark
6.25 +[
6.26 +/Title(Divide and Conquer)
6.27 +/Count -5
6.28 +/Action/GoTo/Dest(section.2)cvn
6.29 +/OUT pdfmark
6.30 +[
6.31 +/Title(Formulierung des Divide and Conquer Prinzips)
6.32 +/Action/GoTo/Dest(subsection.2.1)cvn
6.33 +/OUT pdfmark
6.34 +[
6.35 +/Title(Quicksort)
6.36 +/Count -2
6.37 +/Action/GoTo/Dest(subsection.2.2)cvn
6.38 +/OUT pdfmark
6.39 +[
6.40 +/Title(Algorithmus)
6.41 +/Action/GoTo/Dest(subsubsection.2.2.1)cvn
6.42 +/OUT pdfmark
6.43 +[
6.44 +/Title(Analyse)
6.45 +/Action/GoTo/Dest(subsubsection.2.2.2)cvn
6.46 +/OUT pdfmark
6.47 +[
6.48 +/Title(N\344chste Paare)
6.49 +/Count -2
6.50 +/Action/GoTo/Dest(subsection.2.3)cvn
6.51 +/OUT pdfmark
6.52 +[
6.53 +/Title(Algorithmus)
6.54 +/Action/GoTo/Dest(subsubsection.2.3.1)cvn
6.55 +/OUT pdfmark
6.56 +[
6.57 +/Title(Analyse)
6.58 +/Action/GoTo/Dest(subsubsection.2.3.2)cvn
6.59 +/OUT pdfmark
6.60 +[
6.61 +/Title(Segmentschnitt)
6.62 +/Count -2
6.63 +/Action/GoTo/Dest(subsection.2.4)cvn
6.64 +/OUT pdfmark
6.65 +[
6.66 +/Title(Algorithmus)
6.67 +/Action/GoTo/Dest(subsubsection.2.4.1)cvn
6.68 +/OUT pdfmark
6.69 +[
6.70 +/Title(Analyse)
6.71 +/Action/GoTo/Dest(subsubsection.2.4.2)cvn
6.72 +/OUT pdfmark
6.73 +[
6.74 +/Title(Polynomprodukt und Fast Fourier-Transformation \(TODO\))
6.75 +/Action/GoTo/Dest(subsection.2.5)cvn
6.76 +/OUT pdfmark
6.77 +[
6.78 +/Title(Randomisierung)
6.79 +/Count -5
6.80 +/Action/GoTo/Dest(section.3)cvn
6.81 +/OUT pdfmark
6.82 +[
6.83 +/Title(Randomisierter Quicksort)
6.84 +/Count -1
6.85 +/Action/GoTo/Dest(subsection.3.1)cvn
6.86 +/OUT pdfmark
6.87 +[
6.88 +/Title(Analyse)
6.89 +/Action/GoTo/Dest(subsubsection.3.1.1)cvn
6.90 +/OUT pdfmark
6.91 +[
6.92 +/Title(Randomisierter Primzahltest \(TODO\))
6.93 +/Action/GoTo/Dest(subsection.3.2)cvn
6.94 +/OUT pdfmark
6.95 +[
6.96 +/Title(RSA \(TODO\))
6.97 +/Action/GoTo/Dest(subsection.3.3)cvn
6.98 +/OUT pdfmark
6.99 +[
6.100 +/Title(Treaps \(TODO\))
6.101 +/Action/GoTo/Dest(subsection.3.4)cvn
6.102 +/OUT pdfmark
6.103 +[
6.104 +/Title(Hashing \(TODO\))
6.105 +/Action/GoTo/Dest(subsection.3.5)cvn
6.106 +/OUT pdfmark
6.107 +[
6.108 +/Title(Amortisierte Analyse \(TODO\))
6.109 +/Count -3
6.110 +/Action/GoTo/Dest(section.4)cvn
6.111 +/OUT pdfmark
6.112 +[
6.113 +/Title(Binomial Heaps \(TODO\))
6.114 +/Action/GoTo/Dest(subsection.4.1)cvn
6.115 +/OUT pdfmark
6.116 +[
6.117 +/Title(Fibonacci Heaps \(TODO\))
6.118 +/Action/GoTo/Dest(subsection.4.2)cvn
6.119 +/OUT pdfmark
6.120 +[
6.121 +/Title(Union Find \(TODO\))
6.122 +/Action/GoTo/Dest(subsection.4.3)cvn
6.123 +/OUT pdfmark
6.124 +[
6.125 +/Title(Greedy)
6.126 +/Count -2
6.127 +/Action/GoTo/Dest(section.5)cvn
6.128 +/OUT pdfmark
6.129 +[
6.130 +/Title(K\374rzeste \(billigste\) Wege)
6.131 +/Count -1
6.132 +/Action/GoTo/Dest(subsection.5.1)cvn
6.133 +/OUT pdfmark
6.134 +[
6.135 +/Title(Single Source Shortest Paths)
6.136 +/Action/GoTo/Dest(subsubsection.5.1.1)cvn
6.137 +/OUT pdfmark
6.138 +[
6.139 +/Title(Spannb\344ume minimalen Gewichts)
6.140 +/Count -6
6.141 +/Action/GoTo/Dest(subsection.5.2)cvn
6.142 +/OUT pdfmark
6.143 +[
6.144 +/Title(Das Wachsen von min. Spannb\344umen)
6.145 +/Action/GoTo/Dest(subsubsection.5.2.1)cvn
6.146 +/OUT pdfmark
6.147 +[
6.148 +/Title(Schnitte)
6.149 +/Action/GoTo/Dest(subsubsection.5.2.2)cvn
6.150 +/OUT pdfmark
6.151 +[
6.152 +/Title(Sichere Kanten)
6.153 +/Action/GoTo/Dest(subsubsection.5.2.3)cvn
6.154 +/OUT pdfmark
6.155 +[
6.156 +/Title(Der Graph GA)
6.157 +/Action/GoTo/Dest(subsubsection.5.2.4)cvn
6.158 +/OUT pdfmark
6.159 +[
6.160 +/Title(Algorithmus von Kruskal)
6.161 +/Action/GoTo/Dest(subsubsection.5.2.5)cvn
6.162 +/OUT pdfmark
6.163 +[
6.164 +/Title(Algorithmus von Prim)
6.165 +/Action/GoTo/Dest(subsubsection.5.2.6)cvn
6.166 +/OUT pdfmark
6.167 +[
6.168 +/Title(Bin Packing)
6.169 +/Count -2
6.170 +/Action/GoTo/Dest(section.6)cvn
6.171 +/OUT pdfmark
6.172 +[
6.173 +/Title(Online Verfahren)
6.174 +/Count -3
6.175 +/Action/GoTo/Dest(subsection.6.1)cvn
6.176 +/OUT pdfmark
6.177 +[
6.178 +/Title(Next Fit \(NF\))
6.179 +/Action/GoTo/Dest(subsubsection.6.1.1)cvn
6.180 +/OUT pdfmark
6.181 +[
6.182 +/Title(First-Fit \(FF\))
6.183 +/Action/GoTo/Dest(subsubsection.6.1.2)cvn
6.184 +/OUT pdfmark
6.185 +[
6.186 +/Title(Best-Fit \(BF\))
6.187 +/Action/GoTo/Dest(subsubsection.6.1.3)cvn
6.188 +/OUT pdfmark
6.189 +[
6.190 +/Title(Offline Verfahren)
6.191 +/Count -2
6.192 +/Action/GoTo/Dest(subsection.6.2)cvn
6.193 +/OUT pdfmark
6.194 +[
6.195 +/Title(First Fit Decreasing \(FFD oder FFNI\))
6.196 +/Action/GoTo/Dest(subsubsection.6.2.1)cvn
6.197 +/OUT pdfmark
6.198 +[
6.199 +/Title(Best Fit Decreasing \(BFD\))
6.200 +/Action/GoTo/Dest(subsubsection.6.2.2)cvn
6.201 +/OUT pdfmark
6.202 +[
6.203 +/Title(Dynamische Programmierung)
6.204 +/Count -3
6.205 +/Action/GoTo/Dest(section.7)cvn
6.206 +/OUT pdfmark
6.207 +[
6.208 +/Title(Matrixkettenprodukt \(TODO\))
6.209 +/Action/GoTo/Dest(subsection.7.1)cvn
6.210 +/OUT pdfmark
6.211 +[
6.212 +/Title(Optimale Suchb\344ume \(TODO\))
6.213 +/Action/GoTo/Dest(subsection.7.2)cvn
6.214 +/OUT pdfmark
6.215 +[
6.216 +/Title(Editierdistanz)
6.217 +/Action/GoTo/Dest(subsection.7.3)cvn
6.218 +/OUT pdfmark
6.219 +[
6.220 +/Title(Suche in Texten)
6.221 +/Action/GoTo/Dest(section.8)cvn
6.222 +/OUT pdfmark
6.223 +[
6.224 +/Title(Landau-Symbole)
6.225 +/Action/GoTo/Dest(appendix.A)cvn
6.226 +/OUT pdfmark
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/AT_Exzerpt.tex Tue Feb 22 19:14:19 2011 +0100
7.3 @@ -0,0 +1,624 @@
7.4 +\documentclass[a4paper,11pt,twoside]{article}
7.5 +
7.6 +\usepackage[ngerman]{babel} \usepackage[T1]{fontenc}
7.7 +\usepackage[latin1]{inputenc}
7.8 +\usepackage[colorlinks=true,linkcolor=black]{hyperref}
7.9 +
7.10 +\usepackage{vaucanson-g}
7.11 +\usepackage{hyperref}
7.12 +\usepackage{hypcap}
7.13 +\usepackage{fancyhdr}
7.14 +\usepackage{graphicx}
7.15 +\usepackage{lastpage}
7.16 +\usepackage[cm]{fullpage}
7.17 +\usepackage{amsthm, amsmath, amsfonts}
7.18 +\usepackage{float}
7.19 +\usepackage{paralist}
7.20 +\usepackage{listings}
7.21 +\usepackage{color}
7.22 +\usepackage{bookmark}
7.23 +
7.24 +\bibliographystyle{alphadin}
7.25 +
7.26 +\title{\underline{Exzerpt Algorithmentheorie WS10/11}}
7.27 +\author{Markus Lindenmann}
7.28 +\date{\today{} }
7.29 +
7.30 +\begin{document}
7.31 +\maketitle
7.32 +
7.33 +\tableofcontents \newpage
7.34 +
7.35 +\section{Einleitung}\label{sec:intro}
7.36 +Dozent: Matthias Westermann\\
7.37 +Website: \url{http://lak.informatik.uni-freiburg.de}\\
7.38 +Klausur: 09.03.2011\\
7.39 +Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
7.40 +\subsection{Themen:}
7.41 +\begin{itemize}
7.42 + \item[$\bullet$] Divide and Conquer
7.43 + \item[$\bullet$] Greedy Prinzip
7.44 + \item[$\bullet$] Dynamische Programmierung
7.45 + \item[$\bullet$] Randomisierung
7.46 + \item[$\bullet$] Amortisierte Analyse
7.47 +\end{itemize}
7.48 +\subsection{Problem-/Anwendungsbereiche:}
7.49 +\begin{itemize}
7.50 + \item[$\bullet$] Geometrische Algorithmen
7.51 + \item[$\bullet$] Algebraische Algorithmen
7.52 + \item[$\bullet$] Graphenalgorithmen
7.53 + \item[$\bullet$] Datenstrukturen
7.54 + \item[$\bullet$] Internet-Algorithmen
7.55 + \item[$\bullet$] Optimierungs-Verfahren
7.56 + \item[$\bullet$] Zeichenkettenverarbeitung
7.57 +\end{itemize}
7.58 +\subsection{Literatur:}
7.59 +\bibliography{literatur}
7.60 +\nocite{*}
7.61 +
7.62 +\newpage
7.63 +\section{Divide and Conquer}\label{sec:div&conq}
7.64 +\begin{itemize}
7.65 + \item[$\bullet$] Quicksort
7.66 + \item[$\bullet$] Formulierung und Analyse des Prinzips
7.67 + \item[$\bullet$] Geometrisches Devide and Conquer
7.68 + \begin{itemize}
7.69 + \item[-] Closest-Pair
7.70 + \item[-] Segmentschnitt
7.71 + \end{itemize}
7.72 +\end{itemize}
7.73 +
7.74 +\subsection{Formulierung des Divide and Conquer Prinzips}
7.75 +D\&C Verfahren zur Lösung eines Problems der Größe $n$
7.76 +\begin{itemize}
7.77 + \item[1.] Divide\\$n>2$: Teile das Problem in $k$ Teilprobleme der Größe $n_1,\ldots n_k$ ($k\geq2$)\\$n\leq c:$ Löse das Problem direkt
7.78 + \item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
7.79 + \item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
7.80 +\end{itemize}
7.81 +
7.82 +\subsection{Quicksort}\label{ch:qs}
7.83 +Wähle beliebiges Pivot Element $v$ (meist das letzte Element in der
7.84 +Input-Folge!) und sortiere alle Elemente aus der Menge, die größer sind als $v$
7.85 +rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen
7.86 +Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge
7.87 +$F$ nur ein Element beinhaltet, gebe $F$ zurück.
7.88 +\subsubsection{Algorithmus}
7.89 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus Quicksort,
7.90 +captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
7.91 +basicstyle=\footnotesize]{./code/quicksort.code}
7.92 +
7.93 +\subsubsection{Analyse}
7.94 +$T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
7.95 +\[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
7.96 +Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
7.97 +Divide- und Mergeaufwand: $DM(n)$\\
7.98 +$T(1)=a$\\
7.99 +$T(n)=2T(\frac{n}{2})+DM(n)$
7.100 +
7.101 +\subsection{Nächste Paare}
7.102 +Eingabe: $n$ Punkte in Ebene\\
7.103 +Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\
7.104 +Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
7.105 +\subsubsection{Algorithmus}
7.106 +\begin{itemize}
7.107 + \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
7.108 + \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
7.109 + \item[$\bullet$] Löse rekursiv auf Q und R
7.110 + \item[$\bullet$] Sortiere Punkte nach y-Koordinate
7.111 + \item[$\bullet$] Teste alle Paare, deren Abstand in der
7.112 + Sortierung kleiner als 16 ist (siehe unten)
7.113 + \item[$\bullet$] Füge zusammen
7.114 +\end{itemize}
7.115 +
7.116 +$\delta=$ Minimum der Teillösungen\\
7.117 +Gibt es $q\in Q$ und $r\in R$ mit $d(q,r)<\delta$, dann sind sowohl $q$ als auch $r$ höchstens $\delta$ von $L$ (Mitte) entfernt.\\
7.118 +\textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
7.119 +\textbf{Lösung:}\begin{itemize}
7.120 +\item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
7.121 +\item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
7.122 +\end{itemize}
7.123 +
7.124 +Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
7.125 +\begin{itemize}
7.126 + \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
7.127 + \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
7.128 + \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
7.129 +\end{itemize}
7.130 +
7.131 +\begin{figure}[H]
7.132 +\centering
7.133 +\includegraphics[scale=0.5]{img/cl_pair}
7.134 +\caption{Nächste Paare: Prüf Distanz}
7.135 +\label{cl_pair}
7.136 +\end{figure}
7.137 +
7.138 +\subsubsection{Analyse}
7.139 +\[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
7.140 +\[T(n)\leq an \log n \]
7.141 +
7.142 +\subsection{Segmentschnitt}
7.143 +Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
7.144 +Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
7.145 +
7.146 +\subsubsection{Algorithmus}
7.147 +\textbf{Divide \& Conquer:}\\Fallunterscheidung
7.148 +\begin{itemize}
7.149 + \item[1.] $\left| S\right| > 1$:\\ Teile S mittels einer vertikalen Gerade G in 2 gleichgroße Mengen $S_1$ (links von G) und $S_2$ (rechts von G). Führe rekursiv auf beiden Hälften aus.
7.150 + \item[2.] else: S enthält keine Schnitte
7.151 +\end{itemize}
7.152 +
7.153 +\textbf{Merge}\\
7.154 +Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
7.155 +\begin{itemize}
7.156 + \item[$\bullet$] L(S): y-Koordinate aller linken Endpunkte in S, deren rechter Partner nicht in S\\$=L(S_2)\cup(L(S_1)-R(S_2))$
7.157 + \item[$\bullet$] R(S): y-Koordinate aller rechten Endpunkte in S, deren linker Partner nicht in S\\$=R(S_1)\cup(R(S_2)-L(S_1))$
7.158 + \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
7.159 +\end{itemize}
7.160 +L,R sortiert nach steigender y-Koordinate\\
7.161 +V sortiert nach steigendem unteren Endpunkt\\
7.162 +\medskip
7.163 +
7.164 +\textbf{Basisfälle}\\
7.165 +S enthält nur ein Element s. Fallunterscheidung:
7.166 +\begin{itemize}
7.167 + \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
7.168 + \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
7.169 + \item[3.] $s=(x,y_1,y_2)$ ist ein vertikales Segment:\\$L(S)=\emptyset,\qquad R(S)=\emptyset,\qquad V(S)=\{[y_1,y_2]\}$
7.170 +\end{itemize}
7.171 +
7.172 +\subsubsection{Analyse}
7.173 +Eingabe wird Anfangs sortiert und in Array gespeichert
7.174 +\[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
7.175 +\[T(1)=O(1)\]
7.176 +\[O(n \log n + k \mid k=\#Schnittpunkte\]
7.177 +
7.178 +\subsection{Polynomprodukt und Fast Fourier-Transformation (TODO)}
7.179 +%TODO
7.180 +
7.181 +\newpage
7.182 +\section{Randomisierung}
7.183 +\begin{itemize}
7.184 + \item Klassen von randomisierten Algorithmen
7.185 + \begin{itemize}
7.186 + \item \textbf{Las Vegas}: \underline{immer} Korrekt, erwartete Laufzeit
7.187 + (randomisierter Qicksort)
7.188 + \item \textbf{Monte Carlo}: \underline{wahrscheinlich} (MC:mostly correct)
7.189 + Korrekt, garantierte Laufzeit (randomisierter Primzahltest)
7.190 + \end{itemize}
7.191 + \item Randomisierter Quicksort
7.192 + \item Randomisierter Primzahltest
7.193 + \item Kryptographie
7.194 +\end{itemize}
7.195 +\subsection{Randomisierter Quicksort}
7.196 + Refer to \ref{ch:qs} for basic description of the algorithm.\\
7.197 + Problem von Quicksort: bisher nimmt Quicksort immer das letzte Element in der
7.198 + Folge $\implies$ Worst-Case: sortierte Folge als Eingabe ($\Theta(n^2)$).
7.199 + Ziel: keine quadratische Laufzeit.\\
7.200 + Lösung: randomisierte Auswahl des Pivotelements an Stelle $i$. Anschließend
7.201 + tauschen von Position $i$ und $r$ (mit $r$=rechte Grenze des zu sortierenden
7.202 + Segments).
7.203 + \subsubsection{Analyse}
7.204 + \textbf{Analyse 1: erwartete Laufzeit}\\
7.205 + Mit Wahrscheinlichkeit $\frac{1}{n}$ wird das $i$-kleinste Element $S_i$
7.206 + gewählt wobei $n$ zu sortierenden Elemente vorhanden sind. Abhängig von der
7.207 + Wahl von $S_i$ ergeben sich Teilprobleme der Größe $i-1$ und $n-i$. Damit
7.208 + ergibt sich für die Laufzeit $T(n)$.
7.209 + \[T(n)=\frac{1}{n}(T(0)+T(n-1))+\frac{1}{n}(T(1)+T(n-2))+\ldots+\frac{1}{n}(T(k-1)+T(n-k))+\ldots+\]
7.210 + \[\frac{1}{n}(T(n-1)+T(0))+\Theta(n))\mid
7.211 + \Theta(n)\text{ für partition}\]
7.212 + \[=\frac{1}{n}\sum_{k=1}^n(T(k-1)+T(n-k))+\Theta(n)\]
7.213 + \[\frac{2}{n}\sum_{k=1}^nT(k-1)+\Theta(n)\]
7.214 + \[=O(n \log n)\]
7.215 + \textbf{Analys 2: Erwartete Anzahl der Vergleiche}\\
7.216 + $x_{ij}=
7.217 + \begin{cases}
7.218 + 1&\text{falls }S_i\text{ mit }S_j\text{ verglichen wird}\\
7.219 + 0&\text{sonst}
7.220 + \end{cases}$
7.221 + \[E\left[\sum_{i=1}^n\sum_{j>1}x_{ij}\right]=\sum_{i=1}^n\sum_{j>1}E[x_{ij}]\]
7.222 + $p_{ij} =$ Wahrscheinlichkeit $S_i$ wird mit $S_j$ verglichen
7.223 + \[E[x_{ij}=1\cdot p_{ij}+0\cdot(1-p_{ij}=p_{ij}\]
7.224 +\subsection{Randomisierter Primzahltest (TODO)}
7.225 +%TODO schnelle exponentiation
7.226 +\subsection{RSA (TODO)}
7.227 +%TODO
7.228 +%erw. Euklid
7.229 +\subsection{Treaps (TODO)}
7.230 +%TODO haben wir nicht so im detail gemacht wie Elsässer!
7.231 +\subsection{Hashing (TODO)}
7.232 +%TODO
7.233 +
7.234 +\newpage
7.235 +\section{Amortisierte Analyse (TODO)}
7.236 +%TODO
7.237 +\subsection{Binomial Heaps (TODO)}
7.238 +%TODO
7.239 +\subsection{Fibonacci Heaps (TODO)}
7.240 +%TODO
7.241 +\subsection{Union Find (TODO)}
7.242 +%TODO
7.243 +
7.244 +\newpage
7.245 +\section{Greedy}
7.246 +Momentan beste Teillösung wählen. Die Summe dieser optimalen Teillösung ergibt
7.247 +die gesamt Lösung. Möglicher Zustand der Gesamtlösung:
7.248 +\begin{itemize}
7.249 + \item Wir erhalten die optimale Gesamtlösung.
7.250 + \item Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom
7.251 + Optimum stets nur wenig abweicht.
7.252 + \item Die berechnete Lösung kann beliebig schlecht werden.
7.253 +\end{itemize}
7.254 +\underline{Beispiele:}
7.255 +\begin{itemize}
7.256 + \item Münzwechselproblem\\\textbf{Ziel:} Bezahlung eines Betrages in möglichst
7.257 + wenig Münzen und Banknoten.\\\textbf{Lösung (Greedy):} Wähle die maximale
7.258 + Anzahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der
7.259 + gewünschte Betrag erreicht ist. (Dies führt nur für bestimmte Werte der
7.260 + Zahlungsmittel zur optimalen Gesamtlösung!)
7.261 + \item Handlungsreisenden-Problem (Traveling Sales Man Problem,
7.262 + TSP)\\\textbf{Ziel:} Finden der billigsten Rundreise, diealle Orte genau
7.263 + einmal besucht.\\\textbf{Lösung (Greedy):} Gehe immer den günstigsten Weg vom
7.264 + aktuellen Knoten zu einem noch nicht besuchten Knoten. Wenn alle besucht
7.265 + wurden, kehre zum Anfang zurück. (Mit Greedy keine optimale Gesamtlösung!)
7.266 + \item Aktivitäten Auswahlproblem\\\textbf{Ziel:} möglichst viele Anfragen
7.267 + erfüllen. (Muss nicht bedeuten, dass die Ressource optimal
7.268 + genutzt wird!)\\\textbf{Lösung (Greedy):} Nimm die Anfrage, die am frühesten
7.269 + fertig ist. (optimale Gesamtlösung!)\\\textbf{Analyse:} $\Theta(n)$
7.270 +\end{itemize}
7.271 +
7.272 +\subsection{Kürzeste (billigste) Wege}
7.273 +Pfad $P=$ Folge von Knoten.
7.274 +Kosten eines Pfades:\[c(P)=\sum_{i=0}^{P.length-1}c(v_i,v_{i+1}\]
7.275 +Entfernung von $v$ nach $w$ sind die Kosten des
7.276 +günstigsten Pfades:\[dist(v,w)=inf{c(P)\mid P\text{= Weg von v nach
7.277 +w}}\]
7.278 +Kosten eines unerreichbaren Knoten sind definiert als $\infty$. Kosten eines
7.279 +Pfades in einem negativen Zyklus: $-\infty$. Es können also nur Graphen ohne
7.280 +negative Zyklen sinnvoll betrachtet werden!
7.281 +\subsubsection{Single Source Shortest Paths}
7.282 +Kürzeste/Günstigste Pfade von einem Knoten $s$ zu allen anderen Knoten. Hierfür
7.283 +nutzt man die Dreiecksungleichung über $dist(u,v)\mid (u,v)\in E$ und $s\in V$:
7.284 +\[dist(s,v)\leq dist(s,u)+dist(u,v)\]
7.285 +\textbf{Greedy-Ansatz}
7.286 +\begin{itemize}
7.287 + \item Überschätze die dist-Funktion \[dist(s,v)=\begin{cases}0&\text{ falls }
7.288 + v=s\\\infty&\text{ falls }v\neq s\end{cases}\]
7.289 + \item Solange eine Kante $e=(u,v)$ existiert mit
7.290 + $dist(s,v)>dist(s,u)+c(u,v)$ setze $dist(s,v)=dist(s,u)+c(u,v)$
7.291 +\end{itemize}
7.292 +Durch die Überschätzung kann die Dreicksungleichung nur noch für Knoten $s$ und
7.293 +seine direkten Nachfolger verletzt werden!\\Alle folgenden Verfahren basieren
7.294 +auf diesem Prinzip!\\
7.295 +%Elsässer führt einige Lemmas ein und beweist sie - diese beziehen sich auf den
7.296 +% ersten optimimierten Algorithmus und diesen erachte ich in Relation zu
7.297 +% Dijkstra als irrelevant!
7.298 +\textbf{Effiziente Implementierungen}
7.299 +Diese sind im Allgemeinen nicht bekannt, jedoch für wichtige Spezialfälle.
7.300 +\begin{itemize}
7.301 + \item Nicht-negative Netzwerke: \underline{Dijkstra}
7.302 + \item Netzwerke ohne negative Zyklen: \underline{Bellman-Ford}
7.303 + \item Azyklische Netzwerke
7.304 +\end{itemize}
7.305 +\underline{Dijkstra}
7.306 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
7.307 +Dijkstra, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
7.308 +basicstyle=\footnotesize]{./code/dijkstra.code}
7.309 +Dijkstra Beispiel:
7.310 +\begin{figure}
7.311 + \centering
7.312 + \includegraphics[scale=0.6]{img/dijkstraExT}
7.313 + \caption{Tree for Dijkstra Example}
7.314 + \label{fig:dijExT}
7.315 +\end{figure}
7.316 +\begin{table}[ht]
7.317 + \centering
7.318 + \begin{tabular}{|c c c c c c c|c|}
7.319 + \hline
7.320 + \multicolumn{7}{|c|}{DIST[v]} & \\
7.321 + \hline
7.322 + s & a & b & c & d & e & f & U\\\hline\hline
7.323 + 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & s,a,b,c,d,e,f\\
7.324 + 0* & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & a,b,c,d,e,f\\
7.325 + 0* & 6 & 7 & 5* & $\infty$ & $\infty$ & $\infty$ & a,b,d,e,f\\
7.326 + 0* & 6* & 7 & 5* & $\infty$ & $\infty$ & 14 & b,d,e,f\\
7.327 + 0* & 6* & 7* & 5* & 9 & 10 & 14 & d,e,f\\
7.328 + 0* & 6* & 7* & 5* & 9* & 10 & 11 & e,f\\
7.329 + 0* & 6* & 7* & 5* & 9* & 10* & 11 & f\\
7.330 + 0* & 6* & 7* & 5* & 9* & 10* & 11* & $\emptyset$\\\hline
7.331 + \end{tabular}
7.332 + \caption{Dijkstra Example}\label{tab:dijEx}
7.333 +\end{table}
7.334 +Komplexität:
7.335 +\[O(n\cdot(T_{insert}+T_{Empty}+T_{DeleteMin})+m\cdot T_{DecreaseKey}+m+n)\]
7.336 +Implementierung mit Fibonaci-Heaps:\\
7.337 +$T_{Insert}:O(1)$\\
7.338 +$T_{DeleteMin}:O(\log n)$ (amortisiert)\\
7.339 +$T_{DecreaseKey}:O(1)$ (amortisiert)
7.340 +\[O(n\log n+m)\]
7.341 +\underline{Bellman-Ford}
7.342 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
7.343 +Belman-Ford, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
7.344 +basicstyle=\footnotesize]{./code/BelmanFord.code}
7.345 +\underline{Azyklische Netzwerke}
7.346 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus für
7.347 +Azyklische Netzwerke, captionpos=b, numbers=left, numberstyle=\tiny,
7.348 +numbersep=5pt, basicstyle=\footnotesize]{./code/AzyklischeNetzwerke.code}
7.349 +\subsection{Spannbäume minimalen Gewichts}
7.350 +Ungerichteter Graph $G=(V,E)$, Kostenfunktion $c:E\rightarrow R$.\\Sei
7.351 +$T\subseteq E$ ein Baum (zusammenhängender azyklischer Teilgraph) Kosten von T:
7.352 +$c(T)=\sum_{(u,v)\in T}c(u,v)$.\\Ein minimaler Spannbaum ist ein Baum
7.353 +$T\subseteq E$, der alle Knoten in $V$ verbindet minimale Kosten hat.
7.354 +\subsubsection{Das Wachsen von min. Spannbäumen}
7.355 +\textbf{Invariante:} Verwalte Menge $A\subseteq E$, die Teilmenge eines
7.356 +minimalen Spannbaums ist.\\
7.357 +\textbf{Definition:} Eine Kante $(u,v)\in E\backslash A$ ist sicher für $A$, wenn
7.358 +$A\cup {(u,v)}$ Teilmenge eines minimalen Spannbaums ist.
7.359 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Greedy Algorithmus für
7.360 +Spannbäume, captionpos=b, numbers=left, numberstyle=\tiny,
7.361 +numbersep=5pt, basicstyle=\footnotesize]{./code/spannbaeumeGreedy.code}
7.362 +\subsubsection{Schnitte}
7.363 +Ein Schnitt $(S,V\backslash S)$ ist eine Partition von $V$. Eine Kante $(u,v)$
7.364 +schneidet $(S,V\backslash S)$, wenn ein Endpunkt in $S$ und der andere in
7.365 +$V\backslash S$ liegt.\\Ein Schnitt "`respektiert $A$"', wenn keine Kante aus
7.366 +$A$ den Schnitt schneidet.\\Eine Kante heißt minimal bzgl. eines Schnitts, wenn
7.367 +sie den Schnitt schneidet und unter allen solchen Kanten minimale Kosten hat.
7.368 +\subsubsection{Sichere Kanten}
7.369 +\textbf{Satz:} Sei $A$ Teilmenge eines minimalen Spannbaums $T$ und
7.370 +$(S,V\backslash S)$ ein Schnitt, der $A$ respektiert. Ist $(u,v)$ eine minimale
7.371 +Kante bzgl. $(S,V\S)$, dann ist $(u,v)$ sicher für $A$.\\
7.372 +\textbf{Beweis}: \begin{itemize}
7.373 + \item[1. Fall] $(u,v)\in T$ : ok
7.374 + \item[2. Fall] $(u,v)\not\in T$ : Wir konstruieren minimalen Spannbaum $T'$
7.375 + mit $(u,v)\in T'$ und $A\subseteq T'$.
7.376 +\end{itemize}
7.377 +\subsubsection{Der Graph $G_A$}
7.378 +\[G_A=(V,A)\]
7.379 +\begin{itemize}
7.380 + \item ist ein \underline{Wald}, d.h. eine Menge von Bäumen
7.381 + \item anfangs, wenn $A=\emptyset$, ist jeder Baum ein einzelner Knoten
7.382 + \item eine sichere Kante verbindet verschiedene Bäume
7.383 +\end{itemize}
7.384 +\textbf{Korollar:} Sei $B$ ein Baum in $G_A=(V,A)$. Ist $(u,v)$ eine Kante
7.385 +minimaler Kosten, die $B$ und einen anderen Baum in $G_A$ verbindet, dann ist
7.386 +$(u,v)$ sicher für A.
7.387 +\subsubsection{Algorithmus von Kruskal}
7.388 +Wähle stets eine Kante minimaler Kosten, die zwei Bäume $B_1$ und $B_2$ in $G_A$
7.389 +verbindet.
7.390 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
7.391 +Kruskal, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
7.392 +basicstyle=\footnotesize]{./code/spannbaeumeKruskal.code}
7.393 +Laufzeit: $O(m\alpha(n)+m+m\log n)$
7.394 +\subsubsection{Algorithmus von Prim}
7.395 +$A$ ist immer ein einziger Baum. Starte mit einem beliebigen Wurzelknoten $w$.
7.396 +Füge in jedem Schritt eine minimale Kante hinzu, die einen Knoten in $A$ mit
7.397 +einem Knoten in $V\backslash A$ verbindet.
7.398 +\textbf{Implementierung}\\$Q$: Prioritätenwarteschlange, die alle Knoten $v\in
7.399 +V\backslash A$ enthält.\\Schlüssel von $v$: minimale Kosten einer Kante, die $v$
7.400 +mit einem Knoten aus $A$ verbindet.\\Für einen Knoten $v$ ist $p[v]$ der
7.401 +Elter-Knoten von $v$ in dem Baum.\[A={(v,p[v]):v\in V-{w}-Q}\]
7.402 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
7.403 +Prim, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
7.404 +basicstyle=\footnotesize]{./code/spannbaeumePrim.code}
7.405 +Laufzeit: $O(n\log n+m)$
7.406 +
7.407 +\newpage
7.408 +\section{Bin Packing}
7.409 +\textbf{Problembeschreibung:}\\
7.410 +Man hat $n$ Objekte verschiedener Größe mit $0<s_i\leq1\mid 1\leq i\leq n$. Gesucht ist die kleinst mögliche Anzahl an Kisten (Bins) der Größe 1, mit der alle Objekte verpackt werden können.
7.411 +\subsection{Online Verfahren}
7.412 +Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste
7.413 +Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste,
7.414 +in die es zuerst gepackt wird.\\ Kein Online Bin Packing Verfahren
7.415 +kann stets eine optimale Lösung finden!\\ \textbf{Satz 1}: Es gibt
7.416 +Eingaben, die jeden Online Bin Packing Algorithmus zwingen,
7.417 +wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die
7.418 +minimal mögliche Binzahl ist.\\ \textbf{Beweis} Annahme: Online Bin
7.419 +Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$
7.420 +Bins.\\ Es wird eine Eingabe mit $2m$ Objekten angenommen. Die
7.421 +ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die
7.422 +zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$
7.423 +Kisten, da immer ein großes mit einem kleinen Paket kombiniert
7.424 +werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$
7.425 +Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$
7.426 +Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3}
7.427 +OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit:
7.428 +$b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid
7.429 +b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so
7.430 +folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach
7.431 +$2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können
7.432 +zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt
7.433 +werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl
7.434 +der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq
7.435 +b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m
7.436 +\wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn
7.437 +$b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem
7.438 +\underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten
7.439 +$<\frac{2}{3}m$ sein muss.
7.440 +
7.441 +\subsubsection{Next Fit (NF)}
7.442 +Verpacke das nächste Objekt in dieselbe Kiste wie das
7.443 +vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue
7.444 +Kiste und verpacke es dort.\\ \textbf{Satz 2}: (a) Für alle
7.445 +Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt
7.446 +Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\ \textbf{Beweis}\\ (a)
7.447 +Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1},
7.448 +B_{2k}$. Man weiß, dass die beinhalteten Objekte eine
7.449 +Summengröße $>1$ haben, sonst wären selbige in einer Kiste.
7.450 +Daraus folgt, man kann nicht mehr als die doppelte Anzahl an
7.451 +Kisten als beim Optimum erreichen!\\ (b) Inputfolge: $0.5,
7.452 +\frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5,
7.453 +\frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5
7.454 ++ \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und
7.455 +$OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in
7.456 +$=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er
7.457 +Objekte in eine Kiste passen)\\ Laufzeit für Inputfolgen der
7.458 +Länge $n$: NF $O(n)$
7.459 +\subsubsection{First-Fit (FF)}
7.460 +Packe nächstes Objekt in die erste Kiste, in die es noch
7.461 +hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue
7.462 +Kiste.\\ \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es
7.463 +höchstens eine Kiste geben, die weniger als halb voll ist.
7.464 +($\implies FF(I) \leq 2OPT(I)$)\\ \textbf{Satz 3}: (a) Für alle
7.465 +Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10}
7.466 +OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit
7.467 +$FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen
7.468 +$I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\ \textbf{Beweis}\\ (b')
7.469 +Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der
7.470 +Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon,
7.471 +\frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in
7.472 +Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten
7.473 +gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$
7.474 +(jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten
7.475 +gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils
7.476 +2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt
7.477 +der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$
7.478 +Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in
7.479 +eine Kiste und benötigt somit nur $6m$ Kisten.\\ Laufzeit für
7.480 +Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
7.481 +\subsubsection{Best-Fit (BF)}
7.482 +Verpacke das nächste Objekt in diejenige Kiste, in die es am
7.483 +besten passt (d.h. den geringsten Platz ungenutzt lässt).
7.484 +Verhalten von BF ähnlich zu FF. Laufzeit für Inputfolgen der
7.485 +Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
7.486 +\subsection{Offline Verfahren}
7.487 +\underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
7.488 +Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann
7.489 +beginnt die Verpackung.\\ $n$ und $s_1, ..., s_n$ sind gegeben,
7.490 +bevor die Verpackung beginnt!\\ $\rightarrow$ \underline{Optimale
7.491 +Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER:
7.492 +Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die
7.493 +schneller sind aber dafür unter Umständen nicht optimal!\\
7.494 +Idee für Offline Approximationsalgorithmen: Sortiere die Objekte
7.495 +zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
7.496 +\subsubsection{First Fit Decreasing (FFD oder FFNI)}
7.497 +\textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit
7.498 +Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
7.499 +haben alle von FFD in den Bins
7.500 +$B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine
7.501 +Größe von höchstens $\frac{1}{3}$.
7.502 +\\ \textbf{Beweis}:
7.503 +%TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang
7.504 +\textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit
7.505 +Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
7.506 +ist die Anzahl der Objekte, die FFD in die Kisten
7.507 +$B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens
7.508 +$m-1$.\\ \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$
7.509 +Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten
7.510 +verpacken. Dies führt zu einem Widerspruch.
7.511 +%TODO:Warum?
7.512 +\textbf{Satz}: Für alle Inputfolgen I
7.513 +gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\ \textbf{Satz}:
7.514 +\begin{itemize}
7.515 + \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
7.516 + \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
7.517 +\end{itemize}
7.518 +\textbf{Beweis}: %TODO
7.519 +\subsubsection{Best Fit Decreasing (BFD)}
7.520 +%TODO Nicht im Script???
7.521 +
7.522 +\newpage
7.523 +\section{Dynamische Programmierung}
7.524 +\textbf{Idee:} Speichern von zwischen Ergebnissen, welche sonst mehrfach
7.525 +berechnet werden müssten.\\
7.526 +\textbf{Vorgehen:}
7.527 +\begin{itemize}
7.528 + \item Rekursive Beschreibung des Problems P
7.529 + \item Bestimmung einer Menge T, die alle Teilprobleme von P enthält, auf die
7.530 + bei der Lösung von P zugegriffen wird.
7.531 + \item Bestimmung einer Reihenfolge $T_0,\ldots T_k$ der Probleme in T, so dass
7.532 + bei der Lösung von $T_i$ nur auf Probleme $T_j$ mit $j<i$ zurückgegriffen
7.533 + wird.
7.534 + \item Sukzessive Berechnung und Speicherung von Lösungen für $T_0,\ldots T_k$.
7.535 +\end{itemize}
7.536 +Wird im Script anhand der Fibonacci Zahlen demonstriert aber ist trivial \ldots
7.537 +\subsection{Matrixkettenprodukt (TODO)}
7.538 +%TODO
7.539 +\subsection{Optimale Suchbäume (TODO)}
7.540 +%TODO
7.541 +\subsection{Editierdistanz}
7.542 +Berechne für zwei gegebene Zeichenfolgen $A$ und $B$ möglichst effizient die
7.543 +Editier-Distanz $D(A,B)$ und eine minimale Folge von Editieroperationen, die
7.544 +$A$ in $B$ überführt.\\
7.545 +\textbf{Editieroperationen:}
7.546 +\begin{itemize}
7.547 + \item Ersetzen eines Zeichens von $A$ durch ein Zeichen von $B$
7.548 + \item Löschen eines Zeichens von $A$
7.549 + \item Einfügen eines Zeichens von $B$
7.550 +\end{itemize}
7.551 +\textbf{Einheitskostenmodell:}
7.552 +\[c(a,b)=\begin{cases}1 & \text{falls } a\neq b\\0 & \text{falls } a=b\end{cases}\]
7.553 +$a=\epsilon, b=\epsilon$ möglich Dreiecksungleichung soll für $c$ im
7.554 +allgemeinen gelten:
7.555 +\[c(a,c)\leq c(a,b)+c(b,c)\]
7.556 +$\rightarrow$ ein Buchstabe wird höchstens einmal
7.557 +verändert.\\
7.558 +Rekursionsgleichung, falls $m,n\geq 1$
7.559 +\[D_{m,n}=min\left.\begin{cases}D_{m-1,n-1}+c(a_m,b_n)\\D_{m-1,n}+1\\D_{m,n-1}+1\end{cases}\right\}\]
7.560 +Anfangsbedingung:\\
7.561 +\[D_{0,0}=D(\epsilon,\epsilon)=0\]
7.562 +\[D_{0,j}=D(\epsilon,B_j)=j\]
7.563 +\[D_{i,0}=D(A_i,\epsilon)=i\]
7.564 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zur
7.565 +Editierdistanz, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
7.566 +basicstyle=\footnotesize]{./code/editierdistanz.code}
7.567 +\textbf{Spurgraph:}\\
7.568 +Übersicht über alle möglichen Spuren zur Transformation von $A$ in $B$,
7.569 +gerichtete Kanten von Knoten $(i,j)$ zu $(i+1,j)$, $(i,j+1)$ und $(i+1,j+1)$.
7.570 +Gewichtung der Kanten entspricht den Editierkosten. Kosten nehmen entlang eines
7.571 +optimalen Weges monoton zu. Jeder Weg mit monotin wachsenden Kosten von der
7.572 +linken oberen Ecke zur rechten unteren Ecke entspricht einer optimalen Spur. Zur
7.573 +Berechnung der Spur der minimalen Editieroperationen (es gibt mehrere
7.574 +Lösungen), kann folgender Algorithmus verwendet werden:
7.575 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zum Spurgraphen, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/spurgraph.code}
7.576 +
7.577 +\section{Suche in Texten}
7.578 +\underline{Gegeben:} Text T $t_1t_2t_3\ldots t_n\in\Sigma^n$ und
7.579 +rin Muster P $p_1p_2p_3\ldots p_m\in\Sigma^m$\\
7.580 +\underline{Gesucht:} Ein oder alle Vorkommen des Musters im Text, d.h.
7.581 +Verschiebungen $i$ mit $0\leq i\leq n-m$.\\
7.582 +\textbf{Naives Verfahren:} iteriere über den Text und suche das Muster. Aufwand:
7.583 +$m\cdot(n-m+1)$ Vergleiche $\implies \Omega(n\cdot m)$
7.584 +\textbf{Verfahren nach Knuth-Morris-Pratt (KMP):}
7.585 +Präffix=Suffix Verfahren. Daraus resultiert eine Shiftmöglichkeit des Musters
7.586 +über den Text. Der Shift geschieht um $next[j]$=Länge des längsten Präfix von
7.587 +$P$, das echtes Suffix von $P_{1\ldots j}$ ist, wobei $j=$Position des letzten
7.588 +Vergleiches.\\
7.589 +\underline{Erstellung des $next[j]$ arrays über P.}\\
7.590 +$P=0101101011$
7.591 +\begin{table}[H]
7.592 + \centering
7.593 + \begin{tabular}{c|c|c|c|c|c|c|c|c|c}
7.594 + 1&2&3&4&5&6&7&8&9&10\\\hline
7.595 + 0&1&0&1&1&0&1&0&1&1\\\hline
7.596 + & &0& & & & & & & \\
7.597 + & &0&1& & & & & & \\
7.598 + & & & & &0& & & & \\
7.599 + & & & & &0&1& & & \\
7.600 + & & & & &0&1&0& & \\
7.601 + & & & & &0&1&0&1& \\
7.602 + & & & & &0&1&0&1&1\\
7.603 + \end{tabular}
7.604 + \caption{next[j] Beispiel}
7.605 + \label{tab:nextJ}
7.606 +\end{table}
7.607 +$\rightarrow next[j]=[0,0,1,2,0,1,2,3,4,5]$\\
7.608 +\underline{Algorithmus:}
7.609 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=KMP Algorithmus,
7.610 +captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/kmp.code}
7.611 +\underline{Analyse:}
7.612 +inkrement $j$ = inkrement $i$ und dekrement $j$ = inkrement $j$!
7.613 +$\rightarrow O(n)$ hinzu kommt noch die Berechnung des next-arrays mit $O(m)$.\\
7.614 +KMP kann also mit $O(n+m)$ berechnet werden. (i.e. Untere Schranke
7.615 +$\Omega(m+n/m)$)
7.616 +
7.617 +\newpage
7.618 +\begin{appendix}
7.619 +\section{Landau-Symbole}
7.620 +\begin{figure}[H]
7.621 +\centering
7.622 +\includegraphics[scale=0.45]{img/landau_sym}
7.623 +\caption{Definition der Landau Symbole}
7.624 +\label{fig:landau_sym}
7.625 +\end{figure}
7.626 +\end{appendix}
7.627 +\end{document}
7.628 \ No newline at end of file
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/AT_Exzerpt.toc Tue Feb 22 19:14:19 2011 +0100
8.3 @@ -0,0 +1,52 @@
8.4 +\select@language {ngerman}
8.5 +\contentsline {section}{\numberline {1}Einleitung}{3}{section.1}
8.6 +\contentsline {subsection}{\numberline {1.1}Themen:}{3}{subsection.1.1}
8.7 +\contentsline {subsection}{\numberline {1.2}Problem-/Anwendungsbereiche:}{3}{subsection.1.2}
8.8 +\contentsline {subsection}{\numberline {1.3}Literatur:}{3}{subsection.1.3}
8.9 +\contentsline {section}{\numberline {2}Divide and Conquer}{4}{section.2}
8.10 +\contentsline {subsection}{\numberline {2.1}Formulierung des Divide and Conquer Prinzips}{4}{subsection.2.1}
8.11 +\contentsline {subsection}{\numberline {2.2}Quicksort}{4}{subsection.2.2}
8.12 +\contentsline {subsubsection}{\numberline {2.2.1}Algorithmus}{4}{subsubsection.2.2.1}
8.13 +\contentsline {subsubsection}{\numberline {2.2.2}Analyse}{4}{subsubsection.2.2.2}
8.14 +\contentsline {subsection}{\numberline {2.3}N\"achste Paare}{5}{subsection.2.3}
8.15 +\contentsline {subsubsection}{\numberline {2.3.1}Algorithmus}{5}{subsubsection.2.3.1}
8.16 +\contentsline {subsubsection}{\numberline {2.3.2}Analyse}{5}{subsubsection.2.3.2}
8.17 +\contentsline {subsection}{\numberline {2.4}Segmentschnitt}{6}{subsection.2.4}
8.18 +\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{6}{subsubsection.2.4.1}
8.19 +\contentsline {subsubsection}{\numberline {2.4.2}Analyse}{6}{subsubsection.2.4.2}
8.20 +\contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation (TODO)}{6}{subsection.2.5}
8.21 +\contentsline {section}{\numberline {3}Randomisierung}{7}{section.3}
8.22 +\contentsline {subsection}{\numberline {3.1}Randomisierter Quicksort}{7}{subsection.3.1}
8.23 +\contentsline {subsubsection}{\numberline {3.1.1}Analyse}{7}{subsubsection.3.1.1}
8.24 +\contentsline {subsection}{\numberline {3.2}Randomisierter Primzahltest (TODO)}{7}{subsection.3.2}
8.25 +\contentsline {subsection}{\numberline {3.3}RSA (TODO)}{7}{subsection.3.3}
8.26 +\contentsline {subsection}{\numberline {3.4}Treaps (TODO)}{7}{subsection.3.4}
8.27 +\contentsline {subsection}{\numberline {3.5}Hashing (TODO)}{7}{subsection.3.5}
8.28 +\contentsline {section}{\numberline {4}Amortisierte Analyse (TODO)}{8}{section.4}
8.29 +\contentsline {subsection}{\numberline {4.1}Binomial Heaps (TODO)}{8}{subsection.4.1}
8.30 +\contentsline {subsection}{\numberline {4.2}Fibonacci Heaps (TODO)}{8}{subsection.4.2}
8.31 +\contentsline {subsection}{\numberline {4.3}Union Find (TODO)}{8}{subsection.4.3}
8.32 +\contentsline {section}{\numberline {5}Greedy}{9}{section.5}
8.33 +\contentsline {subsection}{\numberline {5.1}K\"urzeste (billigste) Wege}{9}{subsection.5.1}
8.34 +\contentsline {subsubsection}{\numberline {5.1.1}Single Source Shortest Paths}{9}{subsubsection.5.1.1}
8.35 +\contentsline {subsection}{\numberline {5.2}Spannb\"aume minimalen Gewichts}{11}{subsection.5.2}
8.36 +\contentsline {subsubsection}{\numberline {5.2.1}Das Wachsen von min. Spannb\"aumen}{11}{subsubsection.5.2.1}
8.37 +\contentsline {subsubsection}{\numberline {5.2.2}Schnitte}{12}{subsubsection.5.2.2}
8.38 +\contentsline {subsubsection}{\numberline {5.2.3}Sichere Kanten}{12}{subsubsection.5.2.3}
8.39 +\contentsline {subsubsection}{\numberline {5.2.4}Der Graph $G_A$}{12}{subsubsection.5.2.4}
8.40 +\contentsline {subsubsection}{\numberline {5.2.5}Algorithmus von Kruskal}{12}{subsubsection.5.2.5}
8.41 +\contentsline {subsubsection}{\numberline {5.2.6}Algorithmus von Prim}{13}{subsubsection.5.2.6}
8.42 +\contentsline {section}{\numberline {6}Bin Packing}{14}{section.6}
8.43 +\contentsline {subsection}{\numberline {6.1}Online Verfahren}{14}{subsection.6.1}
8.44 +\contentsline {subsubsection}{\numberline {6.1.1}Next Fit (NF)}{14}{subsubsection.6.1.1}
8.45 +\contentsline {subsubsection}{\numberline {6.1.2}First-Fit (FF)}{14}{subsubsection.6.1.2}
8.46 +\contentsline {subsubsection}{\numberline {6.1.3}Best-Fit (BF)}{15}{subsubsection.6.1.3}
8.47 +\contentsline {subsection}{\numberline {6.2}Offline Verfahren}{15}{subsection.6.2}
8.48 +\contentsline {subsubsection}{\numberline {6.2.1}First Fit Decreasing (FFD oder FFNI)}{15}{subsubsection.6.2.1}
8.49 +\contentsline {subsubsection}{\numberline {6.2.2}Best Fit Decreasing (BFD)}{15}{subsubsection.6.2.2}
8.50 +\contentsline {section}{\numberline {7}Dynamische Programmierung}{16}{section.7}
8.51 +\contentsline {subsection}{\numberline {7.1}Matrixkettenprodukt (TODO)}{16}{subsection.7.1}
8.52 +\contentsline {subsection}{\numberline {7.2}Optimale Suchb\"aume (TODO)}{16}{subsection.7.2}
8.53 +\contentsline {subsection}{\numberline {7.3}Editierdistanz}{16}{subsection.7.3}
8.54 +\contentsline {section}{\numberline {8}Suche in Texten}{17}{section.8}
8.55 +\contentsline {section}{\numberline {A}Landau-Symbole}{19}{appendix.A}
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/code/AzyklischeNetzwerke.code Tue Feb 22 19:14:19 2011 +0100
9.3 @@ -0,0 +1,12 @@
9.4 +Sortiere G=(V,E,c) topologisch;
9.5 +DIST[s]=0;
9.6 +forall(v:V\{s}){
9.7 + DIST[v]=infty;
9.8 +}
9.9 +U={v|v:V mit num(v)<n};
9.10 +while(!U.Empty) {
9.11 + Wähle und streiche Knoten u:U mit kleinstem num-Wert;
9.12 + forall(e=(u,v):E) {
9.13 + if(DIST[v]>DIST[u]+c(u,v)) {
9.14 + DIST[v]=DIST[u]+c(u,v);
9.15 +}}}
9.16 \ No newline at end of file
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/code/BelmanFord.code Tue Feb 22 19:14:19 2011 +0100
10.3 @@ -0,0 +1,17 @@
10.4 +DIST[s]=0;
10.5 +Z[s]=0;
10.6 +forall(v:V\{s}) {
10.7 + DIST[v]=infty;
10.8 + Z[v]=0;
10.9 +}
10.10 +U={s};
10.11 +while(!U.Empty) {
10.12 + Wähle und streiche Knoten u am Kopf von U;
10.13 + Z[u]=Z[u]+1;
10.14 + if Z[u]>n
10.15 + return "negativer Zyklus";
10.16 + forall(e=(u,v):E) {
10.17 + if(DIST[v]>DIST[u]+c(u,v)) {
10.18 + DIST[v]=DIST[u]+c(u,v);
10.19 + U=[U,{v}];
10.20 +}}}
10.21 \ No newline at end of file
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/code/dijkstra.code Tue Feb 22 19:14:19 2011 +0100
11.3 @@ -0,0 +1,13 @@
11.4 +DIST[s]=0;
11.5 +Insert(U,0,s);
11.6 +forall(v:V\{s}) {
11.7 + DIST[v]=infty;
11.8 + Insert(U, infty, v);
11.9 +}
11.10 +while !Empty(U) {
11.11 + (d,u)=DeleteMin(U);
11.12 + forall(e=(u,v):E) {
11.13 + if(DIST[v]>DIST[u]+c(u,v)){
11.14 + DIST[v]=DIST[u]+c(u,v);
11.15 + DecreaseKey(U,v,DIST[v]);
11.16 +}}}
11.17 \ No newline at end of file
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/code/editierdistanz.code Tue Feb 22 19:14:19 2011 +0100
12.3 @@ -0,0 +1,10 @@
12.4 +Input: Zwei Zeichenketten A und B
12.5 +Output: Matrix D=(Dij)
12.6 +D[0,0]:= 0
12.7 +for i := 1 to m do D[i,0] = i
12.8 +for j := 1 to n do D[0,j] = j
12.9 +for i := 1 to m do
12.10 + for j := 1 to n do
12.11 + D[i,j] := min(D[i - 1,j] + 1,
12.12 + D[i,j - 1] + 1,
12.13 + D[i-1,j-1]+c(ai,bj))
12.14 \ No newline at end of file
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/code/kmp.code Tue Feb 22 19:14:19 2011 +0100
13.3 @@ -0,0 +1,34 @@
13.4 +KMP := proc (T::string, P::string)
13.5 +# Input: Text T und Muster P
13.6 +# Output: Liste L mit Verschiebungen i,
13.7 +# an denen P in T vorkommt
13.8 + n := length (T); m := length(P);
13.9 + L := []; next := KMPnext(P);
13.10 + j := 0;
13.11 + for i from 1 to n do
13.12 + whilej>0and T[i]!=P[j+1]
13.13 + do j := next [j] od;
13.14 + if T[i] = P[j+1] then j := j+1 fi;
13.15 + if j = m then
13.16 + L := [L[] , i-m];
13.17 + j := next [j]
13.18 + fi;
13.19 + od;
13.20 + RETURN (L);
13.21 +end;
13.22 +
13.23 +KMPnext := proc (P : : string)
13.24 +#Input : Muster P
13.25 +#Output : next-Array für P
13.26 + m := length (P);
13.27 + next := array (1..m);
13.28 + next [1] := 0;
13.29 + j := 0;
13.30 + for i from 2 to m do
13.31 + while j > 0 and P[i] <> P[j+1]
13.32 + do j := next [j] od;
13.33 + if P[i] = P[j+1] then j := j+1 fi;
13.34 + next [i] := j
13.35 + od;
13.36 + RETURN (next);
13.37 +end;
13.38 \ No newline at end of file
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/code/quicksort.code Tue Feb 22 19:14:19 2011 +0100
14.3 @@ -0,0 +1,10 @@
14.4 +Input: unsortierter Bereich [p, r] in Array A
14.5 +Output: sortierter Bereich [p, r] in Array A
14.6 + if r > p then
14.7 + wähle Pivotelement x = A[r]
14.8 + m = partition(A, p , r)
14.9 + /* Teile A bzgl. x auf:
14.10 + * A[p],...,A[m-1] <= x <= A[m+1],...,A[r]
14.11 + */
14.12 + Quicksort(A, p , m - 1)
14.13 + Quicksort (A, m + 1, r)
14.14 \ No newline at end of file
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
15.2 +++ b/code/spannbaeumeGreedy.code Tue Feb 22 19:14:19 2011 +0100
15.3 @@ -0,0 +1,6 @@
15.4 +Algorithmus Generischer-MST(G,c);
15.5 +A = EmptySet;
15.6 +while(A ist kein Spannbaum) {
15.7 + Finde sichere Kante (u,v) für A;
15.8 + A = [A, {(u,v)}];
15.9 +}
15.10 \ No newline at end of file
16.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
16.2 +++ b/code/spannbaeumeKruskal.code Tue Feb 22 19:14:19 2011 +0100
16.3 @@ -0,0 +1,12 @@
16.4 +A = EmptySet;
16.5 +forall(v:V)
16.6 + Bv={v};
16.7 +Erzeuge eine Liste L der Kanten in E, welche gemäß
16.8 +nicht-fallenden Kantenkosten sortiert ist;
16.9 +forall (u,v):L {
16.10 + B1=FIND(u);
16.11 + B2=FIND(v);
16.12 + if(B1!=B2)
16.13 + A=[A,{(u,v)}];
16.14 + UNION(B1, B2, B1);
16.15 +}
16.16 \ No newline at end of file
17.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
17.2 +++ b/code/spannbaeumePrim.code Tue Feb 22 19:14:19 2011 +0100
17.3 @@ -0,0 +1,12 @@
17.4 +forall(v:V)
17.5 + Insert(Q, infty, v);
17.6 +Wähle einen Knoten w:V als Wurzel;
17.7 +DecreaseKey(Q, 0, w);
17.8 +p[w]=nil;
17.9 +while(!Empty(Q)) {
17.10 + (d,u)=DeleteMin(Q);
17.11 + forall((u,v):E)
17.12 + if(v:Q && c(u,v)<v.Key) {
17.13 + DecreaseKey(Q, c(u,v), v);
17.14 + p[v]=u;
17.15 + }
17.16 \ No newline at end of file
18.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
18.2 +++ b/code/spurgraph.code Tue Feb 22 19:14:19 2011 +0100
18.3 @@ -0,0 +1,12 @@
18.4 +Input: Berechnete Matrix D
18.5 +Output: Sequenz der Editieroperationen
18.6 +if i==0 & j==0 then return
18.7 +if i!=0 and D[i,j]==D[i-1,j]+1
18.8 + then Editieroperationen(i-1,j)
18.9 + "lösche a[i]"
18.10 +else if j!=0 and D[i,j]==D[i,j-1]+1
18.11 + then Editieroperationen(i,j-1)
18.12 + "füge b[j] ein"
18.13 +else /* D[i,j]=D[i-1,j-1 ]+c(a[i],b[j]) */
18.14 + Editieroperationen(i-1,j-1)
18.15 + "ersetze a[i] durch b[j]"
18.16 \ No newline at end of file
19.1 --- a/comp.log Tue Feb 22 18:58:21 2011 +0100
19.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
19.3 @@ -1,126 +0,0 @@
19.4 -This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8)
19.5 -entering extended mode
19.6 -
19.7 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
19.8 -thms_theory/exzerpt.tex
19.9 -LaTeX2e <2009/09/24>
19.10 -Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, ge
19.11 -rman, ngerman, german-x-2009-06-19, ngerman-x-2009-06-19, french, loaded.
19.12 -("C:\Program Files\MikTex\tex\latex\base\article.cls"
19.13 -Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
19.14 -("C:\Program Files\MikTex\tex\latex\base\size11.clo"))
19.15 -("C:\Program Files\MikTex\tex\generic\babel\babel.sty"
19.16 -*************************************
19.17 -* Local config file bblopts.cfg used
19.18 -*
19.19 -("C:\Program Files\MikTex\tex\latex\00miktex\bblopts.cfg")
19.20 -("C:\Program Files\MikTex\tex\generic\babel\ngermanb.ldf"
19.21 -("C:\Program Files\MikTex\tex\generic\babel\babel.def")))
19.22 -("C:\Program Files\MikTex\tex\latex\base\fontenc.sty"
19.23 -("C:\Program Files\MikTex\tex\latex\base\t1enc.def"))
19.24 -("C:\Program Files\MikTex\tex\latex\base\inputenc.sty"
19.25 -("C:\Program Files\MikTex\tex\latex\base\latin1.def"))
19.26 -("C:\Program Files\MikTex\tex\latex\hyperref\hyperref.sty"
19.27 -("C:\Program Files\MikTex\tex\generic\oberdiek\ltxcmds.sty")
19.28 -("C:\Program Files\MikTex\tex\generic\oberdiek\infwarerr.sty")
19.29 -("C:\Program Files\MikTex\tex\latex\graphics\keyval.sty")
19.30 -("C:\Program Files\MikTex\tex\generic\oberdiek\kvsetkeys.sty"
19.31 -("C:\Program Files\MikTex\tex\generic\oberdiek\etexcmds.sty"))
19.32 -("C:\Program Files\MikTex\tex\generic\oberdiek\pdfescape.sty"
19.33 -("C:\Program Files\MikTex\tex\generic\oberdiek\pdftexcmds.sty"
19.34 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifluatex.sty")))
19.35 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifpdf.sty")
19.36 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifvtex.sty")
19.37 -("C:\Program Files\MikTex\tex\generic\ifxetex\ifxetex.sty")
19.38 -("C:\Program Files\MikTex\tex\latex\oberdiek\hycolor.sty"
19.39 -("C:\Program Files\MikTex\tex\latex\oberdiek\xcolor-patch.sty"))
19.40 -("C:\Program Files\MikTex\tex\latex\oberdiek\letltxmacro.sty")
19.41 -("C:\Program Files\MikTex\tex\latex\oberdiek\kvoptions.sty")
19.42 -("C:\Program Files\MikTex\tex\latex\hyperref\pd1enc.def")
19.43 -("C:\Program Files\MikTex\tex\generic\oberdiek\intcalc.sty")
19.44 -("C:\Program Files\MikTex\tex\latex\00miktex\hyperref.cfg")
19.45 -("C:\Program Files\MikTex\tex\latex\ltxmisc\url.sty")
19.46 -("C:\Program Files\MikTex\tex\generic\oberdiek\bitset.sty"
19.47 -("C:\Program Files\MikTex\tex\generic\oberdiek\bigintcalc.sty"))
19.48 -("C:\Program Files\MikTex\tex\generic\oberdiek\atbegshi.sty"))
19.49 -
19.50 -Package hyperref Message: Driver (default): hdvips.
19.51 -
19.52 -("C:\Program Files\MikTex\tex\latex\hyperref\hdvips.def"
19.53 -("C:\Program Files\MikTex\tex\latex\hyperref\pdfmark.def"
19.54 -("C:\Program Files\MikTex\tex\latex\oberdiek\rerunfilecheck.sty"
19.55 -("C:\Program Files\MikTex\tex\latex\oberdiek\atveryend.sty")
19.56 -("C:\Program Files\MikTex\tex\generic\oberdiek\uniquecounter.sty"))))
19.57 -("C:\Program Files\MikTex\tex\latex\vaucanson-g\vaucanson-g.sty"
19.58 -("C:\Program Files\MikTex\tex\latex\base\ifthen.sty")
19.59 -("C:\Program Files\MikTex\tex\latex\xcolor\xcolor.sty"
19.60 -("C:\Program Files\MikTex\tex\latex\00miktex\color.cfg")
19.61 -("C:\Program Files\MikTex\tex\latex\graphics\dvips.def"))
19.62 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCColor-names.def")
19.63 -("C:\Program Files\MikTex\tex\latex\pstricks\pstricks.sty"
19.64 -("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.tex"
19.65 -("C:\Program Files\MikTex\tex\generic\xkeyval\pst-xkey.tex"
19.66 -("C:\Program Files\MikTex\tex\latex\xkeyval\xkeyval.sty"
19.67 -("C:\Program Files\MikTex\tex\generic\xkeyval\xkeyval.tex")))
19.68 -("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"
19.69 -`pst-fp' v0.05, 2010/01/17 (hv))
19.70 -`PSTricks' v2.12 <2010/09/16> (tvz)
19.71 -("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.con"))
19.72 -("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"))
19.73 -("C:\Program Files\MikTex\tex\latex\pst-node\pst-node.sty"
19.74 -("C:\Program Files\MikTex\tex\generic\pst-node\pst-node.tex"
19.75 - v1.13, 2010/06/06)) ("C:\Program Files\MikTex\tex\latex\pst-plot\pst-plot.sty"
19.76 -("C:\Program Files\MikTex\tex\generic\pst-plot\pst-plot.tex"
19.77 -("C:\Program Files\MikTex\tex\generic\multido\multido.tex"
19.78 - v1.42, 2010/05/14 <tvz>) v1.21, 2010/09/28 (tvz,hv)))
19.79 -("C:\Program Files\MikTex\tex\latex\pst-coil\pst-coil.sty"
19.80 -("C:\Program Files\MikTex\tex\generic\pst-coil\pst-coil.tex"
19.81 - v1.21, 2010/09/28)) ("C:\Program Files\MikTex\tex\latex\multido\multido.sty")
19.82 -("C:\Program Files\MikTex\tex\latex\pst-3d\pst-3d.sty"
19.83 -("C:\Program Files\MikTex\tex\generic\pst-3d\pst-3d.tex"
19.84 -`PST-3d' v1.11, 2010/02/14 (tvz)))
19.85 -("C:\Program Files\MikTex\tex\latex\tools\calc.sty")
19.86 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\Vaucanson-G.tex")
19.87 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCPref-default.tex"))
19.88 -("C:\Program Files\MikTex\tex\latex\oberdiek\hypcap.sty")
19.89 -("C:\Program Files\MikTex\tex\latex\fancyhdr\fancyhdr.sty")
19.90 -("C:\Program Files\MikTex\tex\latex\graphics\graphicx.sty"
19.91 -("C:\Program Files\MikTex\tex\latex\graphics\graphics.sty"
19.92 -("C:\Program Files\MikTex\tex\latex\graphics\trig.sty")
19.93 -("C:\Program Files\MikTex\tex\latex\00miktex\graphics.cfg")))
19.94 -("C:\Program Files\MikTex\tex\latex\lastpage\lastpage.sty")
19.95 -("C:\Program Files\MikTex\tex\latex\preprint\fullpage.sty")
19.96 -("C:\Program Files\MikTex\tex\latex\ams\classes\amsthm.sty")
19.97 -("C:\Program Files\MikTex\tex\latex\ams\math\amsmath.sty"
19.98 -For additional information on amsmath, use the `?' option.
19.99 -("C:\Program Files\MikTex\tex\latex\ams\math\amstext.sty"
19.100 -("C:\Program Files\MikTex\tex\latex\ams\math\amsgen.sty"))
19.101 -("C:\Program Files\MikTex\tex\latex\ams\math\amsbsy.sty")
19.102 -("C:\Program Files\MikTex\tex\latex\ams\math\amsopn.sty"))
19.103 -("C:\Program Files\MikTex\tex\latex\amsfonts\amsfonts.sty")
19.104 -("C:\Program Files\MikTex\tex\latex\float\float.sty")
19.105 -("C:\Program Files\MikTex\tex\latex\paralist\paralist.sty")
19.106 -("C:\Program Files\MikTex\tex\latex\listings\listings.sty"
19.107 -("C:\Program Files\MikTex\tex\latex\listings\lstmisc.sty")
19.108 -("C:\Program Files\MikTex\tex\latex\listings\listings.cfg"))
19.109 -("C:\Program Files\MikTex\tex\latex\oberdiek\bookmark.sty"
19.110 -("C:\Program Files\MikTex\tex\latex\oberdiek\auxhook.sty")
19.111 -("C:\Program Files\MikTex\tex\latex\oberdiek\bkm-dvips.def"))
19.112 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
19.113 -thms_theory\exzerpt.aux)
19.114 -("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
19.115 -("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty")
19.116 -("C:\Program Files\MikTex\tex\generic\oberdiek\gettitlestring.sty"))
19.117 -("C:\Program Files\MikTex\tex\latex\amsfonts\umsa.fd")
19.118 -("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd")
19.119 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
19.120 -thms_theory\exzerpt.toc) [1] ("C:\Program Files\MikTex\tex\latex\base\t1cmtt.fd
19.121 -")
19.122 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
19.123 -thms_theory\exzerpt.bbl) [2] [3] <img/cl_pair.eps> [4] [5] [6] [7] [8] [9]
19.124 -[10] [11] <img/landau_sym.eps> AED: lastpage setting LastPage
19.125 -[12]
19.126 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
19.127 -thms_theory\exzerpt.aux) )
19.128 -Output written on exzerpt.dvi (12 pages, 67136 bytes).
19.129 -Transcript written on exzerpt.log.
20.1 --- a/exzerpt.aux Tue Feb 22 18:58:21 2011 +0100
20.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
20.3 @@ -1,97 +0,0 @@
20.4 -\relax
20.5 -\providecommand\BKM@entry[2]{}
20.6 -\catcode`"\active
20.7 -\ifx\hyper@anchor\@undefined
20.8 -\global \let \oldcontentsline\contentsline
20.9 -\gdef \contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
20.10 -\global \let \oldnewlabel\newlabel
20.11 -\gdef \newlabel#1#2{\newlabelxx{#1}#2}
20.12 -\gdef \newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
20.13 -\AtEndDocument{\let \contentsline\oldcontentsline
20.14 -\let \newlabel\oldnewlabel}
20.15 -\else
20.16 -\global \let \hyper@last\relax
20.17 -\fi
20.18 -
20.19 -\bibstyle{alphadin}
20.20 -\select@language{ngerman}
20.21 -\@writefile{toc}{\select@language{ngerman}}
20.22 -\@writefile{lof}{\select@language{ngerman}}
20.23 -\@writefile{lot}{\select@language{ngerman}}
20.24 -\BKM@entry{id=1,dest={73656374696F6E2E31}}{45696E6C656974756E67}
20.25 -\BKM@entry{id=2,dest={73756273656374696F6E2E312E31}}{5468656D656E3A}
20.26 -\BKM@entry{id=3,dest={73756273656374696F6E2E312E32}}{50726F626C656D2D2F416E77656E64756E677362657265696368653A}
20.27 -\BKM@entry{id=4,dest={73756273656374696F6E2E312E33}}{4C69746572617475723A}
20.28 -\bibdata{literatur}
20.29 -\bibcite{2}{PW02}
20.30 -\bibcite{1}{THC01}
20.31 -\citation{*}
20.32 -\@writefile{toc}{\contentsline {section}{\numberline {1}Einleitung}{2}{section.1}}
20.33 -\newlabel{sec:intro}{{1}{2}{Einleitung\relax }{section.1}{}}
20.34 -\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Themen:}{2}{subsection.1.1}}
20.35 -\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Problem-/Anwendungsbereiche:}{2}{subsection.1.2}}
20.36 -\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}Literatur:}{2}{subsection.1.3}}
20.37 -\BKM@entry{id=5,dest={73656374696F6E2E32}}{44697669646520616E6420436F6E71756572}
20.38 -\BKM@entry{id=6,dest={73756273656374696F6E2E322E31}}{466F726D756C696572756E67206465732044697669646520616E6420436F6E71756572205072696E7A697073}
20.39 -\BKM@entry{id=7,dest={73756273656374696F6E2E322E32}}{517569636B736F7274}
20.40 -\BKM@entry{id=8,dest={73756273756273656374696F6E2E322E322E31}}{416E616C797365}
20.41 -\BKM@entry{id=9,dest={73756273656374696F6E2E322E33}}{4E5C3334346368737465205061617265}
20.42 -\BKM@entry{id=10,dest={73756273756273656374696F6E2E322E332E31}}{416C676F726974686D7573}
20.43 -\@writefile{toc}{\contentsline {section}{\numberline {2}Divide and Conquer}{3}{section.2}}
20.44 -\newlabel{sec:div&conq}{{2}{3}{Divide and Conquer\relax }{section.2}{}}
20.45 -\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Formulierung des Divide and Conquer Prinzips}{3}{subsection.2.1}}
20.46 -\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Quicksort}{3}{subsection.2.2}}
20.47 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1}Analyse}{3}{subsubsection.2.2.1}}
20.48 -\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}N\"achste Paare}{3}{subsection.2.3}}
20.49 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1}Algorithmus}{3}{subsubsection.2.3.1}}
20.50 -\BKM@entry{id=11,dest={73756273756273656374696F6E2E322E332E32}}{416E616C797365}
20.51 -\BKM@entry{id=12,dest={73756273656374696F6E2E322E34}}{5365676D656E747363686E697474}
20.52 -\BKM@entry{id=13,dest={73756273756273656374696F6E2E322E342E31}}{416C676F726974686D7573}
20.53 -\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces N\"achste Paare: Pr\"uf Distanz}}{4}{figure.1}}
20.54 -\newlabel{cl_pair}{{1}{4}{Nächste Paare: Prüf Distanz\relax }{figure.1}{}}
20.55 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.2}Analyse}{4}{subsubsection.2.3.2}}
20.56 -\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Segmentschnitt}{4}{subsection.2.4}}
20.57 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{4}{subsubsection.2.4.1}}
20.58 -\BKM@entry{id=14,dest={73756273756273656374696F6E2E322E342E32}}{416E616C797365}
20.59 -\BKM@entry{id=15,dest={73756273656374696F6E2E322E35}}{506F6C796E6F6D70726F64756B7420756E64204661737420466F75726965722D5472616E73666F726D6174696F6E}
20.60 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.2}Analyse}{5}{subsubsection.2.4.2}}
20.61 -\@writefile{toc}{\contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation}{5}{subsection.2.5}}
20.62 -\BKM@entry{id=16,dest={73656374696F6E2E33}}{52616E646F6D6973696572756E67}
20.63 -\BKM@entry{id=17,dest={73756273656374696F6E2E332E31}}{48617368696E67}
20.64 -\@writefile{toc}{\contentsline {section}{\numberline {3}Randomisierung}{6}{section.3}}
20.65 -\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Hashing}{6}{subsection.3.1}}
20.66 -\BKM@entry{id=18,dest={73656374696F6E2E34}}{416D6F72746973696572746520416E616C797365}
20.67 -\BKM@entry{id=19,dest={73756273656374696F6E2E342E31}}{42696E6F6D69616C204865617073}
20.68 -\BKM@entry{id=20,dest={73756273656374696F6E2E342E32}}{4669626F6E61636369204865617073}
20.69 -\BKM@entry{id=21,dest={73756273656374696F6E2E342E33}}{556E696F6E2046696E64}
20.70 -\@writefile{toc}{\contentsline {section}{\numberline {4}Amortisierte Analyse}{7}{section.4}}
20.71 -\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Binomial Heaps}{7}{subsection.4.1}}
20.72 -\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Fibonacci Heaps}{7}{subsection.4.2}}
20.73 -\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Union Find}{7}{subsection.4.3}}
20.74 -\BKM@entry{id=22,dest={73656374696F6E2E35}}{477265656479}
20.75 -\BKM@entry{id=23,dest={73756273656374696F6E2E352E31}}{4B5C333734727A65737465205C2862696C6C69677374655C292057656765}
20.76 -\@writefile{toc}{\contentsline {section}{\numberline {5}Greedy}{8}{section.5}}
20.77 -\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}K\"urzeste (billigste) Wege}{8}{subsection.5.1}}
20.78 -\BKM@entry{id=24,dest={73656374696F6E2E36}}{42696E205061636B696E67}
20.79 -\BKM@entry{id=25,dest={73756273656374696F6E2E362E31}}{4F6E6C696E652056657266616872656E}
20.80 -\BKM@entry{id=26,dest={73756273756273656374696F6E2E362E312E31}}{4E65787420466974205C284E465C29}
20.81 -\BKM@entry{id=27,dest={73756273756273656374696F6E2E362E312E32}}{46697273742D466974205C2846465C29}
20.82 -\@writefile{toc}{\contentsline {section}{\numberline {6}Bin Packing}{9}{section.6}}
20.83 -\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Online Verfahren}{9}{subsection.6.1}}
20.84 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.1}Next Fit (NF)}{9}{subsubsection.6.1.1}}
20.85 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.2}First-Fit (FF)}{9}{subsubsection.6.1.2}}
20.86 -\BKM@entry{id=28,dest={73756273756273656374696F6E2E362E312E33}}{426573742D466974205C2842465C29}
20.87 -\BKM@entry{id=29,dest={73756273656374696F6E2E362E32}}{4F66666C696E652056657266616872656E}
20.88 -\BKM@entry{id=30,dest={73756273756273656374696F6E2E362E322E31}}{4669727374204669742044656372656173696E67205C28464644206F6465722046464E495C29}
20.89 -\BKM@entry{id=31,dest={73756273756273656374696F6E2E362E322E32}}{42657374204669742044656372656173696E67205C284246445C29}
20.90 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.3}Best-Fit (BF)}{10}{subsubsection.6.1.3}}
20.91 -\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Offline Verfahren}{10}{subsection.6.2}}
20.92 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.1}First Fit Decreasing (FFD oder FFNI)}{10}{subsubsection.6.2.1}}
20.93 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.2}Best Fit Decreasing (BFD)}{10}{subsubsection.6.2.2}}
20.94 -\BKM@entry{id=32,dest={73656374696F6E2E37}}{44796E616D69736368652050726F6772616D6D696572756E67}
20.95 -\@writefile{toc}{\contentsline {section}{\numberline {7}Dynamische Programmierung}{11}{section.7}}
20.96 -\BKM@entry{id=33,dest={617070656E6469782E41}}{4C616E6461752D53796D626F6C65}
20.97 -\@writefile{toc}{\contentsline {section}{\numberline {A}Landau-Symbole}{12}{appendix.A}}
20.98 -\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Definition der Landau Symbole}}{12}{figure.2}}
20.99 -\newlabel{fig:landau_sym}{{2}{12}{Definition der Landau Symbole\relax }{figure.2}{}}
20.100 -\newlabel{LastPage}{{}{12}{}{page.12}{}}
21.1 --- a/exzerpt.bbl Tue Feb 22 18:58:21 2011 +0100
21.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
21.3 @@ -1,25 +0,0 @@
21.4 -\begin{thebibliography}{THC01}
21.5 -
21.6 -% this bibliography is generated by alphadin.bst [8.2] from 2005-12-21
21.7 -
21.8 -\providecommand{\url}[1]{\texttt{#1}}
21.9 -\expandafter\ifx\csname urlstyle\endcsname\relax
21.10 - \providecommand{\doi}[1]{doi: #1}\else
21.11 - \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi
21.12 -
21.13 -\bibitem[PW02]{2}
21.14 -\textsc{Peter~Widmayer}, Thomas~O.:
21.15 -\newblock \emph{Algorithmen und Datenstrukturen}.
21.16 -\newblock 4. Auflage.
21.17 -\newblock Spektrum Akademischer Verlag, 2002. --
21.18 -\newblock ISBN 978--3827410290
21.19 -
21.20 -\bibitem[THC01]{1}
21.21 -\textsc{Thomas H.~Cormen}, Robert L. Rivest und Cliford~S. Charles
21.22 - E.~Leiserson~L. Charles E.~Leiserson:
21.23 -\newblock \emph{Introduction to Algorithms}.
21.24 -\newblock 2nd.
21.25 -\newblock Prentice Hall India, 2001. --
21.26 -\newblock ISBN 978--8120321410
21.27 -
21.28 -\end{thebibliography}
22.1 --- a/exzerpt.blg Tue Feb 22 18:58:21 2011 +0100
22.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
22.3 @@ -1,3 +0,0 @@
22.4 -This is BibTeX, Version 0.99cThe top-level auxiliary file: M:\Documents\004_Uni Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\exzerpt.aux
22.5 -The style file: alphadin.bst
22.6 -Database file #1: literatur.bib
23.1 Binary file exzerpt.dvi has changed
24.1 --- a/exzerpt.log Tue Feb 22 18:58:21 2011 +0100
24.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
24.3 @@ -1,647 +0,0 @@
24.4 -This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian) (format=pdflatex 2011.1.10) 19 FEB 2011 22:56
24.5 -entering extended mode
24.6 - restricted \write18 enabled.
24.7 - %&-line parsing enabled.
24.8 -**exzerpt
24.9 -(./exzerpt.tex
24.10 -LaTeX2e <2009/09/24>
24.11 -Babel <v3.8l> and hyphenation patterns for english, usenglishmax, dumylang, noh
24.12 -yphenation, ngerman, german, german-x-2009-06-19, ngerman-x-2009-06-19, loaded.
24.13 -
24.14 -(/usr/share/texmf-texlive/tex/latex/base/article.cls
24.15 -Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
24.16 -(/usr/share/texmf-texlive/tex/latex/base/size11.clo
24.17 -File: size11.clo 2007/10/19 v1.4h Standard LaTeX file (size option)
24.18 -)
24.19 -\c@part=\count79
24.20 -\c@section=\count80
24.21 -\c@subsection=\count81
24.22 -\c@subsubsection=\count82
24.23 -\c@paragraph=\count83
24.24 -\c@subparagraph=\count84
24.25 -\c@figure=\count85
24.26 -\c@table=\count86
24.27 -\abovecaptionskip=\skip41
24.28 -\belowcaptionskip=\skip42
24.29 -\bibindent=\dimen102
24.30 -)
24.31 -(/usr/share/texmf-texlive/tex/generic/babel/babel.sty
24.32 -Package: babel 2008/07/06 v3.8l The Babel package
24.33 -
24.34 -(/usr/share/texmf-texlive/tex/generic/babel/ngermanb.ldf
24.35 -Language: ngermanb 2008/07/06 v2.6n new German support from the babel system
24.36 -
24.37 -(/usr/share/texmf-texlive/tex/generic/babel/babel.def
24.38 -File: babel.def 2008/07/06 v3.8l Babel common definitions
24.39 -\babel@savecnt=\count87
24.40 -\U@D=\dimen103
24.41 -)
24.42 -\l@naustrian = a dialect from \language\l@ngerman
24.43 -Package babel Info: Making " an active character on input line 92.
24.44 -))
24.45 -(/usr/share/texmf-texlive/tex/latex/base/fontenc.sty
24.46 -Package: fontenc 2005/09/27 v1.99g Standard LaTeX package
24.47 -
24.48 -(/usr/share/texmf-texlive/tex/latex/base/t1enc.def
24.49 -File: t1enc.def 2005/09/27 v1.99g Standard LaTeX file
24.50 -LaTeX Font Info: Redeclaring font encoding T1 on input line 43.
24.51 -))
24.52 -(/usr/share/texmf-texlive/tex/latex/base/inputenc.sty
24.53 -Package: inputenc 2008/03/30 v1.1d Input encoding file
24.54 -\inpenc@prehook=\toks14
24.55 -\inpenc@posthook=\toks15
24.56 -
24.57 -(/usr/share/texmf-texlive/tex/latex/base/latin1.def
24.58 -File: latin1.def 2008/03/30 v1.1d Input encoding file
24.59 -))
24.60 -(/usr/share/texmf-texlive/tex/latex/hyperref/hyperref.sty
24.61 -Package: hyperref 2009/10/09 v6.79a Hypertext links for LaTeX
24.62 -
24.63 -(/usr/share/texmf-texlive/tex/latex/graphics/keyval.sty
24.64 -Package: keyval 1999/03/16 v1.13 key=value parser (DPC)
24.65 -\KV@toks@=\toks16
24.66 -)
24.67 -(/usr/share/texmf-texlive/tex/generic/oberdiek/ifpdf.sty
24.68 -Package: ifpdf 2009/04/10 v2.0 Provides the ifpdf switch (HO)
24.69 -Package ifpdf Info: pdfTeX in pdf mode detected.
24.70 -)
24.71 -(/usr/share/texmf-texlive/tex/generic/oberdiek/ifvtex.sty
24.72 -Package: ifvtex 2008/11/04 v1.4 Switches for detecting VTeX and its modes (HO)
24.73 -Package ifvtex Info: VTeX not detected.
24.74 -)
24.75 -(/usr/share/texmf-texlive/tex/generic/ifxetex/ifxetex.sty
24.76 -Package: ifxetex 2009/01/23 v0.5 Provides ifxetex conditional
24.77 -)
24.78 -(/usr/share/texmf-texlive/tex/latex/oberdiek/hycolor.sty
24.79 -Package: hycolor 2009/10/02 v1.5 Code for color options of hyperref/bookmark (H
24.80 -O)
24.81 -
24.82 -(/usr/share/texmf-texlive/tex/latex/oberdiek/xcolor-patch.sty
24.83 -Package: xcolor-patch 2009/10/02 xcolor patch
24.84 -))
24.85 -\@linkdim=\dimen104
24.86 -\Hy@linkcounter=\count88
24.87 -\Hy@pagecounter=\count89
24.88 -
24.89 -(/usr/share/texmf-texlive/tex/latex/hyperref/pd1enc.def
24.90 -File: pd1enc.def 2009/10/09 v6.79a Hyperref: PDFDocEncoding definition (HO)
24.91 -)
24.92 -(/usr/share/texmf-texlive/tex/generic/oberdiek/etexcmds.sty
24.93 -Package: etexcmds 2007/12/12 v1.2 Prefix for e-TeX command names (HO)
24.94 -
24.95 -(/usr/share/texmf-texlive/tex/generic/oberdiek/infwarerr.sty
24.96 -Package: infwarerr 2007/09/09 v1.2 Providing info/warning/message (HO)
24.97 -)
24.98 -Package etexcmds Info: Could not find \expanded.
24.99 -(etexcmds) That can mean that you are not using pdfTeX 1.50 or
24.100 -(etexcmds) that some package has redefined \expanded.
24.101 -(etexcmds) In the latter case, load this package earlier.
24.102 -)
24.103 -(/usr/share/texmf-texlive/tex/latex/latexconfig/hyperref.cfg
24.104 -File: hyperref.cfg 2002/06/06 v1.2 hyperref configuration of TeXLive
24.105 -)
24.106 -(/usr/share/texmf-texlive/tex/latex/oberdiek/kvoptions.sty
24.107 -Package: kvoptions 2009/08/13 v3.4 Keyval support for LaTeX options (HO)
24.108 -
24.109 -(/usr/share/texmf-texlive/tex/generic/oberdiek/kvsetkeys.sty
24.110 -Package: kvsetkeys 2009/07/30 v1.5 Key value parser with default handler suppor
24.111 -t (HO)
24.112 -))
24.113 -Package hyperref Info: Option `colorlinks' set `true' on input line 2864.
24.114 -Package hyperref Info: Hyper figures OFF on input line 2975.
24.115 -Package hyperref Info: Link nesting OFF on input line 2980.
24.116 -Package hyperref Info: Hyper index ON on input line 2983.
24.117 -Package hyperref Info: Plain pages OFF on input line 2990.
24.118 -Package hyperref Info: Backreferencing OFF on input line 2995.
24.119 -
24.120 -Implicit mode ON; LaTeX internals redefined
24.121 -Package hyperref Info: Bookmarks ON on input line 3191.
24.122 -(/usr/share/texmf-texlive/tex/latex/ltxmisc/url.sty
24.123 -\Urlmuskip=\muskip10
24.124 -Package: url 2006/04/12 ver 3.3 Verb mode for urls, etc.
24.125 -)
24.126 -LaTeX Info: Redefining \url on input line 3428.
24.127 -
24.128 -(/usr/share/texmf-texlive/tex/generic/oberdiek/bitset.sty
24.129 -Package: bitset 2007/09/28 v1.0 Data type bit set (HO)
24.130 -
24.131 -(/usr/share/texmf-texlive/tex/generic/oberdiek/intcalc.sty
24.132 -Package: intcalc 2007/09/27 v1.1 Expandable integer calculations (HO)
24.133 -)
24.134 -(/usr/share/texmf-texlive/tex/generic/oberdiek/bigintcalc.sty
24.135 -Package: bigintcalc 2007/11/11 v1.1 Expandable big integer calculations (HO)
24.136 -
24.137 -(/usr/share/texmf-texlive/tex/generic/oberdiek/pdftexcmds.sty
24.138 -Package: pdftexcmds 2009/09/23 v0.6 LuaTeX support for pdfTeX utility functions
24.139 - (HO)
24.140 -
24.141 -(/usr/share/texmf-texlive/tex/generic/oberdiek/ifluatex.sty
24.142 -Package: ifluatex 2009/04/17 v1.2 Provides the ifluatex switch (HO)
24.143 -Package ifluatex Info: LuaTeX not detected.
24.144 -)
24.145 -(/usr/share/texmf-texlive/tex/generic/oberdiek/ltxcmds.sty
24.146 -Package: ltxcmds 2009/08/05 v1.0 Some LaTeX kernel commands for general use (HO
24.147 -)
24.148 -)
24.149 -Package pdftexcmds Info: LuaTeX not detected.
24.150 -Package pdftexcmds Info: \pdf@primitive is available.
24.151 -Package pdftexcmds Info: \pdf@ifprimitive is available.
24.152 -)))
24.153 -\Fld@menulength=\count90
24.154 -\Field@Width=\dimen105
24.155 -\Fld@charsize=\dimen106
24.156 -\Field@toks=\toks17
24.157 -Package hyperref Info: Hyper figures OFF on input line 4377.
24.158 -Package hyperref Info: Link nesting OFF on input line 4382.
24.159 -Package hyperref Info: Hyper index ON on input line 4385.
24.160 -Package hyperref Info: backreferencing OFF on input line 4392.
24.161 -Package hyperref Info: Link coloring ON on input line 4395.
24.162 -Package hyperref Info: Link coloring with OCG OFF on input line 4402.
24.163 -Package hyperref Info: PDF/A mode OFF on input line 4407.
24.164 -
24.165 -(/usr/share/texmf-texlive/tex/generic/oberdiek/atbegshi.sty
24.166 -Package: atbegshi 2008/07/31 v1.9 At begin shipout hook (HO)
24.167 -)
24.168 -\Hy@abspage=\count91
24.169 -\c@Item=\count92
24.170 -\c@Hfootnote=\count93
24.171 -)
24.172 -*hyperref using default driver hpdftex*
24.173 -(/usr/share/texmf-texlive/tex/latex/hyperref/hpdftex.def
24.174 -File: hpdftex.def 2009/10/09 v6.79a Hyperref driver for pdfTeX
24.175 -\Fld@listcount=\count94
24.176 -)
24.177 -(/usr/share/texmf-texlive/tex/generic/vaucanson-g/vaucanson-g.sty
24.178 -Package: vaucanson-g 2008/10/27 package wrapper for VauCanSon-G v. 0.4
24.179 -
24.180 -(/usr/share/texmf-texlive/tex/latex/base/ifthen.sty
24.181 -Package: ifthen 2001/05/26 v1.1c Standard LaTeX ifthen package (DPC)
24.182 -)
24.183 -(/usr/share/texmf/tex/latex/xcolor/xcolor.sty
24.184 -Package: xcolor 2007/01/21 v2.11 LaTeX color extensions (UK)
24.185 -
24.186 -(/etc/texmf/tex/latex/config/color.cfg
24.187 -File: color.cfg 2007/01/18 v1.5 color configuration of teTeX/TeXLive
24.188 -)
24.189 -Package xcolor Info: Package option `pst' ignored on input line 216.
24.190 -Package xcolor Info: Driver file: pdftex.def on input line 225.
24.191 -
24.192 -(/usr/share/texmf-texlive/tex/latex/pdftex-def/pdftex.def
24.193 -File: pdftex.def 2009/08/25 v0.04m Graphics/color for pdfTeX
24.194 -\Gread@gobject=\count95
24.195 -)
24.196 -Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1337.
24.197 -Package xcolor Info: Model `hsb' substituted by `rgb' on input line 1341.
24.198 -Package xcolor Info: Model `RGB' extended on input line 1353.
24.199 -Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1355.
24.200 -Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1356.
24.201 -Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1357.
24.202 -Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1358.
24.203 -Package xcolor Info: Model `Gray' substituted by `gray' on input line 1359.
24.204 -Package xcolor Info: Model `wave' substituted by `hsb' on input line 1360.
24.205 -)
24.206 -(/usr/share/texmf-texlive/tex/generic/vaucanson-g/VCColor-names.def)
24.207 -(/usr/share/texmf-texlive/tex/latex/pstricks/pstricks.sty
24.208 -Package: pstricks 2008/11/26 v0.40 LaTeX wrapper for `PSTricks' (RN,HV)
24.209 -
24.210 -(/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.tex
24.211 -`PSTricks' v1.29 <2009/05/19> (tvz)
24.212 -\pst@dima=\dimen107
24.213 -\pst@dimb=\dimen108
24.214 -\pst@dimc=\dimen109
24.215 -\pst@dimd=\dimen110
24.216 -\pst@dimg=\dimen111
24.217 -\pst@dimh=\dimen112
24.218 -\pst@hbox=\box26
24.219 -\pst@boxg=\box27
24.220 -\pst@cnta=\count96
24.221 -\pst@cntb=\count97
24.222 -\pst@cntc=\count98
24.223 -\pst@cntd=\count99
24.224 -\pst@cntg=\count100
24.225 -\pst@cnth=\count101
24.226 -\pst@toks=\toks18
24.227 -(/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.con)
24.228 -\psunit=\dimen113
24.229 -\psxunit=\dimen114
24.230 -\psyunit=\dimen115
24.231 -\pslinewidth=\dimen116
24.232 -\pst@customdefs=\toks19
24.233 -\pslinearc=\dimen117
24.234 -\everypsbox=\toks20
24.235 -\psframesep=\dimen118
24.236 -\pslabelsep=\dimen119
24.237 -\pst@shift=\dimen120
24.238 -\theoverlaybox=\box28
24.239 -)
24.240 -File: pstricks.tex 2009/05/19 v1.29 `PSTricks' (tvz,hv)
24.241 -)
24.242 -(/usr/share/texmf-texlive/tex/latex/pstricks/pst-node.sty
24.243 -Package: pst-node 2006/01/01 package wrapper for pst-node.tex
24.244 -
24.245 -(/usr/share/texmf-texlive/tex/generic/pstricks/pst-node.tex v1.01, 2008/11/26
24.246 -\psrow=\count102
24.247 -\pscol=\count103
24.248 -\psmatrixcnt=\count104
24.249 -\psrowsep=\skip43
24.250 -\pscolsep=\skip44
24.251 -)
24.252 -File: pst-node.tex 2008/11/26 1.01 `pst-node' (tvz)
24.253 -) (/usr/share/texmf-texlive/tex/latex/pstricks/pst-plot.sty
24.254 -Package: pst-plot 2004/07/15 package wrapper for pst-plot.tex
24.255 -
24.256 -(/usr/share/texmf-texlive/tex/generic/pstricks/pst-plot.tex
24.257 -(/usr/share/texmf-texlive/tex/generic/multido/multido.tex
24.258 - v1.41, 2004/05/18 <tvz>
24.259 -\multido@count=\count105
24.260 -\multidocount=\count106
24.261 -\multido@stuff=\toks21
24.262 -) v1.04, 2009/06/08)
24.263 -File: pst-plot.tex 2009/06/08 1.04 `pst-plot' (tvz)
24.264 -)
24.265 -(/usr/share/texmf-texlive/tex/latex/pst-coil/pst-coil.sty
24.266 -Package: pst-coil 2006/08/11 package wrapper for pst-coil.tex (hv)
24.267 -
24.268 -(/usr/share/texmf-texlive/tex/generic/pst-coil/pst-coil.tex v1.04, 2009/06/08
24.269 -(/usr/share/texmf-texlive/tex/generic/xkeyval/pst-xkey.tex
24.270 -File: pst-xkey.tex 2005/11/25 v1.6 PSTricks specialization of xkeyval (HA)
24.271 -
24.272 -(/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.sty
24.273 -Package: xkeyval 2008/08/13 v2.6a package option processing (HA)
24.274 -
24.275 -(/usr/share/texmf-texlive/tex/generic/xkeyval/xkeyval.tex
24.276 -\XKV@toks=\toks22
24.277 -\XKV@tempa@toks=\toks23
24.278 -\XKV@depth=\count107
24.279 -File: xkeyval.tex 2008/08/13 v2.6a key=value parser (HA)
24.280 -))))
24.281 -File: pst-coil.tex 2006/11/05 v1.00 `pst-coil' (tvz)
24.282 -)
24.283 -(/usr/share/texmf-texlive/tex/latex/multido/multido.sty
24.284 -Package: multido 2004/05/17 package wrapper for PSTricks `multido.tex', (HV/RN)
24.285 -
24.286 -)
24.287 -(/usr/share/texmf-texlive/tex/latex/pst-3d/pst-3d.sty
24.288 -Package: pst-3d 2005/09/02 package wrapper for pst-3d.tex (hv)
24.289 -
24.290 -(/usr/share/texmf-texlive/tex/generic/pst-3d/pst-3d.tex
24.291 -`PST-3d' v1.00, 2005/09/03 (tvz))
24.292 -File: pst-3d.tex 2005/09/03 v1.00 `PST-3d' (tvz)
24.293 -)
24.294 -(/usr/share/texmf-texlive/tex/latex/tools/calc.sty
24.295 -Package: calc 2007/08/22 v4.3 Infix arithmetic (KKT,FJ)
24.296 -\calc@Acount=\count108
24.297 -\calc@Bcount=\count109
24.298 -\calc@Adimen=\dimen121
24.299 -\calc@Bdimen=\dimen122
24.300 -\calc@Askip=\skip45
24.301 -\calc@Bskip=\skip46
24.302 -LaTeX Info: Redefining \setlength on input line 76.
24.303 -LaTeX Info: Redefining \addtolength on input line 77.
24.304 -\calc@Ccount=\count110
24.305 -\calc@Cskip=\skip47
24.306 -)
24.307 -(/usr/share/texmf-texlive/tex/generic/vaucanson-g/Vaucanson-G.tex
24.308 -\MediumStateDiameter=\skip48
24.309 -\SmallStateDiameter=\skip49
24.310 -\LargeStateDiameter=\skip50
24.311 -\VerySmallStateDiameter=\skip51
24.312 -\StateLineWidth=\skip52
24.313 -\EdgeLineWidth=\skip53
24.314 -\EdgeArrowWidth=\skip54
24.315 -\EdgeDblArrowWidth=\skip55
24.316 -\ZZSize=\skip56
24.317 -\EdgeOffset=\skip57
24.318 -\EdgeNodeSep=\skip58
24.319 -\VaucArcOffset=\skip59
24.320 -\LoopOffset=\skip60
24.321 -\LoopVarOffset=\skip61
24.322 -\TransLabelSep=\skip62
24.323 -\VertShiftH=\skip63
24.324 -LaTeX Font Info: External font `cmex10' loaded for size
24.325 -(Font) <10.95> on input line 206.
24.326 -LaTeX Font Info: External font `cmex10' loaded for size
24.327 -(Font) <8> on input line 206.
24.328 -LaTeX Font Info: External font `cmex10' loaded for size
24.329 -(Font) <6> on input line 206.
24.330 -\VertShiftD=\skip64
24.331 -\VertShift=\skip65
24.332 -\StateLineWid=\skip66
24.333 -\StateDiam=\skip67
24.334 -\VaucAOS=\skip68
24.335 -\VaucAOSdiag=\skip69
24.336 -\VariableStateIntDiam=\skip70
24.337 -\VariableStateWidth=\skip71
24.338 -\VariableStateITPos=\skip72
24.339 -\ExtraSpace=\skip73
24.340 -\EdgeLineWid=\skip74
24.341 -\EdgeArrowSZDim=\skip75
24.342 -\EdgeLineBord=\skip76
24.343 -\ZZSiZ=\skip77
24.344 -\EdgeOff=\skip78
24.345 -\VaucArcOff=\skip79
24.346 -\LoopOff=\skip80
24.347 -\LoopVarOff=\skip81
24.348 -\EdgeNodeSP=\skip82
24.349 -\TransLabelSP=\skip83
24.350 -\c@anglea=\count111
24.351 -\c@angleb=\count112
24.352 -)
24.353 -\VaucMinHeight=\skip84
24.354 -\VaucMaxHeight=\skip85
24.355 -
24.356 -(/usr/share/texmf-texlive/tex/generic/vaucanson-g/VCPref-default.tex))
24.357 -(/usr/share/texmf-texlive/tex/latex/oberdiek/hypcap.sty
24.358 -Package: hypcap 2008/09/08 v1.10 Adjusting anchors of captions (HO)
24.359 -)
24.360 -(/usr/share/texmf-texlive/tex/latex/fancyhdr/fancyhdr.sty
24.361 -\fancy@headwidth=\skip86
24.362 -\f@ncyO@elh=\skip87
24.363 -\f@ncyO@erh=\skip88
24.364 -\f@ncyO@olh=\skip89
24.365 -\f@ncyO@orh=\skip90
24.366 -\f@ncyO@elf=\skip91
24.367 -\f@ncyO@erf=\skip92
24.368 -\f@ncyO@olf=\skip93
24.369 -\f@ncyO@orf=\skip94
24.370 -)
24.371 -(/usr/share/texmf-texlive/tex/latex/graphics/graphicx.sty
24.372 -Package: graphicx 1999/02/16 v1.0f Enhanced LaTeX Graphics (DPC,SPQR)
24.373 -
24.374 -(/usr/share/texmf-texlive/tex/latex/graphics/graphics.sty
24.375 -Package: graphics 2009/02/05 v1.0o Standard LaTeX Graphics (DPC,SPQR)
24.376 -
24.377 -(/usr/share/texmf-texlive/tex/latex/graphics/trig.sty
24.378 -Package: trig 1999/03/16 v1.09 sin cos tan (DPC)
24.379 -)
24.380 -(/etc/texmf/tex/latex/config/graphics.cfg
24.381 -File: graphics.cfg 2009/08/28 v1.8 graphics configuration of TeX Live
24.382 -)
24.383 -Package graphics Info: Driver file: pdftex.def on input line 91.
24.384 -)
24.385 -\Gin@req@height=\dimen123
24.386 -\Gin@req@width=\dimen124
24.387 -)
24.388 -(/usr/share/texmf-texlive/tex/latex/lastpage/lastpage.sty
24.389 -Package: lastpage 1994/06/25 v0.1b LaTeX2e package for refs to last page number
24.390 - (JPG)
24.391 -)
24.392 -(/usr/share/texmf-texlive/tex/latex/preprint/fullpage.sty
24.393 -Package: fullpage 1999/02/23 1.1 (PWD)
24.394 -\FP@margin=\skip95
24.395 -)
24.396 -(/usr/share/texmf-texlive/tex/latex/amscls/amsthm.sty
24.397 -Package: amsthm 2004/08/06 v2.20
24.398 -\thm@style=\toks24
24.399 -\thm@bodyfont=\toks25
24.400 -\thm@headfont=\toks26
24.401 -\thm@notefont=\toks27
24.402 -\thm@headpunct=\toks28
24.403 -\thm@preskip=\skip96
24.404 -\thm@postskip=\skip97
24.405 -\thm@headsep=\skip98
24.406 -\dth@everypar=\toks29
24.407 -)
24.408 -(/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty
24.409 -Package: amsmath 2000/07/18 v2.13 AMS math features
24.410 -\@mathmargin=\skip99
24.411 -
24.412 -For additional information on amsmath, use the `?' option.
24.413 -(/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty
24.414 -Package: amstext 2000/06/29 v2.01
24.415 -
24.416 -(/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty
24.417 -File: amsgen.sty 1999/11/30 v2.0
24.418 -\@emptytoks=\toks30
24.419 -\ex@=\dimen125
24.420 -))
24.421 -(/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty
24.422 -Package: amsbsy 1999/11/29 v1.2d
24.423 -\pmbraise@=\dimen126
24.424 -)
24.425 -(/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty
24.426 -Package: amsopn 1999/12/14 v2.01 operator names
24.427 -)
24.428 -\inf@bad=\count113
24.429 -LaTeX Info: Redefining \frac on input line 211.
24.430 -\uproot@=\count114
24.431 -\leftroot@=\count115
24.432 -LaTeX Info: Redefining \overline on input line 307.
24.433 -\classnum@=\count116
24.434 -\DOTSCASE@=\count117
24.435 -LaTeX Info: Redefining \ldots on input line 379.
24.436 -LaTeX Info: Redefining \dots on input line 382.
24.437 -LaTeX Info: Redefining \cdots on input line 467.
24.438 -\Mathstrutbox@=\box29
24.439 -\strutbox@=\box30
24.440 -\big@size=\dimen127
24.441 -LaTeX Font Info: Redeclaring font encoding OML on input line 567.
24.442 -LaTeX Font Info: Redeclaring font encoding OMS on input line 568.
24.443 -\macc@depth=\count118
24.444 -\c@MaxMatrixCols=\count119
24.445 -\dotsspace@=\muskip11
24.446 -\c@parentequation=\count120
24.447 -\dspbrk@lvl=\count121
24.448 -\tag@help=\toks31
24.449 -\row@=\count122
24.450 -\column@=\count123
24.451 -\maxfields@=\count124
24.452 -\andhelp@=\toks32
24.453 -\eqnshift@=\dimen128
24.454 -\alignsep@=\dimen129
24.455 -\tagshift@=\dimen130
24.456 -\tagwidth@=\dimen131
24.457 -\totwidth@=\dimen132
24.458 -\lineht@=\dimen133
24.459 -\@envbody=\toks33
24.460 -\multlinegap=\skip100
24.461 -\multlinetaggap=\skip101
24.462 -\mathdisplay@stack=\toks34
24.463 -LaTeX Info: Redefining \[ on input line 2666.
24.464 -LaTeX Info: Redefining \] on input line 2667.
24.465 -)
24.466 -(/usr/share/texmf-texlive/tex/latex/amsfonts/amsfonts.sty
24.467 -Package: amsfonts 2009/06/22 v3.00 Basic AMSFonts support
24.468 -\symAMSa=\mathgroup4
24.469 -\symAMSb=\mathgroup5
24.470 -LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold'
24.471 -(Font) U/euf/m/n --> U/euf/b/n on input line 96.
24.472 -)
24.473 -(/usr/share/texmf-texlive/tex/latex/float/float.sty
24.474 -Package: float 2001/11/08 v1.3d Float enhancements (AL)
24.475 -\c@float@type=\count125
24.476 -\float@exts=\toks35
24.477 -\float@box=\box31
24.478 -\@float@everytoks=\toks36
24.479 -\@floatcapt=\box32
24.480 -)
24.481 -(/usr/share/texmf-texlive/tex/latex/paralist/paralist.sty
24.482 -Package: paralist 2002/03/18 v2.3b Extended list environments (BS)
24.483 -\pltopsep=\skip102
24.484 -\plpartopsep=\skip103
24.485 -\plitemsep=\skip104
24.486 -\plparsep=\skip105
24.487 -\pl@lab=\toks37
24.488 -)
24.489 -(/usr/share/texmf-texlive/tex/latex/listings/listings.sty
24.490 -\lst@mode=\count126
24.491 -\lst@gtempboxa=\box33
24.492 -\lst@token=\toks38
24.493 -\lst@length=\count127
24.494 -\lst@currlwidth=\dimen134
24.495 -\lst@column=\count128
24.496 -\lst@pos=\count129
24.497 -\lst@lostspace=\dimen135
24.498 -\lst@width=\dimen136
24.499 -\lst@newlines=\count130
24.500 -\lst@lineno=\count131
24.501 -\lst@maxwidth=\dimen137
24.502 -
24.503 -(/usr/share/texmf-texlive/tex/latex/listings/lstmisc.sty
24.504 -File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz)
24.505 -\c@lstnumber=\count132
24.506 -\lst@skipnumbers=\count133
24.507 -\lst@framebox=\box34
24.508 -)
24.509 -(/usr/share/texmf-texlive/tex/latex/listings/listings.cfg
24.510 -File: listings.cfg 2007/02/22 1.4 listings configuration
24.511 -))
24.512 -Package: listings 2007/02/22 1.4 (Carsten Heinz)
24.513 -
24.514 -(/usr/share/texmf-texlive/tex/latex/oberdiek/bookmark.sty
24.515 -Package: bookmark 2009/08/13 v1.5 PDF bookmarks (HO)
24.516 -
24.517 -(/usr/share/texmf-texlive/tex/generic/oberdiek/pdfescape.sty
24.518 -Package: pdfescape 2007/11/11 v1.8 Provides hex, PDF name and string conversion
24.519 -s (HO)
24.520 -)
24.521 -(/usr/share/texmf-texlive/tex/latex/oberdiek/auxhook.sty
24.522 -Package: auxhook 2007/04/06 v1.1 Hooks for auxiliary files (HO)
24.523 -)
24.524 -(/usr/share/texmf-texlive/tex/latex/oberdiek/bkm-pdftex.def
24.525 -File: bkm-pdftex.def 2009/08/13 v1.5 bookmark driver for pdfTeX (HO)
24.526 -\BKM@id=\count134
24.527 -)) (./exzerpt.aux)
24.528 -\openout1 = `exzerpt.aux'.
24.529 -
24.530 -LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 29.
24.531 -LaTeX Font Info: ... okay on input line 29.
24.532 -LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 29.
24.533 -LaTeX Font Info: ... okay on input line 29.
24.534 -LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 29.
24.535 -LaTeX Font Info: ... okay on input line 29.
24.536 -LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 29.
24.537 -LaTeX Font Info: ... okay on input line 29.
24.538 -LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 29.
24.539 -LaTeX Font Info: ... okay on input line 29.
24.540 -LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 29.
24.541 -LaTeX Font Info: ... okay on input line 29.
24.542 -LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 29.
24.543 -LaTeX Font Info: ... okay on input line 29.
24.544 -Package hyperref Info: Link coloring ON on input line 29.
24.545 -
24.546 -(/usr/share/texmf-texlive/tex/latex/hyperref/nameref.sty
24.547 -Package: nameref 2007/05/29 v2.31 Cross-referencing by name of section
24.548 -
24.549 -(/usr/share/texmf-texlive/tex/latex/oberdiek/refcount.sty
24.550 -Package: refcount 2008/08/11 v3.1 Data extraction from references (HO)
24.551 -)
24.552 -\c@section@level=\count135
24.553 -)
24.554 -LaTeX Info: Redefining \ref on input line 29.
24.555 -LaTeX Info: Redefining \pageref on input line 29.
24.556 -\AtBeginShipoutBox=\box35
24.557 -
24.558 -(/usr/share/texmf-texlive/tex/context/base/supp-pdf.mkii
24.559 -[Loading MPS to PDF converter (version 2006.09.02).]
24.560 -\scratchcounter=\count136
24.561 -\scratchdimen=\dimen138
24.562 -\scratchbox=\box36
24.563 -\nofMPsegments=\count137
24.564 -\nofMParguments=\count138
24.565 -\everyMPshowfont=\toks39
24.566 -\MPscratchCnt=\count139
24.567 -\MPscratchDim=\dimen139
24.568 -\MPnumerator=\count140
24.569 -\everyMPtoPDFconversion=\toks40
24.570 -)
24.571 -\c@lstlisting=\count141
24.572 -LaTeX Font Info: Try loading font information for U+msa on input line 31.
24.573 - (/usr/share/texmf-texlive/tex/latex/amsfonts/umsa.fd
24.574 -File: umsa.fd 2009/06/22 v3.00 AMS symbols A
24.575 -)
24.576 -LaTeX Font Info: Try loading font information for U+msb on input line 31.
24.577 -
24.578 -(/usr/share/texmf-texlive/tex/latex/amsfonts/umsb.fd
24.579 -File: umsb.fd 2009/06/22 v3.00 AMS symbols B
24.580 -) (./exzerpt.toc)
24.581 -\tf@toc=\write3
24.582 -\openout3 = `exzerpt.toc'.
24.583 -
24.584 - [1
24.585 -Non-PDF special ignored!
24.586 -Non-PDF special ignored!
24.587 -Non-PDF special ignored!
24.588 -Non-PDF special ignored!
24.589 -Non-PDF special ignored!
24.590 -
24.591 -{/var/lib/texmf/fonts/map/pdftex/updmap/pdftex.map}]
24.592 -LaTeX Font Info: Try loading font information for T1+cmtt on input line 37.
24.593 -
24.594 -(/usr/share/texmf-texlive/tex/latex/base/t1cmtt.fd
24.595 -File: t1cmtt.fd 1999/05/25 v2.5h Standard LaTeX font definitions
24.596 -) (./exzerpt.bbl) [2]
24.597 -[3] <img/cl_pair.png, id=103, 127.22531pt x 240.14719pt>
24.598 -File: img/cl_pair.png Graphic file (type png)
24.599 - <use img/cl_pair.png>
24.600 -[4pdfTeX warning (ext4): destination with the same identifier (name{figure.1})
24.601 -has been already used, duplicate ignored
24.602 -
24.603 -\AtBegShi@Output ...ipout \box \AtBeginShipoutBox
24.604 - \fi \fi
24.605 -l.148 \item[$\bullet$]
24.606 - R(S): y-Koordinate aller rechten ...
24.607 - <./img/cl_pair.png>] [5] [6] [7] [8] [9] [10] [11]
24.608 -<img/landau_sym.png, id=141, 786.68906pt x 201.75375pt>
24.609 -File: img/landau_sym.png Graphic file (type png)
24.610 -
24.611 -<use img/landau_sym.png> [12pdfTeX warning (ext4): destination with the same id
24.612 -entifier (name{figure.2}) has been already used, duplicate ignored
24.613 -
24.614 -\AtBegShi@Output ...ipout \box \AtBeginShipoutBox
24.615 - \fi \fi
24.616 -l.250 \end{document}
24.617 - <./img/landau_sym.png>] AED: lastpage setting LastPage
24.618 -(./exzerpt.aux)
24.619 -
24.620 -LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
24.621 -
24.622 - )
24.623 -Here is how much of TeX's memory you used:
24.624 - 10449 strings out of 495021
24.625 - 140322 string characters out of 1181035
24.626 - 263373 words of memory out of 3000000
24.627 - 13361 multiletter control sequences out of 15000+50000
24.628 - 19725 words of font info for 55 fonts, out of 3000000 for 9000
24.629 - 28 hyphenation exceptions out of 8191
24.630 - 38i,9n,56p,1246b,384s stack positions out of 5000i,500n,10000p,200000b,50000s
24.631 - </home/sawine/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecti1095.600pk> </home/
24.632 -sawine/.texmf-var/fonts/pk/ljfour/jknappen/ec/eccc1095.600pk> </home/sawine/.te
24.633 -xmf-var/fonts/pk/ljfour/jknappen/ec/ecbx1200.600pk> </home/sawine/.texmf-var/fo
24.634 -nts/pk/ljfour/jknappen/ec/ectt1095.600pk> </home/sawine/.texmf-var/fonts/pk/ljf
24.635 -our/jknappen/ec/ecrm1095.600pk> </home/sawine/.texmf-var/fonts/pk/ljfour/jknapp
24.636 -en/ec/ecbx1095.600pk> </home/sawine/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecbx
24.637 -1440.600pk> </home/sawine/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecrm1200.600pk
24.638 -> </home/sawine/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecrm1728.600pk></usr/sha
24.639 -re/texmf-texlive/fonts/type1/public/amsfonts/cm/cmex10.pfb></usr/share/texmf-te
24.640 -xlive/fonts/type1/public/amsfonts/cm/cmmi10.pfb></usr/share/texmf-texlive/fonts
24.641 -/type1/public/amsfonts/cm/cmmi8.pfb></usr/share/texmf-texlive/fonts/type1/publi
24.642 -c/amsfonts/cm/cmr10.pfb></usr/share/texmf-texlive/fonts/type1/public/amsfonts/c
24.643 -m/cmr8.pfb></usr/share/texmf-texlive/fonts/type1/public/amsfonts/cm/cmsy10.pfb>
24.644 -</usr/share/texmf-texlive/fonts/type1/public/amsfonts/cm/cmsy8.pfb>
24.645 -Output written on exzerpt.pdf (12 pages, 260307 bytes).
24.646 -PDF statistics:
24.647 - 643 PDF objects out of 1000 (max. 8388607)
24.648 - 52 named destinations out of 1000 (max. 500000)
24.649 - 275 words of extra memory for PDF output out of 10000 (max. 10000000)
24.650 -
25.1 --- a/exzerpt.out.ps Tue Feb 22 18:58:21 2011 +0100
25.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
25.3 @@ -1,147 +0,0 @@
25.4 -%!
25.5 -/pdfmark where{pop}
25.6 -{/globaldict where{pop globaldict}{userdict}ifelse/pdfmark/cleartomark load put}
25.7 -ifelse
25.8 -[
25.9 -/Title(Einleitung)
25.10 -/Count -3
25.11 -/Action/GoTo/Dest(section.1)cvn
25.12 -/OUT pdfmark
25.13 -[
25.14 -/Title(Themen:)
25.15 -/Action/GoTo/Dest(subsection.1.1)cvn
25.16 -/OUT pdfmark
25.17 -[
25.18 -/Title(Problem-/Anwendungsbereiche:)
25.19 -/Action/GoTo/Dest(subsection.1.2)cvn
25.20 -/OUT pdfmark
25.21 -[
25.22 -/Title(Literatur:)
25.23 -/Action/GoTo/Dest(subsection.1.3)cvn
25.24 -/OUT pdfmark
25.25 -[
25.26 -/Title(Divide and Conquer)
25.27 -/Count -5
25.28 -/Action/GoTo/Dest(section.2)cvn
25.29 -/OUT pdfmark
25.30 -[
25.31 -/Title(Formulierung des Divide and Conquer Prinzips)
25.32 -/Action/GoTo/Dest(subsection.2.1)cvn
25.33 -/OUT pdfmark
25.34 -[
25.35 -/Title(Quicksort)
25.36 -/Count -1
25.37 -/Action/GoTo/Dest(subsection.2.2)cvn
25.38 -/OUT pdfmark
25.39 -[
25.40 -/Title(Analyse)
25.41 -/Action/GoTo/Dest(subsubsection.2.2.1)cvn
25.42 -/OUT pdfmark
25.43 -[
25.44 -/Title(N\344chste Paare)
25.45 -/Count -2
25.46 -/Action/GoTo/Dest(subsection.2.3)cvn
25.47 -/OUT pdfmark
25.48 -[
25.49 -/Title(Algorithmus)
25.50 -/Action/GoTo/Dest(subsubsection.2.3.1)cvn
25.51 -/OUT pdfmark
25.52 -[
25.53 -/Title(Analyse)
25.54 -/Action/GoTo/Dest(subsubsection.2.3.2)cvn
25.55 -/OUT pdfmark
25.56 -[
25.57 -/Title(Segmentschnitt)
25.58 -/Count -2
25.59 -/Action/GoTo/Dest(subsection.2.4)cvn
25.60 -/OUT pdfmark
25.61 -[
25.62 -/Title(Algorithmus)
25.63 -/Action/GoTo/Dest(subsubsection.2.4.1)cvn
25.64 -/OUT pdfmark
25.65 -[
25.66 -/Title(Analyse)
25.67 -/Action/GoTo/Dest(subsubsection.2.4.2)cvn
25.68 -/OUT pdfmark
25.69 -[
25.70 -/Title(Polynomprodukt und Fast Fourier-Transformation)
25.71 -/Action/GoTo/Dest(subsection.2.5)cvn
25.72 -/OUT pdfmark
25.73 -[
25.74 -/Title(Randomisierung)
25.75 -/Count -1
25.76 -/Action/GoTo/Dest(section.3)cvn
25.77 -/OUT pdfmark
25.78 -[
25.79 -/Title(Hashing)
25.80 -/Action/GoTo/Dest(subsection.3.1)cvn
25.81 -/OUT pdfmark
25.82 -[
25.83 -/Title(Amortisierte Analyse)
25.84 -/Count -3
25.85 -/Action/GoTo/Dest(section.4)cvn
25.86 -/OUT pdfmark
25.87 -[
25.88 -/Title(Binomial Heaps)
25.89 -/Action/GoTo/Dest(subsection.4.1)cvn
25.90 -/OUT pdfmark
25.91 -[
25.92 -/Title(Fibonacci Heaps)
25.93 -/Action/GoTo/Dest(subsection.4.2)cvn
25.94 -/OUT pdfmark
25.95 -[
25.96 -/Title(Union Find)
25.97 -/Action/GoTo/Dest(subsection.4.3)cvn
25.98 -/OUT pdfmark
25.99 -[
25.100 -/Title(Greedy)
25.101 -/Count -1
25.102 -/Action/GoTo/Dest(section.5)cvn
25.103 -/OUT pdfmark
25.104 -[
25.105 -/Title(K\374rzeste \(billigste\) Wege)
25.106 -/Action/GoTo/Dest(subsection.5.1)cvn
25.107 -/OUT pdfmark
25.108 -[
25.109 -/Title(Bin Packing)
25.110 -/Count -2
25.111 -/Action/GoTo/Dest(section.6)cvn
25.112 -/OUT pdfmark
25.113 -[
25.114 -/Title(Online Verfahren)
25.115 -/Count -3
25.116 -/Action/GoTo/Dest(subsection.6.1)cvn
25.117 -/OUT pdfmark
25.118 -[
25.119 -/Title(Next Fit \(NF\))
25.120 -/Action/GoTo/Dest(subsubsection.6.1.1)cvn
25.121 -/OUT pdfmark
25.122 -[
25.123 -/Title(First-Fit \(FF\))
25.124 -/Action/GoTo/Dest(subsubsection.6.1.2)cvn
25.125 -/OUT pdfmark
25.126 -[
25.127 -/Title(Best-Fit \(BF\))
25.128 -/Action/GoTo/Dest(subsubsection.6.1.3)cvn
25.129 -/OUT pdfmark
25.130 -[
25.131 -/Title(Offline Verfahren)
25.132 -/Count -2
25.133 -/Action/GoTo/Dest(subsection.6.2)cvn
25.134 -/OUT pdfmark
25.135 -[
25.136 -/Title(First Fit Decreasing \(FFD oder FFNI\))
25.137 -/Action/GoTo/Dest(subsubsection.6.2.1)cvn
25.138 -/OUT pdfmark
25.139 -[
25.140 -/Title(Best Fit Decreasing \(BFD\))
25.141 -/Action/GoTo/Dest(subsubsection.6.2.2)cvn
25.142 -/OUT pdfmark
25.143 -[
25.144 -/Title(Dynamische Programmierung)
25.145 -/Action/GoTo/Dest(section.7)cvn
25.146 -/OUT pdfmark
25.147 -[
25.148 -/Title(Landau-Symbole)
25.149 -/Action/GoTo/Dest(appendix.A)cvn
25.150 -/OUT pdfmark
26.1 --- a/exzerpt.tex Tue Feb 22 18:58:21 2011 +0100
26.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
26.3 @@ -1,250 +0,0 @@
26.4 -\documentclass[a4paper,11pt,twoside]{article}
26.5 -
26.6 -\usepackage[ngerman]{babel}
26.7 -\usepackage[T1]{fontenc}
26.8 -\usepackage[latin1]{inputenc}
26.9 -\usepackage[colorlinks=true,linkcolor=black]{hyperref}
26.10 -
26.11 -\usepackage{vaucanson-g}
26.12 -\usepackage{hyperref}
26.13 -\usepackage{hypcap}
26.14 -\usepackage{fancyhdr}
26.15 -\usepackage{graphicx}
26.16 -\usepackage{lastpage}
26.17 -\usepackage[cm]{fullpage}
26.18 -\usepackage{amsthm, amsmath, amsfonts}
26.19 -\usepackage{float}
26.20 -\usepackage{paralist}
26.21 -\usepackage{listings}
26.22 -\usepackage{color}
26.23 -\usepackage{bookmark}
26.24 -
26.25 -% Festlegung Art der Zitierung - Havardmethode: Abkuerzung Autor + Jahr
26.26 -\bibliographystyle{alphadin}
26.27 -
26.28 -\title{\underline{Exzerpt Algorithmentheorie WS10/11}}
26.29 -\author{Markus Lindenmann}
26.30 -\date{\today{} }
26.31 -
26.32 -\begin{document}
26.33 - \maketitle
26.34 -
26.35 - \tableofcontents
26.36 - \newpage
26.37 -
26.38 - \section{Einleitung}\label{sec:intro}
26.39 - Dozent: Matthias Westermann\\
26.40 - Website: \url{http://lak.informatik.uni-freiburg.de}\\
26.41 - Klausur: 09.03.2011\\
26.42 - Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
26.43 - \subsection{Themen:}
26.44 - \begin{itemize}
26.45 - \item[$\bullet$] Divide and Conquer
26.46 - \item[$\bullet$] Greedy Prinzip
26.47 - \item[$\bullet$] Dynamische Programmierung
26.48 - \item[$\bullet$] Randomisierung
26.49 - \item[$\bullet$] Amortisierte Analyse
26.50 - \end{itemize}
26.51 - \subsection{Problem-/Anwendungsbereiche:}
26.52 - \begin{itemize}
26.53 - \item[$\bullet$] Geometrische Algorithmen
26.54 - \item[$\bullet$] Algebraische Algorithmen
26.55 - \item[$\bullet$] Graphenalgorithmen
26.56 - \item[$\bullet$] Datenstrukturen
26.57 - \item[$\bullet$] Internet-Algorithmen
26.58 - \item[$\bullet$] ptimierungs-Verfahren
26.59 - \item[$\bullet$] Zeichenkettenverarbeitung
26.60 - \end{itemize}
26.61 - \subsection{Literatur:}
26.62 - \bibliography{literatur}
26.63 - \nocite{*}
26.64 -
26.65 - \newpage
26.66 - \section{Divide and Conquer}\label{sec:div&conq}
26.67 - \begin{itemize}
26.68 - \item[$\bullet$] Quicksort
26.69 - \item[$\bullet$] Formulierung und Analyse des Prinzips
26.70 - \item[$\bullet$] Geometrisches Devide and Conquer
26.71 - \begin{itemize}
26.72 - \item[-] Closest-Pair
26.73 - \item[-] Segmentschnitt
26.74 - \end{itemize}
26.75 - \end{itemize}
26.76 -
26.77 - \subsection{Formulierung des Divide and Conquer Prinzips}
26.78 - D\&C Verfahren zur Lösung eines Problems der Größe $n$
26.79 - \begin{itemize}
26.80 - \item[1.] Divide\\$n>2$: Teile das Problem in $k$ Teilprobleme der Größe $n_1,\ldots n_k$ ($k\geq2$)\\$n\leq c:$ Löse das Problem direkt
26.81 - \item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
26.82 - \item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
26.83 - \end{itemize}
26.84 -
26.85 - \subsection{Quicksort}
26.86 - Wähle beliebiges Pivot Element $v$ und sortiere alle Elemente aus der Menge, die größer sind als $v$ rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge $F$ nur ein Element beinhaltet, gebe $F$ zurück.
26.87 -
26.88 - \subsubsection{Analyse}
26.89 - $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
26.90 - \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
26.91 - Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
26.92 - Divide- und Mergeaufwand: $DM(n)$\\
26.93 - $T(1)=a$\\
26.94 - $T(n)=2T(\frac{n}{2})+DM(n)$
26.95 -
26.96 - \subsection{Nächste Paare}
26.97 - Eingabe: $n$ Punkte in Ebene\\
26.98 - Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\
26.99 - Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
26.100 - \subsubsection{Algorithmus}
26.101 - \begin{itemize}
26.102 - \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
26.103 - \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
26.104 - \item[$\bullet$] Löse rekursiv auf Q und R
26.105 - \item[$\bullet$] Sortiere Punkte nach y-Koordinate
26.106 - \item[$\bullet$] Teste alle Paare, deren Abstand in der Sortierung kleiner als 16 ist (siehe unten)
26.107 - \item[$\bullet$] Füge zusammen
26.108 - \end{itemize}
26.109 -
26.110 - $\delta=$ Minimum der Teillösungen\\
26.111 - Gibt es $q\in Q$ und $r\in R$ mit $d(q,r)<\delta$, dann sind sowohl $q$ als auch $r$ höchstens $\delta$ von $L$ (Mitte) entfernt.\\
26.112 - \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
26.113 - \textbf{Lösung:}\begin{itemize}
26.114 - \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
26.115 - \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
26.116 - \end{itemize}
26.117 -
26.118 - Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
26.119 - \begin{itemize}
26.120 - \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
26.121 - \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
26.122 - \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
26.123 - \end{itemize}
26.124 -
26.125 - \begin{figure}[H]
26.126 - \centering
26.127 - \includegraphics[scale=0.5]{img/cl_pair}
26.128 - \caption{Nächste Paare: Prüf Distanz}
26.129 - \label{cl_pair}
26.130 - \end{figure}
26.131 -
26.132 - \subsubsection{Analyse}
26.133 - \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
26.134 - \[T(n)\leq an \log n \]
26.135 -
26.136 - \subsection{Segmentschnitt}
26.137 - Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
26.138 - Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
26.139 -
26.140 - \subsubsection{Algorithmus}
26.141 - \textbf{Divide \& Conquer:}\\Fallunterscheidung
26.142 - \begin{itemize}
26.143 - \item[1.] $\left| S\right| > 1$:\\ Teile S mittels einer vertikalen Gerade G in 2 gleichgroße Mengen $S_1$ (links von G) und $S_2$ (rechts von G). Führe rekursiv auf beiden Hälften aus.
26.144 - \item[2.] else: S enthält keine Schnitte
26.145 - \end{itemize}
26.146 -
26.147 - \textbf{Merge}\\
26.148 - Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
26.149 - \begin{itemize}
26.150 - \item[$\bullet$] L(S): y-Koordinate aller linken Endpunkte in S, deren rechter Partner nicht in S\\$=L(S_2)\cup(L(S_1)-R(S_2))$
26.151 - \item[$\bullet$] R(S): y-Koordinate aller rechten Endpunkte in S, deren linker Partner nicht in S\\$=R(S_1)\cup(R(S_2)-L(S_1))$
26.152 - \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
26.153 - \end{itemize}
26.154 - L,R sortiert nach steigender y-Koordinate\\
26.155 - V sortiert nach steigendem unteren Endpunkt\\
26.156 - \medskip
26.157 -
26.158 - \textbf{Basisfälle}\\
26.159 - S enthält nur ein Element s. Fallunterscheidung:
26.160 - \begin{itemize}
26.161 - \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
26.162 - \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
26.163 - \item[3.] $s=(x,y_1,y_2)$ ist ein vertikales Segment:\\$L(S)=\emptyset,\qquad R(S)=\emptyset,\qquad V(S)=\{[y_1,y_2]\}$
26.164 - \end{itemize}
26.165 -
26.166 - \subsubsection{Analyse}
26.167 - Eingabe wird Anfangs sortiert und in Array gespeichert
26.168 - \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
26.169 - \[T(1)=O(1)\]
26.170 - \[O(n \log n + k \mid k=\#Schnittpunkte\]
26.171 -
26.172 - \subsection{Polynomprodukt und Fast Fourier-Transformation}
26.173 -
26.174 -
26.175 - \newpage
26.176 - \section{Randomisierung}
26.177 - \subsection{Hashing}
26.178 -
26.179 - \newpage
26.180 - \section{Amortisierte Analyse}
26.181 - \subsection{Binomial Heaps}
26.182 - \subsection{Fibonacci Heaps}
26.183 - \subsection{Union Find}
26.184 -
26.185 - \newpage
26.186 - \section{Greedy}
26.187 - \subsection{Kürzeste (billigste) Wege}
26.188 -
26.189 - \newpage
26.190 - \section{Bin Packing}
26.191 - \textbf{Problembeschreibung:}\\
26.192 - Man hat $n$ Objekte verschiedener Größe mit $0<s_i\leq1\mid 1\leq i\leq n$. Gesucht ist die kleinst mögliche Anzahl an Kisten (Bins) der Größe 1, mit der alle Objekte verpackt werden können.
26.193 - \subsection{Online Verfahren}
26.194 - Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste, in die es zuerst gepackt wird.\\
26.195 - Kein Online Bin Packing Verfahren kann stets eine optimale Lösung finden!\\
26.196 - \textbf{Satz 1}: Es gibt Eingaben, die jeden Online Bin Packing Algorithmus zwingen, wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die minimal mögliche Binzahl ist.\\
26.197 - \textbf{Beweis} Annahme: Online Bin Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$ Bins.\\
26.198 - Es wird eine Eingabe mit $2m$ Objekten angenommen. Die ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$ Kisten, da immer ein großes mit einem kleinen Paket kombiniert werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$ Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$ Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3} OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit: $b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach $2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m \wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn $b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem \underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten $<\frac{2}{3}m$ sein muss.
26.199 -
26.200 - \subsubsection{Next Fit (NF)}
26.201 - Verpacke das nächste Objekt in dieselbe Kiste wie das vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue Kiste und verpacke es dort.\\
26.202 - \textbf{Satz 2}: (a) Für alle Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\
26.203 - \textbf{Beweis}\\
26.204 - (a) Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1}, B_{2k}$. Man weiß, dass die beinhalteten Objekte eine Summengröße $>1$ haben, sonst wären selbige in einer Kiste. Daraus folgt, man kann nicht mehr als die doppelte Anzahl an Kisten als beim Optimum erreichen!\\
26.205 - (b) Inputfolge: $0.5, \frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5, \frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5 + \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und $OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in $=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er Objekte in eine Kiste passen)\\
26.206 - Laufzeit für Inputfolgen der Länge $n$: NF $O(n)$
26.207 - \subsubsection{First-Fit (FF)}
26.208 - Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue Kiste.\\
26.209 - \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger als halb voll ist. ($\implies FF(I) \leq 2OPT(I)$)\\
26.210 - \textbf{Satz 3}: (a) Für alle Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10} OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit $FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen $I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\
26.211 - \textbf{Beweis}\\
26.212 - (b') Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon, \frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$ (jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils 2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$ Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in eine Kiste und benötigt somit nur $6m$ Kisten.\\
26.213 - Laufzeit für Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
26.214 - \subsubsection{Best-Fit (BF)}
26.215 - Verpacke das nächste Objekt in diejenige Kiste, in die es am besten passt (d.h. den geringsten Platz ungenutzt lässt).
26.216 - Verhalten von BF ähnlich zu FF.
26.217 - Laufzeit für Inputfolgen der Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
26.218 - \subsection{Offline Verfahren}
26.219 - \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
26.220 - Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann beginnt die Verpackung.\\
26.221 - $n$ und $s_1, ..., s_n$ sind gegeben, bevor die Verpackung beginnt!\\
26.222 - $\rightarrow$ \underline{Optimale Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER: Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die schneller sind aber dafür unter Umständen nicht optimal!\\
26.223 - Idee für Offline Approximationsalgorithmen: Sortiere die Objekte zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
26.224 - \subsubsection{First Fit Decreasing (FFD oder FFNI)}
26.225 - \textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann haben alle von FFD in den Bins $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine Größe von höchstens $\frac{1}{3}$.\\
26.226 - \textbf{Beweis}: \$\$\$TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang\$\$\$\\
26.227 - \textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann ist die Anzahl der Objekte, die FFD in die Kisten $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens $m-1$.\\
26.228 - \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$ Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten verpacken. Dies führt zu einem Widerspruch. \$\$\$TODO:Warum?\$\$\$\\
26.229 - \textbf{Satz}: Für alle Inputfolgen I gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\
26.230 - \textbf{Satz}:
26.231 - \begin{itemize}
26.232 - \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
26.233 - \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
26.234 - \end{itemize}
26.235 - \textbf{Beweis}: \$\$\$TODO\$\$\$
26.236 - \subsubsection{Best Fit Decreasing (BFD)}
26.237 - Nicht im Script???
26.238 -
26.239 - \newpage
26.240 - \section{Dynamische Programmierung}
26.241 -
26.242 -
26.243 - \newpage
26.244 - \begin{appendix}
26.245 - \section{Landau-Symbole}
26.246 - \begin{figure}[H]
26.247 - \centering
26.248 - \includegraphics[scale=0.45]{img/landau_sym}
26.249 - \caption{Definition der Landau Symbole}
26.250 - \label{fig:landau_sym}
26.251 - \end{figure}
26.252 - \end{appendix}
26.253 -\end{document}
27.1 --- a/exzerpt.toc Tue Feb 22 18:58:21 2011 +0100
27.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
27.3 @@ -1,34 +0,0 @@
27.4 -\select@language {ngerman}
27.5 -\contentsline {section}{\numberline {1}Einleitung}{2}{section.1}
27.6 -\contentsline {subsection}{\numberline {1.1}Themen:}{2}{subsection.1.1}
27.7 -\contentsline {subsection}{\numberline {1.2}Problem-/Anwendungsbereiche:}{2}{subsection.1.2}
27.8 -\contentsline {subsection}{\numberline {1.3}Literatur:}{2}{subsection.1.3}
27.9 -\contentsline {section}{\numberline {2}Divide and Conquer}{3}{section.2}
27.10 -\contentsline {subsection}{\numberline {2.1}Formulierung des Divide and Conquer Prinzips}{3}{subsection.2.1}
27.11 -\contentsline {subsection}{\numberline {2.2}Quicksort}{3}{subsection.2.2}
27.12 -\contentsline {subsubsection}{\numberline {2.2.1}Analyse}{3}{subsubsection.2.2.1}
27.13 -\contentsline {subsection}{\numberline {2.3}N\"achste Paare}{3}{subsection.2.3}
27.14 -\contentsline {subsubsection}{\numberline {2.3.1}Algorithmus}{3}{subsubsection.2.3.1}
27.15 -\contentsline {subsubsection}{\numberline {2.3.2}Analyse}{4}{subsubsection.2.3.2}
27.16 -\contentsline {subsection}{\numberline {2.4}Segmentschnitt}{4}{subsection.2.4}
27.17 -\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{4}{subsubsection.2.4.1}
27.18 -\contentsline {subsubsection}{\numberline {2.4.2}Analyse}{5}{subsubsection.2.4.2}
27.19 -\contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation}{5}{subsection.2.5}
27.20 -\contentsline {section}{\numberline {3}Randomisierung}{6}{section.3}
27.21 -\contentsline {subsection}{\numberline {3.1}Hashing}{6}{subsection.3.1}
27.22 -\contentsline {section}{\numberline {4}Amortisierte Analyse}{7}{section.4}
27.23 -\contentsline {subsection}{\numberline {4.1}Binomial Heaps}{7}{subsection.4.1}
27.24 -\contentsline {subsection}{\numberline {4.2}Fibonacci Heaps}{7}{subsection.4.2}
27.25 -\contentsline {subsection}{\numberline {4.3}Union Find}{7}{subsection.4.3}
27.26 -\contentsline {section}{\numberline {5}Greedy}{8}{section.5}
27.27 -\contentsline {subsection}{\numberline {5.1}K\"urzeste (billigste) Wege}{8}{subsection.5.1}
27.28 -\contentsline {section}{\numberline {6}Bin Packing}{9}{section.6}
27.29 -\contentsline {subsection}{\numberline {6.1}Online Verfahren}{9}{subsection.6.1}
27.30 -\contentsline {subsubsection}{\numberline {6.1.1}Next Fit (NF)}{9}{subsubsection.6.1.1}
27.31 -\contentsline {subsubsection}{\numberline {6.1.2}First-Fit (FF)}{9}{subsubsection.6.1.2}
27.32 -\contentsline {subsubsection}{\numberline {6.1.3}Best-Fit (BF)}{10}{subsubsection.6.1.3}
27.33 -\contentsline {subsection}{\numberline {6.2}Offline Verfahren}{10}{subsection.6.2}
27.34 -\contentsline {subsubsection}{\numberline {6.2.1}First Fit Decreasing (FFD oder FFNI)}{10}{subsubsection.6.2.1}
27.35 -\contentsline {subsubsection}{\numberline {6.2.2}Best Fit Decreasing (BFD)}{10}{subsubsection.6.2.2}
27.36 -\contentsline {section}{\numberline {7}Dynamische Programmierung}{11}{section.7}
27.37 -\contentsline {section}{\numberline {A}Landau-Symbole}{12}{appendix.A}
28.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
28.2 +++ b/img/dijkstraExT.eps Tue Feb 22 19:14:19 2011 +0100
28.3 @@ -0,0 +1,99 @@
28.4 +%!PS-Adobe-3.0 EPSF-3.0
28.5 +%%Pages: 1
28.6 +%%BoundingBox: 0 0 420 263
28.7 +%%DocumentData: Clean7Bit
28.8 +%%LanguageLevel: 2
28.9 +%%EndComments
28.10 +%%Page: 1 1
28.11 +save 9 dict begin
28.12 +{/T currentfile/ASCII85Decode filter def/DeviceGray setcolorspace
28.13 +/F T/LZWDecode filter def
28.14 +<</ImageType 1/Width 420/Height 263/BitsPerComponent
28.15 +8/ImageMatrix[1 0 0 -1 0 263]/Decode
28.16 +[0 1]/DataSource F>> image
28.17 + F closefile T closefile}
28.18 +%%BeginData:
28.19 +exec
28.20 +J3Vsg3$]7K#D>EP:q1$o*=mro@So+\<\5,H7Uo<*jE<[.O@Wn[3@'nb-^757;Rp>H>q_R=AlC^cenm
28.21 +@9:1mM9jS"!dTMT<$3[GQ$8#0$s<4ZX!SPQ1`C/m<k<ioH)<b27<j_DJ9YY9QY3us(#B=(5][[Uj:h
28.22 +%I-MmT2B[NO%68f4hF(]=-sRPIT*h5QO"5KGpOdO(r7kN:pMICPPiee,X#Uhln!.j(Bj8]KmR=P9AC
28.23 +[8@@5d:M"DiM4/uYRHZH+:LTdK7.mS8A0nNl1-"LOROaF.[t?i.,??/SSI^&mbaaJa[tR8RC8_P+#<
28.24 +!L\g@P5=Y*Sc$`#A=HEHZi/+SO$*r_OnTPKaVCPQ(SAK=#B+U/1C]r]0.T!;.N].74.\6`_&[]s$3.
28.25 +^QNFp.0DVmRLj;M8>ut)6VI=d#pKMB*tY,6.<:-Ia>:XH0BL;&\r#s/&pjTj+q!][K-U[@/]4X%KLM
28.26 +h,h&mh8$3"RtW,-^0Q*EH5["bg-"L?/5)!`9b%&qr]`!B>JJ$[RlgG-kB7):ZC"!KTWT[(d%1<dp8`
28.27 +idQbPk@2cPO/64ckHom6-tiIoH(@f4,Fp$'<85tb3/]/29KifC-g,N,o7#LP]G/$Te=S9'Zb:sBQ;I
28.28 +b;TOPePk)^DUB5fT)a21dRj(jMXJJuK`GB.E5Ljib0ht81a\p`Je%m%J`=7;m=S;`1Am$U^lV+kjBa
28.29 +6.X`[#;VP'28RX.4"">$TcpTgCo*?it7Z7;/1,DHpqEEZU4J\g$jOa)0RTbg-H)L;"I`lE!!3W2aA:
28.30 +QP7+5Zrd4j#!EeA'_l+h3iNT!YVF/m&@S;=oN;G7rHD^hj-N0-B5#@Qj%@$!Gc[gJ$7F#Q3SHfS\RH
28.31 +#3i"kWQOZaH9@]8=HKV`Thn<7Ga&:#$cM+@ke5Cp1N?uqrRl@*?"(kaCHateo)6<defDLn%cB,N$DL
28.32 +:\So\.GN,H`jAP8g(_uk0(srl^;XiWgb6s!,0&7DUZ6IHMTL',(!R2HSVZQe9c*2@[FbQS-1L]_K<'
28.33 +&bK/lH(!S0iE]_>d]Ta7LOKK:<8`8CE"4S^ri]kak*<[6$FT'*Xjl"5c=Guk!,^J-h8dBI#GDO;&q&
28.34 +fYBr!j#8<h3X&QrG[U%>R=1&K$a-.2@b0it0hJKPJ&V`L)aCr$C'\!$pC+3E3.a(kG$1_cG!iBf2AS
28.35 +k7a3ZA=dq.cCmZ%SC1%XT?o#$QrLd9#GkAa'cN<O3?G.jB(T4p::VsR6DcS#m>f;"MpEd$g(`PS8$c
28.36 +FYebE-*iH;b8@r^6L@WQCuhr"/V9nrb'_bMd!lW&hq-EZ7n\0t)#+dL5>0/[N&npu85e?VnU-@\U`J
28.37 +mrWK\k[TH5g[>fRba8G1Om\bn^st7H6K'>n*Tt1#-+;si(CES#o=\O;VL*<r*@W,5KSLq\t,88$P11
28.38 +Sn[hX>ZkHs.o1HRh?B9T6kD/ijI?/Tt.GW*jWdYJS&)d`S^Mj7Q]eloso(KjPl2LKD/GK5KTs(dnr%
28.39 +"u!CBpgMHcl=RcsmEL_X.u9h8$7j%\#ime/nE7O[M7^,uBM($*95g7h.-_]?:sYbH_9jU9@4>&k8!?
28.40 +Cr!3X]N6>uP!hKk`\#tXZUUmhSK&j$e6=7I1"mor\WRr1,,2BKh[h`q/@NWmO6iP"b"IDdpVG8Tf.8
28.41 +1>r3\C/P3O&@]/'lU0qra=:5c??bkAA<LkORK:(+GiL/F-i0Y1#D/JP,/mkk2<ctp@!"k-..*:VAar
28.42 +?Vt!0\&_0;idJ4<7D=5[8GJtX\AIh$nYI),P>nmZW7V@AR<rMl9AM*9'pa!f8Mk?Z;@t=R--k:eW"7
28.43 +q'='E*g<*Ed#$MG;UsLDgXh^T3P23NdgPVOXDr"!u`?&9C^!*;$-iMM?-C89YG@*:\Q%!%`r*Z,*<b
28.44 +:dK?V/64I_YYQ!Gl1(*Zp!WM.R?WanT1+J`4j3+PnE2p-gWDq%bcLj)a3aO(D.B6^hP%AD$80cDkTC
28.45 +k3E4SS$S?sc(6-SPN&!D#bC@/2-N__UI,?jJ"U10D",7*2En%!?lE@>R]SXaJsjXTk.8U[g9)m1_-.
28.46 +W2J\!p9%AU'T[V(9XfqO0a^`0j$]'@nEZ*L/equaa-]<:gBDjk;:3lTlZQCDiZ(Cdnsq0%abE(S(j;
28.47 +K<_*8GVKHX8S<)>hTM0^"G>C"`-9WD:YGP1\Z<@=Ip2WG3CScqH@1f71Ss]#'"rh?0?QMGQ(2JiG]Q
28.48 +&S)Z](8"tTZ4Jb@+q:-jdm3,f+)#\g\]>O"5BJ6nC38X\O/c8sb(\7I7pZ(nVT3pl:^?!dJ?]4J@O4
28.49 +!t=a6riH0E>O@jk:gnqZ5G-AK@^0[?Hq2E$-tM+g<7E^rJW-T@p&m0Q;`]"VaVbW==J,[LL)_*=%_c
28.50 +?\N'C#G%ed$j^Al9h#I.S>4=:iR&0j89E4rpL_]G4?84.2BF-]P7QVdLPSeaLdY2R6m5e[0$uF)&Eo
28.51 +^DO6`'gA_noUnfnn\g(/-WE3dIHcpPuY\Jaaj&3"X"4%0IPN:FiC&f<,$<jF;iKnMe5ZTfESnI6M7b
28.52 +U87ugq=BLjrVENG)FZ,!t'SG(kPFBT]18GA#[.Z1+\q'OIcFSLbos$N.ZjQ*$%Eq\WBX8Pq1hJ-c5p
28.53 +-$R<#`LflnA,n-OpV&!4U@K&7+aK5l$e5hWBa":jW2B62e.tk^1.#FIZPG$Dd`2IuT(%Co6J^?:T$'
28.54 +%VJ(s`m>4=AAD<_"Ng$l^A>)U(RP.;"u/*+=pa:P/j(6)]L+$>HH<,4dq<>kNULg4)g@"uFUD"-HOM
28.55 +,#L2p+[UG6TZ#LC8;%Zp)^,`b6P,2Qi?gtu*6rF9@Z(qOM%.OO*23\ce=#7\*GIql#.0bU#Z1ptWE?
28.56 +BJe@_ST\\LSNQt2kqfY3i;-Q^1-.3c/BMMsfm;b3S-"N&<V'`c<eLo>Hl&O<-+;#1fYbtK>R9!&[!p
28.57 +*Aq"?`!jcN5umR;FUXl!!'a/OV$e.8=RJJ[D'3cE1]B,fb(Aek'g(a67?B$';]jhL'C7t7RShrYiOS
28.58 +ZK^p%/.:%r]1TcelU+9g]M"Ufa=GdMZK4de&JmYpMKV-o6CL6e0RKKo8P+cr%aE7)MDG5Z8qd`P("b
28.59 +NX1KS^!r`=[tmFfC!Wae?>*5t9+B+r:Eq+3VE>=[2s(JWddIK9@a%Ubet-e1qAXel(:7i??gP3KX]s
28.60 +IW*d6^R+Zo?i0qTE#&PkQkoj3lf`-'D?n"F2[<ag+;?Jg\%NU+(1B'IEaTm9Tto71gu`]G0=>Dh!!"
28.61 +q9N'_ca:"O0)K+M?5=$;<Yho5"c\`/8BpVqJ+'t4P)h_H'b#`[SW(M)"Nb[=!+>o^1q^EX9eRu%Hu:
28.62 +Sg&ad&BV$M]?:c+kM&dOtl>o#QA%K=^Zsd>e##udIG-8I`RX#Ak;8`?^RM;f+B0uBI\!oas:P='>cu
28.63 +,1SHD),^_Z/'UnVf%Sn<,@#sO2-_X)MWmG:\D!,7^V=V:I`?a6\-B_IEoKa,sp2GguZ7[XneHF<r!W
28.64 +N4P_'#sq.MW<rKu"hJ<dZYI&rFRM5R8?9.iO"/A!+:urN\;(a<0[\XFYCfHUl_@<n\<2-(3")ZY@)3
28.65 +EtNa:'J]FC:3Ama7qcmu1gC&MTdWTtaP=?u+A%t@EN+(`rm)LVC%Q0<k*9D[=X_QMXTg:<)DNeLMH.
28.66 +4e9=[N0F./pt.(L8IA?+%WjsKehhd?.=Q,aOPNnpsBkbGN+FhGU;8N%[mgQ.?MD:^m]O[:qM:=,g7/
28.67 +=!M:-g;bVg\O[Y"Kg9sHY>#jDn:\%5RBSA%A%^\Ai7337!ctIUY.Lp?8N,GU=danL-Pdi>M<-,GKl[
28.68 +2,EIl?ppX#F![)5R8bU]@&pi_P`U`R[Q4@/'_"M4_`Fj1P20N952/$P7PI/Y_9%SJ+D&XkM?[3e!Cm
28.69 +/$sP3)'c+CkrQK[F@jAR2#6)<W#3:o$cLcI3C5K-B:bLI<?Z%MF`OkFNV]+kYJ>DViEg4@7uj"ZMEO
28.70 +72cn8,InjPH%T&JX]f8R)DRK)=W1=8j+PuVQ;_L,81ReT6=,c8jt::LA<beRRSjHC69A`R\HeC48_o
28.71 +8ids8BH7-=^;m%7*gRY%5H#tfPVBPF00S=o]oG,"4HQ?m[eW_Ekndu"?s5c@:uTL.eK$@J^"UtUj-=
28.72 +CfE,WiG9]!01`\P*;lo>&pdDlM=tb;6!eP[S5tTmZF[:.TKiZkZ\3:Xt4>Q`h.%sK$'^%`.#V2C:OE
28.73 +"SLfJXeXc)LDU,_.$[,[[em!lH\C"MmkdKd2``BS"l`t08O\;#4\aN)Cl<J7aB)4p!$i]_6,YQgI^u
28.74 +[Zn&\g$#q[.SP(+TlWnH:KM`Gh>n&Ao@OAjOG`HqPU$1'TfVA+E1F->TMAY#MGX8"-]21AJU=5r+DV
28.75 +.a?NA[C4B>4S8crF<h44dan*;,&XZV,$151/NQ4"./dUnIWOcu&AtnMF^WY*b^X9Y&8akV^)%5!AC'
28.76 +t?#AJ3:oFF?7Xq`9)cZX0WB]'IS]cGiK>:H,u1d,2teluH<$tp2(k;oHdIO5WMGQ's(j<%oFL=gc`i
28.77 +F:Hmc7bbW[nWKXjWQf4I>KaDV$uO4#_Sh+W`Y8BagWnM_:H7%(Tr\gAj76sr&lhoo)"g#a'u<fs3'n
28.78 +VrmSiG]bSR!o"A/Cc0)b7o@o(#02pbEr%:@iOFC9e3qp@Q2rWSA3>:jYY[=0s6$ft%qbfNO-qih#5L
28.79 +Ko+RCi2bO:8@[G8UG&qu9ua"Y%7:MG>9N&SA(`Q,'c/"j*e4IunNf27=5';Tp:2CQ8ij<9jEaX<1*^
28.80 +XgJg58INUM'33DU1W*9h9jr-(+`J`E6T!7&aK!jI&IaK5[<U==<(Tm5"kgiBD%Tci7o#1?Loe[c(#;
28.81 +gS>>XuT7Fa.f+r"H0;.WEi\BO0n6oT]0XGn8lSt4mkJrJjN@7=Ye*E:4pLlfSN`q]9J9M2`lNg;rMJ
28.82 +i=_`oQj?]nZOO!B'Gh"8PB`(432[r,%!''EKY303Hm/G,`5*TC.^Z=V6]&+1Qa'U'g,(`>:<=,UQP,
28.83 +i9.G3dN9+N9MlHZ"3@T:t,daq2WMWnD3HG3,qW4+9,!h@uJ:/aWTSY,6Nm2:":*f*eRF?%e(A5ci-N
28.84 +T'n#3p%o.En."e7tOBhJj]!aZJ%K(a?5:H4u_!b9DjHKILAUcfr>!;1/.=n6IS@g($lV!c"B&Sd)!*
28.85 +%7CNHp,:DP@mDl16g2WYU.#Q9/r0"WBZ2/C<,BM#e[55$XWaNP%[%KO9YDMt&uARSTi0Iac<dR+6<)
28.86 +7%P\P$@BVVPQ-^('#@Y[b:NBqtG*:d'4Slb2Fr2EHmUDoYm<XL]]Lc%p+Za4^QlNpt"6o(8g7UBS?"
28.87 +_oR\NGMWt,0:71Bs)$1[PdiKeAsdnYD;CrV5ist>J'<p&bL]W]*MPRYf%iQ\iEH^a^Yjdd?!ue)cp5
28.88 +`.qs:hZW8],=Oqm]D!F-U"`DK9Bp/W=ZEgnJ-I,ejGs-qeffOc7p*$./&qBtI3qggX+o#$2LM8.ZK8
28.89 +g9F:]P[#AWO:kXtc#XZ6[3d4Va_Uk8p;a$H/=XK]uUK8Wn187a9+K#-Qi+PR&H6NT@[:H16L]^^Y,f
28.90 +64T\PH*(b-!!PA204EBI)XF[WDk6MiBafrdGHVL-WBOQf>p^'/Z73QhAMi$WNX&D&EH#)77Ng2sQ?u
28.91 +;@K-aboQ749<T^!Ob-pJ3O.A%F#7$^Ht72=sDT8$!;'uV]I,@rePj+GK;L3T0o!B2,TCeH"0<^n4M-
28.92 +R5EQ`[&OEj#Y-*Pt2N.LIg!(b/l=bjq9Rf,H.`cAc"At9Gr9,i<kQiRDGAU*Jec_50:dDo<<mY3:i*
28.93 +8[Z;!8kG2]-1H?FA=sbEO+oX*6=u@*VcU5;]]nKV_L5"XJbakX97.40BB:=@-l1g!O6T(a'Ubb:$4Y
28.94 +NJLOKEW9dou'SDlttC]%;9"?L.!.XTDNOV'+Ak\?04X71O]lj(.%^I:?c/G/cIdeh:L\$\;b(:E`5L
28.95 +;NVQJ['lC3b:+5V]F5ED6RLZl].\.Xh8:Ks<,3as7W4AE:V2Z'GUB-99uVAL0f0[A2gMKn&hV?%ine
28.96 +D-B,l\6im`?$E@3)B[s;r1N_#02'?[U?TFq=2`S<X9,=POa5LeeJaJkQcr.NgfmJK<[M,'H@N&"fC(
28.97 +gm)O/N2cR72TlSb%<qp't9BWQ!SWhKk[S%,<Tf$F>%^RSp?@*W3-Mu9ngpPX2Q)%h-7O"%8;nNjO(&
28.98 +PktCf%:<sjE]sG0@mbce]O)jZ:e$kDM~>
28.99 +%%EndData
28.100 +end restore showpage
28.101 +%%Trailer
28.102 +%%EOF
29.1 Binary file img/dijkstraExT.png has changed
