Leitfäden und Monographien der Informatik – serie

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.

Die Theoretische Informatik ist älter als die Praktische, Angewandte oder Techni­ sche Informatik. Daher ist sie als wissenschaftliche Disziplin bereits weiter ausgebaut als andere Bereiche der Informatik, und ihre Ergebnisse sind schwerer zugänglich, da sie auf ein größeres und tieferes Fundament aufbauen. Stark verästelte Theorien tendieren dazu, sich als Selbstzweck aufzufassen und als l'art pour l'art betrieben zu werden. In der vorliegenden Einführung in die Theoretische Informatik begegnen wir dieser Gefahr, indem wir die Orientierung moderner Theorien an den Anwendun­ gen in den Mittelpunkt stellen. Schon Novalis (1772~ 1801) hat darauf hingewiesen, daß die Theorie häufig den Anwendungen vorauseilt: "Wenn die Theorie auf die Erfahrung warten sollte, so käme sie nie zustande. " Nicht immer sind die Anwendungen von Ergebnissen der Theoretischen Informatik so direkt zu sehen wie die Anwendungen anderer Zweige der Informatik. Dies gilt insbesondere für negative Resultate. Dabei sind deren Konsequenzen klar. Wenn wir beweisen, daß es bestimmte für die Praxis wünschenswerte Werkzeuge oder Algorithmen nicht geben kann, muß die unsinnige, weil hoffnungslose Arbeit an diesen Werkzeugen oder Algorithmen eingestellt und statt dessen die Suche nach bestmöglichen Auswegen begonnen werden. Andererseits sind positive Resultate nicht automatisch anwendungsorientiert. Exi­ stenzaussagen oder Algorithmen mit exponentieller oder noch größerer Laufzeit sind häufig praktisch wertlos. Das Neue an der vorliegenden Einführung in die Theore­ tische Informatik ist die konsequent algorithmenorientierte Sichtweise (zum didak­ tischen Hintergrund siehe Wegener (1992)). Stets wurde bei positiven Resultaten eine Umsetzung in praktisch und theoretisch effizienteAlgorithmen angestrebt.

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.

Dieses Buch entstand aus Manuskripten des Autors zu Informatik-I-Vor­ lesungen an der Christian-Albrechts-Universität Kiel und der Eberhard­ Karls-Universität Tübingen. An diesen Universitäten wird die Informatik­ I-Vorlesung außer von den Hauptfachstudenten der Informatik und den Ne­ benfachstudenten aus der Mathematik und Physik und ggf. weiterer N atur­ wissenschaften auch von "fachfremden" Studenten der Studiengänge Wirt­ schaftswissenschaften (Kiel) und Allgemeine Sprachwissenschaft (Tübingen) besucht. Es kommt daher darauf an, neben einer allgemeinen Einführung in Methoden der Informatik und speziell der Programmierung Verständnis für das Wesen der Informatik als einer formalen, der Mathematik nahe verwand­ ten Wissenschaft zu wecken und im übrigen die notwendigen mathematischen Grundlagen innerhalb der Vorlesung selbst anzubieten. Das Buch eignet sich zu Informatik-Grundkursen für Natur-und Geistes­ wissenschaftler, aber auch zur Informatik-Nebenfachausbildung allgemein sowie, je nach Studienplan, auch für Informatik-I-Vorlesungen. Darüber hin­ aus ist es auch zu einem Selbststudium von Informatik-Grundkenntnissen ge­ eignet; hierzu dienen unter anderem auch die aufgeführten Übungen und ihre im Anhang vorgestellten Lösungen. Es muß jedoch entsprechend dem Cha­ rakter der Informatik ein gewisses mathematisches Rüstzeug mitgebracht werden oder doch zumindest die Bereitschaft, sich dieses anzueignen. Im Anhang listen wir (im Sinne einer Festlegung von Notationen) die notwen­ digsten mathematischen Konstruktionen auf; darüber hinaus wird auf die angegebenen Lehrbücher verwiesen.

