2021 | OriginalPaper | Buchkapitel
Diskrete Wahrscheinlichkeitstheorie
verfasst von : Rudolf Berghammer
Erschienen in: Mathematik für die Informatik
Verlag: Springer Fachmedien Wiesbaden
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Wahrscheinlichkeiten und Methoden der Statistik spielen in der Informatik eine immer größere Rolle. Am Ende von Kapitel 10 werden wir skizzieren, wie sie beispielsweise bei der Analyse von evolutionären Algorithmen eingesetzt werden. Ein evolutionärer Algorithmus ist ein Spezialfall eines randomisierten Algorithmus. Solch ein Algorithmus versucht, mit Hilfe zufällig ausgewählter Zwischenschritte zu einem gegebenen Problem eine im Mittel gute bzw. korrekte Lösung zu finden. Das bekannte Quicksort-Sortierverfahren ist ein weiteres Beispiel für einen randomisierten Algorithmus. Mit Hilfe der Wahrscheinlichkeitstheorie kann man zeigen, dass bei n > 0 zu sortierenden Objekten die erwartete Laufzeit $$\mathcal{O} (n\,glog_2(n))$$ O ( n g l o g 2 ( n ) ) ist, wobei $$glog_2(n)$$ g l o g 2 ( n ) den ganzzahligen Anteil des dualen Logarithmus $$log_2(n)$$ l o g 2 ( n ) von n bezeichnet. In diesem Kapitel stellen wir die Grundlagen der Wahrscheinlichkeitstheorie vor. Weil uns die Hilfsmittel aus der Analysis und der mathematischen Maßtheorie nicht zur Verfügung stehen, beschränken wir uns auf die sogenannte diskrete Wahrscheinlichkeitstheorie. Diese ist für die meisten Anwendungen von Wahrscheinlichkeiten in der Informatik ausreichend.