Basic investigations about aspects of entropy in algorithms and algorithmic processes

• Applicant: Professor Dr. Uwe Schöning
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5415839

• Final Report Year: 2008

Final Report Abstract

Das Verhalten verschiedener konkreter probabilistischer Algorithmen, insbesondere Quicksort und Min-Cut, wurde untersucht im Hinblick auf die Verwendung von Zufallszahlen mit geringer Entropie. Mit Hilfe von Graphen mit hoher Entropie als Basisbaustein konnten Superi^onzentratoren mit dem zur Zeit besten Kanten zu Knoten-Verhältnis konstruiert werden. Verschiedene Pseudozufallszahlengeneratoren wurden mit Hilfe generischer Simulated Annealing und genetischer Algorithmen getestet In Bezug auf ihre Brauchbarkeit und Einflussnahme auf die Qualität der Ergebnisse. Hierisei zeigten sich erstaunliche Unterschiede darin, in welcher Weise manche Algorithmen von manchen Zufallszahlengeneratoren profitieren bzw. umgekehrt in ihrer Qualität einbrechen. Das Grundkonzept und die betreffenden FragesteKungen von "Algorithmen und Entropie" flössen ein in die erfolgreiche Beantragung eines interdiszioplinären Promotionskotlegs und eines Schwerpunktprogramms.

Publications

• Beatrice List, Maricus Maucher, Uwe Schöning, Rainer Schuler Randomized Quicksort and the Entropy of the Random Number Generator. Electronic CoHoqutum on Computatiortal Complexity, Vol 11, 2004, Report Nr. 59.
  
  
• Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler Randomized Quicksort and the Entropy of the Random Source. Proceedings CoCooN2005, Lecture Notes in Computer Science22B5, Springer-Veriag, 2005, Seite450-460.
  
  
• Markus Maucher, Uwe Schöning, Hans A. Kestler. An empirical assessment of local and population based &earct) mettiods witti different degrees of pseudorandom-ness. Ulmer Informatik-Berichte, Nr. 2008-07, Juni 2008.
  
  
• Uwe Schöning. Smaller superconcentrators of density 28. Infomtation Processing Letters 98(2006)127-129.
  
  
• Walter Guttmann, Mari^us Maucher. Constraint Ordering. Ulmer Informatik-Berichte, Nr. 2005-03, Dezember 2005.
  
  
• Watter Guttmann, Markus Maucher. Variations on an ordering theme with constraints. In International Federation for Infonn. Processing. Vol 209. 4tti IFIP Int Conf. on Ttteoretical Computer Science 2006, Springer-Veriag, pp. 77-90.