Bücher der Reihe Teubner Texte Zur Informatik

be­ ziehen sich viele Veröffentlichungen auf eingeschränkte Netzklassen.

Dieses Buch hat die sogenannte average-case Komplexitätstheorie zum Gegenstand, ein vergleichsweise junges Gebiet der strukturellen Komplexitätstheorie. Die "klassische" strukturelle Komplexitätstheorie untersucht, wie schwierig ein al­ gorithmisches Problem im schwierigsten Fall (worst-case) ist. Ein solches algorith­ misches Problem ist zum Beispiel das Traveling Salesman Problem: gegeben eine Menge von Städten mit einer Entfernungstabelle, man suche die kürzeste Route, die einen Handlungsreisenden alle Städte genau einmal besuchen läßt und ihn an seinen Ausgangsort zurückbringt. Jede konkrete Entfernungstabelle ist eine soge­ nannte Probleminstanz des obigen, allgemeinen Problems. Vom Traveling Salesman Problem wird angenommen, daß es im worst-case sehr schwierig ist, d. h. , jeder Algo­ rithmus, der zu jeder Probleminstanz eine Lösung findet, benötigt für einige "schwie­ rige" Eingaben eine sehr lange Laufzeit. In der Praxis beobachtet man aber häufig bei derartigen worst-case schwierigen Problemen, daß man die tatsächlich auftreten­ den Probleminstanzen in sehr kurzer Zeit lösen kann, daß also das Auftreten von schwierigen Probleminstanzen sehr unwahrscheinlich ist. Unterliegt die Eingabe ei­ ner Wahrscheinlichkeitsverteilung, so ist es daher wichtig zu wissen, wie die mittlere Laufzeit eines Algorithmus zum Lösen des Problems aussieht. Man interessiert sich somit dafür, wie aufwendig die Problemlösung im Mittel ist, d. h. zum Beispiel welche mittlere Laufzeit ein optimaler Lösungsalgorithmus hat. Die average-case Komple­ xitätstheorie beschäftigt sich mit der Frage nach dem mittleren Aufwand, der zum Lösen einer Probleminstanz notwendig ist, wenn die Probleminstanzen einer gege­ benen Verteilung unterliegen.

Das vorliegende Lehrbuch beschaftigt sich in mathematisch praziser Weise mit ei- nem ganz und gar praktischen Thema, namlich dem Entwurf von Hardware. Kapitel 1 enthalt eine Diskussion mathematischer Grundbegriffe. In den Kapiteln 2 bis 4 werden die notwendigen theoretischen Grundlagen uber Boole'sche Ausdrucke, Schaltkreiskomplexitat und Rechnerarithmetik behandelt. Der Ubergang von der abstrakten Schaltkreistheorie zum Entwurf konkreter Schaltungen findet nahtlos in Kapitel 5 statt, wo aus den Verzogerungszeiten von Gattern das zeitliche Verhal- ten von Flipflops und anderen Speicherbausteinen abgeleitet wird. Kapitel 6 enthalt dann das vollstandige Design eines einfachen Rechners. Das Lehrbuch ist aus Vorlesungen des zweiten Autors entstanden. Kapitel 2 bis 6 enthalten den Stoff fur eine einsemestrige Anfangervorlesung. Kapitel 1 ist mehr ein Nachschlagewerk fur nagende Fragen, die sich fruher oder spater einstellen. Kapitel und Abschnitte, die mit einem Stern gekennzeichnet sind, kann man uberspringen. Die Darstellung groer Teile der Kapitell, 5 und 6 ist neu. Die Kapitel 2 bis 4 haben einen erheblichen Anteil an fortgeschrittenem Material. Es hat sich jedoch gezeigt, da Erstsemester damit keine besonderen Schwierigkeiten haben. Im Einzelnen enthalt Kapitell eine Entwicklung des formalen Mengenkonzepts in einer fur Studienanfanger verstandlichen Form. Die Satze und Beweise in diesem Kapitel sind von vorne bis hinten klassische Mathematik. Der Standpunkt, von dem aus wir sie interpretieren, ist bewut ubermutig und nicht klassisch. Wir wollen damit den Studierenden schmackhaft machen, von Zeit zu Zeit auch Wohlvertrautes von einem frischen - naturlich nicht unsinnigen - Standpunkt aus zu betrachten. Das ist insbesondere beim Forschen manchmal sehr nutzlich.

