Highlights aus der Informatik

Nach einer Erläuterung der Ziele der Aufsatzsammlung sollen Kurzbeschreibungen der Aufsätze Appetit auf das in sechzehn Gängen präsentierte Menü „Highlights aus der Informatik“ machen.

Es fahren zu viele Autos auf den Straßen. Oft werden sie nur als Transportmittel zur Arbeitsstätte eingesetzt, wo sie unproduktiv den ganzen Tag herumstehen und anderweitig nutzbare Flächen belegen. Fahrgemeinschaften (abgekürzt FGMs), die aus drei oder vier Personen bestehen, könnten eine deutliche Entlastung bewirken.

Was können wir vom Computer als Spieler lernen?

Diese bewußt zweideutige Frage soll exostisches Randgebeit der Informatik einführen: die Kunst, Computer zum Spielen zu bringen. Bevor man untersucht, wie diese Leistung zu erbringen ist, taucht aber die Frage „war-um denn?“ auf. Eine Antwort darauf ist zugegebenermaßen dieselbe, die das Erklimmen der Eiger Nordwand erklärt: „Um zu zeigen, daß man es kann.“

Wir suchen in diesem Artikel nach einer befriedigenderen Antwort. Wir versuchen anhand einiger Episoden aus der Entwicklung des Computer-schachs zu interpretieren, was erreicht worden ist. Wir vergleichen dies mit der Leistung menschlicher Experten, versuchen einige Unterschiede zu verstehen und kommen zum Schluß nochmals auf die verzwickte Frage zurück: Was hat die Wissenschaft gelernt aus einem Experiment, das seit der Frühzeit der Computer vor fast einem halben Jahrhundert etwas chaotisch, aber mit großer Hingabe von Hunderten von faszinierten Bastlern und Wissenschaftlern geführt worden ist?

Die menschliche Intelligenz spiegelt sich auch in der Fähigkeit wider, Entscheidungen unter Berücksichtigung zukünftiger Entwicklungen zu treffen. Daher werden in der Informatik seit vielen Jahren Algorithmen untersucht, die eine solche Vorausschau in die Zukunft ermöglichen und dann aufgrund von Abschätzungen der Ergebnisse der einzelnen Handlungsalternativen eine Alternative auswählen. Strategische Spiele erfordern eine derartige Leistung, wenn der Ausgang einer Folge von eigenen Handlungen unter Berücksichtigung der Interventionen eines Gegners abgeschätzt werden muß. Auch wegen ihrer klaren Definitionen bieten sich daher immer wieder Spiele, wie z.B. Schach, als Testumgebung für solche Algorithmen an. Den Blick in die Zukunft ermöglicht dabei die Spielbaumsuche.

Springerkreise sind Zugfolgen des Springers auf dem Schachbrett, mit denen er jedes Feld genau einmal erreicht und zum Ausgangsfeld zurückkehrt. Sie faszinieren seit über 400 Jahren auch solche Menschen, die sich nicht hauptsächlich mit Schach, Mathematik oder Informatik befassen. Nach einem historischen Rückblick wird beschrieben, wie es nun gelungen ist, die exakte Zahl der Springerkreise zu bestimmen. Wichtiger als die Zahl ist die Methode ihrer Berechnung. Es werden für die Hardwareverifikation entworfene Datenstrukturen eingesetzt. Damit wird gezeigt, daß diese Datenstrukturen die Lösung endlicher Probleme aus sehr unterschiedlichen Gebieten unterstützen.

Der rapide anwachsende Umfang an Daten und Erkenntnissen in der Molekularbiologie, der durch die vor knapp zehn Jahren begonnenen Genomsequenzierungsprojekte sowie die Fortschritte bei der experimentellen molekularen Strukturaufklärung erzeugt wird, stellt eine beträchtliche Herausforderung auch an die Informatik dar. Schon bei der Genomsequenzierung selbst fallen wichtige Informatikprobleme an. Die größte Herausforderung besteht jedoch in der Unterstützung der Interpretation genomischer Information. Hier gilt es, außerordentlich umfangreiche und in hohem Maße unstrukturierte Daten zu analysieren und aus ihnen biologische Erkenntnisse abzuleiten. Die Daten liegen zunächst in der Form von Sequenzen, d. h. Strings vor. Nach den ersten Interpretationsschritten sind jedoch auch dreidimensionale Strukturdaten von Biomolekülen zu analysieren. Schließlich spielen die Wechselwirkungen zwischen Biomolekülen eine zentrale Rolle, die zu Reaktionsketten und -netzwerken zusammengefaßt den Metabolismus lebender Organismen ausmachen. Informatiker werden zur Bewältigung dieser Herausforderung nur dann wesentlich beitragen können, wenn sie selbst sich dabei engagieren, ihre Methoden in die molekularbiologische Anwendung einzubringen, und damit eigene Kompetenz in diesem hochaktuellen Anwendungsgebiet erwerben. Das bedeutet auch, neue Probleme, Methoden und Validierungsverfahren zu entwickeln, die auf diese Anwendung zugeschnitten sind.

