1.1 --- a/comp.log Mon Jan 10 00:16:59 2011 +0100
1.2 +++ b/comp.log Thu Jan 20 00:56:20 2011 +0100
1.3 @@ -1,8 +1,8 @@
1.4 This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8)
1.5 entering extended mode
1.6
1.7 -("M:/Documents/004_Uni Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/exzer
1.8 -pt.tex"
1.9 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
1.10 +thms_theory/exzerpt.tex
1.11 LaTeX2e <2009/09/24>
1.12 Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, ge
1.13 rman, ngerman, german-x-2009-06-19, ngerman-x-2009-06-19, french, loaded.
1.14 @@ -106,305 +106,21 @@
1.15 ("C:\Program Files\MikTex\tex\latex\oberdiek\bookmark.sty"
1.16 ("C:\Program Files\MikTex\tex\latex\oberdiek\auxhook.sty")
1.17 ("C:\Program Files\MikTex\tex\latex\oberdiek\bkm-dvips.def"))
1.18 -No file exzerpt.aux.
1.19 -("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
1.20 -("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty")
1.21 -("C:\Program Files\MikTex\tex\generic\oberdiek\gettitlestring.sty"))
1.22 -
1.23 -Package hyperref Warning: Rerun to get /PageLabels entry.
1.24 -
1.25 -("C:\Program Files\MikTex\tex\latex\amsfonts\umsa.fd")
1.26 -("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd")
1.27 -
1.28 -LaTeX Warning: Citation `1' on page 1 undefined on input line 58.
1.29 -
1.30 -
1.31 -LaTeX Warning: Citation `2' on page 1 undefined on input line 58.
1.32 -
1.33 -No file exzerpt.bbl.
1.34 -[1] AED: lastpage setting LastPage
1.35 -[2] (C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.aux)
1.36 -
1.37 -LaTeX Warning: There were undefined references.
1.38 -
1.39 -
1.40 -LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
1.41 -
1.42 - )
1.43 -Output written on exzerpt.dvi (2 pages, 11188 bytes).
1.44 -Transcript written on exzerpt.log.
1.45 -This is BibTeX, Version 0.99c (MiKTeX 2.8)
1.46 -The top-level auxiliary file: exzerpt.aux
1.47 -The style file: alphadin.bst
1.48 -Database file #1: literatur.bib
1.49 -I was expecting a `,' or a `}'---line 12 of file literatur.bib
1.50 - :
1.51 - : YEAR="2000"
1.52 -(Error may have been on previous line)
1.53 -I'm skipping whatever remains of this entry
1.54 -Warning--neither address nor publication date in 2
1.55 -(There was 1 error message)
1.56 -This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8)
1.57 -entering extended mode
1.58 -
1.59 -("M:/Documents/004_Uni Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/exzer
1.60 -pt.tex"
1.61 -LaTeX2e <2009/09/24>
1.62 -Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, ge
1.63 -rman, ngerman, german-x-2009-06-19, ngerman-x-2009-06-19, french, loaded.
1.64 -("C:\Program Files\MikTex\tex\latex\base\article.cls"
1.65 -Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
1.66 -("C:\Program Files\MikTex\tex\latex\base\size11.clo"))
1.67 -("C:\Program Files\MikTex\tex\generic\babel\babel.sty"
1.68 -*************************************
1.69 -* Local config file bblopts.cfg used
1.70 -*
1.71 -("C:\Program Files\MikTex\tex\latex\00miktex\bblopts.cfg")
1.72 -("C:\Program Files\MikTex\tex\generic\babel\ngermanb.ldf"
1.73 -("C:\Program Files\MikTex\tex\generic\babel\babel.def")))
1.74 -("C:\Program Files\MikTex\tex\latex\base\fontenc.sty"
1.75 -("C:\Program Files\MikTex\tex\latex\base\t1enc.def"))
1.76 -("C:\Program Files\MikTex\tex\latex\base\inputenc.sty"
1.77 -("C:\Program Files\MikTex\tex\latex\base\latin1.def"))
1.78 -("C:\Program Files\MikTex\tex\latex\hyperref\hyperref.sty"
1.79 -("C:\Program Files\MikTex\tex\generic\oberdiek\ltxcmds.sty")
1.80 -("C:\Program Files\MikTex\tex\generic\oberdiek\infwarerr.sty")
1.81 -("C:\Program Files\MikTex\tex\latex\graphics\keyval.sty")
1.82 -("C:\Program Files\MikTex\tex\generic\oberdiek\kvsetkeys.sty"
1.83 -("C:\Program Files\MikTex\tex\generic\oberdiek\etexcmds.sty"))
1.84 -("C:\Program Files\MikTex\tex\generic\oberdiek\pdfescape.sty"
1.85 -("C:\Program Files\MikTex\tex\generic\oberdiek\pdftexcmds.sty"
1.86 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifluatex.sty")))
1.87 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifpdf.sty")
1.88 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifvtex.sty")
1.89 -("C:\Program Files\MikTex\tex\generic\ifxetex\ifxetex.sty")
1.90 -("C:\Program Files\MikTex\tex\latex\oberdiek\hycolor.sty"
1.91 -("C:\Program Files\MikTex\tex\latex\oberdiek\xcolor-patch.sty"))
1.92 -("C:\Program Files\MikTex\tex\latex\oberdiek\letltxmacro.sty")
1.93 -("C:\Program Files\MikTex\tex\latex\oberdiek\kvoptions.sty")
1.94 -("C:\Program Files\MikTex\tex\latex\hyperref\pd1enc.def")
1.95 -("C:\Program Files\MikTex\tex\generic\oberdiek\intcalc.sty")
1.96 -("C:\Program Files\MikTex\tex\latex\00miktex\hyperref.cfg")
1.97 -("C:\Program Files\MikTex\tex\latex\ltxmisc\url.sty")
1.98 -("C:\Program Files\MikTex\tex\generic\oberdiek\bitset.sty"
1.99 -("C:\Program Files\MikTex\tex\generic\oberdiek\bigintcalc.sty"))
1.100 -("C:\Program Files\MikTex\tex\generic\oberdiek\atbegshi.sty"))
1.101 -
1.102 -Package hyperref Message: Driver (default): hdvips.
1.103 -
1.104 -("C:\Program Files\MikTex\tex\latex\hyperref\hdvips.def"
1.105 -("C:\Program Files\MikTex\tex\latex\hyperref\pdfmark.def"
1.106 -("C:\Program Files\MikTex\tex\latex\oberdiek\rerunfilecheck.sty"
1.107 -("C:\Program Files\MikTex\tex\latex\oberdiek\atveryend.sty")
1.108 -("C:\Program Files\MikTex\tex\generic\oberdiek\uniquecounter.sty"))))
1.109 -("C:\Program Files\MikTex\tex\latex\vaucanson-g\vaucanson-g.sty"
1.110 -("C:\Program Files\MikTex\tex\latex\base\ifthen.sty")
1.111 -("C:\Program Files\MikTex\tex\latex\xcolor\xcolor.sty"
1.112 -("C:\Program Files\MikTex\tex\latex\00miktex\color.cfg")
1.113 -("C:\Program Files\MikTex\tex\latex\graphics\dvips.def"))
1.114 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCColor-names.def")
1.115 -("C:\Program Files\MikTex\tex\latex\pstricks\pstricks.sty"
1.116 -("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.tex"
1.117 -("C:\Program Files\MikTex\tex\generic\xkeyval\pst-xkey.tex"
1.118 -("C:\Program Files\MikTex\tex\latex\xkeyval\xkeyval.sty"
1.119 -("C:\Program Files\MikTex\tex\generic\xkeyval\xkeyval.tex")))
1.120 -("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"
1.121 -`pst-fp' v0.05, 2010/01/17 (hv))
1.122 -`PSTricks' v2.12 <2010/09/16> (tvz)
1.123 -("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.con"))
1.124 -("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"))
1.125 -("C:\Program Files\MikTex\tex\latex\pst-node\pst-node.sty"
1.126 -("C:\Program Files\MikTex\tex\generic\pst-node\pst-node.tex"
1.127 - v1.13, 2010/06/06)) ("C:\Program Files\MikTex\tex\latex\pst-plot\pst-plot.sty"
1.128 -("C:\Program Files\MikTex\tex\generic\pst-plot\pst-plot.tex"
1.129 -("C:\Program Files\MikTex\tex\generic\multido\multido.tex"
1.130 - v1.42, 2010/05/14 <tvz>) v1.21, 2010/09/28 (tvz,hv)))
1.131 -("C:\Program Files\MikTex\tex\latex\pst-coil\pst-coil.sty"
1.132 -("C:\Program Files\MikTex\tex\generic\pst-coil\pst-coil.tex"
1.133 - v1.21, 2010/09/28)) ("C:\Program Files\MikTex\tex\latex\multido\multido.sty")
1.134 -("C:\Program Files\MikTex\tex\latex\pst-3d\pst-3d.sty"
1.135 -("C:\Program Files\MikTex\tex\generic\pst-3d\pst-3d.tex"
1.136 -`PST-3d' v1.11, 2010/02/14 (tvz)))
1.137 -("C:\Program Files\MikTex\tex\latex\tools\calc.sty")
1.138 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\Vaucanson-G.tex")
1.139 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCPref-default.tex"))
1.140 -("C:\Program Files\MikTex\tex\latex\oberdiek\hypcap.sty")
1.141 -("C:\Program Files\MikTex\tex\latex\fancyhdr\fancyhdr.sty")
1.142 -("C:\Program Files\MikTex\tex\latex\graphics\graphicx.sty"
1.143 -("C:\Program Files\MikTex\tex\latex\graphics\graphics.sty"
1.144 -("C:\Program Files\MikTex\tex\latex\graphics\trig.sty")
1.145 -("C:\Program Files\MikTex\tex\latex\00miktex\graphics.cfg")))
1.146 -("C:\Program Files\MikTex\tex\latex\lastpage\lastpage.sty")
1.147 -("C:\Program Files\MikTex\tex\latex\preprint\fullpage.sty")
1.148 -("C:\Program Files\MikTex\tex\latex\ams\classes\amsthm.sty")
1.149 -("C:\Program Files\MikTex\tex\latex\ams\math\amsmath.sty"
1.150 -For additional information on amsmath, use the `?' option.
1.151 -("C:\Program Files\MikTex\tex\latex\ams\math\amstext.sty"
1.152 -("C:\Program Files\MikTex\tex\latex\ams\math\amsgen.sty"))
1.153 -("C:\Program Files\MikTex\tex\latex\ams\math\amsbsy.sty")
1.154 -("C:\Program Files\MikTex\tex\latex\ams\math\amsopn.sty"))
1.155 -("C:\Program Files\MikTex\tex\latex\amsfonts\amsfonts.sty")
1.156 -("C:\Program Files\MikTex\tex\latex\float\float.sty")
1.157 -("C:\Program Files\MikTex\tex\latex\paralist\paralist.sty")
1.158 -("C:\Program Files\MikTex\tex\latex\listings\listings.sty"
1.159 -("C:\Program Files\MikTex\tex\latex\listings\lstmisc.sty")
1.160 -("C:\Program Files\MikTex\tex\latex\listings\listings.cfg"))
1.161 -("C:\Program Files\MikTex\tex\latex\oberdiek\bookmark.sty"
1.162 -("C:\Program Files\MikTex\tex\latex\oberdiek\auxhook.sty")
1.163 -("C:\Program Files\MikTex\tex\latex\oberdiek\bkm-dvips.def"))
1.164 -(C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.aux)
1.165 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
1.166 +thms_theory\exzerpt.aux)
1.167 ("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
1.168 ("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty")
1.169 ("C:\Program Files\MikTex\tex\generic\oberdiek\gettitlestring.sty"))
1.170 ("C:\Program Files\MikTex\tex\latex\amsfonts\umsa.fd")
1.171 ("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd")
1.172 -(C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.toc)
1.173 -
1.174 -LaTeX Warning: Citation `1' on page 1 undefined on input line 58.
1.175 -
1.176 -
1.177 -LaTeX Warning: Citation `2' on page 1 undefined on input line 58.
1.178 -
1.179 -(C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.bbl [1]) [2]
1.180 -AED: lastpage setting LastPage
1.181 -[3] (C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.aux)
1.182 -
1.183 -LaTeX Warning: There were undefined references.
1.184 -
1.185 -
1.186 -LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
1.187 -
1.188 - )
1.189 -Output written on exzerpt.dvi (3 pages, 19016 bytes).
1.190 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
1.191 +thms_theory\exzerpt.toc) [1] ("C:\Program Files\MikTex\tex\latex\base\t1cmtt.fd
1.192 +")
1.193 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
1.194 +thms_theory\exzerpt.bbl) [2] [3] <img/cl_pair.eps> [4] [5] [6] [7] [8] [9]
1.195 +[10] [11] <img/landau_sym.eps> AED: lastpage setting LastPage
1.196 +[12]
1.197 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
1.198 +thms_theory\exzerpt.aux) )
1.199 +Output written on exzerpt.dvi (12 pages, 67136 bytes).
1.200 Transcript written on exzerpt.log.
1.201 -This is BibTeX, Version 0.99c (MiKTeX 2.8)
1.202 -The top-level auxiliary file: exzerpt.aux
1.203 -The style file: alphadin.bst
1.204 -Database file #1: literatur.bib
1.205 -I was expecting a `,' or a `}'---line 12 of file literatur.bib
1.206 - :
1.207 - : YEAR="2000"
1.208 -(Error may have been on previous line)
1.209 -I'm skipping whatever remains of this entry
1.210 -Warning--neither address nor publication date in 2
1.211 -(There was 1 error message)
1.212 -This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8)
1.213 -entering extended mode
1.214 -
1.215 -("M:/Documents/004_Uni Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/exzer
1.216 -pt.tex"
1.217 -LaTeX2e <2009/09/24>
1.218 -Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, ge
1.219 -rman, ngerman, german-x-2009-06-19, ngerman-x-2009-06-19, french, loaded.
1.220 -("C:\Program Files\MikTex\tex\latex\base\article.cls"
1.221 -Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
1.222 -("C:\Program Files\MikTex\tex\latex\base\size11.clo"))
1.223 -("C:\Program Files\MikTex\tex\generic\babel\babel.sty"
1.224 -*************************************
1.225 -* Local config file bblopts.cfg used
1.226 -*
1.227 -("C:\Program Files\MikTex\tex\latex\00miktex\bblopts.cfg")
1.228 -("C:\Program Files\MikTex\tex\generic\babel\ngermanb.ldf"
1.229 -("C:\Program Files\MikTex\tex\generic\babel\babel.def")))
1.230 -("C:\Program Files\MikTex\tex\latex\base\fontenc.sty"
1.231 -("C:\Program Files\MikTex\tex\latex\base\t1enc.def"))
1.232 -("C:\Program Files\MikTex\tex\latex\base\inputenc.sty"
1.233 -("C:\Program Files\MikTex\tex\latex\base\latin1.def"))
1.234 -("C:\Program Files\MikTex\tex\latex\hyperref\hyperref.sty"
1.235 -("C:\Program Files\MikTex\tex\generic\oberdiek\ltxcmds.sty")
1.236 -("C:\Program Files\MikTex\tex\generic\oberdiek\infwarerr.sty")
1.237 -("C:\Program Files\MikTex\tex\latex\graphics\keyval.sty")
1.238 -("C:\Program Files\MikTex\tex\generic\oberdiek\kvsetkeys.sty"
1.239 -("C:\Program Files\MikTex\tex\generic\oberdiek\etexcmds.sty"))
1.240 -("C:\Program Files\MikTex\tex\generic\oberdiek\pdfescape.sty"
1.241 -("C:\Program Files\MikTex\tex\generic\oberdiek\pdftexcmds.sty"
1.242 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifluatex.sty")))
1.243 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifpdf.sty")
1.244 -("C:\Program Files\MikTex\tex\generic\oberdiek\ifvtex.sty")
1.245 -("C:\Program Files\MikTex\tex\generic\ifxetex\ifxetex.sty")
1.246 -("C:\Program Files\MikTex\tex\latex\oberdiek\hycolor.sty"
1.247 -("C:\Program Files\MikTex\tex\latex\oberdiek\xcolor-patch.sty"))
1.248 -("C:\Program Files\MikTex\tex\latex\oberdiek\letltxmacro.sty")
1.249 -("C:\Program Files\MikTex\tex\latex\oberdiek\kvoptions.sty")
1.250 -("C:\Program Files\MikTex\tex\latex\hyperref\pd1enc.def")
1.251 -("C:\Program Files\MikTex\tex\generic\oberdiek\intcalc.sty")
1.252 -("C:\Program Files\MikTex\tex\latex\00miktex\hyperref.cfg")
1.253 -("C:\Program Files\MikTex\tex\latex\ltxmisc\url.sty")
1.254 -("C:\Program Files\MikTex\tex\generic\oberdiek\bitset.sty"
1.255 -("C:\Program Files\MikTex\tex\generic\oberdiek\bigintcalc.sty"))
1.256 -("C:\Program Files\MikTex\tex\generic\oberdiek\atbegshi.sty"))
1.257 -
1.258 -Package hyperref Message: Driver (default): hdvips.
1.259 -
1.260 -("C:\Program Files\MikTex\tex\latex\hyperref\hdvips.def"
1.261 -("C:\Program Files\MikTex\tex\latex\hyperref\pdfmark.def"
1.262 -("C:\Program Files\MikTex\tex\latex\oberdiek\rerunfilecheck.sty"
1.263 -("C:\Program Files\MikTex\tex\latex\oberdiek\atveryend.sty")
1.264 -("C:\Program Files\MikTex\tex\generic\oberdiek\uniquecounter.sty"))))
1.265 -("C:\Program Files\MikTex\tex\latex\vaucanson-g\vaucanson-g.sty"
1.266 -("C:\Program Files\MikTex\tex\latex\base\ifthen.sty")
1.267 -("C:\Program Files\MikTex\tex\latex\xcolor\xcolor.sty"
1.268 -("C:\Program Files\MikTex\tex\latex\00miktex\color.cfg")
1.269 -("C:\Program Files\MikTex\tex\latex\graphics\dvips.def"))
1.270 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCColor-names.def")
1.271 -("C:\Program Files\MikTex\tex\latex\pstricks\pstricks.sty"
1.272 -("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.tex"
1.273 -("C:\Program Files\MikTex\tex\generic\xkeyval\pst-xkey.tex"
1.274 -("C:\Program Files\MikTex\tex\latex\xkeyval\xkeyval.sty"
1.275 -("C:\Program Files\MikTex\tex\generic\xkeyval\xkeyval.tex")))
1.276 -("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"
1.277 -`pst-fp' v0.05, 2010/01/17 (hv))
1.278 -`PSTricks' v2.12 <2010/09/16> (tvz)
1.279 -("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.con"))
1.280 -("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"))
1.281 -("C:\Program Files\MikTex\tex\latex\pst-node\pst-node.sty"
1.282 -("C:\Program Files\MikTex\tex\generic\pst-node\pst-node.tex"
1.283 - v1.13, 2010/06/06)) ("C:\Program Files\MikTex\tex\latex\pst-plot\pst-plot.sty"
1.284 -("C:\Program Files\MikTex\tex\generic\pst-plot\pst-plot.tex"
1.285 -("C:\Program Files\MikTex\tex\generic\multido\multido.tex"
1.286 - v1.42, 2010/05/14 <tvz>) v1.21, 2010/09/28 (tvz,hv)))
1.287 -("C:\Program Files\MikTex\tex\latex\pst-coil\pst-coil.sty"
1.288 -("C:\Program Files\MikTex\tex\generic\pst-coil\pst-coil.tex"
1.289 - v1.21, 2010/09/28)) ("C:\Program Files\MikTex\tex\latex\multido\multido.sty")
1.290 -("C:\Program Files\MikTex\tex\latex\pst-3d\pst-3d.sty"
1.291 -("C:\Program Files\MikTex\tex\generic\pst-3d\pst-3d.tex"
1.292 -`PST-3d' v1.11, 2010/02/14 (tvz)))
1.293 -("C:\Program Files\MikTex\tex\latex\tools\calc.sty")
1.294 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\Vaucanson-G.tex")
1.295 -("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCPref-default.tex"))
1.296 -("C:\Program Files\MikTex\tex\latex\oberdiek\hypcap.sty")
1.297 -("C:\Program Files\MikTex\tex\latex\fancyhdr\fancyhdr.sty")
1.298 -("C:\Program Files\MikTex\tex\latex\graphics\graphicx.sty"
1.299 -("C:\Program Files\MikTex\tex\latex\graphics\graphics.sty"
1.300 -("C:\Program Files\MikTex\tex\latex\graphics\trig.sty")
1.301 -("C:\Program Files\MikTex\tex\latex\00miktex\graphics.cfg")))
1.302 -("C:\Program Files\MikTex\tex\latex\lastpage\lastpage.sty")
1.303 -("C:\Program Files\MikTex\tex\latex\preprint\fullpage.sty")
1.304 -("C:\Program Files\MikTex\tex\latex\ams\classes\amsthm.sty")
1.305 -("C:\Program Files\MikTex\tex\latex\ams\math\amsmath.sty"
1.306 -For additional information on amsmath, use the `?' option.
1.307 -("C:\Program Files\MikTex\tex\latex\ams\math\amstext.sty"
1.308 -("C:\Program Files\MikTex\tex\latex\ams\math\amsgen.sty"))
1.309 -("C:\Program Files\MikTex\tex\latex\ams\math\amsbsy.sty")
1.310 -("C:\Program Files\MikTex\tex\latex\ams\math\amsopn.sty"))
1.311 -("C:\Program Files\MikTex\tex\latex\amsfonts\amsfonts.sty")
1.312 -("C:\Program Files\MikTex\tex\latex\float\float.sty")
1.313 -("C:\Program Files\MikTex\tex\latex\paralist\paralist.sty")
1.314 -("C:\Program Files\MikTex\tex\latex\listings\listings.sty"
1.315 -("C:\Program Files\MikTex\tex\latex\listings\lstmisc.sty")
1.316 -("C:\Program Files\MikTex\tex\latex\listings\listings.cfg"))
1.317 -("C:\Program Files\MikTex\tex\latex\oberdiek\bookmark.sty"
1.318 -("C:\Program Files\MikTex\tex\latex\oberdiek\auxhook.sty")
1.319 -("C:\Program Files\MikTex\tex\latex\oberdiek\bkm-dvips.def"))
1.320 -(C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.aux)
1.321 -("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
1.322 -("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty")
1.323 -("C:\Program Files\MikTex\tex\generic\oberdiek\gettitlestring.sty"))
1.324 -("C:\Program Files\MikTex\tex\latex\amsfonts\umsa.fd")
1.325 -("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd")
1.326 -(C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.toc)
1.327 -(C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.bbl [1]) [2]
1.328 -AED: lastpage setting LastPage
1.329 -[3] (C:\Users\Markus\AppData\Local\Temp\mik5894\_src\exzerpt.aux) )
1.330 -Output written on exzerpt.dvi (3 pages, 19520 bytes).
1.331 -Transcript written on exzerpt.log.
2.1 --- a/exzerpt.aux Mon Jan 10 00:16:59 2011 +0100
2.2 +++ b/exzerpt.aux Thu Jan 20 00:56:20 2011 +0100
2.3 @@ -29,8 +29,7 @@
2.4 \bibdata{literatur}
2.5 \bibcite{2}{PW02}
2.6 \bibcite{1}{THC01}
2.7 -\citation{1}
2.8 -\citation{2}
2.9 +\citation{*}
2.10 \@writefile{toc}{\contentsline {section}{\numberline {1}Einleitung}{2}{section.1}}
2.11 \newlabel{sec:intro}{{1}{2}{Einleitung\relax }{section.1}{}}
2.12 \@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Themen:}{2}{subsection.1.1}}
2.13 @@ -57,10 +56,10 @@
2.14 \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.2}Analyse}{4}{subsubsection.2.3.2}}
2.15 \@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Segmentschnitt}{4}{subsection.2.4}}
2.16 \BKM@entry{id=14,dest={73756273756273656374696F6E2E322E342E32}}{416E616C797365}
2.17 -\BKM@entry{id=15,dest={73756273656374696F6E2E322E35}}{4661737420466F75726965722D5472616E73666F726D6174696F6E}
2.18 +\BKM@entry{id=15,dest={73756273656374696F6E2E322E35}}{506F6C796E6F6D70726F64756B7420756E64204661737420466F75726965722D5472616E73666F726D6174696F6E}
2.19 \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{5}{subsubsection.2.4.1}}
2.20 \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.2}Analyse}{5}{subsubsection.2.4.2}}
2.21 -\@writefile{toc}{\contentsline {subsection}{\numberline {2.5}Fast Fourier-Transformation}{5}{subsection.2.5}}
2.22 +\@writefile{toc}{\contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation}{5}{subsection.2.5}}
2.23 \BKM@entry{id=16,dest={73656374696F6E2E33}}{52616E646F6D6973696572756E67}
2.24 \BKM@entry{id=17,dest={73756273656374696F6E2E332E31}}{48617368696E67}
2.25 \@writefile{toc}{\contentsline {section}{\numberline {3}Randomisierung}{6}{section.3}}
2.26 @@ -74,11 +73,29 @@
2.27 \@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Fibonacci Heaps}{7}{subsection.4.2}}
2.28 \@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Union Find}{7}{subsection.4.3}}
2.29 \BKM@entry{id=22,dest={73656374696F6E2E35}}{477265656479}
2.30 +\BKM@entry{id=23,dest={73756273656374696F6E2E352E31}}{4B5C333734727A65737465205C2862696C6C69677374655C292057656765}
2.31 \@writefile{toc}{\contentsline {section}{\numberline {5}Greedy}{8}{section.5}}
2.32 -\BKM@entry{id=23,dest={73656374696F6E2E36}}{416E68616E67}
2.33 -\BKM@entry{id=24,dest={73756273656374696F6E2E362E31}}{4C616E6461752D53796D626F6C65}
2.34 -\@writefile{toc}{\contentsline {section}{\numberline {6}Anhang}{9}{section.6}}
2.35 -\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Landau-Symbole}{9}{subsection.6.1}}
2.36 -\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Definition der Landau Symbole}}{9}{figure.2}}
2.37 -\newlabel{fig:landau_sym}{{2}{9}{Definition der Landau Symbole\relax }{figure.2}{}}
2.38 -\newlabel{LastPage}{{}{9}{}{page.9}{}}
2.39 +\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}K\"urzeste (billigste) Wege}{8}{subsection.5.1}}
2.40 +\BKM@entry{id=24,dest={73656374696F6E2E36}}{42696E205061636B696E67}
2.41 +\BKM@entry{id=25,dest={73756273656374696F6E2E362E31}}{4F6E6C696E652056657266616872656E}
2.42 +\BKM@entry{id=26,dest={73756273756273656374696F6E2E362E312E31}}{4E65787420466974205C284E465C29}
2.43 +\BKM@entry{id=27,dest={73756273756273656374696F6E2E362E312E32}}{46697273742D466974205C2846465C29}
2.44 +\@writefile{toc}{\contentsline {section}{\numberline {6}Bin Packing}{9}{section.6}}
2.45 +\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Online Verfahren}{9}{subsection.6.1}}
2.46 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.1}Next Fit (NF)}{9}{subsubsection.6.1.1}}
2.47 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.2}First-Fit (FF)}{9}{subsubsection.6.1.2}}
2.48 +\BKM@entry{id=28,dest={73756273756273656374696F6E2E362E312E33}}{426573742D466974205C2842465C29}
2.49 +\BKM@entry{id=29,dest={73756273656374696F6E2E362E32}}{4F66666C696E652056657266616872656E}
2.50 +\BKM@entry{id=30,dest={73756273756273656374696F6E2E362E322E31}}{4669727374204669742044656372656173696E67205C28464644206F6465722046464E495C29}
2.51 +\BKM@entry{id=31,dest={73756273756273656374696F6E2E362E322E32}}{42657374204669742044656372656173696E67205C284246445C29}
2.52 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.1.3}Best-Fit (BF)}{10}{subsubsection.6.1.3}}
2.53 +\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Offline Verfahren}{10}{subsection.6.2}}
2.54 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.1}First Fit Decreasing (FFD oder FFNI)}{10}{subsubsection.6.2.1}}
2.55 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.2.2}Best Fit Decreasing (BFD)}{10}{subsubsection.6.2.2}}
2.56 +\BKM@entry{id=32,dest={73656374696F6E2E37}}{44796E616D69736368652050726F6772616D6D696572756E67}
2.57 +\@writefile{toc}{\contentsline {section}{\numberline {7}Dynamische Programmierung}{11}{section.7}}
2.58 +\BKM@entry{id=33,dest={617070656E6469782E41}}{4C616E6461752D53796D626F6C65}
2.59 +\@writefile{toc}{\contentsline {section}{\numberline {A}Landau-Symbole}{12}{appendix.A}}
2.60 +\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Definition der Landau Symbole}}{12}{figure.2}}
2.61 +\newlabel{fig:landau_sym}{{2}{12}{Definition der Landau Symbole\relax }{figure.2}{}}
2.62 +\newlabel{LastPage}{{}{12}{}{page.12}{}}
3.1 Binary file exzerpt.dvi has changed
4.1 --- a/exzerpt.log Mon Jan 10 00:16:59 2011 +0100
4.2 +++ b/exzerpt.log Thu Jan 20 00:56:20 2011 +0100
4.3 @@ -1,9 +1,10 @@
4.4 -This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8) (preloaded format=latex 2010.11.26) 9 JAN 2011 11:52
4.5 +This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8) (preloaded format=latex 2011.1.19) 20 JAN 2011 00:54
4.6 entering extended mode
4.7 -**exzerpt.tex
4.8 +**M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algor
4.9 +ithms_theory/exzerpt.tex
4.10
4.11 -("M:\Documents\004_Uni Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\exzer
4.12 -pt.tex"
4.13 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
4.14 +thms_theory/exzerpt.tex
4.15 LaTeX2e <2009/09/24>
4.16 Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, ge
4.17 rman, ngerman, german-x-2009-06-19, ngerman-x-2009-06-19, french, loaded.
4.18 @@ -603,8 +604,8 @@
4.19 File: bkm-dvips.def 2010/04/08 v1.12 bookmark driver for dvips (HO)
4.20 \BKM@id=\count156
4.21 ))
4.22 -("M:\Documents\004_Uni Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\exzer
4.23 -pt.aux")
4.24 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
4.25 +thms_theory\exzerpt.aux)
4.26 LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 29.
4.27 LaTeX Font Info: ... okay on input line 29.
4.28 LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 29.
4.29 @@ -621,7 +622,8 @@
4.30 LaTeX Font Info: ... okay on input line 29.
4.31 \AtBeginShipoutBox=\box36
4.32 Package hyperref Info: Link coloring ON on input line 29.
4.33 - ("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
4.34 +
4.35 +("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
4.36 Package: nameref 2010/04/30 v2.40 Cross-referencing by name of section
4.37
4.38 ("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty"
4.39 @@ -653,39 +655,39 @@
4.40 ("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd"
4.41 File: umsb.fd 2009/06/22 v3.00 AMS symbols B
4.42 )
4.43 -("M:\Documents\004_Uni Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\exzer
4.44 -pt.toc")
4.45 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
4.46 +thms_theory\exzerpt.toc)
4.47 \tf@toc=\write3
4.48 [1
4.49
4.50 ]
4.51 -("M:\Documents\004_Uni Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\exzer
4.52 -pt.bbl") [2] [3]
4.53 +LaTeX Font Info: Try loading font information for T1+cmtt on input line 37.
4.54 + ("C:\Program Files\MikTex\tex\latex\base\t1cmtt.fd"
4.55 +File: t1cmtt.fd 1999/05/25 v2.5h Standard LaTeX font definitions
4.56 +)
4.57 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
4.58 +thms_theory\exzerpt.bbl) [2] [3]
4.59 File: img/cl_pair.eps Graphic file (type eps)
4.60 - <img/cl_pair.eps> [4] [5] [6] [7] [8]
4.61 + <img/cl_pair.eps> [4] [5] [6] [7] [8] [9]
4.62 +[10] [11]
4.63 File: img/landau_sym.eps Graphic file (type eps)
4.64 - <img/landau_sym.eps>
4.65 -AED: lastpage setting LastPage
4.66 -[9]
4.67 -Package atveryend Info: Empty hook `BeforeClearDocument' on input line 193.
4.68 -Package atveryend Info: Executing hook `AfterLastShipout' on input line 193.
4.69 + <img/landau_sym.eps> AED: lastpage setting LastPage
4.70 +[12]
4.71 +Package atveryend Info: Empty hook `BeforeClearDocument' on input line 250.
4.72 +Package atveryend Info: Executing hook `AfterLastShipout' on input line 250.
4.73 \BKM@file=\write4
4.74
4.75 -("M:\Documents\004_Uni Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\exzer
4.76 -pt.aux")
4.77 -Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 193.
4.78 -
4.79 -
4.80 -LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
4.81 -
4.82 +(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
4.83 +thms_theory\exzerpt.aux)
4.84 +Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 250.
4.85 )
4.86 Here is how much of TeX's memory you used:
4.87 - 11506 strings out of 495270
4.88 - 163673 string characters out of 3180476
4.89 - 301233 words of memory out of 3000000
4.90 - 14473 multiletter control sequences out of 15000+200000
4.91 - 19411 words of font info for 54 fonts, out of 3000000 for 9000
4.92 + 11535 strings out of 495270
4.93 + 164528 string characters out of 3180477
4.94 + 305233 words of memory out of 3000000
4.95 + 14498 multiletter control sequences out of 15000+200000
4.96 + 19725 words of font info for 55 fonts, out of 3000000 for 9000
4.97 14 hyphenation exceptions out of 8191
4.98 - 44i,9n,53p,590b,398s stack positions out of 5000i,500n,10000p,200000b,50000s
4.99 + 44i,9n,53p,1340b,398s stack positions out of 5000i,500n,10000p,200000b,50000s
4.100
4.101 -Output written on exzerpt.dvi (9 pages, 45076 bytes).
4.102 +Output written on exzerpt.dvi (12 pages, 67136 bytes).
5.1 --- a/exzerpt.out.ps Mon Jan 10 00:16:59 2011 +0100
5.2 +++ b/exzerpt.out.ps Thu Jan 20 00:56:20 2011 +0100
5.3 @@ -64,7 +64,7 @@
5.4 /Action/GoTo/Dest(subsubsection.2.4.2)cvn
5.5 /OUT pdfmark
5.6 [
5.7 -/Title(Fast Fourier-Transformation)
5.8 +/Title(Polynomprodukt und Fast Fourier-Transformation)
5.9 /Action/GoTo/Dest(subsection.2.5)cvn
5.10 /OUT pdfmark
5.11 [
5.12 @@ -95,14 +95,53 @@
5.13 /OUT pdfmark
5.14 [
5.15 /Title(Greedy)
5.16 +/Count -1
5.17 /Action/GoTo/Dest(section.5)cvn
5.18 /OUT pdfmark
5.19 [
5.20 -/Title(Anhang)
5.21 -/Count -1
5.22 +/Title(K\374rzeste \(billigste\) Wege)
5.23 +/Action/GoTo/Dest(subsection.5.1)cvn
5.24 +/OUT pdfmark
5.25 +[
5.26 +/Title(Bin Packing)
5.27 +/Count -2
5.28 /Action/GoTo/Dest(section.6)cvn
5.29 /OUT pdfmark
5.30 [
5.31 -/Title(Landau-Symbole)
5.32 +/Title(Online Verfahren)
5.33 +/Count -3
5.34 /Action/GoTo/Dest(subsection.6.1)cvn
5.35 /OUT pdfmark
5.36 +[
5.37 +/Title(Next Fit \(NF\))
5.38 +/Action/GoTo/Dest(subsubsection.6.1.1)cvn
5.39 +/OUT pdfmark
5.40 +[
5.41 +/Title(First-Fit \(FF\))
5.42 +/Action/GoTo/Dest(subsubsection.6.1.2)cvn
5.43 +/OUT pdfmark
5.44 +[
5.45 +/Title(Best-Fit \(BF\))
5.46 +/Action/GoTo/Dest(subsubsection.6.1.3)cvn
5.47 +/OUT pdfmark
5.48 +[
5.49 +/Title(Offline Verfahren)
5.50 +/Count -2
5.51 +/Action/GoTo/Dest(subsection.6.2)cvn
5.52 +/OUT pdfmark
5.53 +[
5.54 +/Title(First Fit Decreasing \(FFD oder FFNI\))
5.55 +/Action/GoTo/Dest(subsubsection.6.2.1)cvn
5.56 +/OUT pdfmark
5.57 +[
5.58 +/Title(Best Fit Decreasing \(BFD\))
5.59 +/Action/GoTo/Dest(subsubsection.6.2.2)cvn
5.60 +/OUT pdfmark
5.61 +[
5.62 +/Title(Dynamische Programmierung)
5.63 +/Action/GoTo/Dest(section.7)cvn
5.64 +/OUT pdfmark
5.65 +[
5.66 +/Title(Landau-Symbole)
5.67 +/Action/GoTo/Dest(appendix.A)cvn
5.68 +/OUT pdfmark
6.1 --- a/exzerpt.tex Mon Jan 10 00:16:59 2011 +0100
6.2 +++ b/exzerpt.tex Thu Jan 20 00:56:20 2011 +0100
6.3 @@ -34,7 +34,7 @@
6.4
6.5 \section{Einleitung}\label{sec:intro}
6.6 Dozent: Matthias Westermann\\
6.7 - Website: lak.informatik.uni-freiburg.de\\
6.8 + Website: \url{http://lak.informatik.uni-freiburg.de}\\
6.9 Klausur: 09.03.2011\\
6.10 Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
6.11 \subsection{Themen:}
6.12 @@ -57,7 +57,7 @@
6.13 \end{itemize}
6.14 \subsection{Literatur:}
6.15 \bibliography{literatur}
6.16 - \cite{1}\cite{2}
6.17 + \nocite{*}
6.18
6.19 \newpage
6.20 \section{Divide and Conquer}\label{sec:div&conq}
6.21 @@ -169,7 +169,7 @@
6.22 \subsection{Polynomprodukt und Fast Fourier-Transformation}
6.23
6.24
6.25 - \newpage
6.26 + \newpage
6.27 \section{Randomisierung}
6.28 \subsection{Hashing}
6.29
6.30 @@ -181,14 +181,70 @@
6.31
6.32 \newpage
6.33 \section{Greedy}
6.34 + \subsection{Kürzeste (billigste) Wege}
6.35
6.36 \newpage
6.37 - \section{Anhang}
6.38 - \subsection{Landau-Symbole}
6.39 + \section{Bin Packing}
6.40 + \textbf{Problembeschreibung:}\\
6.41 + 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.
6.42 + \subsection{Online Verfahren}
6.43 + 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.\\
6.44 + Kein Online Bin Packing Verfahren kann stets eine optimale Lösung finden!\\
6.45 + \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.\\
6.46 + \textbf{Beweis} Annahme: Online Bin Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$ Bins.\\
6.47 + 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.
6.48 +
6.49 + \subsubsection{Next Fit (NF)}
6.50 + 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.\\
6.51 + \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$.\\
6.52 + \textbf{Beweis}\\
6.53 + (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!\\
6.54 + (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)\\
6.55 + Laufzeit für Inputfolgen der Länge $n$: NF $O(n)$
6.56 + \subsubsection{First-Fit (FF)}
6.57 + Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue Kiste.\\
6.58 + \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger als halb voll ist. ($\implies FF(I) \leq 2OPT(I)$)\\
6.59 + \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)$.\\
6.60 + \textbf{Beweis}\\
6.61 + (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.\\
6.62 + Laufzeit für Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
6.63 + \subsubsection{Best-Fit (BF)}
6.64 + Verpacke das nächste Objekt in diejenige Kiste, in die es am besten passt (d.h. den geringsten Platz ungenutzt lässt).
6.65 + Verhalten von BF ähnlich zu FF.
6.66 + Laufzeit für Inputfolgen der Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
6.67 + \subsection{Offline Verfahren}
6.68 + \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
6.69 + Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann beginnt die Verpackung.\\
6.70 + $n$ und $s_1, ..., s_n$ sind gegeben, bevor die Verpackung beginnt!\\
6.71 + $\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!\\
6.72 + Idee für Offline Approximationsalgorithmen: Sortiere die Objekte zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
6.73 + \subsubsection{First Fit Decreasing (FFD oder FFNI)}
6.74 + \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}$.\\
6.75 + \textbf{Beweis}: \$\$\$TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang\$\$\$\\
6.76 + \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$.\\
6.77 + \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?\$\$\$\\
6.78 + \textbf{Satz}: Für alle Inputfolgen I gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\
6.79 + \textbf{Satz}:
6.80 + \begin{itemize}
6.81 + \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
6.82 + \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
6.83 + \end{itemize}
6.84 + \textbf{Beweis}: \$\$\$TODO\$\$\$
6.85 + \subsubsection{Best Fit Decreasing (BFD)}
6.86 + Nicht im Script???
6.87 +
6.88 + \newpage
6.89 + \section{Dynamische Programmierung}
6.90 +
6.91 +
6.92 + \newpage
6.93 + \begin{appendix}
6.94 + \section{Landau-Symbole}
6.95 \begin{figure}[H]
6.96 \centering
6.97 \includegraphics[scale=0.45]{img/landau_sym}
6.98 \caption{Definition der Landau Symbole}
6.99 \label{fig:landau_sym}
6.100 \end{figure}
6.101 + \end{appendix}
6.102 \end{document}
6.103 \ No newline at end of file
7.1 --- a/exzerpt.toc Mon Jan 10 00:16:59 2011 +0100
7.2 +++ b/exzerpt.toc Thu Jan 20 00:56:20 2011 +0100
7.3 @@ -13,7 +13,7 @@
7.4 \contentsline {subsection}{\numberline {2.4}Segmentschnitt}{4}{subsection.2.4}
7.5 \contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{5}{subsubsection.2.4.1}
7.6 \contentsline {subsubsection}{\numberline {2.4.2}Analyse}{5}{subsubsection.2.4.2}
7.7 -\contentsline {subsection}{\numberline {2.5}Fast Fourier-Transformation}{5}{subsection.2.5}
7.8 +\contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation}{5}{subsection.2.5}
7.9 \contentsline {section}{\numberline {3}Randomisierung}{6}{section.3}
7.10 \contentsline {subsection}{\numberline {3.1}Hashing}{6}{subsection.3.1}
7.11 \contentsline {section}{\numberline {4}Amortisierte Analyse}{7}{section.4}
7.12 @@ -21,5 +21,14 @@
7.13 \contentsline {subsection}{\numberline {4.2}Fibonacci Heaps}{7}{subsection.4.2}
7.14 \contentsline {subsection}{\numberline {4.3}Union Find}{7}{subsection.4.3}
7.15 \contentsline {section}{\numberline {5}Greedy}{8}{section.5}
7.16 -\contentsline {section}{\numberline {6}Anhang}{9}{section.6}
7.17 -\contentsline {subsection}{\numberline {6.1}Landau-Symbole}{9}{subsection.6.1}
7.18 +\contentsline {subsection}{\numberline {5.1}K\"urzeste (billigste) Wege}{8}{subsection.5.1}
7.19 +\contentsline {section}{\numberline {6}Bin Packing}{9}{section.6}
7.20 +\contentsline {subsection}{\numberline {6.1}Online Verfahren}{9}{subsection.6.1}
7.21 +\contentsline {subsubsection}{\numberline {6.1.1}Next Fit (NF)}{9}{subsubsection.6.1.1}
7.22 +\contentsline {subsubsection}{\numberline {6.1.2}First-Fit (FF)}{9}{subsubsection.6.1.2}
7.23 +\contentsline {subsubsection}{\numberline {6.1.3}Best-Fit (BF)}{10}{subsubsection.6.1.3}
7.24 +\contentsline {subsection}{\numberline {6.2}Offline Verfahren}{10}{subsection.6.2}
7.25 +\contentsline {subsubsection}{\numberline {6.2.1}First Fit Decreasing (FFD oder FFNI)}{10}{subsubsection.6.2.1}
7.26 +\contentsline {subsubsection}{\numberline {6.2.2}Best Fit Decreasing (BFD)}{10}{subsubsection.6.2.2}
7.27 +\contentsline {section}{\numberline {7}Dynamische Programmierung}{11}{section.7}
7.28 +\contentsline {section}{\numberline {A}Landau-Symbole}{12}{appendix.A}