Ziel des Buches ist es, ein Framework für eine modellseitig mächtige und gleichzeitig effiziente multidimensionale Datenanalyse, basierend auf einem relationalen Datenbanksystem, zu beschreiben. Die multidimensionale Datenanalyse ist im Kontext des "Decision Support" für eine flexible und umfassende betriebs- und volkswirtschaftliche Informationsversorgung einer Organisation verantwortlich und reflektiert somit auf technischer Ebene die zentrale Anwendung basierend auf einer "Data Warehouse"-Datenbasis.

Im vorliegenden Buch wird, basierend auf meiner Dissertation, die Kon­ zeption und Implementierung einer graphischen Arbeitsumgebung fUr das VLSI-Entwurfssystem CADIC beschrieben, welches im Rahmen des Sonder­ forschungsbereiches 124 im Teilprojekt B1 an der Universit?t des Saarlandes entwickelt wurde. Gegenuber anderen Entwurfssystemen zeichnet es sich durch eine besonders flexible Beschreibungsebene aus, die auf einem wohldefinier­ ten mathematischen Kalkiil basiert. Diese gew?hlte Grundlage erweist sich als m?chtiges Werkzeug zur Beschreibung ganzer Klassen von Schaltkreisen durch eine feste Zahl von graphischen Eingaben. Die Spezifikationsebene erlaubt so­ wohl eine Parametrisierung von Schaltungen in Abh?ngigkeit von beispielswei­ se der Operandengrof3e als auch eine generische und damit wiederverwendbare Beschreibung von Berechnungsnetzen. Aus einer derart definierten Schaltungsklasse wahlt der Entwerfer dann einen Vertreter fUr die weiteren Konstruktionsschritte aus, indem er die formalen Parameter des Entwurfs durch konkrete Werte ersetzt. Durch die Integration der Entwurfswerkzeuge in eine gemeinsame graphische Umgebung konnen die berechneten Ergebnisse direkt auf der mathematisch basierten Spezifikation visualisiert werden. Dies stellt dem Entwerfer verbunden mit einer interakti­ ven Navigation durch die Schaltungshierarchie eine komfortable Methode zur Lokalisierung von kritischen Entwurfsstellen zur VerfUgung.

Kaufmännisch-administrative Anwendun­ gen wie Platzbuchungssysteme in Reisebüros oder Online-Buchungssyteme bei Banken fra­ gen typischerweise die klassische Datenbankfunktionalitätnach und werden komfortabel be­ dient.

Evolution in Objekt-Datenbanken behandelt die zunehmende Notwendigkeit der Anpassung bestehender Informationssysteme an das ständig zu erweiternde "Universe of Discourse" . Es handelt sich dabei um eine Thematik, die in jüng­ ster Zeit zentrale Bedeutung erhalten hat, und von der man glaubt, oder doch zumindest hofft, heute käufliche Datenbanksysteme hätten längst die entspre­ chenden Lösungen realisiert. Das Problem kann in zwei Dimensionen betrachtet werden. Die erste ist fast schon klassisch, sie betrachtet die Schemaevolution zur Anpassung von Datenbanken an geänderte Anforderungen. Die zweite Dimension wurde erst in den letzten Jahren als Teilproblem bei der Integration bzw. Interoperabilität von verschiedenen Datenbanken bekannt. Erneut sollen Schemata, jetzt aber aus mehreren Datenbanken, verändert werden, mit dem Ziel einer flexiblen Integration teilweise überlappender und möglicherweise gar widersprüchlicher "Universes of Discourse" . Beide Dimensionen sind bislang sowohl in existierenden Systemen wie auch in der Forschung unbefriedigend gelöst. Formale und systemtechnische Grund­ lagen sowie umfassende und realisierbare Konzepte waren bislang nur im Ansatz vorhanden. Bei diesem Buch handelt es sich um einen der wenigen Texte, die sich mit der Problematik dynamischer Veränderungen in Objektbanken systematisch auseinandersetzen. Der Autor präsentiert einen durchgängigen, auf wenigen Grundprimitiven aufbauenden Ansatz, der in Teilen im Forschungsprojekt CO­ CO ON realisiert wurde.

