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.

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.