Moin,
der Code ist insgesamt 60KB, ich versuch mal, die relevanten Teile zu filtern:
Packages
Code:
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{caption}
\usepackage{color}
\usepackage{fancyhdr}
\usepackage{fragmentation}
\usepackage{listings}
\usepackage[pdftex]{graphicx}
\usepackage{program}
\usepackage{hyperref}
\usepackage{longtable}
\usepackage{xcolor}
Figure
Code:
One concept that we introduced in some detail in Section \fragref{Bounds.Kolmogorov} of this thesis, but so far completely ignored in the discussion of the given example is Kolmogorov Complexity. It would be easy for us to simply refer to Theorem \fragref[theorem]{Bounds.Kolmogorov.NonComputability} and dismiss Kolmogorov Complexity as non-computable and thus completely irrelevant for the rather practical problem of compressing the given source string $s$. Furthermore, it would be valid to claim that Kolmogorov Complexity is of no significance in the scenario put forth in this section because the point of this example is to determine an optimal choice of parameters for a given algorithm, an optimisation problem that does not depend on the (universal) computer used to perform the actual compression.
\begin{figure}
\begin{lstlisting}[caption=ANSI C]
#include
int main(int c,char* p[]) {
char* a = "abababababababababababcd";
char* b = "abcdcdcdcdcdcdcdcdcdcdcd";
printf("%s%s%s%s%s%s%s%s",a,b,b,a,a,b,b,a);
}
\end{lstlisting}
\hrule
\begin{lstlisting}[caption=Java]
public class C {
public static void main(String[] p) {
String a,b,c,d,e;
a = "ab";
b = "";
c = "cd";
d = "";
for (int i=0;i<11;i++) {
b += a;
d += c;
}
e = b+c+a+d+a+d+b+c;
System.out.print(e+e);
}
}
\end{lstlisting}
\hrule
\begin{lstlisting}[caption=Scala]
val a = "ab"*11+"cd";
val b = "ab"+"cd"*11;
print((a+b*2+a)*2);
\end{lstlisting}
\hrule
\begin{lstlisting}[caption=Python]
a = 'ab'*11+'cd';
b = 'ab'+'cd'*11;
print(a+b*2+a)*2
\end{lstlisting}
\hrule
\vspace*{10pt}
\centering
\begin{footnotesize}
\begin{longtable}{|l|r|rr|r|}
\hline
~&\multicolumn{4}{|c|}{\textbf{Program Size}}\\
\textbf{Language}&\textbf{Source}&\multicolumn{2}{|c|}{\textbf{Intermediate}}&\textbf{Machine Code}\\
\hline
ANSI C&160&Assembler:&971&8,498\\
Java&168&Byte Code:&782&n.a\\
Scala&57&Byte Code:&1,679&n.a\\
Python&46&~&n.a.&n.a\\
\hline
\end{longtable}
\end{footnotesize}
\caption{Examples of short programs that generate $s$. The listings in this figure are arranged for readability. The length (in bytes) of the source code, however, refers to the source code without any unnecessary line-breaks and spaces.}\fraglabel[figure]{Bounds.Example.Programs}
\end{figure}
Although Kolmogorov Complexity is a theoretical concept that does not provide any guidance for the optimal choice of $k$ in the given scenario, we could not resist the temptation to collect a few examples of short programs that produce $s$. In order to enable a fair comparison of the lengths of the different programs, we require that all of them produce $s$ to the standard output stream of the operating system. The programs we devised in the four different programming languages ANSI C, Java, Scala and Python\footnote{The Python program was kindly provided by Teemu Roos, PhD, University of Helsinki, Finland.} are given in Figure \fragref[figure]{Bounds.Example.Programs} along with their respective sizes both as source code as well as -- where applicable -- intermediate code and compiled machine code.
Mein Gefühl sagt mir, dass es eigentlich nur an der Figure liegen kann, denn das Problem trat erst auf, als ich diese Figure nachträglich eingefügt habe.
Liberty
P.S.: Zur Sicherheit habe ich nochmal den gesamten Code des Dokuments angehängt.
Lesezeichen