Die vorliegende Arbeit entstand während meiner Tätigkeit als wissenschaftlicher Mitarbeiter am Lehrstuhl für Informatik IV (Prof. Dr. O. Spaniol) der Rheinisch­ Westfälischen Technischen Hochschule Aachen. Herrn Prof. Dr. Otto Spaniol, der durch seine Anregungen, seine konstruktive Kritik und durch die mir gewährten Freiheiten viel zum Gelingen dieser Arbeit beigetragen hat, gilt mein persönlicher Dank. Herrn Prof. Dr. Wolfgang Effelsberg (Universität Mannheim) danke ich besonders herzlich für seine Bereitschaft zur Übernahme des Korreferats und für sein Interesse an meiner Arbeit. Danken möchte ich auch allen meinen Kollegen am Lehrstuhl und den Studenten, die auf die eine oder andere Weise einen Beitrag zum Entstehen und Gelingen der Arbeit geleistet haben und hier nicht alle genannt werden können. Besonders hervorheben möchte ich jedoch Herrn Kai Jakobs und Herrn Prof. Dr. Peter Martini, die mir insbesondere in der Anfangsphase bei der Auffindung meines wissenschaftlichen und beruflichen Weges hilfreich waren und Herrn Bernd Heinrichs und Herrn Christian Engel, die mir in ähnlicher Weise in der Schlußphase dieser Arbeit sehr geholfen haben. Ganz besonderes danken möchte ich den Menschen, die in anderer Weise beim Gelingen und beim Abschluß dieser Arbeit für mich sehr wichtig waren. Namentlich erwähnen möchte ich hier nur meine Frau Cordula Rupprecht, die wahrscheinlich mehr zu dieser Arbeit beigetragen hat, als ich bis heute begriffen habe und meinem Vater, der durch mich nicht nur Probleme mit dem Korrekturlesen dieser Arbeit hatte.

Multimedia bezeichnet die rechnergestützte, integrierte Verarbeitung zeitinvarianter (Text, Graphik und Bild) und zeitvarianter Medien (Audio, Video und Animation). Die meisten Multimedia-Anwendungen sind durch eine starke Interaktivität gekenn­ zeichnet, durch die ein Benutzer die Auswahl und Präsentation multimedialer Infor­ mationen steuern kann. Aufgrund der zunehmenden Leistungsfähigkeit und fallenden Preise multimedia­ fahiger Rechner erschließen sich Multimedia-Anwendungen einem immer größer werdenden Anwenderkreis. Die für die Anwendungsentwicklung gegenwärtig zur Verfügung stehende Hardware erfordert geeignete Software-Umgebungen, die sich nicht nur auf eine ansprechende Gestaltung der Benutzerschnittstellen beschränken, wie an zahlreichen Multimedia-Erweiterungen von Betriebs-, Datenbank- und Kom­ munikationssystemen zu erkennen ist. Die wesentliche Motivation für die Entwick­ lung von Multimedia-Anwendungen besteht jedoch darin, die Effektivität der Kom­ munikation zwischen Benutzern und Rechnern durch die Integration zeitvarianter Medien in die Benutzerschnittstelle zu erhöhen. Aus diesem Grund wird gegen­ wärtig weltweit intensiv an Multimedia-Erweiterungen von Werkzeugen für die Ent­ wicklung von Benutzerschnittstellen· gearbeitet. Diese Erweiterungen erfordern grundlegende Änderungen der zugrundeliegenden Modelle, da die Medien Video, Audio und Animation eine zeitliche Ausprägung besitzen. Dabei kommt den sogenannten Dialogmodellen für die Beschreibung der Struktur und des zulässigen Verlaufs der Kommunikation zwischen einem Benutzer und einer Anwendung eine besondere Bedeutung zu. Multimediaspezifische Dialog­ modelle müssen neben der Interaktivität insbesondere die rechnergestützte Medien­ integration berücksichtigen.