LEDA ist eine Bibliothek von Sofwarekomponenten für kombinatorische und geometrische Probleme. Die wichtigsten Eigenschaften der Bibliothek sind die umfangreiche Sammlung von effizienten Datentypen und Algorithmen, deren präzise und dennoch lesbare Spezifikation, und ihre leichte und elegante Benutzbarkeit. Auf diese Weise stellt LEDA eine Plattform für kombinatorisches und geometrisches Rechnen dar, die den Schritt vom Algorithmus zum ausführbaren Programm erheblich erleichtert. Damit macht LEDA die theoretischen Resultate über effiziente Datenstrukturen und Algorithmen auch für Sofwareentwickler nutzbar, die keine Experten auf diesem Gebiet sind.

Der Aufbau von Rechnern wird in der Regel durch Blockdiagramme erläutert und für einzelne Blöcke dieser Diagramme wie z.B. Prozessoren geschieht das auf gleiche Weise. So tut man dies in schrittweiser Verfeinerung, bis man an die Grenze des Interesses des Lesers stößt. Diese Grenze mag bei den Gattern liegen, sie kann aber auch darüber oder darunter liegen. Beim Chipentwurf interessiert man sich eventuell auch für den Aufbau der Gatter aus Transistoren oder gar für physikalische Eigenschaften der Transistoren.

Verteilte Rechnersysteme erweisen sich als eine attraktive Architektur mit einer Reihe von Vorteilen. Vor allem ist hier zu nennen die lokale Verfügbarkeit und die Möglichkeit des dezentralen Managements, so daß bei Ausfall einzelner Komponenten nicht zwangsläufig das gesamte System zum Stillstand kommen muß. Andererseits erzeugt gerade diese räumliche Trennung eine neuartige Synchronisationsproblematik. Wir diskutieren exemplarisch zwei Prototypprobleme: Konsistenz bei divergenter lokaler Information — auch Consensus oder das Problem der Byzantinischen Generäle genannt — und die zeitliche Synchronisation der lokalen Uhren in den einzelnen Knoten und gemeinsamer Aktionen. Grundlegend hierfür ist eine präzise Analyse, wie aus lokalem Wissen der einzelnen Komponenten globales Wissen über den Gesamtzustand des Systems gewonnen werden kann, und zwar durch den Austausch von Nachrichten und das Eintreffen oder Nichteintreffen von Ereignissen.

Effiziente Kommunikationsmethoden in Netzwerken sind Grundvoraussetzung, um die Leistungsfähigkeit großer paralleler Rechnersysteme auszuschöpfen. Aus diesem Grund wurden und werden erhebliche Forschungsund Entwicklungsanstrengungen unternommen, derartige Kommunikationsmechanismen, sogenannte Router, zu analysieren und herzustellen. In diesem Aufsatz beschreiben wir die Grundideen der Beiträge der theoretischen, algorithmisch orientierten Forschung zur Entwicklung solcher Kommunikationsmethoden.

Die Sprache APL basiert auf einem äußerst eleganten Kalkül für Vektoren, Matrizen und Tensoren. APL-Operationen kommen inzwischen in vielen modernen Programmiersprachen vor. Ihre Parallelisierung ist daher nicht nur für Benutzer von APL von Interesse. Wir zeigen, daß sich alle APL-Operationen effizient parallelisieren lassen. Die wesentlichen Werkzeuge beim Beweis sind

