On the influence of non-perfect randomness on probabilistic algorithms [Elektronische Ressource] / vorgelegt von Markus Maucher

Universitat¨ Ulm¨Institut fur Theoretische InformatikDirektor: Prof. Dr. Uwe Schoning¨On the influence of non-perfectrandomness on probabilisticalgorithmsDissertationzur Erlangung des Doktorgrades Dr. rer. nat.der Fakultat¨ fur¨ Ingenieurwissenschaften undInformatik der Universitat¨ Ulmvorgelegt vonMarkus Maucheraus Ochsenhausen2009Amtierender Dekan: Prof. Dr. M. Weber1. Gutachter: Prof. Dr. U. Schoning¨2. Dr. H. A. KestlerTag der Promotion: 07.10.2009iiAcknowledgementsThe work in this thesis was supported by grants to Uwe Schoning¨ (DFG grantScho302/6) and Hans Kestler (BMBF grant NGFNplus 01 GS 08116) . I am veryindebted for that financial support. I also gratefully thank the bwGRiD project[1] for the computational resources. Most of our experiments were run on thatgrid.I am also indebted to my colleagues at the University of Ulm, both in theTheoretical Computer Science group as well as in the Applied Bioinformaticsgroup. Thank you very much for the many fruitful discussions. Special thanksto Tobias Eibach and Stefan Arnold, who went over parts of this thesis in its laststage and gave me valuable advice.It is a pleasure to thank my supervisor Uwe Schoning¨ for his stimulating sug-gestions and support during the research for this thesis, and I would also liketo show my gratitude to Hans A. Kestler for his encouragement, support andmotivating ideas. Without these two people, this work would not have beenpossible.