Bücher der Reihe Leitfaden Und Monographien Der Informatik

Die beiden Bande "e;Mathematik fur Informatiker"e; , deren ersten wir hiermit vor- legen, beruhen auf einem viersemestrigen Vorlesungskurs, den die beiden Verfasser in den letzten Jahren an der Universitat Paderbom gehalten haben. Die Schwie- rigkeiten einer solchen Vorlesung liegen auf der Hand: Einerseits kann und darf auf mathematische Exaktheit nicht verzichtet werden, andererseits passen -auch wegen der Kurze der zur Verfugung stehenden Zeit -zu komplexe mathematische Begriffe und langwierige Beweise nicht in eine solche Vorlesung. Bei der Planung dieser Vor- lesung versuchten wir, soweit dies moglich war, den algorithmischen Standpunkt in den Vordergrund zu stellen. Bei den Beweisen wurde, wann immer dies moglich war, einer konstruktiven Version der Vorzug gegeben. So enthalt dieses Buch manche Details, die ublicherweise in den Rahmen einer Numerikvorlesung fallen. Nach dem einleitenden Kapitel 1 behandelt Kapitel 2 die Grundlagen der Ma- trizenrechnungj die Kapitel 3 -6 stellen Hilfsmittel aus der Analysis bereit. Kapitel 2 und Kapitel 3 -6 sind voneinander unabhangig und konnen auch in umgekehrter Reihenfolge studiert werden. Zur Zitierweise: Innerhalb eines Kapitels werden die einzelnen Abschnitte in der Form (1.1) zitiert, Formelnummern in der Form (1.1.1). Verweise auf andere Kapitel geschehen in der Form 1(1.1). Am Schlu werden die Lehrbucher aufgefuhrt, auf die im Text hingewiesen wird. Auerdem werden einige Lehrbucher angegeben, die den Stoff dieses Bandes vertiefen.

von Workstations der Bedarf nach Hin­ tergrundwissen im Bereich des physikalischen Entwurfs.

Hiermit legen wir den abschlieBenden Band unserer "Mathematik fiir Informati­ ker" vor. Auch hier haben wir uns bemiiht - soweit dies bei dem diesmal anspruchs­ volleren Stoff maglich ist - den algorithmischen und konstruktiven Aspekt in den Vordergrund zu stellen. Die Stoffauswahl wurde u. a. dadurch bestimmt, daB auch auf die Bediirfnisse der Informatiker mit technischen Nebenfachern eingegangen wurde - so ist ein ausfiihrliches Kapitel iiber Funktionen mehrerer Veranderlicher entstanden, welches fiir den "Nurinformatiker" erst in zweiter Linie interessant ist. Zum Inhalt: In Kapitel VII werden numerische Fragen aus der Linearen Algebra und der Analysis behandelt. Nach einer Einfiihrung in die Gleitpunktarithmetik - die nur bei der ml. merischen Behandlung von linearen Gleichungssystemen in Kapitel VII, §2 und der Fehlerabschatzung bei der Berechnung von Eigenwerten von Tridiagonalmatrizen in Kapitel VIII, §5 benatigt wil'd - werden in §2 Fehlerab­ schatzungen fiir die Lasung von linearen Gleichungssystemen bei Spaltenpivotsuche und Totalpivotsuche hergeleitet. Unitare und orthogonale Matrizen werden in §3 eingefiihrt; neben dem numerisch ungiinstigen Orthogonalisierungsverfahren nach E. Schmidt wird in §4 die QR-Zerlegung einer Matrix nach Householder behandelt, und es wird auf die Anwendung dieser Zerlegung beim Lasen linearer Gleichungs­ systeme hingewiesen. Weitel'e Methoden zur Lasung von linearen Gleichungssy­ stemen werden in Kapitel IX, §3 behandelt, namlich das Gesamtschrittverfahren [Jacobi-Verfahren] und das Einzelschrittverfahren [GauB-Seidel-Verfahren]. Zum Verstandnis der erst en 4 Paragraphen von Kapitel VII l'eichen die Kenntnisse aus Kapitel II aus.

