On the influence of non-perfect randomness on probabilistic algorithms

In modern computer science, many problems are solved with the help of probabilistic algorithms. This thesis concentrates on the analysis of algorithms with respect to the employment of random sources that do not provide perfect random numbers, like pseudorandom generators or biased sources. New theoretical results are presented that describe implications of using non-perfect random numbers with probabilistic algorithms. The theoretical part of this thesis considers several probabilistic algorithms: For a basic randomized algorithm for comparing polynomials, it is shown that repeating the algorithm several times does not always decrease its error probability to the same extent, depending on the pseudorandom generator. For Karger´s probabilistic algorithm for finding the minimum cut of a graph, it is shown how the algorithm can be adapted to a non-uniform source of randomness. This is shown for the basic version as well as for the more sophisticated version with two recursive calls. For the random walk algorithm for the Boolean Satisfiability Problem, it is demonstrated how a bias from the uniform distribution of the random numbers influences the error probability of the algorithm. For the Randomized Quicksort algorithm, a lower bound for the number of comparisons is given, based on the distribution on the choice of the pivot elements. The experimental part of this thesis examines the impact of various sources of randomness on the quality of the solution of probabilistic optimization heuristics, concentrating on Simulated Annealing as a representant for local search heuristics and a genetic algorithm as a representant for population based heuristics. As a reference source of randomness, bits provided with the help of a quantum theoretic experiment are used. The results of the experiments show significant differences between the influence of non-perfect randomness on the Simulated Annealing heuristic and a genetic algorithm