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 Industrie 4.0: Fremde Eindringlinge im Unternehmensnetz erkennen
16.04.2018 | Fraunhofer-Institut für Sichere Informationstechnologie SIT

nachricht Die Thermodynamik des Rechnens
11.04.2018 | Eidgenössische Technische Hochschule Zürich (ETH Zürich)

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

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

Im Focus: Software mit Grips

Ein computergestütztes Netzwerk zeigt, wie die Ionenkanäle in der Membran von Nervenzellen so verschiedenartige Fähigkeiten wie Kurzzeitgedächtnis und Hirnwellen steuern können

Nervenzellen, die auch dann aktiv sind, wenn der auslösende Reiz verstummt ist, sind die Grundlage für ein Kurzzeitgedächtnis. Durch rhythmisch aktive...

Im Focus: Der komplette Zellatlas und Stammbaum eines unsterblichen Plattwurms

Von einer einzigen Stammzelle zur Vielzahl hochdifferenzierter Körperzellen: Den vollständigen Stammbaum eines ausgewachsenen Organismus haben Wissenschaftlerinnen und Wissenschaftler aus Berlin und München in „Science“ publiziert. Entscheidend war der kombinierte Einsatz von RNA- und computerbasierten Technologien.

Wie werden aus einheitlichen Stammzellen komplexe Körperzellen mit sehr unterschiedlichen Funktionen? Die Differenzierung von Stammzellen in verschiedenste...

Im Focus: Spider silk key to new bone-fixing composite

University of Connecticut researchers have created a biodegradable composite made of silk fibers that can be used to repair broken load-bearing bones without the complications sometimes presented by other materials.

Repairing major load-bearing bones such as those in the leg can be a long and uncomfortable process.

Im Focus: Verbesserte Stabilität von Kunststoff-Leuchtdioden

Polymer-Leuchtdioden (PLEDs) sind attraktiv für den Einsatz in großflächigen Displays und Lichtpanelen, aber ihre begrenzte Stabilität verhindert die Kommerzialisierung. Wissenschaftler aus dem Max-Planck-Institut für Polymerforschung (MPIP) in Mainz haben jetzt die Ursachen der Instabilität aufgedeckt.

Bildschirme und Smartphones, die gerollt und hochgeklappt werden können, sind Anwendungen, die in Zukunft durch die Entwicklung von polymerbasierten...

Im Focus: Writing and deleting magnets with lasers

Study published in the journal ACS Applied Materials & Interfaces is the outcome of an international effort that included teams from Dresden and Berlin in Germany, and the US.

Scientists at the Helmholtz-Zentrum Dresden-Rossendorf (HZDR) together with colleagues from the Helmholtz-Zentrum Berlin (HZB) and the University of Virginia...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Internationale Konferenz zur Digitalisierung

19.04.2018 | Veranstaltungen

124. Internistenkongress in Mannheim: Internisten rücken Altersmedizin in den Fokus

19.04.2018 | Veranstaltungen

DFG unterstützt Kongresse und Tagungen - Juni 2018

17.04.2018 | Veranstaltungen

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

Grösster Elektrolaster der Welt nimmt Arbeit auf

20.04.2018 | Interdisziplinäre Forschung

Bilder magnetischer Strukturen auf der Nano-Skala

20.04.2018 | Physik Astronomie

Kieler Forschende entschlüsseln neuen Baustein in der Entwicklung des globalen Klimas

20.04.2018 | Geowissenschaften

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