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 Original bleibt Original - Neues Produktschutzverfahren für KFZ-Kennzeichenschilder
19.01.2018 | Fraunhofer-Institut für Werkstoff- und Strahltechnik IWS

nachricht Fliegen wird smarter – Kommunikationssystem LYRA im Lufthansa FlyingLab
18.01.2018 | Deutsches Forschungszentrum für Künstliche Intelligenz GmbH, DFKI

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

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

Im Focus: Vollmond-Dreierlei am 31. Januar 2018

Am 31. Januar 2018 fallen zum ersten Mal seit dem 30. Dezember 1982 "Supermond" (ein Vollmond in Erdnähe), "Blutmond" (eine totale Mondfinsternis) und "Blue Moon" (ein zweiter Vollmond im Kalendermonat) zusammen - Beobachter im deutschen Sprachraum verpassen allerdings die sichtbaren Phasen der Mondfinsternis.

Nach den letzten drei Vollmonden am 4. November 2017, 3. Dezember 2017 und 2. Januar 2018 ist auch der bevorstehende Vollmond am 31. Januar 2018 ein...

Im Focus: Maschinelles Lernen im Quantenlabor

Auf dem Weg zum intelligenten Labor präsentieren Physiker der Universitäten Innsbruck und Wien ein lernfähiges Programm, das eigenständig Quantenexperimente entwirft. In ersten Versuchen hat das System selbständig experimentelle Techniken (wieder)entdeckt, die heute in modernen quantenoptischen Labors Standard sind. Dies zeigt, dass Maschinen in Zukunft auch eine kreativ unterstützende Rolle in der Forschung einnehmen könnten.

In unseren Taschen stecken Smartphones, auf den Straßen fahren intelligente Autos, Experimente im Forschungslabor aber werden immer noch ausschließlich von...

Im Focus: Artificial agent designs quantum experiments

On the way to an intelligent laboratory, physicists from Innsbruck and Vienna present an artificial agent that autonomously designs quantum experiments. In initial experiments, the system has independently (re)discovered experimental techniques that are nowadays standard in modern quantum optical laboratories. This shows how machines could play a more creative role in research in the future.

We carry smartphones in our pockets, the streets are dotted with semi-autonomous cars, but in the research laboratory experiments are still being designed by...

Im Focus: Fliegen wird smarter – Kommunikationssystem LYRA im Lufthansa FlyingLab

• Prototypen-Test im Lufthansa FlyingLab
• LYRA Connect ist eine von drei ausgewählten Innovationen
• Bessere Kommunikation zwischen Kabinencrew und Passagieren

Die Zukunft des Fliegens beginnt jetzt: Mehrere Monate haben die Finalisten des Mode- und Technologiewettbewerbs „Telekom Fashion Fusion & Lufthansa FlyingLab“...

Im Focus: Ein Atom dünn: Physiker messen erstmals mechanische Eigenschaften zweidimensionaler Materialien

Die dünnsten heute herstellbaren Materialien haben eine Dicke von einem Atom. Sie zeigen völlig neue Eigenschaften und sind zweidimensional – bisher bekannte Materialien sind dreidimensional aufgebaut. Um sie herstellen und handhaben zu können, liegen sie bislang als Film auf dreidimensionalen Materialien auf. Erstmals ist es Physikern der Universität des Saarlandes um Uwe Hartmann jetzt mit Forschern vom Leibniz-Institut für Neue Materialien gelungen, die mechanischen Eigenschaften von freitragenden Membranen atomar dünner Materialien zu charakterisieren. Die Messungen erfolgten mit dem Rastertunnelmikroskop an Graphen. Ihre Ergebnisse veröffentlichen die Forscher im Fachmagazin Nanoscale.

Zweidimensionale Materialien sind erst seit wenigen Jahren bekannt. Die Wissenschaftler André Geim und Konstantin Novoselov erhielten im Jahr 2010 den...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

Veranstaltungen

15. BF21-Jahrestagung „Mobilität & Kfz-Versicherung im Fokus“

22.01.2018 | Veranstaltungen

Transferkonferenz Digitalisierung und Innovation

22.01.2018 | Veranstaltungen

Kongress Meditation und Wissenschaft

19.01.2018 | Veranstaltungen

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

15. BF21-Jahrestagung „Mobilität & Kfz-Versicherung im Fokus“

22.01.2018 | Veranstaltungsnachrichten

Forschungsteam schafft neue Möglichkeiten für Medizin und Materialwissenschaft

22.01.2018 | Biowissenschaften Chemie

Ein Haus mit zwei Gesichtern

22.01.2018 | Architektur Bauwesen

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