Randomisierte Algorithmen

Methoden zum Entwurf von zufallsgesteuerten Systemen für Einsteiger

Häftad, Tyska, 2004

679 kr

Beställningsvara. Skickas inom 10-15 vardagar

Fri frakt för medlemmar vid köp för minst 249 kr.

Zufall ist ein erfolgreiches Mittel fur Entwurf und Entwicklung vieler Systeme in Informatik und Technik. Zufallsgesteuerte Algorithmen sind oft effizienter, einfacher, preiswerter und uberraschenderweise auch zuverlassiger als die besten deterministischen Programme. Warum ist die Zufallssteuerung so erfolgreich und wie entwirft man randomisierte Systeme? Einfach, intuitiv und trotzdem formal prazise gibt dieses Buch dem Leser einen Einstieg in die wunderbare Welt zufallsgesteuerter Algorithmen.

Produktinformation

Utgivningsdatum2004-06-29
Mått170 x 240 x 18 mm
Vikt546 g
FormatHäftad
SpråkTyska
SerieXLeitfäden der Informatik
Antal sidor310
Upplaga2004
FörlagB.G.Teubner GmbH
ISBN9783519004707

Tillhör följande kategorier

Systemvetenskap och AI inom Data och it
Programmeringsböcker inom Data och it
Databaser inom Data och it
Människa – datorinteraktion inom Data och it

1 Einleitung.- 1.1 Was ist Zufall und gibt es überhaupt echten Zufall?.- 1.2 Zufall als Quelle der Effizienz — ein Beispiel zur Motivation.- 1.3 Das Konzept des Buches.- 1.4 Für die Studierenden.- 1.5 Für die Lehrenden.- 2 Grundlagen.- 2.1 Zielsetzung.- 2.2 Elementare Wahrscheinlichkeitstheorie.- 2.3 Modellierung von randomisierten Algorithmen.- 2.4 Klassifizierung von randomisierten Algorithmen.- 2.5 Klassifizierung von randomisierten Algorithmen für Optimierungsprobleme.- 2.6 Paradigmen für den Entwurf randomisierter Algorithmen.- 2.7 Zusammenfassung.- 3 Überlisten des Gegners.- 3.1 Zielsetzung.- 3.2 Hashing.- 3.3 Universelles Hashing.- 3.4 Online-Algorithmen.- 3.5 Randomisierte Online-Algorithmen.- 3.6 Zusammenfassung.- 4 Die Methode der Fingerabdrücke.- 4.1 Zielsetzung.- 4.2 Kommunikationsprotokolle.- 4.3 Das Teilstringproblem.- 4.4 Verifikation der Matrixmultiplikation.- 4.5 Äquivalenz von zwei Polynomen.- 4.6 Zusammenfassung.- 5 Wahrscheinlichkeitsverstärkung durch Wiederholungen und die Stichprobenmethode.- 5.1 Zielsetzung.- 5.2 Effiziente Wahrscheinlichkeitsverstärkung durch Wiederholungen von Berechnungsteilen.- 5.3 Wiederholte Stichproben und Erfüllbarkeit.- 5.4 Stichproben und Generierung von nicht-quadratischen Resten.- 5.5 Zusammenfassung.- 6 Die Methode der häufigen Zeugen.- 6.1 Zielsetzung.- 6.2 Suche nach Zeugen für den Primzahltest.- 6.3 Der randomisierte Primzahltest von Solovay und Strassen.- 6.4 Generierung von zufälligen Primzahlen.- 6.5 Zusammenfassung.- 7 Optimierung und zufälliges Runden.- 7.1 Zielsetzung.- 7.2 Relaxation zur linearen Programmierung.- 7.3 Zufälliges Runden und MAX-SAT.- 7.4 Eine Kombination von Stichproben mit zufälligem Runden.- 7.5 Zusammenfassung.- A Mathematische Grundlagen.- A.1 Zielsetzung.- A.2 Algebraund Zahlentheorie.- A.3 Kombinatorik.- A.4 Zusammenfassung.