An alternative correctness proof of a certification method for FPTIME. - In: 5th International Workshop on Proof, Computation, Complexity, (2006), S. 18-19
5th International Workshop on Proof, Computation, Complexity : PCC '06 ; Ilmenau, July 24 - 25, 2006. - Ilmenau : Univ.-Verl. Ilmenau, 2006. - Online-Ressource (PDF-Datei: 57 S., 412,3 KB)Parallel als Druckausg. erschienen
http://www.db-thueringen.de/servlets/DocumentServlet?id=6361
Zertifizierung von Laufzeit- und Speicherplatzbedarf für imperative Programme. - 134 S. Ilmenau : Techn. Univ., Diplomarbeit, 2006
Diese Diplomarbeit beschreibt ein Verfahren zur statischen Analyse des Ressourcenbedarfs von imperativen Programmen. Unter imperativen Programmen ist dabei eine um (fast) beliebige Datentypen und Basisanweisungen bereicherte Version von loop-Programmen zu verstehen. Einzige Anforderung an Datentypen ist, dass einer Variablen X dieses Datentyps eine natürliche "Größe" oder "Länge" |X| zugeordnet werden kann. Von einer Basisanweisung imp(P_1, ..., P_m) wird gefordert, dass die Größe jedes Ein-/Ausgabe-Parameters polynomiell beschränkt werden kann. Das heißt, dass für jeden Ein-/Ausgabe-Parameter P_i ein Polynom imp_|P_i|(p_1, ..., p_m) existiert, so dass die Größe des in P_i zurückgelieferten Wertes kleiner oder gleich imp_|P_i|(|P_1|, ..., |P_m) ist. Das formale Problem, das diese Arbeit näher betrachtet, besteht nun darin, zu einem gegebenem imperativen Programm alleine durch eine Analyse des Quellcodes zu entscheiden, ob alle auftretenden Variablen "polynomiell längenbeschränkt" sind. Das heißt es ist zu entscheiden, ob für jede Variable X_i eines Programms P, das die Variablen X_1, ..., X_n verwendet, ein Polynom p_{X_i}(x_1, ..., x_n) existiert, so dass gilt: {|X_1| = s_1, ..., |X_n| = s_n} P {|X_i| <= p_{X_i}(s_1, ..., s_n)} Es wird gezeigt, dass dieses Problem unentscheidbar ist. Trotz dieser Erkenntnis werden in dieser Arbeit mit M und M' zwei "Zertifizierer" für die polynomielle Längenbeschränktheit von imperativen Programm vorgestellt. Im Falle, dass ein Programm zertifiziert werden kann, sind M und M' zusätzlich dazu in der Lage, eine konkrete polynomielle Längenschranke anzugeben. Weiterhin werden mit allgemeinen Loop-Programmen, String-Programmen und Powerstring-Programmen drei imperative Programmiersprachen vorgestellt. Es wird gezeigt, dass die durch M bzw. M' zertifizierbaren allgemeinen Loop-Programme genau die Funktionen in FLINSPACE berechnen, die durch M bzw. M' zertifizierbaren String-Programme genau die Funktionen in FP berechnen und die durch M bzw. M' Powerstring-Programme genau die Funktionen in FPSPACE berechnen.
On the probability of rendezvous in graphs. - In: Random structures & algorithms, ISSN 1098-2418, Bd. 26 (2005), 3, S. 266-288
In a simple graph G without isolated nodes the following random experiment is carried out: each node chooses one of its neighbors uniformly at random. We say a rendezvous occurs if there are adjacent nodes u and v such that u chooses v and v chooses u; the probability that this happens is denoted by s(G). Métivier, Saheb, and Zemmari [Randomized rendezvous, Algorithms, trees, combinatorics, and probabilities, Eds. G. Gardy and A. Mokkadem, Trends in Mathematics, 183-194. Birkhäuser, Boston, 2000.] asked whether it is true that s(G) s(Kn) for all n-node graphs G, where Kn is the complete graph on n nodes. We show that this is the case. Moreover, we show that evaluating s(G) for a given graph G is a #P-complete problem, even if only d-regular graphs are considered, for any d 5.
https://doi.org/10.1002/rsa.20032
Balanced allocation and dictionaries with tightly packed constant size bins. - In: Automata, languages and programming, (2005), S. 166-178
http://dx.doi.org/10.1007/11523468_14
Control structures in programs and computational complexity. - In: Annals of pure and applied logic, ISSN 1873-2461, Bd. 133 (2005), 1/3, S. 247-273
http://dx.doi.org/10.1016/j.apal.2004.10.011
Primality testing in polynomial time : from randomized algorithms to "PRIMES is in P". - Berlin : Springer, 2004. - Online-Ressource (X, 147p. Also available online). - (Lecture notes in computer science ; 3000) ISBN 978-3-540-25933-6
This book is devoted to algorithms for the venerable primality problem: Given a natural number n, decide whether it is prime or composite. The problem is basic in number theory, efficient algorithms that solve it, i.e., algorithms that run in a number of computational steps which is polynomial in the number of digits needed to write n, are important for theoretical computer science and for applications in algorithmics and cryptology. This book gives a self-contained account of theoretically and practically important efficient algorithms for the primality problem, covering the randomized algorithms by Solovay-Strassen and Miller-Rabin from the late 1970s as well as the recent deterministic algorithm of Agrawal, Kayal, and Saxena. The textbook is written for students of computer science, in particular for those with a special interest in cryptology, and students of mathematics, and it may be used as a supplement for courses or for self-study
http://dx.doi.org/10.1007/b12334
On the computational complexity of imperative programming languages. - In: Theoretical computer science, Bd. 318 (2004), 1/2, S. 139-161
http://dx.doi.org/10.1016/j.tcs.2003.10.016
Gossiping and broadcasting versus computing functions in networks. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 137 (2004), 2, S. 127-153
https://doi.org/10.1016/S0166-218X(03)00257-9
Platzeffiziente Hashverfahren mit garantierter konstanter Zugriffszeit, 2004. - Online-Ressource (PDF-Datei: 136 S., 1336 KB) : Ilmenau, Techn. Univ., Diss., 2004
Parallel als Druckausg. erschienen
Wir stellen ein neues Verfahren zur Konstruktion einer minimalen perfekten Hashfunktion (MPHF) und ein neues cachefreundliches dynamisches Wörterbuch vor, beschreiben die neuen Verfahren algorithmisch und analysieren sie hinsichtlich Platzbedarf und Laufzeit. Für die Analyse nehmen wir an, dass die in den Verfahren benutzten Hashfunktionen volle Unabhängigkeit gewährleisten. Schließlich werden wir jeweils experimentelle Resultate angeben und interpretieren. Wir zeigen, dass man eine minimale perfekte Hashfunktion für n Schlüssel mit einem Platzbedarf von 0.93n Wörtern in erwarteter Zeit O(n) realisieren kann. Zur Auswertung der MPHF werden 2 Hashfunktionen berechnet und zwei Speicherzugriffe durchgeführt. Unser dynamisches Wörterbuch benötigt (1+epsilon)n Platz für ein beliebiges epsilon > 0. Bei der Suche müssen 2 Hashfunktionen ausgewertet und 2d Speicherzellen inspiziert werden, die in zwei zusammenhängenden Speicherbereichen liegen, wobei d >= 1+3.26 ln(1/epsilon). Wir können zeigen, dass für d >= 90.1 ln(1/epsilon) die erwartete Einfügezeit für einen neuen Schlüssel konstant ist. Am Ende werden wir zeigen, wie man dynamisches Hashing mit Zeichenketten cachefreundlich realisieren kann.
http://www.db-thueringen.de/servlets/DocumentServlet?id=2431