Technik besitzt stets einen ausgepragten gesellschaftlichen Bezug, da sie die gesell­ schaftlich relevante Umsetzung wissenschaftlicher Erkenntnisse darstellt. Dies fuhrt zu Problemen, die oft im Kontext der wissenschaftlichen Forschung unterschatzt oder gar ignoriert werden. Eines davon ist, daB an jede Technik Mindestanforde­ rungen gestellt werden, urn ihren Einsatz rechtfertigen zu konnen. Dazu gehort durchweg ihre Zuverlassigkeit haufig sogar mit hochster Prioritat. Ein anderes damit zusammenhangendes Problem bildet die Akzeptanz technischer Systeme. Hierbei kann die Zuverlassigkeitsbewertung sicherlich sinnvolle Hilfestellungen leisten, aber leider auch miBbraucht werden. Eine Reihe technischer und insbesondere informationstechnischer Systeme erful­ len Aufgaben, bei denen der Zuverlassigkeitsaspekt sowohl aus rein technischer als auch aus gesellschaftlicher Sicht dominiert. Zahlreiche technische Systeme werden jedoch in Bereichen eingesetzt, in denen ihre Zuverlassigkeit nicht so spektakular ist, aber StOrungen ihres Betriebs fur mehr oder weniger starke finanzielle Ein­ buBen, mitunter sogar fur einen Firmenruin verantwortlich sind. Ein Bedarf nach zuverlassigen technischen Systemen ist also auch aus dieser Sicht vorhanden und nimmt mit dem verstarkten Einsatz immer komplexerer Systeme weiterhin zu. Die Technik kann sich nur dann als vertrauenswiirdig erweisen, wenn die Zuverlassig­ keit ihrer Systeme ausreichend beachtet, korrekt bewertet und infolgedessen durch entsprechende MaBnahmen in erforderlichem MaBe sichergestellt wird.

Die elektronische Datenverarbeitung dringt immer mehr in alle Lebensbereiche vor. Computer werden immer leistungsfähiger und preiswerter. Im Rahmen dieser Tendenzen wächst auch die Speicherkapazität der Rechner mit jeder neuen Rechnergeneration. Als entscheidender Faktor der Entwicklung in den letzten Jahren ist jedoch die weltweite Ver­ netzung von Rechnern zu nennen, die es ermöglicht hat, daß in kürzester Zeit viele neue Anwendungsgebiete erschlossen wurden und neue, stark expandierende Wirtschafts­ zweige entstanden sind. Vielfach wird das Zeitalter der Informationstechnologie heute schon proklamiert. Information ist zu einer kostbaren Ressource geworden, die genutzt werden kann und muß, um die Konkurrenzfähigkeit von Unternehmen sicherzustellen. Angesichts dieser Entwicklung ist es nicht verwunderlich, daß der Verfügbarkeit von Da­ ten eine zunehmend große Bedeutung beigemessen wird. Die Replikation von Daten ist das wichtigste und effektivste Mittel zur Erreichung einer hohen Verfügbarkeit in verteil­ ten Datenverwaltungssystemen. Durch Replikation wird die Zugriffslokalität ermöglicht, die für akzeptable Antwortzeiten oft vorausgesetzt werden muß. Da die Speicherkapazi­ tät der Rechner einen ständig geringer werdenden Kostenfaktor darstellt, lohnt sich die Replikation von Daten, zumindest bei Daten, die selten geändert werden, immer mehr.

Dieses Buch spannt einen Bogen von den Defekten bei der Halbleiterfertigung über die klassischen Testmethoden hin zu Selbsttestverfahren und den neuesten Forschungsarbeiten, die auf eine Integration von Entwurf und Test zielen und aus Verhaltensbeschreibungen automatisch gut testbare Schaltungen synthetisieren.

Dieses Lehrbuch beschäftigt sich in mathematisch präziser Weise mit einem ganz und gar praktischen Thema, nämlich dem Entwurf digitaler Hardware. Neben einer Diskussion der mathematischen Grundbegriffe werden die notwendigen theoretischen Grundlagen behandelt. Schließlich wird dann das vollständige Design eines einfachen Rechners entwickelt.

beispielsweise zur Formulierung von Anfragen oder Transaktionen, keine formale Semantik besitzen.

It is the good reader that makes the good book. RALPH WALDO EMERSON, Society & Solitude. In the course of two projects, the author of this book was involved in the design of the platforms PARFORM [CS93) and LOLA [Cap94), [CS) for the support of parallel computing in distributed systems. The former system was geared towards the highly efficient use of idle resources in networks of workstations, and the latter system was intended as a scalability study: How many workstations in the global Internet can be used simultaneously for solving a massively parallel problem? In one of the experiments conducted with these systems, up to 800 workstations on all five continents were cooperating for the solution of a search problem from molecular biology [Cap94). The most important lessons which the author was forced to learn during the course of these projects were not to rely on any documentation of network-and low-level system-calls, to use neither common sense nor mathematical logic during the design of a large distributed system, but to be happy with a working program, and not to ask, why it would work.