Format:
1 Online-Ressource (310S.)
ISBN:
9783322800725
,
9783519004707
Series Statement:
Leitfäden der Informatik
Note:
Randomisierte (zufallsgesteuerte) Verfahren sind zu einem Standardansatz für den Algorithmenentwurf geworden. Einfachheit und Effizienz sind die Merkmale, die sie oft fast zu Wundermitteln zur Lösung unterschiedlicher, komplexer Aufgaben gemacht haben. Besonders in den Bereichen der Kommunikation, der Kryptographie und der diskreten Optimierung sind sie unentbehrlich für die Softwareentwicklung geworden. Wir kennen mehrere Situationen und Aufgabenstellungen, für deren Lösung die besten deterministischen Ansätze so viel Rechenaufwand erfordern, dass sie nicht praktikabel sind, während randomisierte Methoden einen in der Praxis umsetzbaren Lösungsweg bieten. Diesen Sprung von einer riesigen Menge an Rechenarbeit deterministischer Algorithmen (die oft in Milliarden von Jahren auf den schnellsten Rechnern nicht zu bewaltigen wäre) zu den kurzen Berechnungen zufallsgesteuerter Algorithmen bezahlen wir mit dem Risiko, ein falsches Resultat zu erhalten. Aber die Wahrscheinlichkeit einer fehlerhaften Berechnung eines randomisierten Algorithmus kann man typischerweise wesentlich kleiner machen als die Wahrscheinlichkeit, mit einem einzigen Lottoschein den ersten Preis zu gewinnen (auf Anhieb sechs Richtige zu tippen). Wir zahlen also nur mit einem winzigen Verlust an Zuverlässigkeit des Algorithmus für die Ersparnis einer ungeheuren Menge an Rechenzeit. Wie solche großen quantitativen Sprünge der Berechnungskomplexität durch kleine Abschwächungen unserer Sicherheitsanforderungen (garantiert die richtigen Ergebnisse zu erhalten) zu erreichen sind, und warum so etwas überhaupt möglich ist, ist das Thema dieses Buches. Trotz eines breiten Einsatzes und vieler Erfolge der randomisierten Verfahren in unterschiedlichen Anwendungen haben nur wenige Informatiker hinreichende Kenntnisse über Randomisierung
Language:
German
Keywords:
Randomisierter Algorithmus
;
Lehrbuch
;
Lehrbuch
DOI:
10.1007/978-3-322-80072-5
URL:
Volltext
(lizenzpflichtig)
Author information:
Hromkovič, Juraj 1958-
Bookmarklink
