Forum für Wissenschaft, Industrie und Wirtschaft

Hauptsponsoren:     3M 
Datenbankrecherche:

 

Vom Zufall in der Informatik

15.04.2004


Zufall und Informatik - zwei Begriffe die sich gegenseitig auszuschließen scheinen: Computer würfeln nicht! Oder doch? Computer benützen Generatoren für sogenannte (Pseudo-) Zufallszahlen. Damit können sie Zahlenreihen erzeugen, die wie zufällig aussehen. Diese Zufallszahlen kann man natürlich in seinen Lottoschein eintragen. Für Zufallszahlen gibt es aber auch eine Fülle von sehr nützlichen Anwendungen. Ein schönes Beispiel ist hierfür die Berechnung von Primzahlen, also jenen Zahlen, die nur durch 1 und sich selbst teilbar sind. Primzahlen sind nicht nur eine Spielerei für Mathematiker, sondern unersetzliche Grundbausteine in vielen Anwendungen. Insbesondere die moderne Kryptographie braucht Primzahlen in astronomischer Größe. Wie bekommt man aber eine Primzahl mit, sagen wir, 100 Dezimalstellen?

... mehr zu:
»DFG »Matching »Primzahl »Zufallszahl

Unglücklicherweise kennt man bis heute keine einfache Formel, die ausschließlich Primzahlen produziert. Andererseits weiß man, dass es sehr viele Primzahlen gibt. Um nun eine große Primzahl zu bekommen wählt man einfach eine zufällige Zahl und testet dann, ob diese eine Primzahl ist. Falls nicht, wird der Versuch wiederholt. Im Mittel hat man bereits nach wenigen Versuchen eine Primzahl gefunden.

Die effizienten Verfahren, die Zahlen daraufhin testen, ob sie Primzahlen sind, arbeiten ebenfalls mit Zufallszahlen. Mit verschwindend geringer Wahrscheinlichkeit kann dabei allerdings eine zusammengesetzte Zahl fälschlicherweise als Primzahl deklariert werden. Bereits Carl Friedrich Gauß erklärte im Jahr 1801, dass ein effizienter Primzahltest (,der ohne Zufallszahlen auskommt,) zu einem der wichtigsten Ziele in der Forschung zählt. So war die Sensation perfekt, als der indische Informatik-Professor Manindra Agrawal mit seinen beiden Studenten Neeraj Kayal und Nitin Saxena im Sommer 2002 einen solchen Primzahltest veröffentlichte.


Die dabei verwendeten Techniken sind so mächtig und trickreich, dass sie sich auch auf andere Probleme erfolgreich anwenden lassen sollten. Dieser Intuition folgt Prof. Dr. Thomas Thierauf vom Fachbereich Elektronik und Informatik der FH Aalen. In Zusammenarbeit mit Prof. Dr. Uwe Schoening von der Universität Ulm untersucht er in einem von der Deutschen Forschungsgemeinschaft (DFG) geförderten Projekt unter anderem das sogenannte perfekte Matching Problem.

Ein Beispiel für perfektes Matching ist folgende Situation: 100 Männer sollen mit 100 Frauen verheiratet werden. Jede Frau gibt vorab diejenigen Männer an, die sie bereit ist zu heiraten. Das Gleiche macht umgekehrt jeder Mann. Mit diesen Wahl-Einschränkungen muss nun eine Zuordnung gefunden werden (ein perfektes Matching), so dass am Ende jeder einen Partner hat. Ein anderes Anwendungsgebiet ist die Bio-Informatik. Hier spielt das Matching Problem eine wichtige Rolle bei der Vorhersage der Struktur von RNA-Faltungen.

Ähnlich wie früher beim Primzahlproblem kennt man für das perfekte Matching lediglich randomisierte Verfahren um das Problem effizient auf einem Parallelrechner zu lösen. Prof. Dr. Thierauf, der auch mit Prof. Dr. Agrawal zusammen arbeitet, sieht gute Chancen, beim Problem des perfekten Matching ein Stück voran zu kommen. Interessante Teilergebnisse liegen zur Veröffentlichung bereit. Vorab kann man sich die Arbeiten bereits auf der Homepage von Prof. Dr. Thierauf ansehen.

Dass ein Forschungsprojekt an einer Fachhochschule von der DFG gefördert wird, ist ungewöhnlich. Üblicherweise finanziert die DFG Forschungsvorhaben von Wissenschaftlern einer Universität oder Forschungseinrichtung. Die geförderten Forschungsvorhaben mussten sich allesamt in einem erlesenen Wettbewerb gegen anderen Vorhaben durchsetzen. "Dass sich das Forschungsvorhaben von Prof. Dr. Thierauf durchsetzen konnte, belegt eindrucksvoll, dass auch an der Fachhochschule Aalen Spitzenforschung betrieben wird", sagte der Studiengangleiter der Informatik, Prof. Dr. Ulrich Klauck.