Es sollen hier Resultate aus drei verschiedenen Gebieten bewiesen werden. Ein Verfahren zum Lernen Boolescher Funktionen, wobei man möglichst wenige Fehler macht [7]. Eine Konstruktion für eine Schranke aus der kombinatorischen Geometrie [4] mit algorithmischen Anwendungen (siehe auch [13]). Und ein Algorithmus zur Optimierung X. Aus der Vielfalt der Ergebnisse ergibt sich bereits, daß weniger das Ziel als vielmehr der Weg dorthin unser zentrales Anliegen ist: Eine Beweismethode, die man als „iteratives Umgewichten“ oder „Suchen bzw. Konstruktion durch Verdoppeln“ bezeichnen kann. Dabei beginnen wir mit einer Menge Mo und ziehen daraus eine Teilmenge T₀. Durch Verdoppeln der Elemente aus T₀ erhalten wir eine Menge M₁ (tatsächlich haben hier die Elemente nun Vielfachheiten). Dann ziehen wir eine Teilmenge T₁ aus M₁, verdoppeln alle Elemente in M₁, die in T₁ vorkommen, und erhalten dadurch M₂, usw. Wie wir die Teilmengen bekommen, ergibt sich erst in den konkreten Beispielen. Mit dem Verdoppeln verfolgen wir unterschiedliche Ziele. In einem Fall verringert hohe Vielfachheit die Chance, in einer der Mengen T_i aufzutauchen. Das heißt, kein Element wird viel öfter als andere in den Iterationen gezogen werden. In einer anderen Anwendung hat M gute und schlechte Elemente—welche gut und welche schlecht sind, ist uns nicht bekannt. Es gelingt uns aber immer, Teilmengen Ti zu ziehen, die mindestens ein gutes Element haben, wir wissen aber nicht, welches. Verdoppeln erhöht die Chance, in späteren T_i’s aufzutreten. Da aber immer mindestens ein gutes Element verdoppelt wird, gewinnen diese schnell die Überhand und können dadurch identifiziert werden. Diese Skizze der Idee wird vielleicht erst im Rückblick verständlich, deutet aber schon den evolutionären Charakter der Verfahren an (Brönnimann und Goodrich nennen dies „algorithmischen Darwinismus“ [1]). In jedem Fall geht es uns aber nur um Methoden, in denen die Intuition auch durch Beweise untermauert werden kann.

Software-Engineering umfaßt technische wie organisatorische Aspekte. Aus technischer Sicht arbeiten wir beim Software-Engineering mit einer Entwicklungsmethode und Beschreibungsformalismen, mit Modellierungs- und Implementierungstechniken. Die Entwicklung eines Softwaresystems ist als Entwicklungsprozeß organisiert und wird durch CASE- Werkzeuge unterstützt. Wir zeigen im folgenden, wie geeignete Mathematik das Software-Engineering auf eine wissenschaftliche Grundlage stellen kann. Dadurch werden ein gründlicheres Verständnis für die Disziplin und auch eine mächtigere zielgerichtetere Werkzeugunterstützung für den Entwicklungsprozeß möglich. Um zu einer angemessenen mathematischen Fundierung zu gelangen, muß der wirtschaftliche und technische Nutzen mathematischer Konzepte im Bereich Software-Engineering klar identifiziert werden. Dazu ist es erforderlich, die Rolle von Mathematik und Logik im Software-Engineering sorgfältig zu analysieren. Wir beschreiben, wie Methoden des Software-Engineering durch die Mathematik fundiert werden können. Wir erläutern den Nutzen einer solchen mathematischen Grundlage. Dieser Nutzen geht weit über die sogenannten formalen Methoden für die Spezifikation und Verifikation von Software hinaus.

Dieser Vortrag handelt von algorithmischen Problemen der elementaren Zahlentheorie und einer Revolution der Kryptographie in den siebziger Jahren. Es werden kaum Mathematik- und überhaupt keine Informatik-Kenntnisse vorausgesetzt.

Wir betrachten neuronale Netzwerke mit diskreten oder analogen Gatterfunktionen. Selbst die Berechnungskraft relativ kleiner neuronaler Netzwerke beschränkter Tiefe ist, besonders in Hinsicht auf arithmetische Operationen, immens. Aber gerade diese Stärke ist auch ein Grund für die Schwierigkeit des Lernens von und mit „einfachen“ neuronalen Netzwerken.

Der Vorgang des Beweisens kann in einer interaktiven Weise zwischen zwei Parteien, dem Beweiser und dem Verifizierer, stattfinden. Durch das Verwenden von Zufallszahlen wird es möglich gemacht, daß derartige interaktive Beweise kürzer sein können als konventionelle. Ferner ist es möglich, daß der Verifizierer vollständig von der Tatsache überzeugt wird, daß der Be-weiser den Beweis (das kann zum Beispiel ein Passwort sein) kennt, ohne daß aus der Kommunikation zwischen Beweiser und Verifizierer auf den Beweis rückgeschlossen werden kann. Solche interaktiven Zero-Knowledge Beweise spielen eine wichtige Rolle in verschiedenen kryptographischen Anwendungen.

Ein Traum eines jeden Studenten, Doktoranden und Professors: Die Richtigkeit eines komplizierten Beweises zu verifizieren, ohne ihn mühselig Zeile für Zeile zu lesen und zu verstehen.