In den letzten Jahren sind ein Vielzahl neuer Rechnerstrukturen entstanden. Diese unterscheiden sich sehr stark in der Anzahl der Prozessoren, in den Möglichkeiten der Kommunikation und damit auch in der Leistungsfähigkeit. Für den Benutzer solcher parallelen Architekturen wird es immer schwieriger, seine Probleme effizient auf einem bestimmten System zum Laufen zu bringen. Es genügt nicht mehr, einen Algorithmus für eine Problem­ stellung zu finden und zu programmieren. Der Benutzer muß in Kenntnis der Architektur den Algorithmus finden, der auf der ausgewählten Struktur eine effiziente Behandlung der Problemstellung gewährleistet. Es wird immer klarer, daß die Architektur, die Kommunikation und der gewählte Algorithmus als Einheit zu sehen sind. Dieses Buch soll sowohl dem Studenten als auch dem Praktiker eine Einführung in die Hard- und Software von Parallelrechnerarchitekturen geben und ihm ein Gefühl für das notwendige Zusammenspiel der Komponenten Architektur, Kommunikation und Algorithmus vermitteln. Es werden Grundkenntnisse in Rechnerarchitektur und Linearer Algebra für das Verständnis dieses Buches voraus­ gesetzt. VI Mein besonderer Dank gilt den Professoren Dr. U. Herzog, Dr. W. Händler und Dr. W.D. Geyer, die diese Arbeit begutachtet haben. Mein Dank gilt insbesondere auch Frau ehr. Moog, die mit großer Geduld die Bilder für dieses Buch gezeichnet hat. Letztlich gilt mein Dank auch den Herausgebern der Reihe "Leitfäden und Monographien der Informatik" sowie dem Teubner-Verlag, die die Herausgabe dieses Buches ermöglichten.

Vierzig Jahre, nachdem John von Neumann sein Konzept eines rechnenden, programmgesteuerten Automaten entworfen hat, setzt sich nun in der Informatik die Erkenntnis durch, daß sequentiell arbeitende Rechner für manche Probleme zu langsam arbeiten. Mit vielen, parallel arbeitenden Prozessoren versucht man heutzutage in Multiprozessoranlagen, den "von Neumann-Flaschenhals" zu umgehen. Dabei ergeben sich eine Menge neuer Probleme: Die Aktivität der Prozessoren muß synchronisiert werden, die Daten müssen effektiv verteilt werden und "Knoten" im Datenfluß (hot spots) zwischen den Prozessoren und dem Speicher müssen vermieden werden. Dazu werden Mechanismen benötigt, um auftretende Defekte in ihren Auswirkungen zu erfassen und zu kompensieren, das Gesamtsystem zu rekonfigurieren und alle Systemdaten zu aktualisieren. Bedenken wir noch zusätzlich die Schwierigkeiten, die mit einer parallelen Programmierung der eigentlichen Probleme verbunden sind, so können wir uns nur wundem, wieso wir Menschen "im Handumdrehen" und "ganz natürlich" Leistungen erbringen können, die mit den heutigen Rechnern bisher nicht nachvollziehbar waren. Betrachten wir beispielsweise die Probleme der "künstlichen Intelligenz", besser "wissensbasierte Datenverarbeitung" genannt, so hinken die heutigen Systeme zum Sehen. Hören und Bewegen hoffnungslos der menschlichen Realität hinterher. Weder in der Bildverarbeitung und -erkennung, noch in der Spracherkennung oder in der Robotersteuerung reichen die Systeme in Punkto Schnelligkeit (real-time), Effektivität und Flexibilität (Lernen) oder Fehlertoleranz an die menschlichen Leistungen heran.