Dr. Marc Dressler | idw
Weitere Informationen:
http://linux2.image.fh-aalen.de/Thierauf/

Weitere Berichte zu: DFG Matching Primzahl Zufallszahl

Weitere Nachrichten aus der Kategorie Informationstechnologie:

nachricht Rostocker Forscher entwickeln autonom fahrende Kräne
20.07.2018 | Universität Rostock

nachricht Maschinelles Lernen: Neue Methode ermöglicht genaue Extrapolation
13.07.2018 | Institute of Science and Technology Austria

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Future electronic components to be printed like newspapers

A new manufacturing technique uses a process similar to newspaper printing to form smoother and more flexible metals for making ultrafast electronic devices.

The low-cost process, developed by Purdue University researchers, combines tools already used in industry for manufacturing metals on a large scale, but uses...

Im Focus: Rostocker Forscher entwickeln autonom fahrende Kräne

Industriepartner kommen aus sechs Ländern

Autonom fahrende, intelligente Kräne und Hebezeuge – dieser Ingenieurs-Traum könnte in den nächsten drei Jahren zur Wirklichkeit werden. Forscher aus dem...

Im Focus: Superscharfe Bilder von der neuen Adaptiven Optik des VLT

Das Very Large Telescope (VLT) der ESO hat das erste Licht mit einem neuen Modus Adaptiver Optik erreicht, die als Lasertomografie bezeichnet wird – und hat in diesem Rahmen bemerkenswert scharfe Testbilder vom Planeten Neptun, von Sternhaufen und anderen Objekten aufgenommen. Das bahnbrechende MUSE-Instrument kann ab sofort im sogenannten Narrow-Field-Modus mit dem adaptiven Optikmodul GALACSI diese neue Technik nutzen, um Turbulenzen in verschiedenen Höhen in der Erdatmosphäre zu korrigieren. Damit ist jetzt möglich, Bilder vom Erdboden im sichtbaren Licht aufzunehmen, die schärfer sind als die des NASA/ESA Hubble-Weltraumteleskops. Die Kombination aus exquisiter Bildschärfe und den spektroskopischen Fähigkeiten von MUSE wird es den Astronomen ermöglichen, die Eigenschaften astronomischer Objekte viel detaillierter als bisher zu untersuchen.

Das MUSE-Instrument (kurz für Multi Unit Spectroscopic Explorer) am Very Large Telescope (VLT) der ESO arbeitet mit einer adaptiven Optikeinheit namens GALACSI. Dabei kommt auch die Laser Guide Stars Facility, kurz ...

Im Focus: Diamant – ein unverzichtbarer Werkstoff der Fusionstechnologie

Forscher am KIT entwickeln Fenstereinheiten mit Diamantscheiben für Fusionsreaktoren – Neue Scheibe mit Rekorddurchmesser von 180 Millimetern

Klimafreundliche und fast unbegrenzte Energie aus dem Fusionskraftwerk – für dieses Ziel kooperieren Wissenschaftlerinnen und Wissenschaftler weltweit. Bislang...

Im Focus: Wiener Forscher finden vollkommen neues Konzept zur Messung von Quantenverschränkung

Quantenphysiker/innen der ÖAW entwickelten eine neuartige Methode für den Nachweis von hochdimensional verschränkten Quantensystemen. Diese ermöglicht mehr Effizienz, Sicherheit und eine weitaus geringere Fehleranfälligkeit gegenüber bisher gängigen Mess-Methoden, wie die Forscher/innen nun im Fachmagazin „Nature Physics“ berichten.

Die Vision einer vollständig abhörsicheren Übertragung von Information rückt dank der Verschränkung von Quantenteilchen immer mehr in Reichweite. Wird eine...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Stadtklima verbessern, Energiemix optimieren, sauberes Trinkwasser bereitstellen

19.07.2018 | Veranstaltungen

Innovation – the name of the game

18.07.2018 | Veranstaltungen

Wie geht es unserer Ostsee? Ein aktueller Zustandsbericht

17.07.2018 | Veranstaltungen

VideoLinks
Wissenschaft & Forschung
Weitere VideoLinks im Überblick >>>
 
Aktuelle Beiträge

Neue Anwendungen für Mikrolaser in der Quanten-Nanophotonik

20.07.2018 | Physik Astronomie

Need for speed: Warum Malaria-Parasiten schneller sind als die menschlichen Abwehrzellen

20.07.2018 | Biowissenschaften Chemie

Die Gene sind nicht schuld

20.07.2018 | Medizin Gesundheit

Weitere B2B-VideoLinks
IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics