Stochastik für Informatiker

Das vorliegende Buch entstand aus einer Reihe von Vorlesungen, die wir an der Rheinisch-Westfcilischen Technischen Hochschule Aachen, der European Business School, der Universitat Oldenburg und der Universitat Augsburg seit 1984 ge halt en haben. Diese Vorlesungen wandten sich vor allem an Informatikstudenten und Mathematikstudenten mit Nebenfach Informatik mit dem Ziel, stochastische Grundbegriffe unter besonderer Beriicksichtigung Informatik-spezifischer Aspekte zu vermitteln. Unter den zahlreichen Einsatzfeldern stochastischer Methoden in der Informatik seien hier beispielhaft genannt: Die Average-Case-Analyse von Algorithmen, die stochastische Automatentheorie, Anwendungen im Bereich des CAD (Bezier-Kurven und -Flii.chen), stochastische Informationstheorie und Codierungstheorie, Rechnernetze und Leistungsbewer tung von Rechnersystemen (Warteschlangenprobleme), Bildverarbeitung (Compu tertomographie), automatische Spracherkennung (Hidden-Markov-Modelle), Ex pertensysteme (effiziente Bereclmung von bedingten Wahrscheinlichkeiten), kiinst liche Intelligenz (Neuronale Netze), stochastische Optimierungs- und Suchverfah ren (Simulated Annealing), stochastische Simulation, probabilistische Algorithmen u.v.a .. Die zum Verstiindnis benotigten theoretischen Grundlagen, die erfahrungsgemiill haufig weit iiber den in einfiihrenden Veranstaltungen angebotenen Stoff hinausge hen, sind dementsprechend vielfci.ltig und reichen von einfachen kombinatorischen Uberlegungen bei einigen Problemen der Average-Case-Analyse von Algorithmen bis hin zu tiefliegenden Satzen der axiomatischen Wahrscheinlichkeitstheorie, etwa bei den Markoff-Ketten und -Prozessen oder der Theorie der Punktprozesse im Bereich der Bildverarbeitung.

Inhalt

1. Grundbegriffe der Wahrscheinlichkeitstheorie.- 1.1. (?-Algebren und Wahrscheinlichkeitsmaße.- 1.2. Verteilungsfunktionen und Dichten.- 1.3. Zufallsvariablen und ihre Verteilung.- 1.4. Produkträume und Zufallsvektoren.- 1.5. Aufgaben.- 2. Transformation und Integration von Zufallsvariablen.- 2.1. Spezielle Verteilungen.- 2.2. Erwartungswert und Varianz.- 2.3. Grenzwertsätze.- 2.4. Aufgaben.- 3. Grundlagen Stochastischer Prozesse.- 3.1. Bedingte Verteilungen und Erwartungswerte.- 3.2. Markoff-Ketten.- 3.3. Simulated Annealing.- 3.4. Markoff-und Punktprozesse.- 3.5. Aufgaben.- 4. Probabilistische Analyse von Algorithmen.- 4.1. Sortier- und Suchverfahren.- 4.2. Markoff-Modelle für Algorithmen.- 4.3. Konvexe Hüllen von Zufallspunkten.- 4.4. Aufgaben.- 5. Elemente der Informationstheorie.- 5.1. Information und Entropie.- 5.2. Optimale Codierung.- 5.3. Binäre Suchbäume.- 5.4. Stationäre Quellen und Markoff-Quellen.- 5.5. Aufgaben.- 6. Simulationsverfahren.- 6.1. Erzeugung von Zufallszahlen.- 6.2. Testen von Zufallszahlen.- 6.3. Transformationsverfahren.- 6.4. Aufgaben.- Literatur.- Symbolverzeichnis.