Die Ausgangsbasis fiir die Erstellung dieses Buches waren Vorlesungen iiber Grundlagen wissensbasierter Systeme und iiber Deduktionssysteme. Ein zen­ trales Thema dieser Veranstaltungen ist die Frage, inwieweit und mit wel­ chen Verfahren man entscheiden kann, ob aus einem Ausdruck ein anderer Ausdruck folgt. Flir die Pradikatenlogik und deren Teilklassen tritt diese Problemstellung z.B. in der Logik-Programmierung, dem automatischen Be­ weisen, in Inferenzkomponenten wissensbasierter Systeme und - aquivalent formuliert - als Erfiillbarkeitsproblem auf. Es hat sich dabei herausgestellt, daB selbst die fiir die Aussagenlogik interes­ santen Resultate zu reichhaltig sind, urn sie zusammen mit der Pradikaten­ logik in nur einem Zyklus zu behandeln. Da aber viele Ergebnisse fiir eine effiziente Behandlung der vollen Pradikatenlogik von groBem N utzen sind, haben wir uns entschlossen, die Themenbereiche, die von allgemeinem Inter­ esse sind, zu sammeln, zusammenhangend aufzuarbeiten und in Buchform zu veroffentlichen. Aber selbst die Beschrankung auf die Aussagenlogik ist nicht ausreichend, urn wirklich aile Problemstellungen und Ansatze aufzu­ nehmen. Wir haben daher hier zu Gunsten der Grundlagen und von eher klassischen Inhalten auf Abschnitte iiber z.B. die mehrwertige Aussagenlogik verzichtet.

Die Computergraphik beschäftigt sich mit der Erzeugung und Manipulation von Bildern durch einen Computer. Die erzeugten Darstellungen sind meistens Ab­ bilder von nicht in der Realität existierenden Objekten, die mit mathematischen Verfahren definiert sind. Ein wesentliches Ziel dabei ist es, den dargestellten Objekten ein möglichst realistisches Aussehen zu verleihen, so daß sie von real existierenden Objekten nicht zu unterscheiden sind. Dadurch wird ein Durch­ mischen und Überblenden von real existierenden und synthetisch definierten Objekten ermöglicht, die Grenzen zwischen Realität und Illusion verschwim­ men. Dies wird insbesondere von der Film-und Werbeindustrie ausgenutzt, um beim Zuschauer je nach Situation Interesse, Neugier, Verwunderung oder Verblüffung hervorzurufen. Neben diesem vielleicht als Spielerei und unwissenschaftlich zu bezeichnenden Einsatzgebiet haben die Verfahren der Computergraphik mittlerweile Einzug in viele Bereiche des täglichen Lebens genommen. Dabei sind Anwendungen in der Medizin zu nennen, wo z. B. bei der Computertomographie mit Hilfe der Computergraphik ein dreidimensionales Modell eines nicht sichtbaren Be­ reiches des menschlichen Körpers gewonnen wird. Weitere Anwendungsgebiete sind der weite Bereich der CAD (computer aided design), der im Maschinenbau und der Fahrzeugindustrie eine große Rolle spielt, und der Bereich der Archi­ tektur, wo mit Hilfe des Computers ein Modell des zu erstellenden Gebäudes erzeugt werden kann. Mit Raumplanungswerkzeugen kann ein genaues Modell der Innenräume des Gebäudes entworfen werden, an dem besser als mit jedem anderen Modell aus Pappe oder Holz die Licht-und Klimaverhältnisse vor Fer­ tigstellung des Gebäudes genau analysiert und gegebenenfalls verändert werden können.

Der Entwurf und die Analyse von Datenstrukturen und effizienten Algorithmen hat in den letzten Jahren große Bedeutung erlangt: Algorithmus ist der zentrale Begriff der Informatik und Effizienz bedeutet Geld. Ich habe den Stoff in drei Bände und neun Kapitel gegliedert. Band 1: Sortieren und Suchen (Kapitel I bis ill) Band 2: Graphenalgorithmen und NP-Vollständigkeit (Kapitel IV bis VI) Band 3: Mehrdimensionales Suchen und Algorithmische Geometrie (Kapitel VII und Vill), Algorithmische Paradigmen (Kapitel IX) Die Bände 2 und 3 haben Band 1 als gemeinsame Basis, sind aber voneinander un­ abhängig. Große Teile dieser Bände können ohne detaillierte Kenntnis von Band 1 gelesen werden; eine Kenntnis der algorithmischen Grundprinzipien, wie sie etwa in Kapitel I oder in vielen anderen Büchern über Datenstrukturen und Algorith­ men vermittelt werden, genügt. Die spezifischen Voraussetzungen für die Bände 2 und 3 sind in den jeweiligen Vorworten angegeben. In allen drei Bänden stellen wir wichtige effiziente Algorithmen für die grundlegenden Probleme in dem jeweiligen Gebiet vor und analysieren sie. Wir messen dabei Effizienz durch die Laufzeit auf einem realistischen Modell einer Rechenanlage, das wir in Kapitel I einführen. Die meisten der vorgestellten Algorithmen wurden erst in den letzten Jahren gefunden; die Informatik ist ja schließlich eine sehr junge Wissenschaft. Es gibt kaum Sätze in diesem Buch, die älter als 20 Jahre sind, und mindestens die Hälfte des Stoffes ist jünger als 10 Jahre. Ich habe stets versucht, den Leser bis an den Stand der Forschung heranzuführen.

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.

Grundlage der Effizienz von Algorithmen bilden, und weniger die begleitenden Datenstrukturen der Algorithmen betont.