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 Brain-Computer-Interface: Wenn der Computer uns intuitiv versteht
18.01.2017 | Technische Universität Berlin

nachricht »Lernlabor Cybersicherheit« startet in Weiden i. d. Oberpfalz
12.01.2017 | Fraunhofer-Gesellschaft

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

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

Im Focus: Innovatives Hochleistungsmaterial: Biofasern aus Florfliegenseide

Neuartige Biofasern aus einem Seidenprotein der Florfliege werden am Fraunhofer-Institut für Angewandte Polymerforschung IAP gemeinsam mit der Firma AMSilk GmbH entwickelt. Die Forscher arbeiten daran, das Protein in großen Mengen biotechnologisch herzustellen. Als hochgradig biegesteife Faser soll das Material künftig zum Beispiel in Leichtbaukunststoffen für die Verkehrstechnik eingesetzt werden. Im Bereich Medizintechnik sind beispielsweise biokompatible Seidenbeschichtungen von Implantaten denkbar. Ein erstes Materialmuster präsentiert das Fraunhofer IAP auf der Internationalen Grünen Woche in Berlin vom 20.1. bis 29.1.2017 in Halle 4.2 am Stand 212.

Zum Schutz des Nachwuchses vor bodennahen Fressfeinden lagern Florfliegen ihre Eier auf der Unterseite von Blättern ab – auf der Spitze von stabilen seidenen...

Im Focus: Verkehrsstau im Nichts

Konstanzer Physiker verbuchen neue Erfolge bei der Vermessung des Quanten-Vakuums

An der Universität Konstanz ist ein weiterer bedeutender Schritt hin zu einem völlig neuen experimentellen Zugang zur Quantenphysik gelungen. Das Team um Prof....

Im Focus: Traffic jam in empty space

New success for Konstanz physicists in studying the quantum vacuum

An important step towards a completely new experimental access to quantum physics has been made at University of Konstanz. The team of scientists headed by...

Im Focus: Textiler Hochwasserschutz erhöht Sicherheit

Wissenschaftler der TU Chemnitz präsentieren im Februar und März 2017 ein neues temporäres System zum Schutz gegen Hochwasser auf Baumessen in Chemnitz und Dresden

Auch die jüngsten Hochwasserereignisse zeigen, dass vielerorts das natürliche Rückhaltepotential von Uferbereichen schnell erschöpft ist und angrenzende...

Im Focus: Wie Darmbakterien krank machen

HZI-Forscher entschlüsseln Infektionsmechanismen von Yersinien und Immunantworten des Wirts

Yersinien verursachen schwere Darminfektionen. Um ihre Infektionsmechanismen besser zu verstehen, werden Studien mit dem Modellorganismus Yersinia...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics
Veranstaltungen

Mittelstand 4.0 – Mehrwerte durch Digitalisierung: Hintergründe, Beispiele, Lösungen

20.01.2017 | Veranstaltungen

Nachhaltige Wassernutzung in der Landwirtschaft Osteuropas und Zentralasiens

19.01.2017 | Veranstaltungen

Künftige Rohstoffexperten aus aller Welt in Freiberg zur Winterschule

18.01.2017 | Veranstaltungen

 
VideoLinks
B2B-VideoLinks
Weitere VideoLinks >>>
Aktuelle Beiträge

21.500 Euro für eine grüne Zukunft – Unserer Umwelt zuliebe

20.01.2017 | Unternehmensmeldung

innovations-report im Interview mit Rolf-Dieter Lafrenz, Gründer und Geschäftsführer der Hamburger Start ups Cargonexx

20.01.2017 | Unternehmensmeldung

Niederlande: Intelligente Lösungen für Bahn und Stahlindustrie werden gefördert

20.01.2017 | Förderungen Preise