Grundlagenuntersuchungen zu Aspekten der Entropie in Algorithmen und algorithmischen Prozessen

• Antragsteller: Professor Dr. Uwe Schöning
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2003 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5415839

• Erstellungsjahr: 2008

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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.