In den vergangenen Jahren wurde die Programmierung wm Rechenanlagen als diejenige Disziplin erkannt, deren Beherrschung grundlegend und entscheidend für den Erfolg vieler Entwicklungsprojekte ist und die wissenschaftlicher Behandlung und Darlegung zugänglich ist Vom Handwerk stieg sie zur akademischen Disziplin auf. Die ersten hervorragenden Beiträge zu dieser Entwicklung wurden von E. W. Dijkstra und C. A. R. Hoare geliefert Dijkstra's Notes on Struetured Programming [6J führten zu einer neuen Betrachtung der Programmierung als wissenschaftliches Thema und als intellektuelle Herausforderung. Sie bahnten den Weg zu einer "Revolution" in der Programmierung [35J. Hoare's An Axiommic Ba3is for Computer Programming [10J zeigte deutlich, dass Progamme einer exakten Analyse nach mathematischen Grundsätzen zugänglich sind. Beide Artikel argumentieren überzeugend, dass viele Programmierfehler vermieden werden können, wenn man den Programmierern die Methoden und Techniken, die sie bisher intuitiv und oft unbewusst verwendeten, zur Kenntnis bringt Diese Artikel konzentrierten sich auf die Aspekte des Aufbauens und Analysierens von Programmen oder, genauer ausgedruckt, auf die Struktur der durch die Progammtexte dargestellten Algorithmen. Es ist jedoch völlig klar, dass ein systematisches und wissenschaftliches Angehen der Konstruktion von Programmen seine grösste Wirkung im Fall grosser komplexer Programme hat, die komplizierte Datenmengen bearbeiten. Folglich muss eine Methodik des Programmierens auch alle Aspekte der Datenstrukturierung behandeln. Programme sind letztlich konkrete Formulierungen abstrakter Algorithmen, die sich auf bestimmte Darstellungen und Datenstrukturen stützen. Einen wesentlichen Beitrag, Ordnung in die verwirrende Vielfalt der Terminologie undKonzepte von Datenstrukturen zu bringen, leistete Hoare durch seine Notes on Daltl Strueturing [13J.

Die vorliegende zweite Auflage dieses Buches stellt eine vollständige Neubearbeitung der 1977 in diesem Verlag erschienenen Erstauflage sowie des 1981 von der Fernuniversität Hagen publizierten Fernstudienkurses "Betriebssysteme" dar. Der Text wurde mehrfach in vom Verfasser an der Abteilung Informatik der Universität Dortmund gehaltenen Vorlesungen benutzt und hat in der nun vorliegenden Form sicherlich beträchtlich von den zahlreichen Anregungen aus dem Kreise der Kollegen sowie der Studenten, die diese Vorlesungen hörten, profitiert. Die Darstellung ist orientiert an einer Gesamteinführung in die Aufgaben von Betriebssystemen moderner digitaler Rechnersysteme. Vom Leser werden lediglich Grundkenntnisse der Datenverarbeitung bzw. Informatik erwartet und diejenigen Teile des Textes, die gewisse mathematische Grundlagen erfordern, können ohne Einbuße für das Gesamtverständnis bei einem ersten Studium des Textes übergangen werden. Die Herausarbeitung der funktionalen Strukturen sowie die Motivation für die globalen Zusammenhänge der AufgabensteIlungen in komplexen Betriebssystemen ist ein besonderes Anliegen dieser Darstellung. Nach dem Durcharbeiten dieses Buches sollte der Leser in der Lage sein, eine selbständige Einordnung und Bewertung der AufgabensteIlungen, der Strukturen sowie der qualitativen und quantitativen Eigenschaften moderner Betriebssysteme vorzunehmen.

Dieses Buch behandelt Grundlagen von Programmiersprachen, deren Verknüpfung mit realen Rechenmaschinen und - exemplarisch - Algorithmen. Das Ziel des Buches ist es, eine solide Basis für das Studium der Informatik zu legen. Es ist ins­ besondere für Studenten im Grundstudium des Studienganges Informatik gedacht. Ein Programm ist nur dann brauchbar, wenn es das gestellte Problem korrekt löst, und dies darüber hinaus mit der gewünschten Effizienz tut. Aussagen über die Korrektheit und Effizienz eines Programms sind nur dann möglich, wenn die verwendete Programmiersprache exakt definiert ist, d.h., wenn die Menge der Pro­ gramme (Syntax) und deren Bedeutung (Semantik) festliegen. Die Definition von Syntax und Semantik nimmt daher in diesem Buch einen wichtigen Platz ein. For­ male Definitionen werden erst dann lebendig, wenn sie auf einem guten intuitiven Verständnis aufbauen, und wenn sie zu Folgerungen in der Form von Sätzen führen. Daher enthält dieses Buch eine große Anzahl von Beispielen, Sätzen und Aufgaben. Die Grundlagen der Programmiersprachen werden eingeführt anhand einer spezifischen Programmiersprache, PROSA genannt (PROgrammiersprache SAar­ brücken). PROSA ist der Programmiersprache Pascal sehr ähnlich, weicht aber in einigen Punkten (z.B. dynamische Felder, geschachtelte Verbunde) aus didaktischen Gründen ab. Die Abweichungen dienen zum einen der Vereinfachung, und zum an­ deren der lllustration einiger Konzepte, die Pascal nicht kennt. Die Benutzung von Pascal in einem begleitenden Programmierpraktikum stellt aber keinerlei Problem dar.

Der moderne Digital-Computer wurde entwickelt, um komplizierte und zeitraubende Berechnungen zu erleichtern und zu beschleunigen. Bei den meisten Anwendungen spielt seine Fähigkeit, grosse Mengen von Informationen zu speichern und wieder zugänglich zu machen, die wichtigste Rolle (und wird als Haupteigenschaft betrachtet): seine Fähigkeit zu rechnen, d.h. zu kalkulieren, Arithmetik auszuführen, ist in vielen Fällen nahezu belanglos. In allen diesen Fällen stellt die grosse Menge an Information, die in irgendeiner Weise verarbeitet werden muss, eine Abstraktion eines Teils der realen Welt dar. Die der Rechenanlage zur Verfügung stehende Information besteht aus einer ausgewählten Menge von Daten über die reale Welt, nämlich der für das vorliegende Problem als wichtig erachteten Menge, von der man annimmt, dass damit die gewünschten Resultate erzielt werden können. Die Daten stellen eine Abstraktion der Wirklichkeit dar, weil die für dieses bestimmte Problem nebensächlichen und belanglosen Eigenschaften und Besonderheiten der realen Objekte unberücksichtigt bleiben. Eine Abstraktion ist somit auch eine Vereirifachung der Tatsachen. Als Beispiel können wir die Personalkartei eines Arbeitgebers betrachten. Jeder Angestellte ist in dieser Kartei (abstrahiert) vertreten durch eine Menge von Daten, die für den Arbeitgeber, bzw. für seine Abrechnungen wichtig sind. Diese Daten enthalten einige Kennzeichen des Arbeitnehmers, wie z.B. seinen Namen und sein Gehalt. Sehr wahrscheinlich werden jedoch in diesem Zusammenhang unwichtige Angaben, wie Haarfarbe, Gewicht und Grösse nicht vermerkt sein.

Der Test stellt einen wichtigen Schritt im Entwurfs-und Herstellungsablauf digitaler Schal­ tungen dar, indem er unter Anwendung bestimmter Eingangssignale die Funktion einer ent­ worfenen Schaltung an einem hergestellten Exemplar zu verifizieren erlaubt. Diese Aufga­ bensteIlung gilt gleichermaßen für diskret aufgebaute Logik wie für integrierte Schaltungen. Doch kommt wegen der begrenzten Zahl der externen Anschlüsse bei größeren integrierten Schaltungen fast zwangsläufig die Aufgabe hinzu, Testbarkeitsaspekte beim Entwurf zu berücksichtigen, da andernfalls ein hinreichender Test häufig nicht oder nur mit größeren Schwierigkeiten durchzuführen ist. Das liegt an der "Zugänglichkeit" integrierter Schal­ tungen, die durch die Anzahl externer Anschlüsse beschränkt ist. Aus diesen und anderen Gründen ist der Test digitaler Schaltungen sinnvollerweise zusammen mit Überlegungen zur Testbarkeit einer Schaltung zu sehen. Traditionell ist der Test digitaler Schaltungen um die logische Entwurfsebene herum ange­ ordnet, d.h. daß die logische Ebene den Ausgangspunkt für die Testvorbereitung und die Testdurchführung darstellt. Es gibt darüber hinaus heute auch Ansätze, die von hierar­ chisch höheren Ebenen ausgehen, doch hat sich bisher in diesem Bereich keine allgemein anerkannte Methodik etabliert, wie das für die logische Ebene der Fall ist. Es ist jedoch auch für den Testbereich wichtig, der wachsenden Komplexität der Schaltungen dadurch Rechnung zu tragen, daß man hierarchische Methoden für deren Prüfung einsetzt. Die Notwendigkeit, eine Schaltung zu prüfen, ergibt sich im Rahmen ihrer Entstehung mehrfach, wenn auch mit unterschiedlicher Zielsetzung.

Dieses Buch ist aus einer Vorlesung flir Studenten der Informatik hervorgegangen, die in ein regelmäßig angebotenes Praktikum in Systemprogrammierung einfuhren soll. Ziel dieser Vorlesung ist die Vermittlung grundlegender Methoden der systemnahen Programmierung, während im Praktikum vor allem der Einsatz einer höheren Program­ miersprache für Probleme der systemnahen Programmierung geübt werden soll. Kenntnisse in einer höheren Programmiersprache, vorzugsweise Pascal, Modula-2 oder C, werden deshalb vorausgesetzt. Das Buch richtet sich aber nicht nur an Informatikstudenten, sondern in erster Linie auch an die Benutzer von Personal Computern, vor allem an solche, die sich intensiver mit der Programmierung ihres Rechners befassen wollen, als dies für die Erstellung reiner Anwendersoftware nötig wäre. Sie können nämlich, im Vergleich zu den Benutzern eines großen Systems, die vorhandenen Resourcen ihres Rechners gezielter, auf die jeweilige Anwendung abgestimmt, nutzen. Dazu sind jedoch einige Kenntnisse in systemnaher Programmierung erforderlich. Bis auf wenige Ausnahmen habe ich mich bemüht, dem Leser nur vollständige Pro­ grammbeispiele anzubieten. Deshalb wird er sich zuweilen auch mit weniger wichtigen Details befassen müssen. Er kann dafür aber sicher sein, daß die Beispiele lauffähig sind und getestet wurden. Das Buch gl~edert sich in zwei Teile. Teil I soll die Grundprinzipien der modularen, systemnahen Programmierung vermitteln und diese an Hand der Behandlung von Ausnahmen demonstrieren. Teil II befaßt sich mit der concurrenten Programmierung. Dabei steht die Entwicklung und die Modellierung ganzer Prozeß-Systeme im Vordergrund.